Có bốn ngăn (trong một giá để sách) được đánh số thứ tự 1, 2, 3, 4 và tám quyển sách khác nhau. Bạn An xếp hết tám quyển sách nói trên vào bốn ngăn đó sao cho mỗi ngăn có ít nhất một quyển sách và các quyển sách được xếp thẳng đứng thành một hàng ngang với gáy sách quay ra ngoài ở mỗi ngăn. Khi đã xếp xong tám quyển sách, hai cách xếp của bạn An được gọi là giống nhau nếu chúng thỏa mãn đồng thời hai điều kiện sau đây: + Với từng ngăn, số lượng quyển sách ở ngăn đó là như nhau trong cả hai cách xếp. + Với từng ngăn, thứ tự từ trái sang phải của các quyển sách được xếp là như nhau trong cả hai cách xếp. Gọi là số cách xếp đôi một khác nhau của bạn An. Giá trị của bằng bao nhiêu?

Có bốn ngăn (trong một giá để sách) được đánh số thứ tự 1, 2, 3, 4 và tám quyển sách khác nhau. Bạn An xếp hết tám quyển sách nói trên vào bốn ngăn đó sao cho mỗi ngăn có ít nhất một quyển sách và các quyển sách được xếp thẳng đứng thành một hàng ngang với gáy sách quay ra ngoài ở mỗi ngăn. Khi đã xếp xong tám quyển sách, hai cách xếp của bạn An được gọi là giống nhau nếu chúng thỏa mãn đồng thời hai điều kiện sau đây:

+ Với từng ngăn, số lượng quyển sách ở ngăn đó là như nhau trong cả hai cách xếp.

+ Với từng ngăn, thứ tự từ trái sang phải của các quyển sách được xếp là như nhau trong cả hai cách xếp.

Gọi là số cách xếp đôi một khác nhau của bạn An. Giá trị của bằng bao nhiêu?

Hãy suy nghĩ và trả lời câu hỏi trước khi xem đáp án

Lời giải

Để giải bài toán này, ta cần tìm số cách xếp 8 quyển sách vào 4 ngăn sao cho mỗi ngăn có ít nhất 1 quyển. Đầu tiên, ta tìm số nghiệm nguyên dương của phương trình $x_1 + x_2 + x_3 + x_4 = 8$, với $x_i$ là số sách ở ngăn thứ $i$. Số nghiệm của phương trình này là $C_{8-1}^{4-1} = C_7^3 = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$. Với mỗi bộ $(x_1, x_2, x_3, x_4)$, ta có thể sắp xếp các quyển sách trong mỗi ngăn. Ví dụ, nếu $(x_1, x_2, x_3, x_4) = (1, 1, 1, 5)$, số cách sắp xếp là $C_8^1 C_7^1 C_6^1 C_5^5 \times 1! 1! 1! 5! = \frac{8!}{1!1!1!5!} = 8 \times 7 \times 6 = 336$. Nhưng các cách chia số lượng sách vào các ngăn sẽ khác nhau. Ta sẽ xét các trường hợp: 1. (5,1,1,1): Số cách chia là $C_8^5 C_3^1 C_2^1 C_1^1 = \frac{8!}{5!1!1!1!} = 8 \times 7 \times 6 = 336 \times 4 = 6720 \times 4! = 40320$ Khi đó số cách sắp xếp là $4 \times \frac{8!}{5!1!1!1!} = 4 \times (8 \times 7 \times 6) = 4 \times 336 = 1344$ Tuy nhiên, ta cần tính số hoán vị của 8 quyển sách khác nhau, đó là 8! = 40320. Ta cần chia 8 quyển sách vào 4 ngăn sao cho mỗi ngăn có ít nhất 1 quyển. Bài toán này phức tạp hơn ta nghĩ. Số các số nguyên dương $x_1, x_2, x_3, x_4$ sao cho $x_1 + x_2 + x_3 + x_4 = 8$ là $C_{8-1}^{4-1} = C_7^3 = 35$. Tuy nhiên, mỗi cách chia này có một số hoán vị khác nhau. Ta xét trường hợp đơn giản hơn: 2 ngăn, 3 quyển sách. Các trường hợp là (1,2), (2,1). Số cách là $C_3^1 imes 1! imes 2! + C_3^2 imes 2! imes 1! = 3 imes 2 + 3 imes 2 = 12 = A_3^3 \times C_2^1 / 1 \div 1$ Ta thấy công thức này không áp dụng được. Số cách chọn là $S(8,4) imes 4!$, với S(8,4) là số Stirling loại 2. S(8,4) = 1701. Vậy số cách là 1701 * 24 = 40824. Sau khi xếp sách vào ngăn theo số lượng, ta có 8! cách xếp thứ tự cho 8 quyển sách. Do đó đáp án phải là 40320