Dân AnNam mình có truyền thống làm ít-hít nhiều, cứ nói đến thưởng cái gì là cãi vã toán loạn. Nên có lẽ, chúng ta cần quan tâm đến bài toán rất thực tế sau

Bài toán chia phần thưởng. Có $m$ phần thưởng khác nhau. Hỏi, có bao nhiêu cách chia chúng cho $n$ người sao cho ai cũng sẽ được ít nhất một phần thưởng?

Gọi $N(m,\,n)$ là số cách chia thưởng khác nhau, rõ ràng khi mà $m<n$ thì do số phần thưởng không đủ cho nên $N(m,\,n)=0$. Do vậy, ta chỉ cần xét tình huống $m\ge n$. Nếu như không quan tâm đến tình huống bất công, tức là ai đó sẽ chẳng nhận được phần thưởng gì, khi đó ta có bài toán rất dễ sau đây

Bài toán chia phần thưởng kiểu hình thức. Có $m$ phần thưởng đôi một khác nhau, hỏi có bao nhiêu cách chia chúng cho $n$ người?

Lời giải. Thực chất mỗi cách chia phần thưởng ở bài toán này, là một lần lên một kế hoạch gồm $m$ bước, mỗi bước là lựa chọn kẻ được trao gửi phần thưởng từ thứ $1$ đến thứ $m$. Đóng vai một kẻ ban phát sủng ân như thế, khi đó phần thưởng thứ nhất có $n$ lựa chọn ở bước $1$ , ở bước $2$ đến bước cuối cứ tuần tự vậy, cho nên số cách trao thưởng không quan tâm đến việc có kẻ trắng tay sẽ là $n^m$.

$\square$

Tất nhiên bài toán đơn giản vừa xử lý, không phải là bài toán chúng ta đặt ra từ đầu. Một chút động lòng trắc ẩn ở đây, rõ ràng gây ra rắc rối, bởi vì là nó cứ lặp lại-lẫn lộn tứ lung tung các khả năng ban phát. Cho nên trước khi có được một cư xử ái từ nhưng đúng đắn, ta sẽ suy nghĩ đến một kế hoạch ác độc, đó là kiểm soát các cách phân phát mà.. chắc chắn có kẻ ra về tay không.

Đánh số cho $n$ người, ta gọi $A_k$ là tập các cách chia thưởng mà người thứ $k$ không nhận được gì. Bởi vì số cách chia thưởng hình thức là $n^m$, cho nên \[N\left( {m,{\mkern 1mu} n} \right) = {n^m} – \left| {{A_1} \cup {A_2} \cup \ldots \cup {A_n}} \right|.\]Bây giờ thì ta lại phải đi tính $\left| {{A_1} \cup {A_2} \cup \ldots \cup {A_n}} \right|$, may thay việc này ta đã có nguyên lý cơ bản sau đây trong Tổ Hợp.

Nguyên lý bù trừ. Cho các tập hữu hạn $A_1,\,A_2,\,\ldots ,\,A_n$ khi đó\[\begin{array}{l}
\left| {{A_1} \cup {A_2} \cup \ldots \cup {A_n}} \right| = \sum\limits_{1 \le i \le n} {\left| {{A_i}} \right|} – \sum\limits_{1 \le i < j \le n} {\left| {{A_i} \cap {A_j}} \right| + \ldots } \\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, + {\left( { – 1} \right)^{k + 1}}\sum\limits_{1 \le {i_1} < {i_2} < \ldots < {i_k} \le n} {\left| {{A_{{i_1}}} \cap {A_{{i_2}}} \cap \ldots \cap {A_{{i_k}}}} \right|} + \ldots \\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, + {\left( { – 1} \right)^{n + 1}}\left| {{A_1} \cap {A_2} \cap \ldots \cap {A_n}} \right|
\end{array}\]

Chứng minh. Ta sẽ chứng minh rằng rằng mỗi phần tử trong $ \cup _{i = 1}^n{A_i}$ được đếm đúng một lần trong vế phải. Gọi $e$ là một phần tử trong hợp đó và nó nằm trong đúng $m$ tập ${A_i}$, khi đó với lưu ý là $(1-1)^m=0$, thì trong vế phải $e$ sẽ có số lần được đếm là $${\rm C}_m^1 – {\rm C}_m^2 + \cdots + {( – 1)^{m + 1}}{\rm C}_m^m = {\rm C}_m^0=1.$$ Và vì vậy, nguyên lý được chứng minh.

$\square$

Quay lại vấn đề ta đang đeo đuổi, với mỗi bộ $\left(i_1,\,i_2,\,\ldots ,\,i_k\right)$ trong đó $i_j\in\{1,\,2,\,\ldots ,\,n\}$ theo bài toán chia thưởng kiểu hình thức thì ta có\[\left| {{A_{{i_1}}} \cap {A_{{i_2}}} \cap \ldots \cap {A_{{i_k}}}} \right| = {\left( {n – k} \right)^m}.\]Cái này nguyên do là, những người được đánh số $i_j$ không được nhận phần thưởng cũng đồng nghĩa với $m$ phần thưởng kia được dành cho $n-k$ kẻ còn lại. Kết hợp việc sẽ có $\rm{C}_n^k$ bộ $\left(i_1,\,i_2,\,\ldots ,\,i_k\right)$, để thấy là ta có\[\left| {{A_1} \cup {A_2} \cup \ldots \cup {A_n}} \right| = {\rm{C}}_n^1{\left( {n – 1} \right)^m} – {\rm{C}}_n^2{\left( {n – 2} \right)^m} + \ldots + {\left( { – 1} \right)^n}{\rm{C}}_n^{n – 1}{1^m}.\]Và kết quả cho bài toán ban đầu, nó sẽ là\[N(m,\,n)={n^m} – {\rm{C}}_n^1{\left( {n – 1} \right)^m}{\rm{ + C}}_n^2{\left( {n – 2} \right)^m} + \ldots + {\left( { – 1} \right)^{n – 1}}{\rm{C}}_n^{n – 1}{1^m}.\]