Bài tập Toán rời rạc - Bài 13

Toán rời rạc phần Đếm Bài tập 13 1. Bảng chữ Hawaiian gồm 12 chữ cái. Có bao nhiêu xâu gồm sáu chữ trên bảng chữ này? 2. Trong trò chơi thể thao Korfball, mỗi đội chơi có tám người gồm bốn nam và bốn nữ. Trường Halliday High School có 7 nam và 11 nữ muốn tham gia. Có bao nhiêu cách lập đội từ 18 sinh viên này? 3. (a) Có bao nhiêu đồ thị (vô hướng) với n đỉnh? (b) Có bao nhiêu đồ thị có hướng (có thể có khuyên) với n đỉnh? (c) Có bao nhiêu đồ thị thi đấu với n đỉnh? (d) Có bao nhiêu đồ thị thi đấu không có chu trình với n đỉnh? 4. Thầy giáo muốn phát 25 cái bút chì cho An, Bình, Chi, và Dương sao cho An và Dương mỗi người có ít nhất một chiếc, Chi được không quá năm chiếc, và Bình được ít nhất bốn chiếc. Có bao nhiêu cách chia? 5. Các phương trình hoặc bất phương trình dưới đây có bao nhiêu nghiệm nguyên? (a) x1 + x2 + x3 + x4 + x5 = 63, với mọi x i > 0 (b) x1 + x2 + x3 + x4 + x5 = 63, với mọi x i ≥ 0 (c) x1 + x2 + x3 + x4 + x5 ≤ 63, với mọi x i ≥ 0 (d) x1 + x2 + x3 + x4 + x5 = 63, với mọi x i ≥ 0, x2 ≥ 10 (e) x1 + x2 + x3 + x4 + x5 = 63, với mọi x i ≥ 0, x2 ≤ 9 6. Phương trình sau có bao nhiêu nghiệm nguyên x1 + x2 + x3 + x4 = 132 thỏa mãn x1 > 0, và x2, x3, x4 ≥ 0? và có bao nhiêu nếu ta thêm ràng buộc x4 < 17? 7. Hãy đưa ra một chứng minh tổ hợp của đẳng thức sau: k  n k ‹ = n  n− 1 k− 1 ‹ . Gợi ý: Chọn một đội có một đội trưởng. 8. Hãy đưa ra một chứng minh tổ hợp của đẳng thức sau: n2n−1 = n∑ k=1 k  n k ‹ . Gợi ý: Xét tập mọi dãy độ dài n gồm một số ký hiệu 0, 1 và duy nhất một ký hiệu ∗. 9. Có bao nhiêu đường đi trên lưới nguyên từ (0,0) tới (10,12)? 10. Có bao nhiêu đường đi trên lưới nguyên từ (0,0) tới (10,12) đi qua (3,5)? 11. Có bao nhiêu đường đi trên lưới nguyên từ (0,0) tới (14,73) không đi qua (6,37)? 12. Xác định hệ số của x15 y120z25 trong đa thức (2x + 3y2 + z)100. 1 13. Xác định hệ số của x12 y24 trong đa thức (x3 + 2x y2 + y + 3)18. (Chú ý: x hoặc y có thể xuất hiện trong nhiều số hạng!) 14. Với mỗi xâu dưới đây, hãy xác định số cách sắp xếp các chữ trong đó mọi chữ đều được dùng. (a) OVERNUMEROUSNESSES (b) OPHTHALMOOTORHINOLARYNGOLOGY (c) HONORIFICABILITUDINITATIBUS 15. Có bao nhiêu cách tô lên 27 bức tượng sao cho 7 cái được vẽ màu trắng, 6 cái được vẽ màu vàng, 2 cái được vẽ màu xanh da trời, 7 cái được vẽ màu tím, 5 cái được vẽ màu xanh lá cây, và 0 cái được vẽ màu đỏ? 2