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

[hxthanh]

Có N cái kẹo và M túi ( M ≥ 1 và N ≥ M(M+1)/2).
Hỏi có bao nhiêu cách chia N kẹo vào M túi sao cho số kẹo trong mỗi túi là khác nhau và không rỗng, không tính đến các hoán vị
Ví dụ N=10 và M=3 thì (1)(2)(7) ; (1)(7)(2) ; (2)(1)(7) ; (2)(7)(1) ; (7)(1)(2) ; (7)(2)(1) là các cách chia như nhau.

Có thể phát biểu bài toán này dưới dạng tương đương sau:
Có bao nhiêu cách viết số tự nhiên N dưới dạng tổng của M số tự nhiên
N=n₁+n₂+...+n_M
với điều kiện 1≤n₁<n₂<...<n_M.

Với kiến thức tổ hợp, mình đã rất cố gắng mà vẫn không tìm được lời giải cho bài toán này.
Thực sự lời giải cho bài toán này, cho đến nay mình đã tìm được, nhưng phương pháp giải hoàn toàn không dùng kiến thức về tổ hợp.

Công thức về số cách chia đã tìm được là

$C_{N,M}=\sum \lfloor\dfrac{S-M+2-(3k_1+4k_2+...+Mk_{M-2})}{2}\rfloor$

trong đó $S=N-\dfrac{M(M-1)}{2}; M \geq 3; k_1,k_2,...,k_{M-2} \geq 0$
ký hiệu $\lfloor x\rfloor$ để chỉ phần nguyên của x
và biểu thức lấy phần nguyên trong tổng 0.

Gọi là công thức mà tính được công thức cũng khó khăn!

Áp dụng cho N=10 và M=3 ta có
$S=10-\dfrac{3.2}{2}=7; S-M+2=6$

$C_{10,3}= \sum \lfloor\dfrac{6-3k}{2}\rfloor$ (đk k=0,1,2)
$C_{10,3}= \lfloor \dfrac{6}{2}\rfloor+\lfloor \dfrac{3}{2}\rfloor+\lfloor \dfrac{0}{2}\rfloor=3+1+0=4$ cách

Cụ thể là 10 = 1+2+7 = 1+3+6 = 1+4+5 = 2+3+5.

Bạn nào có cách giải khác xin chỉ bảo!

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 15-12-2010 - 15:52

[quanghoa]

Xem thêm phương trình rời rạc

[toiratthichtoan]

Bài này thực chất là tìm số nghiệm nguyên dương của phương trình cậu đặt ra ở đầu. Giải bài này không có gì là khó khăn khi bạn đặt $ n_{1} = a_{1} + 1$, tương tự với các số còn lại. Vậy là ta có một phươg trình như sau:
$ a_{1} +a_{2}+a_{3}+...+a_{M}=N-M$. Bây giờ ta tìm số nghiệm nguyên không âm của phương trình trên.
Vẽ một trục số ra. Đánh dấu điểm 0 và điểm N - M vào. Bây giờ ta có một bài toán tổ hợp như sau: Có bao nhiêu cách đặt M điểm vao trong đoạn từ 0 đến N - M sao cho không có 2 điểm nào trùng nhau. Đáp số của bài toán trên chính là đáp số của bài toán đã cho (với khoảng cách giữa 2 điểm liền nhau là giá trị của một số $ a_{i} $ tương ứng)
=> Xong