Combinations

Combinatorics, Enumerative combinatorics, Pre-Olympiad 8 Minutes

Cho một tập A có n 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ụ 1. Các 3-tổ hợp của A=\{a,b,c,d\} là

\{a,b,c\},\{b,c,d\},\{c,d,a\},\{d,a,b\}.

Định lí 1. Cho một tập A có n 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ụ 2. Có bao nhiêu xâu nhị phân độ dài 7 mà có đúng ba số 0?

Lời giải. Một xâu nhị phân có tính chất như trong đề bài sẽ được hình thành khi ta chọn 3 vị trí trong 7 vị trí để viết số 0. Do đó số xâu thỏa mãn là C_7^3. \Box

Ví dụ 3. 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

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

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

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

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

Hướng dẫn giải. (1) C_{11}^5. (2) C_4^2\times C_7^3. (3) 3 hoặc 4 giáo viên có thể nằm trong hội đồng, đáp số 91.

(4) Dùng quy tắc trừ, đáp số 378. \Box

Ví dụ 4. 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 quy tắc nhân, số phân hoạch thoả mãn là (2n-1)\times (2n-3)\times\cdots\times 1. \Box

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!}. \Box

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)\} có (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

Ví dụ 5. 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

Ví dụ 6. 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 cho 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

Ví dụ 7. 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?

Hướng dẫn. 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

Ví dụ 8. Có bao nhiêu cách xếp 5 cái ghế xanh giống nhau và 5 cái ghế đỏ giống nhau quanh một cái bàn tròn? Hai cách xếp được coi là một nếu một cách có được từ cách còn lại bởi một phép quay quanh tâm của bàn.

Lời giải. Gọi A là tập tất cả các cách xếp có tính chất như trong đề bài và B là tập tất cả các cách xếp 5 cái ghế xanh giống nhau và 5 cái ghế đỏ giống nhau thành một hàng. Khi đó \mid B\mid =C^5_{10}=252 và ta cần tính \mid A\mid.

Đánh số 10 vị trí quanh bàn tròn bởi các số 1,2,\ldots,10 theo chiều kim đồng hồ. Với mỗi cách xếp thuộc A, ta “cắt” tại vị trí giữa 1 và 10, sau đó “kéo thẳng” thì sẽ có một cách xếp thuộc B. Mọi cách xếp trong B sẽ được sinh ra từ một cách xếp trong A theo cách này.

Mỗi cách xếp thuộc B hoàn toàn được xác định bởi vị trí của 5 cái ghế đỏ. Xét một cách xếp thuộc B, ký hiệu b_0, có tập các vị trí của 5 cái ghế đỏ là \{a_1,a_2,a_3,a_4,a_5\}. Với mỗi i\in [9], gọi b_i là cách xếp thuộc B có tập các vị trí của 5 cái ghế đỏ là \{a_1+i,a_2+i,a_3+i,a_4+i,a_5+i\}, trong đó các vị trí được mở rộng theo modulo 10. Ta thấy 10 cách xếp b_0, b_1,\ldots, b_9 được sinh từ 1 cách xếp thuộc A, và nói chung, chúng đôi một khác nhau. Thật vậy nếu có hai cách xếp giống nhau thì tồn tại i\in [9] để

\{a_1,a_2,\ldots,a_5\}=\{a_1+i,a_2+i,\ldots,a_5+i\},

suy ra 5i\equiv 0\pmod{10}\Rightarrow i\in\{2,4,6,8\}. Kiểm tra trực tiếp ta thấy

\{a_1,a_2,a_3,a_4,a_5\}=\{1,3,5,7,9\} hoặc \{2,4,6,8,10\}.

Bây giờ ta phân hoạch B sao cho 2 cách xếp thuộc cùng một khối khi và chỉ khi chúng được sinh từ cùng một cách xếp thuộc A. Ta có \mid A\mid bằng số khối của phân hoạch này, và bằng \displaystyle \frac{250}{10}+\frac{2}{2}=26. \Box

Unknown's avatar

Published by Nguyen Trung-Tuan

A math teacher.

Published

One thought on “Combinations”

  1. Pingback: Principle of Inclusion-Exclusion – T's Lab

Leave a comment