Có bao nhiêu cách xếp 10 người vào bàn tròn. biết rằng các vị trí ngồi được đánh số từ 1 đến 10?
Bài toán xếp khách của Lucas
Gọi số phải tìm là Mn. Xếp cho các bà trước(cứ xếp một ghế thì một ghế để trống dành cho các ông), số cách xếp cho các bà là 2n! cách. Gọi số cách xếp cho các ông ứng với một cách xếp các bà là Un ta được số cách xếp là: Mn= 2n! x Un. Đánh số các bà (đã xếp) từ 1đến n,đánh số các ông tương ứng với các bà (ông i là chồng bà i), sau đó đánh số các ghế trống theo nguyên tắc: ghế số i nằm giữa bà i và bà i+1 (các phép cộng được hiểu lấy modul n nghĩa là n +1 = 1). Mỗi cách xếp các ông được biểu diễn bằng một phép thế ϕ trên tập {1, 2,.., n } với qui ước ϕ(i) = j có nghĩa là ghế i được xếp cho ông j. Theo giả thiết ϕ phải thoả mãn: ϕ(i)≠i và ϕ(i) ≠ i+1 (**) Trong toán học gọi Un là số phân bố . Xét tập hợp tất cả các phép thế ϕ của { 1, 2,.., n }. Trên tập này ta gọi Pi là tính chất ϕ(i) = i, Qi là tính chất ϕ(i) = i+1. Đặt Pn+i= Qi, theo nguyên lý bù trừ tương ứng với 2n tính chất Pi ta có: [You must be registered and logged in to see this image.] Trong đó Nk là tổng số tất cả các phép thế thoả mãn k tính chất lấy từ 2n tính chất đang xét. Cần chú ý rằng, không thể xảy ra đồng thời thoả mãn Pi và Qi hoặc đồng thời thoả mãn Pi+1và Qi. Do đó trong các phép lấy ra k tính chất từ 2n tính chất đang xét cần thêm vào điều kiện: Pi và Qi hoặc Pi+1 và Qi không được đồng thời có mặt. Gọi số các cách này là g(2n, k) (nói riêng g(2n,k) = 0 khi k > n). Với mỗi cách lấy ra k tính chất như vậy (k ≤ n) ta có (n - k)! phép thế thoả mãn chúng. Từ đó ta nhận được: Nk = g(2n, k) (n-k)! và: Un = n! - g(2n, 1).(n - 1)! + g(2n, 2).(n - 2)! -...+(-1)ng(2n, n) (***) Bây giờ chúng ta phải tính các hệ số g(2n,k), k = 1, 2,.., n. Xếp 2n tính chất đang xét trên vòng tròn theo thứ tự P1, Q1, P2, Q2,.., Pn, Qn, ta thấy rằng g(2n,k) chính là số cách lấy k phần tử trong 2n phần tử xếp thành vòng tròn sao cho không có hai phần tử nào kề nhau cùng được lấy ra. Để tính g(2n,k) ta áp dụng công thức (*) của bài toán 2: [You must be registered and logged in to see this image.] Số phân bố Un lắp công thức trên vào (***) ta nhận được: [You must be registered and logged in to see this image.] Vậy đáp số cần tìm sẽ là Công thức Lucas: Mn= 2n! x Un. [You must be registered and logged in to see this image.] Áp dụng cho bài tập 8 trang 81, bài tập củ chuối nhất trong các loại bài tâp: Có 4 cặp vợ chồng khách đến dự tiệc tại một gia đình vợ chồng chủ nhà sắp chỗ ngồi quanh bàn tròn. Hãy tính số cách sắp xếp sao cho các ông ngồi xen kẽ với các bà và không có cặp vợ chồng nào ngồi cạnh nhau. Vợ chồng chủ nhà luôn ngồi cạnh nhau và chồng luôn ngồi bên phải. Giải Bỏ vợ chồng chủ nhà ra, chưa ngồi vào thì ta có 4 cặp vợ chồng ngồi quanh bàn tròn với bài toán Lucas áp dụng cho n = 4 thay vào công thức Lucas: [You must be registered and logged in to see this image.] Tính trong ngoặc cẩn thận: [You must be registered and logged in to see this image.] M4 = 190*8* 6! Kinh không? Đấy là chưa kể xếp vào với chủ nhà đấy nhé! Ta thấy 8 người trên khi xếp vào vòng tròn sẽ có 8 cái khe. Vợ chồng chủ nhà ngồi cạnh nhau có thể nhét vào 1 trong 8 cái khe đó. Vậy theo nguyên lý nhân sẽ có tới M4 * 8 cách xếp cả thảy. Đáp số quả là một số kinh khủng luôn: Số cách xếp = 190*8*6!*8 Nhân ra xem mặt mũi nó thế nào sẽ được: 12160 * 6! = 12160 * 720 = 8.755.200 cách xếp. Ngồi nhà có thời gian bấm tính từng tí một, kiểm tra đã thấy nhức đầu, nếu đề thi mà ra bài toán dạng này có lẽ thí sinh sẽ có người phát điên. Có 4 cặp vợ chồng khách đến dự tiệc tại một gia đình vợ chồng chủ nhà sắp chỗ ngồi quanh bàn tròn. Hãy tính số cách sắp xếp sao cho các ông ngồi xen kẽ với các bà và không có cặp vợ chồng nào ngồi cạnh nhau. Vợ chồng chủ nhà luôn ngồi cạnh nhau và chồng luôn ngồi bên phải. @ Đạt
Bài toán 8T81: 4 cặp vợ chồng khách và vợ chồng chủ nhà sao cho vợ chồng chủ nhà luôn ngồi cạnh nhau và ông chồng ngồi bên phải có thể giải như sau: Em không nói là kết quả sai. Mà em nói là lý luận sai bản chất. Kết quả em cũng ra là 720 cách.
|