Chủ đề này có 2 trả lời

[tranwhy]

Có 10 quả cầu được đặt vào 10 cái hộp khác nhau ( không nhất thiết hộp nào cũng có quả cầu )

Hỏi có bao nhiêu cách đặt khác nhau nếu các quả cầu giống hệt nhau ??

[L Lawliet]

Có 10 quả cầu được đặt vào 10 cái hộp khác nhau ( không nhất thiết hộp nào cũng có quả cầu )

Hỏi có bao nhiêu cách đặt khác nhau nếu các quả cầu giống hệt nhau ??

Đây là một trường hợp của bài toán chia kẹo Euler bạn có thể tìm thêm trên mạng tài liệu về các dạng toán này. Mình trình bày bài toán tổng quát và lời giải cho bạn nhé:

 

Bài toán. Có bao nhiêu cách phân phối $n$ đồ vật giống nhau cho $p$ người (không nhất thiết người nào cũng nhận được đồ vật)?

Lời giải.

Giả sử người thứ nhất nhận được $k_{1}$ đồ vật, người thứ hai nhận được $k_{2}$ đồ vật,..., người thứ $p$ nhận được $k_{p}$ đồ vật ($k_{1}+k_{2}+...+k_{p}=n$) ($k_{i}\geq 0$). Ta viết tượng trưng cách phân phối đó như sau:

$$11...122...2...pp...p$$

Trong đó có $k_{1}$ số $1$, $k_{2}$ số $2$,..., $k_{p}$ số $p$ (nếu $k_{i}=0$ thì ta không viết dãy chữ số $i$ tương ứng).

Như vậy mỗi cách phân phối ứng với một tổ hợp có lặp chập $n$ của $p$ phần tử. Đảo lại, ứng với mỗi tổ hợp có lặp chập $n$ của $p$ phần tử, có một cách phân phối $n$ đồ vật giống nhau cho $p$ người.

Vậy số cách phân phối bằng số tổ hợp có lặp chập $n$ của $p$ phần tử, tức là:

$$\overline{C_{p}^{n}}=C_{n+p-1}^{n}=\dfrac{\left ( n+p-1 \right )!}{n!\left ( p-1 \right )!}$$

[12345678987654321123456789]

Có 10 quả cầu được đặt vào 10 cái hộp khác nhau ( không nhất thiết hộp nào cũng có quả cầu )

Hỏi có bao nhiêu cách đặt khác nhau nếu các quả cầu giống hệt nhau ??

Một cách khác cho bài toán : Có bao nhiêu cách chia $n$ đồ vật giống nhau cho $p$ người (không nhất thiết người nào cũng nhận được đồ vật)

Nếu ta đưa trước cho mỗi người $1$ đồ vật thì bài toán trở thành : Có bao nhiêu cách chia $n+p$ đồ vật giống nhau cho $p$ người mà mỗi người có ít nhất $1$ đồ vật.

Lúc này, nếu ta đặt các đồ vật ở cạnh nhau và đặt $p-1$ vách ngăn thì các đồ vật sẽ được chia thành $p$ nhóm, rõ ràng đó là một cách chọn cần tìm.

Số cách đặt $1$ vách ngăn là $n+p-1$, nên số cách đặt vách ngăn sẽ là $C_{n+p-1}^{p-1}$ và đó là đáp án của đề bài

Áp dụng với $n=10;\;p=10$ ta có $C_{10+10-1}^{10-1}=\boxed{92378}$

$C_{n+p-1}^{p-1}=\overline{C_{n}^{p}}$ được gọi là tổ hợp lặp chập $p$ của $n$

Bài viết đã được chỉnh sửa nội dung bởi 12345678987654321123456789: 30-08-2016 - 00:41