Với bài toán này có thể liệt kê tất cả các trường hợp, nhưng với những bài toán tương tự như thế nhưng số lương rất nhiều chúng ta sẽ gặp nhiều khó khăn trong việc liệt kê. 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 nhau 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:
- logic mệnh đề – Bài tập toán rời rạc chương 1 có lời giải
- bài tập toán rời rạc chương 2 có lời giải
- bài tập hoán vị chỉnh hợp tổ hợp có lời giải
I. Chỉnh hợp lặp
Định nghĩa
Một dãy bao gồm k phần tử của 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 gọi là một chỉnh hợp lặp chập k của n phần tử.
Công thức chỉnh hợp lặp chập k của n phần tử
\(F_{n}^{k} = n^{k}\)II. Tổ hợp lặp toán rời rạc
Tổ hợp lặp là gì?
Một dãy bao gồm k phần tử (k có thể lớn hơn n) của tập A, trong đó mỗi phần tử có thể được lặp lại nhiều lần (không tính đến thứ tự sắp xếp của chúng) được gọi là một tổ hợp lặp chập k của n phần tử.
Công thức tổ hợp lặp
\(K_{n}^{k} = C_{n+k-1}^{k} = C_{n+k-1}^{n-1}\)III. Bài tập chỉnh hợp lặp có lời giải
Bài 1: 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.
IV. Bài tập tổ hợp lặp có lời giải
Bài 1: 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 |
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
Liên quan: hệ thức truy hồi trong toán rời rạc
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.
