Cách tính số tập hợp con

     

Khi học tập tới phần tập hợp, chúng ta được ra mắt với một tập hợp tất cả n thành phần thì nó bao gồm 2^n tập con. Nhưng tại sao là 2^n?


*

Trước khi xử lý bài toán, họ cần ôn lại một số trong những kiến thức cơ bạn dạng về tập hợp

Tập hòa hợp là gì?

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. Nhưng mà hiểu một cách đơn giản, tập hợp là sự việc quần tụ của hữu hạn hoặc vô hạn các đối tượng có và một thuộc tính nào đó. Các đối tượng này được hotline là phần tử của tập hợp. Với trong bài viết này, mình chỉ xét với rất nhiều tập hợp hữu hạn phần tử như


*

Ví dụ về tập hợp có hữu hạn phần tử

Lí bởi vì sao lại không đề cập tới số đông tập hợp bao gồm vô hạn bộ phận vì với đều tập hợp bởi vậy thì số phần tử của nó không thể được chỉ ra vì chưng một con số nhất định mặc dù cho đó là vô hạn đếm được hay vô hạn ko đếm được.

Bạn đang xem: Cách tính số tập hợp con

Tập nhỏ là gì?

Tập con hay tập thích hợp con phiên bản thân của chính nó cũng là một tập hợp. Tập thích hợp A được call là tập nhỏ của B nếu như trong B gồm A (B chứa A). Quan tiền hệ bởi vậy được gọi là quan hệ giới tính bao hàm. Và tất nhiên với hầu hết tập A thì ta luôn luôn có A chính là tập nhỏ của A vì trong A bao gồm A.


*

Ví dụ về tập A là tập con của tập B

Nhìn thông thường thì kí hiệu với được mọi tín đồ ngầm gọi là như nhau. Tuy nhiên với A ⊆ B ta có thể hiểu tập A là bé của tập B hoặc rất có thể hai tập cân nhau A = B

Tập trống rỗng là gì?

Tập này là 1 tập đặc biệt, cùng duy chỉ có mình nó là có công dụng không chứa phần tử nào. Và theo triết lý tập thích hợp tiên đề thì hầu như tập thích hợp hữu hạn mọi được xây dừng từ tập rỗng, vậy cần tập rỗng là tập nhỏ của mọi tập hợp. Từ đây ta có thể rút ra một nhấn xét là tập rỗng gồm duy tốt nhất một tập con là chủ yếu nó.


*

2 kí hiệu được áp dụng để trình diễn tập vừa lòng rỗngKiểm tra mệnh đề

Những quan niệm cơ phiên bản đã xong, giờ ta sẽ bắt tay vào câu hỏi đếm số tập bé của một tập hòa hợp bằng việc xét một toy example.Đếm số tập nhỏ của tập A=1, 2, 3.Tập vừa lòng này tất nhiên là một tập hữu hạn với n = 3 phần tử. Vày n nhỏ, bắt buộc ta hoàn toàn có thể đếm số tập con bằng cách liệt kê.Đầu tiên phải nói tới đó chính là tập trống rỗng (1 tập), tiếp sau là phần đa tập hòa hợp gồm một phần tử 1, 2, 3 (3 tập), tập tất cả 2 thành phần 1, 2, 1, 3, 2, 3 (3 tập). Ở phía trên ta cần chú ý một điểm là nhị tập 1, 22, 1 đồng nhất và chúng ta sẽ chỉ đếm 1 lần. Tập con sau cùng 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ởi .

Xem thêm: Hãy Chọn Câu Sai Hình Chữ Nhật Có Một Góc Vuông Là Hình Ch, Hãy Chọn Câu Sai

Các chúng ta hoàn toàn hoàn toàn có thể thử với những tập hợp có n = 4, 5, 6,… để kiểm soát lại xem số tập con có bởi 2^n hay không. Tuy vậy việc kiểm tra sẽ trở ngại khi n lớn. Vậy tất cả cách nào bạn có thể chắc chắn rằng điều trên đúng với đa số n?

Chứng minh bằng quy hấp thụ (induction)

Ở toán trung học thêm (hoặc trung học cơ sở) chúng ta đã làm quen với một phương pháp để kiểm tra điều này, đó là quy nạp. Ta sẽ nhắc lại công việc để chứng minh quy nạp. Đầu tiên là bước cơ sở (base case), ta bắt buộc phải minh chứng mệnh đề đúng cùng với n = 0 (đối lúc rất có thể là n = 1). Bước tiếp theo là bước quy hấp thụ (inductive step), ta chứng minh rằng cùng với n = k đúng thì n = k + 1 cũng đúng. Áp dụng vào câu hỏi của bọn chúng ta.

Gọi n là số phần tử của tập phù hợp AVới n = 0, tập A là tập rỗng, với số tập bé của A1 = 2⁰Giả 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 gồm 2^(k+1) tập conThật vậy, với k + 1 bộ phận của A, ta lựa chọn ra bất kỳ k phần tử. Tự k thành phần này ta rất có thể lập ra được 2^k tập con. Tiếp theo ta lấy thành phần còn lại, sau khi lấy k thành phần ra trước đó, đưa vào 2^k tập con vừa lập thì ta sẽ được 2^k tập nhỏ mới. Vậy tổng số tập bé của A2^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ố thoải mái và tự nhiên n.

Chứng minh bởi tổng hệ số nhị thức (binomial coefficient)

Ngoài cách đó ra, mình cũng tự nghĩ về ra một cách chứng tỏ sử dụng loài kiến thức tỷ lệ thông kế.Với tập An phần tử, ta tạo thành các tập bé của A bằng cách lấy k ( k = 0, 1, …, n) thành phần ra. Vậy ta sẽ tính số tập nhỏ được chế tác ra bằng phương pháp đếm tổng số biện pháp lấy.Với k = 0, ta có nC0 bí quyết lấy. (trường phù hợp này tạo ra tập rỗng)Với k = 1, ta gồm nC1 cách lấy.Với k = 2, ta có nC2 phương pháp lấy.…Với k = n, ta gồm nCn bí quyết lấy. (trường phù hợp này tạo nên chính tập đó)Vậy tổng số cách là nC0 + nC1 + nC2 + … + nCn. Đây là 1 trong tổng vô cùng thân thuộc mà các bạn đã biết khi tham gia học về nhị thức Newton hay định lí nhị thức (Binomial theorem), với tổng này đúng bằng 2^n.

Xem thêm: Gương Cầu Lồi Không Được Dùng Ở Đâu ? Gương Cầu Lồi Thường Được Dùng Ở Đâu

Chứng minh bằng quy tắc nhân (multiplication rule)

Cuối cùng, bản thân sẽ trình làng với chúng ta một bí quyết nữa. Đây cũng là bí quyết mà mình học được từ thầy Joseph Blitzstein với là giải pháp mình thấy hay nhất.Cách này sử dụng quy tắc nhân trong xác suất thông kê. Với mỗi phần tử trong tập hợp, ta rất có thể cho giữ này lại hoặc quăng nó ra để tạo thành được một tập con. Vậy theo quy tắc nhân ta được 2.2.2.2.2…2 = 2^n. Đơn giản, ngắn gọn. Nếu như bạn chưa hiểu lắm ta hoàn toàn có thể xét một toy example dễ dàng như sauVới tập A = 1, 2.TH1: bỏ 1, quăng quật 2, ta được TH2: giữ lại 1, vứt 2, ta được 1TH3: bỏ 1, duy trì 2, ta được 2TH4: duy trì 1, giữ 2, ta được 1, 2Ta có thể dễ dàng đếm ra 4 ngôi trường hợp bằng quy tắc nhân 2.2=2²=4