Trong các bài toán tổ hợp, việc liệt kê tất cả các trường hợp có thể rất khó khăn, đặc biệt khi số lượng phần tử lớn. Vậy có một phương pháp nào giúp chúng ta giải những bài toán như thế đơn giản hơn không? Sau đây hãy cùng TTnguyen tìm hiểu về chỉnh hợp lặp và tổ hợp lặp giúp chúng ta giải các bài toán phức tạp một cách dễ dàng hơn.
Xem thêm:
bài tập toán rời rạc chương 1 có lời giải
bài tập về hoán vị chỉnh hợp tổ hợp
bài tập phép đếm toán rời rạc có lời giải
I. Chỉnh hợp lặp là gì?
1. Định nghĩa
Chỉnh hợp lặp là một dãy gồm k phần tử được chọn từ tập A, trong đó:
- Mỗi phần tử có thể được lặp lại nhiều lần.
- Sắp xếp theo một thứ tự nhất định có ý nghĩa.
2. Công thức chỉnh hợp lặp
Số chỉnh hợp lặp chập k của n phần tử được tính bằng:
(F_{n}^{k} = n^{k})
3. Ví dụ
Có bao nhiêu chuỗi có độ dài r có thể được hình thành từ những chữ cái hoa trong bảng chữ cái tiếng Anh?
Lời giải
Mỗi chữ cái có 26 lựa chọn. => Theo công thức chỉnh hợp lặp có (26^{r}) chuỗi có độ dài r.
II. Tổ hợp lặp là gì?
1. Định nghĩa
Tổ hợp lặp là một dãy gồm k phần tử được chọn từ tập A, trong đó:
- Mỗi phần tử có thể được lặp lại nhiều lần.
- Thứ tự sắp xếp các phần tử không quan trọng.
2. Công thức tổ hợp lặp
Số tổ hợp lặp chập k của n phần tử được tính bằng:
(K_{n}^{k} = C_{n+k-1}^{k} = C_{n+k-1}^{n-1}=frac{n+k-1}{k!(n-1)!})
3. Ví dụ
Có bao nhiêu cách để chọn 4 quả từ một đĩa chứa táo, cam, lê nếu thứ tự các quả được chọn không quan trọng, chỉ quan trọng loại quả và số lượng quả, và có ít nhất bốn quả mỗi loại trong đĩa?
Lời giải
Cách để chọn 4 quả từ mỗi loại đĩa là số tổ hợp lặp chập 4 từ tập 3 phần tử {Táo, Cam, Lê}:
(C_{n+k-1}^{n-1} = C_{3+4-1}^{3-1} = 15).
4 Táo 4 Cam 4 Lê 3 táo, 1 cam
3 táo, 1 lê
2 táo, 2 cam
2 táo, 1 cam, 1 lê
3 cam, 1 lê
3 cam, 1 táo
2 cam, 2 lê
2 cam, 1 táo, 1 lê
3 lê, 1 táo
3 lê, 1 cam
2 lê, 2 táo
2 lê, 1 cam, 1 táo
III. So sánh chỉnh hợp lặp và chỉnh hợp không lặp
Loại chỉnh hợp Đặc điểm Công thức Chỉnh hợp không lặp Thứ tự quan trọng, không lặp lại phần tử. (F_{n}^{k} = frac{n!}{(n-k)!}) Chỉnh hợp lặp Thứ tự quan trọng, cho phép lặp lại phần tử. (F_{n}^{k} = n^{k})
IV. Bài tập tổ hợp lặp và chỉnh hợp lặp có lời giải
Bài 2: Có bao nhiêu cách để chọn năm tờ tiền từ một hộp chứa các mệnh giá 1 đồng, 2 đồng, 5
đồng, 10 đồng, 20 đồng, 50 đồng, và 100 đồng? Giả sử rằng thứ tự các tờ tiền được chọn không quan trọng, và rằng các tờ tiền cùng mệnh giá là không phân biệt, và có ít nhất 5 tờ tiền cho mỗi mệnh giá.
Lời giải
Số cách chọn 5 tờ tiền là: (C_{n+k-1}^{n-1} = C_{5+7-1}^{5-1} = 330).
>>Cùng chủ đề: các nguyên lý đếm cơ bản toán rời rạc | Lý thuyết và bài tập
Bài 3: Phương trình dưới đây có bao nhiêu lời giải: (x_{1} + x_{2} + x_{3} = 13) trong đó (x_{1}, x_{2}, x_{3} ) là các số nguyên không âm?
Lời giải
Một lời giải → một cách chọn 13 phần n tử từ tập {a, b, c } sao cho:
có (x_{1}) lần lấy phần tử a.
có (x_{2}) lần lấy phần tử b.
có (x_{3}) lần lấy phần tử c.
→ Số lời giải → số tổ hợp lặp chập 13 từ một tập có 3 phần tử: (C_{n+k-1}^{n-1} = C_{3+11-1}^{3-1} = 66) lời giải
Bài 4: Phương trình dưới đây có bao nhiêu lời giải (x_{1} + x_{2} + x_{3} + x_{4}= 20) trong đó (x_{1}, x_{2}, x_{3} ) là các số nguyên thỏa (x_{1} ≥ 0, x_{2} ≥ 0, x_{3} ≥ 0, x_{4} ≥ 0)?
Lời giải
Bài 5: Phương trình dưới đây có bao nhiêu lời giải (x_{1} + x_{2} + x_{3} + x_{4}= 20) trong đó (x_{1}, x_{2}, x_{3} ) là các số nguyên thỏa (x_{1} ≥ 6, x_{2} ≥ 3, x_{3} ≥ 9, x_{4} ≥ 2)?
Lời giải
Bài 6: Bất phương trình (x_{1} + x_{2} + x_{3} ≤ 11 ) trong đó (x_{1}, x_{2}, x_{3} ) là các số nguyên thỏa (x_{1} ≥ 0, x_{2} ≥ 0, x_{3} ≥ 0)?
Lời giải
Bài 3: Phương trình x1 + x2 + x3 + x4 =9 bao nhiêu nghiệm nguyên trong các trường hợp sau: a) xi ≥ 0 và nguyên (i= ( overline{1,4} )) b) xi nguyên và x1 ≥ 0, x2 ≥ 1, x3 ≥ 2, 0≤ x4 ≤ 3
Giải
a) Số nghiệm là tổ hợp lặp chập 9 của 4 phần tử
b) Đặt x1 = t1 ≥ 0, x2 -1 =t2 ≥ 1, x3 -2 = t3≥ 2, x4 = t4≥ 0
Thay vào phương trình ta được
t1 + t2 + t3 + t4 = 12 (1)
Với x4 =0 số nghiệm của phương trình (1) là:
Với x4 =1 số nghiệm của phương trình (1) là:
Với x4 =2 số nghiệm của phương trình (1) là:
Với x4 =3 số nghiệm của phương trình (1) là:
Vậy số nghiệm là tổng của 4 trường hợp: 455+ 1820 + 6188 + 18564 =27027
Bài 7:
a. Giả sử chúng ta có 5 viên bi giống nhau và 3 chiếc túi khác màu là xanh, vàng và đỏ. Cho biết có bao nhiêu cách bỏ bi vào các túi?
Lời giải
b. Giả sử chúng ta có 5 viên bi (2 bi sắt, 2 bi chai và 1 bi đất) và 3 chiếc túi màu xanh, vàng và đỏ. Cho biết có bao nhiêu cách bỏ bi vào các túi? Ví dụ: Cách 1 túi xanh chứa 2 bi sắt, túi vàng 2 bi chai và túi đỏ 1 bi đất; cách 2 -> túi xanh 1 bi sắt, túi vàng 2 bi chai + 1 bi sắt và túi đỏ 1 bi đất, …
Lời giải
c. Giả sử chúng ta có 5 viên bi (2 bi sắt, 2 bi chai và 1 bi đất. Cho biết có bao nhiêu cách sắp chúng thành hàng? Ví dụ: sắt sắt chai chai đất, sắt chai sắt chai đất,…
Lời giải
Trên đây là các bài tập về tổ hợp lặp và chỉnh hợp lặp. Cảm ơn các bạn đã theo dõi toán rời rạc trên ttnguyen.net.
Bài viết cùng chủ đề:
hệ thức truy hồi trong toán rời rạc
chu trình euler
lý thuyết đồ thị toán rời rạc
thuật toán kruskal
thuật toán prim
