Khi học tập tới phần tập hợp, các bạn được reviews với một tập hợp bao gồm n bộ phận thì nó tất cả 2^n tập con. Nhưng nguyên nhân là 2^n?
Trước khi xử lý bài toán, bọn họ cần ôn lại một trong những kiến thức cơ phiên bản về tập hợp
Tập hợp là một trong những khái niệm nguyên thủy của toán học, ko định nghĩa. Cơ mà hiểu một cách đối chọi giản, tập hợp là sự quần tụ của hữu hạn hoặc vô hạn các đối tượng người sử dụng có và một thuộc tính như thế nào đó. Các đối tượng người dùng này được call là phần tử của tập hợp. Với trong bài viết này, tôi chỉ xét với hồ hết tập thích hợp hữu hạn phần tử như
2 kí hiệu được sử dụng để màn biểu diễn tập thích hợp rỗng
Những có mang cơ bản đã xong, giờ ta sẽ hợp tác vào việc đếm số tập con của một tập vừa lòng bằng việc xét một toy example.Đếm số tập nhỏ của tập A=1, 2, 3.
Bạn đang xem: Cách tính số tập hợp con có 3 phần tử
Tập phù hợp này dĩ nhiên là một tập hữu hạn với n = 3 phần tử. Vì n nhỏ, cần ta có thể đếm số tập con bằng phương pháp liệt kê.Đầu tiên phải nhắc tới đó chính là tập rỗng (1 tập), tiếp theo là đều tập vừa lòng gồm 1 phần tử 1, 2, 3 (3 tập), tập tất cả 2 phần tử 1, 2, 1, 3, 2, 3 (3 tập). Ở đây ta cần xem xét một điểm là nhì tập 1, 2 và 2, 1 đồng nhất và họ sẽ chỉ đếm 1 lần. Tập con ở đầu cuối là chủ yếu nó 1, 2, 3 (1 tập). Vậy ta có tổng số 1 + 3 + 3 + 1 = 8 tập con, đúng bằng 2³.
Các bạn hoàn toàn có thể thử với phần nhiều tập hợp tất cả n = 4, 5, 6, để chất vấn lại coi số tập nhỏ có bởi 2^n tuyệt không. Mặc dù việc soát sổ sẽ khó khăn khi n lớn. Vậy gồm cách nào bạn có thể chắc chắn rằng điều bên trên đúng với mọi n?
Ở toán trung học thêm (hoặc trung học tập cơ sở) họ đã có tác dụng quen với một phương pháp để kiểm tra điều này, đó là quy nạp. Ta đã nhắc lại công việc để minh chứng quy nạp. Đầu tiên là bước cơ sở (base case), ta cần phải chứng tỏ mệnh đề đúng với n = 0 (đối lúc có thể là n = 1). Bước tiếp theo là cách quy nạp (inductive step), ta chứng tỏ rằng với n = k đúng thì n = k + 1 cũng đúng. Áp dụng vào bài toán của chúng ta.
Gọi n là số thành phần của tập hợp AVới n = 0, tập A là tập rỗng, và số tập con của A là 1 = 2Giả sử đúng cùng với n = k, thì tập A gồm 2^k tập conTa cần chứng tỏ với n = k + 1 thì tập A bao gồm 2^(k+1) tập conThật vậy, cùng với k + 1 bộ phận của A, ta lựa chọn ra bất kì k phần tử. Trường đoản cú k phần tử này ta rất có thể lập ra được 2^k tập con. Tiếp sau ta lấy phần tử còn lại, sau khoản thời gian lấy k bộ phận ra trước đó, chuyển vào 2^k tập nhỏ vừa lập thì ta sẽ tiến hành 2^k tập nhỏ mới. Vậy toàn bô tập con của A là 2^k + 2^k = 2.2^k = 2^(k+1). Vậy với n = k + 1 cũng đúng, suy ra mệnh đề đúng với tất cả số tự nhiên n.
Ngoài cách đây ra, tôi cũng tự nghĩ ra một cách minh chứng sử dụng kiến thức phần trăm thông kế.Với tập A gồm n phần tử, ta tạo thành các tập con của A bằng cách lấy k ( k = 0, 1, , n) phần tử ra. Vậy ta công thêm số tập nhỏ được tạo ra ra bằng phương pháp đếm tổng số bí quyết lấy.Với k = 0, ta tất cả nC0 phương pháp lấy. (trường đúng theo này tạo ra tập rỗng)Với k = 1, ta có nC1 biện pháp lấy.Với k = 2, ta có nC2 phương pháp lấy.Với k = n, ta gồm nCn biện pháp lấy. (trường phù hợp này tạo thành chính tập đó)Vậy tổng số phương pháp là nC0 + nC1 + nC2 + + nCn. Đây là một trong tổng vô cùng thân thuộc mà chúng ta đã biết khi học về nhị thức Newton tốt định lí nhị thức (Binomial theorem), với tổng này đúng bởi 2^n.
Xem thêm: Những Bài Hát Hay Nhất Của Jack, Hồi Chuông Cho Nghệ Sĩ Trẻ
Cuối cùng, bản thân sẽ reviews với các bạn một phương pháp nữa. Đây cũng là biện pháp mà mình học tập được tự thầy Joseph Blitzstein và là phương pháp mình thấy tốt nhất.Cách này thực hiện quy tắc nhân trong phần trăm thông kê. Cùng với mỗi phần tử trong tập hợp, ta rất có thể cho giữ nó lại hoặc quăng nó ra để tạo thành được một tập con. Vậy theo nguyên tắc nhân ta được 2.2.2.2.22 = 2^n. Đơn giản, ngắn gọn. Nếu như bạn chưa phát âm lắm ta hoàn toàn có thể xét một toy example dễ dàng và đơn giản như sauVới tập A = 1, 2.TH1: vứt 1, bỏ 2, ta được TH2: giữ 1, quăng quật 2, ta được 1TH3: vứt 1, giữ lại 2, ta được 2TH4: duy trì 1, giữ lại 2, ta được 1, 2Ta có thể dễ dàng đếm ra 4 ngôi trường hợp bởi quy tắc nhân 2.2=2²=4