Chuyên đề Tổ hợp 4

Chuyên đề: Đại số tổ hợp
Dạng 4
Phân chia một tập hợp gồm các phần tử giống nhau
Nội dung
Nội dung
Dạng 4:
Dạng 4A. Một số bài toán về phân chia các phần tử của một tập hợp gồm các phần tử giống nhau
Dạng 4B. Tính số nghiệm nguyên của phương trình
Dạng 4A
Một số bài toán về phân chia các phần tử của một tập hợp gồm các phần tử giống nhau
Bài tập mẫu
Bài 1. Có bao nhiêu cách chia 50 đồ vật giống nhau cho ba người sao cho mỗi người đười được ít nhất một đồ vật.
Giải
Giả sử ta đặt 50 đồ vật đã cho thành một hàng ngang, giữa chúng có 49 khoảng trống (xem hình minh hoạ).
o o . . o │ o o o o . . . o o │ o o . . o o o
người 1 người 2 người 3
Nếu đặt hai vạch một cách bất kỳ vào hai trong số 49 khoảng trống đó, ta được một phép chia 50 đồ vật ra làm ba phần, mỗi phần có ít nhất một đồ vật. Ba người lần lượt nhận số đồ vật trong ba phần tương ứng, ta được một cách chia thoả mãn bài toán.
Vậy số cách chia là số cách đặt hai vạch vào hai trong 49 khoảng trống. Ta được số cách chia là
Đáp số: 1176 cách chia.
Một số bài toán về phân chia
các phần tử của một tập hợp gồm các phần tử giống nhau
Lưu ý
Nếu chia m đồ vật giống nhau cho n người sao cho mỗi người được ít nhất một đồ vật thì số cách chia là
Một số bài toán về phân chia
các phần tử của một tập hợp gồm các phần tử giống nhau
Bài tập tương tự - Bài tập 1
Có bao nhiêu cách chia 60 đồ vật giống nhau cho bốn người sao cho mỗi người được ít nhất 5 đồ vật.
Giải
Ta đem chia trước cho mỗi người 4 đồ vật. Số đồ vật còn lại là: 60 – 4.4 = 44
Bây giờ ta đem 44 đồ vật đó chia cho bốn người, mỗi người được ít nhất một đồ vật. Khi đó cùng với 4 đồ vật đã nhận trước, mỗi người được ít nhất 5 đồ vật, thoả mãn bài toán.
Giả sử ta đặt 44 đồ vật đó thành một hàng ngang, giữa chúng có 43 khoảng trống (xem hình minh hoạ).
o o . . o │ o o o o . . . o o │ o o . . o o o │ o o . . o o
người 1 người 2 người 3 người 4
Một số bài toán về phân chia
các phần tử của một tập hợp gồm các phần tử giống nhau
Bài tập tương tự (tt) - Bài tập 1 (tt)
Nếu đặt ba vạch một cách bất kỳ vào ba trong số 43 khoảng trống này, ta được một phép chia 44 đồ vật ra làm bốn phần, mỗi phần có ít nhất một đồ vật. Bốn người lần lượt nhận số đồ vật trong bốn phần tương ứng, ta được một cách chia thoả mãn bài toán.
Vậy số cách chia là số cách đặt ba vạch vào ba trong 43 khoảng trống. Ta được số cách chia là
Đáp số: 12341 cách chia.
Một số bài toán về phân chia
các phần tử của một tập hợp gồm các phần tử giống nhau
Lưu ý:
Tính số cách chia m đồ vật giống nhau cho n người sao cho mỗi người được ít nhất k đồ vật (m  kn).
Cách giải
Ta chia trước cho mỗi người k –1 đồ vật.
Số đồ vật còn lại là s = m – n(k – 1)
Đem số đồ vật này chia cho n người sao cho mỗi người được ít nhất 1 đồ vật, thì số cách chia là Mỗi cách chia như vậy thoả mãn bài toán.
Một số bài toán về phân chia
các phần tử của một tập hợp gồm các phần tử giống nhau
Dạng 4B
Tính số nghiệm nguyên của phương trình
Bài tập mẫu
Tính số nghiệm của phương trình x + y + z = 100 với x, y, z  N*.
Nhận xét
Về bản chất mỗi nghiệm của phương trình tương ứng với một phép chia 100 đồ vật cho ba người sao cho mỗi người được ít nhất một đồ vật.
Lặp lại cách làm như hai bài tập trên, ta được số nghiệm của phương trình là
Đáp số: 4851 nghiệm.
Tính số nghiệm nguyên của phương trình
Lưu ý
Bài toán tổng quát: Tính số nghiệm của phương trình
x1 + x2 + …. + xn = m với m, n, x1, x2, ….., xn  N*; m  n
Giải
Giả sử ta đặt m dấu chấm theo một hàng ngang, giữa chúng có m -1 khoảng trống (xem hình minh hoạ).


Nếu đặt n -1 vạch một cách bất kỳ vào n -1 trong số m – 1 khoảng trống đó, ta được một cách chia m dấu chấm ra thành n phần. Gán giá trị cho x1, x2, .., xn lần lượt bằng số dấu chấm trong các phần 1, 2, …, n, ta được một nghiệm của phương trình đã cho.
Vậy số nghiệm của phương trình là số cách đặt n -1 vạch một cách bất kỳ vào n -1 trong số m – 1 khoảng trống đó, ta được số nghiệm phải tìm là
Tính số nghiệm nguyên của phương trình
Bài tập tương tự - Bài tập 1
Tính số nghiệm của phương trình
x + y + x + t = 100 (1) với x, y, z, t  N
Giải
Đặt a = x + 1, b = y + 1, c = z + 1, d = t + 1 ta được phương trình
a + b + c + d = 104 (2) với a, b, c, d  N*
Mỗi nghiệm của PT (2) tương ứng với một nghiệm của PT (1).
Theo bài toán tổng quát trên, ta được số nghiệm của phương trình là

Đáp số: 176851 nghiệm.
Tính số nghiệm nguyên của phương trình
Lưu ý:
Bài toán tổng quát: Tính số nghiệm của phương trình
x1 + x2 + …. + xn = m với m, n, x1, x2, ….., xn  N.
Giải.
Đặt a1 = x1+1, a2 = x2+1, ….., an = xn+1 ta được phương trình
a1 + a2 + …. + an = m + n (2) với a1, a2, ….., an  N*.
Mỗi nghiệm của PT (2) tương ứng với một nghiệm của PT (1).
Theo bài toán tổng quát trên, ta được số nghiệm của phương trình là
Tính số nghiệm nguyên của phương trình
Bài tập tương tự (tt) - Bài tập 2
Tính số nghiệm của phương trình x + y + z + t = 100 với x, y, z, t  Z và x > - 2, y > - 1, z > 0, t > 1
Giải.
Đặt a = x + 2, b = y + 1, c = z, d = t – 1 a, b, c, d  1. Ta được phương trình
a + b + c + d = 102 (2) với a, b, c, d  N*.
Theo bài toán tổng quát trên, ta được số nghiệm của phương trình là

Nhắc lại bài toán tổng quát. Tính số nghiệm của phương trình
x1 + x2 + …. + xn = m với m, n, x1, x2, ….., xn  N*, m  n.
Số nghiệm của phương trình là
Tính số nghiệm nguyên của phương trình