Chuyên đề Tổ hợp 3

Chuyên đề: Đại số tổ hợp
Dạng 3
Một số bài toán về sắp thứ tự các phần tử của một tập hợp
Nội dung
Nội dung
Dạng 3. Một số bài toán về sắp thứ tự các phần tử của một tập hợp
Dạng 3A. Sắp xếp các phần tử thành một dãy
Dạng 3B. Sắp xếp các phần tử thành một dãy có điều kiện
Dạng 3C. Sắp xếp các phần tử thành một vòng tròn
Dạng 3A
Sắp xếp các phần tử thành một dãy
Bài tập mẫu
Bài 1. Có 3 viên bi trắng khác nhau, 4 bi xanh giống nhau và 5 bi đỏ giống nhau. Có bao nhiêu cách xếp chúng thành một hàng ngang?
Giải
Cách 1. Có tất cả 12 viên bi, tương ứng với 12 vị trí theo một hàng ngang. Số cách chọn 3 trong 12 vị trí cho 3 viên bi trắng khác nhau là sau đó số cách chọn 4 trong 9 vị trí còn lại cho 4 viên bi xanh giống nhau là khi đó năm vị trí còn lại của 5 viên bi đỏ.
Theo quy tắc nhân, ta được số khả năng cần tìm là:
Dạng 3A: Sắp xếp các phần tử thành một dãy
Bài tập mẫu (tt)
Cách 2. Số cách chọn 4 trong 12 vị trí cho 4 viên bi xanh giống nhau
Là sau đó số cách chọn 5 trong 8 vị trí còn lại cho 5 viên bi đỏ giống nhau là tiếp theo số hoán vị của 3 viên bi trắng khác nhau vào 3 vị trí còn lại là P3 = 3!.
Theo quy tắc nhân, số khả năng cần tìm là:
Cách 3. Với 12 viên bi đã cho tạo thành 12! hoán vị để xếp thành hàng ngang. Nhưng các hoán vị 4 viên bi xanh giống nhau cho cùng một kết quả; các hoán vị 5 viên bi đỏ giống nhau cho cùng một kết quả nên số cách xếp phải tìm là
Dạng 3A: Sắp xếp các phần tử thành một dãy
Lưu ý
Lưu ý 1.
Số cách chọn k trong n vị trí cho k phần tử giống nhau là
Số cách chọn k trong n vị trí cho k phần tử khác nhau là
Lưu ý 2.
Giả sử cho n phần tử trong đó có n1 phần tử giống nhau thuộc tập hợp A1, n2 phần tử giông nhau thuộc tập hợp A2, … Số cách xếp n phần tử đó thành một hàng ngang là
Dạng 3A: Sắp xếp các phần tử thành một dãy
Bài tập tương tự
Có 2 viên bi trắng khác nhau, 3 bi xanh khác nhau 4 bi đỏ giống nhau và 5 bi vàng giống nhau. Có bao nhiêu cách xếp chúng theo một hàng ngang?
Giải
Cách 1. Có tất cả 14 viên bi, tương ứng với 14 vị trí theo một hàng ngang. Số cách chọn 2 trong 14 vị trí cho 2 viên bi trắng khác nhau là sau đó số cách chọn 3 trong 12 vị trí còn lại cho 3 viên bi xanh khác nhau là ; tiếp theo số cách chọn 4 trong 9 vị trí còn lại cho 4 viên bi đỏ giống nhau là ; khi đó năm vị trí còn lại của 5 viên bi vàng.
Theo quy tắc nhân, số khả năng cần tìm là:
Cách 2. Cũng lý luận như cách 3 của bài trên, ta được kết quả là
Dạng 3A: Sắp xếp các phần tử thành một dãy
Dạng 3B
Sắp xếp các phần tử thành một dãy có điều kiện
Bài tập mẫu
Có 5 học sinh nam và 4 học sinh nữ. Có bao nhiêu cách sắp số học trên thành một hàng ngang sao cho không có hai học sinh nữ nào cạnh nhau?
Giải
Giả sử đã xếp 5 học sinh nam thành một hàng ngang, khi đó vì 4 học sinh nữ không cạnh nhau nên họ được chọn 4 trong 6 vị trí xen kẽ với 5 học sinh nam (xem hình minh hoạ dưới đây).
. o . o . o . o . o .
Số cách chọn 4 trong 6 vị trí cho học sinh nữ là ; số hoán vị của 5 học sinh nam vào 5 vị trí định trước là 5!.
Theo quy tắc nhân, ta được số cách xếp phải tìm là:
Đáp số: có 43200 cách xếp.
Dạng 3B: Sắp xếp các phần tử thành một dãy có điều kiện
Lưu ý
Cho tập hợp A có n phần tử, tập hợp B có m phần tử. Tính số cách sắp xếp các phần tử của A, B thành một hàng ngang sao cho không có hai phần tử nào của B cạnh nhau.
Cách giải
Giả sử n phần tử của A đã xếp thành một hàng ngang, khi đó các phần tử của B được chọn m trong (n+1) vị trí xen kẽ giữa các phần tử của A.
Nếu các PT của B giống nhau thì số cách chọn vị trí là
Nếu các PT của B khác nhau thì số cách chọn vị trí là
Nếu các PT của A khác nhau thì số cách xếp chúng vào n vị trí là n!
Theo quy tắc nhân, ta tính được kết quả của bài toán.

Dạng 3B: Sắp xếp các phần tử thành một dãy có điều kiện
Bài tập tương tự
Có 3 viên bi trắng khác nhau, 4 bi xanh giống nhau và 5 bi đỏ giống nhau. Có bao nhiêu cách xếp chúng thành một hàng ngang sao cho không có hai viên bi trắng nào cạnh nhau?
Giải
Giả sử đã xếp 4 bi xanh và 5 viên bi đỏ thành một hàng ngang, khi đó vì 3 viên bi trắng được chọn 3 trong 10 vị trí xen kẽ với 9 viên bi xanh, đỏ (xem hình minh hoạ dưới đây):
. o . o . o . o . o . o . o . o . o .
Số cách chọn 3 trong 10 vị trí cho 3 viên bi trắng khác nhau là ; số cách đặt 4 bi xanh giống nhau vào 9 vị trí định trước là ; 5 vị trí còn lại của 5 viên bi đỏ giống nhau.
Theo quy tắc nhân, ta được số cách xếp phải tìm là
Đáp số: có 90720 cách xếp.
Dạng 3B: Sắp xếp các phần tử thành một dãy có điều kiện
Dạng 3C
Sắp xếp các phần tử thành một vòng tròn
Bài tập mẫu
Có 5 học sinh nam và 3 học sinh nữ. Có bao nhiêu cách sắp số học trên thành một vòng tròn sao cho không có hai học sinh nữ nào cạnh nhau (hai cách xếp khác nhau nhưng có cùng một thứ tự của các phần tử được coi là một)?
Giải
Giả sử 5 học sinh nam đã xếp thành vòng tròn, khi đó 3 học sinh nữ được chọn 3 trong 5 vị trí xen kẽ giữa các học sinh nam, số cách chọn là . Mặt khác trong 5 học sinh nam ta có thể chọn trước một vị trí cho một người, số hoán vị của 4 nam còn lại vào 4 vị trí là 4!.
Theo quy tắc nhân, ta được số cách xếp phải tìm là
Cách 2. Giả sử ta đã chọn vị trí cho một học sinh nữ và năm học sinh nam đã xếp quanh vòng tròn. Hai học sinh nữ còn lại được 2 trong 4 vị trí xen kẽ giữa các học sinh nam, số cách chọn là
Mặt khác số hoán vị của 5 nam vào 5 vị trí là 5!.
Theo quy tắc nhân, ta được số cách xếp phải tìm là
Dạng 3C: Sắp xếp các phần tử thành một vòng tròn
Lưu ý
Khi xếp các phần tử xung quanh một vòng tròn, hai cách xếp khác nhau nhưng có cùng một thứ tự của các phần tử được coi là một.

Cách giải. Ta có thể chọn vị trí cho một phần tử định trước nào đó, sau đó tính số khả năng chọn vị trí cho các phần tử còn lại.
Hoặc có thể coi các phần tử đã cho được xếp thành một hàng ngang với một phần tử chọn trước đứng ở đầu hàng.


Dạng 3C: Sắp xếp các phần tử thành một vòng tròn
Bài tập tương tự
Có 4 viên bi trắng khác nhau, 5 bi xanh giống nhau. Có bao nhiêu cách xếp chúng thành một vòng tròn sao cho không có hai viên bi trắng nào cạnh nhau?
Giải
Giả sử ta đã chọn vị trí cho một viên bi trắng và 5 bi xanh đã được xếp quanh vòng tròn. Ba bi trắng còn lại được chọn 3 trong 4 vị trí xen kẽ giữa các bi xanh, số cách chọn là
Ta được số cách xếp phải tìm là
Dạng 3C: Sắp xếp các phần tử thành một vòng tròn