Bài giảng này, là một bài giảng nói đến những vấn đề cơ bản nhất của Tổ Hợp. Cái môn học này nghe nhiều người nói là rất dễ, vì nó đời. Cơ  mà với mình (tức là tác giả), thì mình thấy môn này nó khó khắm-khó khú, đại khái là khó lắm lắm… Bởi vậy, mang tiếng là viết để vác đi dạy, nhưng mình coi là chép lại để đi học. Mình cố chép những thứ dễ nhất, liên hệ đến những hình tượng đơn giản nhất, và cố gằng diễn tả nó bằng thứ ngôn ngữ … nghiêm nghị nhất :D. Mình mong, nhận được những góp ý, nhận xét chân thành từ các bạn.

******

 1.  Các khái niệm mở đầu

1.1  Hoán vị là gì?

Định nghĩa. Với một tập hợp ${{S}_{n}}$ gồm $n$ phần tử, việc sắp xếp $n$ phần tử của ${{S}_{n}}$ theo một thứ tự xác định, sẽ cho chúng ta một hoán vị của ${{S}_{n}}$.

1.1.1  Số các hoán vị của một tập gồm $n$ phần tử

 Ta sẽ sử dụng ký hiệu ${{P}_{n}}$, để nói đến số các hoán vị của một tập hợp gồm $n$ phần tử. Như thế, có thể thấy ngay điều rất tầm thường sau, đó là: ${{P}_{0}}={{P}_{1}}=1$.

Bây giờ, giả sử ta cần xếp hàng cho $n;\,n\ge 2$ bạn học sinh. Để lựa chọn bạn nào lên đầu hàng, từ $n$ bạn kia ta có $n$ giải pháp, (bạn nào trong $n$ bạn kia lên đứng đầu chả được). Với mỗi một giải pháp xác định vị trí đứng đầu hàng, còn $n-1$ vị trí đứng cho các bạn còn lại. Từ định nghĩa, ta có được ${{P}_{n-1}}$ cách xếp sắp $n-1$ bạn đó. Theo quy tắc nhân, ta có ngay ${{P}_{n}}=n\times{{P}_{n-1}}$, và với việc truy toán tới tấp ta có:            \[{{P}_{n}}=n\times\left( n-1 \right)\times\ldots\times 1\]Để tiện lợi, ta sử dụng ký hiệu sau đây: \[n!=\left\{ \begin{matrix}   1;\;&n=0;\,1  \\   1\times\ldots\times\left( n-1 \right)\times n;\;&n\in\mathbb Z^+,\;n\ge 2  \end{matrix} \right.\]Như vậy thì\[\boxed {{P}_{n}=n!}\]

Ví dụ 1. Một trại hè có 2012 người tham gia, họ được xếp sắp chỗ ở vào 4 cư xá theo nguyên tắc. Cư xá thứ nhất sẽ chứa chấp 500 người, cư xá thứ 2 và thứ 3, mỗi cư xá nhận 503 người, số còn lại thì đến tá túc ở cư xá thứ 4. Hãy tính xem, nhà tổ chức có bao nhiêu giải pháp xếp sắp chỗ ăn nghỉ cho họ?

1.2  Tổ hợp là gì?

Định nghĩa. Một tập hợp con ${{S}_{k}}$ gồm $k$ phần tử, của một tập ${{S}_{n}}$ gồm $n$ phần tử, gọi là một tổ hợp chập $k$ của $n$ phần tử của $S_n$.

Nhận xét: Để tạo nên một tập con ${{S}_{k}}$ gồm $k$ phần tử, của một tập ${{S}_{n}}$ cho trước, ta cần chọn ra $k$ phần tử trong $n$ phần tử của ${{S}_{n}}$. Tất nhiên là số cách chọn lựa, để thiết lập một tập $S_k$, không phụ thuộc vào bản chất các phần tử của $S$, mà đơn giản nó chỉ liên quan đến số lượng chọn ra và số phần tử của nguồn cung cấp ( lực lượng $S$). Việc bạn chọn ngẫu nhiên ra 5 con bò từ 10 con bò, cũng có số cách lựa chọn giống như việc chọn ngẫu nhiên 5 giáo sư trong 10 giáo sư (để phong tặng một danh hiệu nào đó). Ta sử dụng ký hiệu $C^k_n$, để nói về số các tổ hợp chập $k$ của $n$ phần tử, hay nói cách khác đi, $C^k_n$ là số tập con gồm $k$ phần tử của $n$ phần tử.

1.2.1  Ví dụ:

Ví dụ 2.  Việc người bán thuốc lá lẻ rút ra 5 điếu thuốc từ bao thuốc nguyên(20 điếu). Chuyên ông huấn luyện viên, chọn tùy theo ý thích thú 5 cấu thủ trong 20 cầu thủ vào sân để đá pê-nan-ti (chưa xác đinh việc ai trong 5 cầu thủ đó đá trước đá sau)..  Hay là sự việc 1 cậu bé ngoan, khi hứng chí nghĩ cách nhặt bừa 5 cái cốc, trong cái khay có 20 cái cốc để tìm cách nghe tiếng thủy tinh rạn..  Nói chung là, cái việc gì đó xảy ra trong cuộc đời chúng ta, mà có xuất hiện việc chọn ngẫu nhiên 5 đối tượng từ 20 đôi tượng. Chính là việc tạo ra 1 tổ hợp chập 5 của 20 phần tử. Và số cách tạo ra là $C^5_20$. Bạn nào, kiêng hai con số 5 và 20 thì thay nó bởi hai con số nào tùy hứng, cứ tự nhiên.

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?

Ví dụ 4.  Chaien thèm ăn táo, Bụt hiện ra, và trước mặt cậu ấy có hai rổ táo mỗi rổ có 10 quả, cả 20 quả đều “thơm-ngon-đáng thèm thuồng” như nhau… Tiêu chuẩn của cậu ta, thì chỉ được chén có đúng 2 quả, chúng ta thử tính xem cậu ấy có bao nhiêu lựa chin cho việc ăn táo nhé

 Lời giải.  Vì Chaien bụ bẫm và to khỏe, bản chất lại háu ăn vô cùng, nên ắt cậu ấy sẽ trút béng 2 rổ táo lại chung. Bây giờ, thì cậu ấy chỉ việc bốc phứa 2 trái trong 20 trái “thơm-ngon-đáng thèm thuồng” như nhau kia, chính là việc tạo ra một tập hợn con có 2 phần tử từ tập (cha) có 20 phần tử. Tức là, Chaien sẽ có $C^2_{20}$ lựa chọn, con số này cụ thể là bao nhiêu chờ tý sẽ rõ..

Nhận xét.  Bây giờ, chúng ta tưởng tượng là chả phải Chaien, mà là Nobita ngốc nghếch và yếu đuối ở hoàn cảnh đó thì sao nhỉ? Vì yếu đuối, nên chắc không có cảnh cậu ấy trút 2 rổ làm một. Và bởi ngốc nghếch, nên cậu ta chưa hẳn đã biết tin 20 trái kia đều “thơm-ngon-đáng thèm thuồng như nhau…”. Đại khái, chắc có lẽ cậu ta sẽ có 3 giải pháp như sau:

1. Nhúp mỗi rổ một quả.. Nếu thế, thì cậu ta sẽ có $10\times 10=100$ cách theo quy tắc nhân..
2. Cậu ta nghe trái tim mách bảo, nên chỉ nhúp 2 quả ở rổ bên tay trái, tức là cái rổ bên tay phải cậu ấy nghi là có độc… Nếu mà như thế thì Nobita có có $C^2_{10}$ lựa chọn…
3. Cậu ấy quá lí trí, nên nhặt 2 quả ở rổ bên tay phải… Như thế thì cậu ấy cũng có $C^2_{10}$ sự lựa chọn…

Tóm lại, theo quy tắc cộng thì chàng ngốc của chúng ta có: $100+C^2_{10}+C^2_{10}$ giải pháp để xơi táo.

Có một câu hỏi đặt ra ở đây là: “Việc ăn táo, thì không phải là đánh lộn, hay chơi bóng chày… Trí tuệ, thì thực ra cũng chả liên can đến số cách bốc táo ăn, khi mà táo đã để sẵn trong rổ. Vậy có lẽ số cách lựa chọn của Chaien và Nobita là phải như nhau, tức là $C^2_{20}=100+C^2_{10}+C^2_{10}$ ”?!

Cái băn khoăn này xảy đến, vì chúng ta chưa khảo cứu các tính chất cơ bản của số các tổ hợp, và nhất là chưa có công thức để tính toán nó. Thôi thế thì tạm tin thế đã, vì đàng nào chả.. đúng.

1.2.2  Các tính chất cơ bản của $C^k_{n}$

 Với các định nghĩa trên, ta thấy.

Tính chất 1. (Tính đối ngẫu:)\[C^k_{n}=C^{n-k}_{n}\]Chuyện này là hiển nhiên, nếu chúng ta liên tưởng đến việc chọn $k$ cô gái trong $n$ cô để làm bạn, điều đó cũng có nghĩa là ta đã chọn $n-k$ cô để phụ rẫy và chối từ.

Tính chất 2.  (Liên hệ giữa tổ hợp của $n$ phần tử và tổ hợp của $n+1$ phần tử)          \[C^k_{n}+C^{k+1}_{n}=C^{k+1}_{n+1}\]Chúng ta có đẳng thức này là bởi, nếu như trong chuồng bò có $n$ con bò đực và 1 con bò cái.. Nếu người ta định bán đi $k+1$ con bò trong số đó, họ có hai kiểu như sau:

1. Cứ vào chuồng bắt bừa $k+1$ con, chả quan tâm đến chuyện đực cái gì ở đây… Cái hành động vô tâm tư này, cho thấy có số cách bán bò là:\[C^{k+1}_{n+1}\]
2. Người bán bò có thể bắt bán con bò cái đi, và để đáp ứng nốt nhu cầu của ông thương lái, thì ông ta cần phải chọn them $k$ con bò đực từ $n$ con kia. Còn nếu ông ta yêu mến con bò cái, thì ông ta chọn tất cả $k+1$ con đem bán trong $n$ con bò đực kia. Tóm lại là, cái ông đa đoan chuyện đực-cái này sẽ có số cách bán bò là: \[C^k_{n}+C^{k+1}_{n}\]

Vô tâm tư, hay là đa đoan đực-cái, thì vẫn là chuyện bán bò, số cách vẫn là như nhau cả, và vì thế mà chúng ta có đẳng thức kia.

1.2.3  Công thức tính số các tổ hợp chập $k$ của $n$ phần tử

Giả sử ta cần xếp $k$ người cô gái và $n-k$ ông lão ngồi vào một hàng ghế gồm $n$ chiếc… Nếu một người vô tâm chỉ xếp cho nó xong thì có $n!$ cách xếp chỗ cho họ. Tuy nhiên với một người xếp chỗ “lịch lãm” thì họ sẽ chú tâm xếp chỗ cho $k$ cô nàng kia trước… Như thế có $C^k_n$ cách chọn ghế cho các quý cô sau đó với $k$ ghế dẫ chọn ta có $k!$ cách lùa các nàng ngồi vào… Tất nhiên đồng thời với điều đó các “quý ông lão” còn lại $n-k$ cái ghế mà tranh nhau ngồi, vậy nên có $\left( n-k \right)!$ cách xếp chỗ cho họ. Theo quy tắc nhân thì như vậy có $C^k_n\times k!\times \left( n-k \right)!$ cách. Từ đó ta có công thức:\[C^k_n=\frac{n!}{k!\left( n-k \right)!}\]

1.2.4  Tam giác Pascal

Tam giác số vô hạn dưới đây, là bảng liệt kê số các tổ hợp chập $k$ của $n$ phần tử tức các số $C^k_n$.

n = 0;  1

n = 1;  1     1

n = 2;  1     2        1

n = 3;  1     3        3        1

n = 4;  1     4        6        4        1

n = 5;  1     5        10      10      5        1

n = 6;  1     6        15      20      15      6        1

…………………………………………………………….

Cái bảng số có hình hài như mái nhà này, cho chúng ta thấy vài điều đã phải là đúng rồi như sau:

1. Những viên ngói ở rìa mái nhà luôn là số 1, điều này thông báo rằng: $C^0_n=C^n_n=1$.
2. Sự cân xứng hai bên, nhắc nhủ cái tính chất $C^{k}_n=C^{n-k}_n$.
3. Những số ở bên trong (tức là không ngoài rìa mái) của hàng dưới, là tổng của hai số đặt chồm hỗm trên đầu nó ở hàng trên. Điều này thể hiện cái tính chất: $C^{k}_n+C^{k+1}_n=C^{k+1}_{n+1}$.

Cuối cùng, vẫn phải nhắc lại điều dễ nhận biết là: “số ở vị trí $k$ (tính từ trái qua), trên dòng thứ $n$ là $C^{k-1}_n$”

1.3  Chỉnh hợp là gì?

 Định nghĩa: Hễ ${{S}_{k}}$ là một tổ hợp chập $k$ của tập ${{S}_{n}}$ gồm $n$ phần tử, thì việc xác định một thứ tự cho $k$ phần tử của ${{S}_{k}}$ sẽ cho chúng ta một chỉnh hợp chập $k$ của ${{S}_{n}}$.

 Nhận xét: Như vậy là để có một chỉnh hợp chập $k$ từ một tập có $n$ phần tử, chúng ta có hai công đoạn cần làm:

1. Lấy ra $k$ phần tử từ cái tập gồm $n$ phần tử kia, việc này chính là kiến tạo một tổ hợp chập $k$ của $n$ phần tử.
2. Xác lập một thứ tự sắp xếp cho $k$ phần tử kia, bản chất của việc này chính là tạo một hoán vị với $k$ phần tử đã lựa chọn từ công đoạn trên.

Số các tổ hợp chập $k$ của $n$ phần tử là $C^k_n=\frac{n!}{k!\left( n-k \right)!}$. Với mỗi tổ hợp kiểu đó, tức là một tập con gồm $k$ phần tử, chúng ta sắp xếp thứ tự cho chúng nhờ thực hiện một phép hoán vị với $k$ phần tử đó. Và bởi vậy, theo quy tắc nhân thì số các chỉnh hợp chập $k$ của $n$ phần tử chính là \[A_{n}^{k}=k!C^k_n=\frac{n!}{\left( n-k \right)!}\]

 (còn tiếp…)