tailieunhanh - GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG II BÀI TOÁN ĐẾM_3

. Sự phân bố các đồ vật vào trong hộp. Thí dụ 10: Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong 4 người chơi từ một cỗ bài chuẩn 52 quân? | CHƯƠNG II BÀI TOÁN ĐẾM . Sự phân bố các đồ vật vào trong hộp. Thí dụ 10 Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong 4 người chơi từ một cỗ bài chuẩn 52 quân Người đầu tiên có thể nhận được 5 quân bài bằng cị2 cách. Người thứ hai có thể được chia 5 quân bài bằng c57 cách vì chỉ còn 47 quân bài. Người thứ ba có thể nhận được 5 quân bài bằng cách. Cuối cùng người thứ tư nhận được 5 quân bài bằng c357 cách. Vì vậy theo nguyên lý nhân tổng cộng có r-5 c5 c5 r5 52_ C52. C47. C42. C37 5 .5 .5 .5 .32 cách chia cho 4 người mỗi người một xấp 5 quân bài. Thí dụ trên là một bài toán điển hình về việc phân bố các đồ vật khác nhau vào các hộp khác nhau. Các đồ vật là 52 quân bài còn 4 hộp là 4 người chơi và số còn lại để trên bàn. Số cách sắp xếp các đồ vật vào trong hộp được cho bởi mệnh đề sau Mệnh đề 3 Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau sao cho có ni vật được đặt vào trong hộp thứ i với i 1 2 . k bằng n nỉ .n2 .nk . n - nx -. - nk . SINH CÁC HOÁN VỊ VÀ TỔ HỢP. . Sinh các hoán vị Có nhiều thuật toán đã được phát triển để sinh ra n hoán vị của tập 1 2 . n . Ta sẽ mô tả một trong các phương pháp đó phương pháp liệt kê các hoán vị của tập 1 2 . n theo thứ tự từ điển. Khi đó hoán vị được gọi là đi trước hoán vị nếu tồn tại k 1 k n a1 b1 a2 b2 . ak-1 bk-1 và ak bk. Thuật toán sinh các hoán vị của tập 1 2 . n dựa trên thủ tục xây dựng hoán vị kế tiếp theo thứ tự từ điển từ hoán vị cho trước a1 a2 .an. Đầu tiên nếu an-1 an thì rõ ràng đổi chỗ an-1 và an cho nhau thì sẽ nhận được hoán vị mới đi liền sau hoán vị đã cho. Nếu tồn tại các số nguyên aj và aj 1 sao cho aj aj 1 và aj 1 aj 2 . an tức là tìm cặp số nguyên liền kề đầu tiên tính từ bên phải sang bên trái của hoán vị mà số đầu nhỏ hơn số sau. Sau đó để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất trong các số lớn hơn aj của tập aj 1 aj 2 . an rồi liệt kê theo thứ tự tăng dần của các số còn lại của aj aj 1 aj 2 . an .