Tổ hợp


Định nghĩa. Cho một tập An phần tử(n\in\mathbb{N}) và 0\leq k\leq n là một số nguyên. Một k-tổ hợp(một tổ hợp chập k) của A là một tập con k phần tử của A.

Ví dụ 4.1. Các 3-tổ hợp của A=\{a,b,c,d\}\{a,b,c\},\{b,c,d\},\{c,d,a\},\{d,a,b\}\Box.

Số tổ hợp. Cho một tập An phần tử(n\in\mathbb{N}) và 0\leq k\leq n là một số nguyên. Khi đó số k-tổ hợp của A bằng C_n^k=\dfrac{A_n^k}{k!}=\dfrac{n!}{k!(n-k)!}.

Chứng minh. Sự khác nhau giữa một k-tổ hợp và một k-hoán vị chính là một đằng không quan tâm đến thứ tự, trong khi đằng kia có quan tâm đến thứ tự. Tận dụng điều này ta có chứng minh như sau.

Một k-hoán vị của A có thể hình thành sau hai bước: Đầu tiên, chọn một k-tổ hợp của A; sau đó xếp k phần tử của tập này thành một hàng. Bởi vì có C_n^k cách để làm bước một, k! cách để làm bước hai nên theo nguyên lý nhân ta có A_n^k=C_n^k\times k!\Box.

Ví dụ 4.2. Chứng minh rằng nếu n là một số nguyên dương và 0\leq k\leq n là một số nguyên thì C_n^k=C_n^{n-k}.

Lời giải. Có thể chứng minh bằng công thức trên hay chú ý rằng có một tương ứng 1-1 giữa tập các tập con có k phần tử và tập các tập con có n-k phần tử\Box.

Ví dụ 4.3. Chứng minh rằng nếu k<n là các số nguyên dương thì C_n^k=C_{n-1}^{k-1}+C_{n-1}^k.

Chứng minh. Có thể chứng minh bằng các biến đổi đại số hoặc đếm số tập con có k phần tử của một tập có n phần tử bằng hai cách khác nhau\Box.

Ví dụ 4.4. Có bao nhiêu xâu nhị phân độ dài 7 mà có đúng ba số 0?

Đáp số. C_7^3\Box.

Ví dụ 4.5. Có bao nhiêu cách có thể thành lập một hội đồng gồm 5 thành viên từ một nhóm có 11 người chứa 4 giáo viên và 7 học sinh nếu

a)Không có thêm điều kiện gì?

b)Hội đồng chứa đúng 2 giáo viên?

c)Hội đồng chứa ít nhất 3 giáo viên?

d)Giáo viên A và học sinh B không thể cùng nằm trong hội đồng?

Lời giải. a)C_{11}^5.

b)C_4^2\times C_7^3.

c)3 hoặc 4 giáo viên có thể nằm trong hội đồng, đáp số 91.

d)Dùng nguyên lý trừ, đáp số 378\Box.

Ví dụ 4.6(Định lý nhị thức). Chứng minh rằng nếu n là một số nguyên dương thì (x+y)^n=\sum_{k=0}^nC_n^kx^ky^{n-k}\,\,\forall x,y\in\mathbb{C}.

Lời giải. Viết (x+y)^n=(x+y)\times (x+y)\times\cdots\times (x+y)(n thừa số). Sau khi khai triển ta sẽ được các số hạng dạng x^ky^{n-k} với k=0,1,\cdots, n. Với mỗi k=\overline{0,n}, cố định nó. Ta sẽ xem sau khi khai triển có bao nhiêu số hạng bằng x^ky^{n-k}. Để hình thành số hạng này đầu tiên ta phải chọn k số x trong n số x của n ngoặc trên, sau đó chọn n-k số y trong các ngoặc còn lại và đem nhân n số đã chọn với nhau. Theo nguyên lý nhân, hệ số của x^ky^{n-k} bằng C_n^k\Box.

Ví dụ 4.7. Cho n là một số nguyên dương và A là một tập có 2n phần tử. Có bao nhiêu cách phân hoạch A thành các tập có 2 phần tử?

Lời giải 1. Đầu tiên, cố định một phần tử x của A và chọn một phần tử trong 2n-1 phần tử còn lại của A để ghép lại với x tạo thành một khối của phân hoạch; sau đó cố định một phần tử y trong các phần tử còn lại của A và chọn một phần tử trong 2n-3 phần tử còn lại của A để ghép lại với y tạo thành một khối của phân hoạch; ta cứ làm như vậy cho đến khi còn 2 phần tử thì đây chính là khối còn lại của phân hoạch. Theo nguyên lý nhân, số phân hoạch thoả mãn là (2n-1)\times (2n-3)\times\cdots\times 1.

Lời giải 2. Chọn một tập con có 2 phần tử của A làm khối thứ nhất, sau đó chọn một tập con có 2 phần tử của tập hợp gồm 2n-2 phần tử còn lại làm khối thứ hai, ta cứ làm như vậy cho đến khi còn hai phần tử thì đây chính là khối thứ n. Vì thứ tự các khối là không quan trọng nên số các phân hoạch thoả mãn là \dfrac{C_{2n}^2\times C_{2n-2}^2\times\cdots\times C_2^2}{n!}.

Lời giải 3. Ta xếp 2n phần tử của A thành một hàng vào 2n vị trí như hình dưới đây

\{(1),(2)\},\{(3),(4)\},\cdots,\{(2n-1),(2n)\}

(2n)! cách để làm điều này. Vì trong mỗi tập con có 2 phần tử thứ tự các phần tử là không quan trọng và thứ tự các khối của phân hoạch là không quan trọng nên số phân hoạch thoả mãn là

\dfrac{(2n)!}{2!\times 2!\times\cdots\times 2!\times n!}=\dfrac{(2n)!}{n!\times 2^n}\Box.

Sau đây là một số bài tập tự luyện.

Bài 4.1. Cho n,k là các số nguyên dương và S là tập gồm n điểm trong mặt phẳng sao cho

a)Không có 3 điểm nào của S thẳng hàng, và

b)Với mỗi điểm P của S có ít nhất k điểm của S cách đều P.

Chứng minh rằng k<\dfrac{1}{2}+\sqrt{2n}.

Lời giải. Nối mỗi cặp điểm của S bằng một đoạn thẳng, ta sẽ có C_n^2 đoạn thẳng như vậy.

Mặt khác, với mỗi P, có ít nhất k điểm nằm trên một đường tròn tâm P, số các đoạn nối k điểm này bằng C_k^2. Vì có n đường tròn như vậy nên sẽ có nC_k^2 đoạn thẳng như vậy. Nhưng có thể có một vài đoạn được đếm nhiều hơn một lần, một đoạn như vậy sẽ là dây chung của 2 trong n đường tròn nói trên, suy ra nhiều nhất tính cả bội sẽ có C_n^2 dây chung. Bởi vậy C_n^2\geq nC_k^2-C_n^2. Giải bất phương trình này ta có điều phải chứng minh \Box.

Bài 4.2. Nếu phải có ít nhất một người ở mỗi bàn, hỏi có bao nhiêu cách có thể xếp 6 người

a)ngồi quanh hai cái bàn giống nhau?

b)ngồi quanh ba cái bàn giống nhau?

Đáp số. Phân nhóm sau đó xếp vị trí.

a)274.

b)225\Box.

Bài 4.3. Cho số nguyên dương n>2 và một n-giác đều. Có bao nhiêu tam giác tù có ba đỉnh là các đỉnh của đa giác đã cho?

Lời giải. Mỗi đỉnh P của đa giác đều ta đếm số tam giác tù mà góc tại đỉnh P nhọn. Khi n chẵn đáp số là \dfrac{n(n-2)(n-4)}{8}, khi n lẻ đáp số là \dfrac{n(n-1)(n-3)}{8}\Box.

Bài 4.4. Cho m,n,k là các số nguyên dương sao cho k\leq\min\{m,n\}. Hỏi có bao nhiêu cách xếp k quân xe lên một bàn cờ m\times n sao không chúng đôi một không ăn nhau?

Lời giải. Các con xe này phải nằm trên k cột khác nhau và k dòng khác nhau, như vậy số cách xếp bằng C_m^k\times C_n^k\times k!\Box.

Bài 4.5. Cho m,n là các số nguyên dương thoả mãn n\leq m+1. Hỏi có bao nhiêu xâu nhị phân độ dài m+n sao cho không có hai số 1 đứng cạnh nhau và có đúng m số 0?

Đáp số. Các số 0 để lại m+1 vị trí trống, đáp số của bài toán là C_{m+1}^n\Box.

Bài 4.6. Cho n>1 là một số nguyên dương, S=\{1,2,\cdots,n+1\}T=\{(x,y,z)\in S^3|x<z,y<z\}. Bằng cách tính |T| bằng hai cách khác nhau, hãy chứng minh \sum_{k=1}^nk^2=C_{n+1}^2+2C_{n+1}^3.

Hướng dẫn. Chia làm hai kiểu: Hai thành phần đầu bằng hoặc khác nhau \Box.

Bài 4.7. Cho một nhóm có 15 học sinh, 5 trong họ là nữ. Nếu có đúng 3 học sinh nữ được chọn, hỏi có bao nhiêu cách chọn 9 học sinh từ họ để

a)thành lập một hội đồng?

b)xếp vào 9 vị trí trong một hội đồng?

Đáp số. a)C_5^3\times C_{10}^6.

b)C_5^3\times C_{10}^6\times 9!\Box.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s