Hoán vị – Chỉnh hợp – Tổ hợp là những khái niệm khiến các bạn dễ bị nhầm lẫn khi học môn toán rời rạc. Bài viết này, TTnguyen sẽ giúp các bạn tổng hợp định nghĩa, công thức thông qua bài tập hoán vị chỉnh hợp tổ hợp có lời giải chi tiết nhé!
Xem thêm:
- logic mệnh đề – Bài tập toán rời rạc chương 1 có lời giải
- 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 tập toán rời rạc chương 2 có lời giải
I. Tóm tắt lý thuyết
1. Hoán vị
Mỗi kết quả của sự sắp xếp thứ tự n phần tử của tập hợp A được gọi là một hoán vị của n phần tử. Hay hoán vị là cách sắp xếp có thứ tự tất cả n phần tử.
– Kí hiệu \(P_{n}\) là số các hoán vị của n phần tử.
– Công thức: \(P_{n} = n(n – 1) = n!\)
2. Chỉnh hợp
Kết quả của việc lấy k phần tử khác nhau từ n phần tử của tập hợp A và sắp xếp chúng theo một thứ tự nào đó được gọi là một chỉnh hợp chập k của n phần tử đã cho.
– Kí hiệu: \(A_{n}^{k}\) là số các chỉnh hợp chập k của n phần tử (1 ≤ k ≤ n).
– Công thức: \(A_{k}^{n} = n(n-1)…(n-k+1)=\frac{n!}{(n-k)!}\)
3. Tổ hợp
– Giả sử A có n phần tử (n ≥ 1). Mỗi tập hợp gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho. (1 ≤ k ≤ n).
– Kí hiệu \(C_{n}^{k}\) là số các tổ hợp chập k của n phần tử (0 ≤ k ≤ n).
– Định lý: \(C_{n}^{k} = \frac{n!}{k!(n-k)!}\)
>>> Xem thêm: chỉnh hợp lặp và tổ hợp lặp
II. Bài tập hoán vị chỉnh hợp tổ hợp có đáp án
1. Các dạng bài tập về hoán vị
Bài 1: Có bao nhiêu cách mà ta có thể sắp xếp tất cả 5 sinh viên đứng thành một hàng cho một bức hình.
Lời giải
Ví trí 1: có 5 cách
Ví trí 2: có 4 cách
Ví trí 3: có 3 cách
Ví trí 4: có 2 cách
Ví trí 5: có 1 cách
=> có 5!=5.4.3.2.1 = 120 cách
Bài 2: Giả sử rằng một cô gái bán hàng phải đi đến tám thành phố khác nhau. Cô phải bắt đầu hành trình từ một thành phố xác định, nhưng cô có thể đến bảy thành phố còn lại theo một thứ tự bất kỳ mà cô muốn. Có bao nhiêu khả năng lựa chọn cách đi để cô đi đến các thành phố này?
Lời giải
có 7! = 5040 cách để cô gái chọn cho hành trình của mình.
Bài 3: Có bao nhiêu hoán vị của những chữ cái ABCDEFGH chứa chuỗi ABC?
Lời giải
Số hoán vị của khối ABC và các chữ cái D, E, F, G và H.
có 6! = 720 hoán vị của các chữ cái ABCDEFGH chứa chuỗi ABC.
Bài 3: Có bao nhiêu xâu khác nhau có thể lập được từ các chữ cái trong từ
MISSISSIPI, COMPUTER yêu cầu phải dùng tất cả các chữ?
Lời giải
Từ MISSISSIPI có chứa : 1 từ M, 4 từ I, 4 từ S và 1 từ P.
Số xâu khác nhau là: \(\frac{10!}{1!.4!.4!.1!}\)
Xâu COMPUTER có 8 ký tự khác nhau, nên lập được 8! xâu.
2. Các bài tập chỉnh hợp
Bài 1: Có bao nhiêu cách mà ta có thể chọn ra 3 sinh viên từ một nhóm 5 sinh
viên để đứng thành một hàng cho một bức hình?
Lời giải
Vị trí 1: Có 5 cách.
Vị trí 2: Có 4 cách
Vị trí 3: Có 3 cách
=> có 5.4.3 = 60 cách hay \(A_{5}^{3}\)
Bài 2: Có bao nhiêu cách để chọn ra một người nhận giải nhất, một người nhận giải nhì và một người nhận giải ba từ 100 người khác nhau tham gia một cuộc thi?
Lời giải
Giải nhất: : Có 100 cách
Giải nhì : Có 99 cách
Giải ba : Có 98 cách
→ là số chỉnh hợp chập 3 của một tập có 100 phần tử: \(A_{100}^{3}\)
Bài 3: Giả sử rằng có tám người tham gia cuộc thi chạy. Người thắng sẽ nhận một huy chương vàng, người đứng vị trí thứ hai nhận một huy chương bạc, và người đứng vị trí thứ ba nhận một huy chương đồng. Có bao nhiêu cách để trao các huy chương này, biết mọi khả năng của cuộc thi đều có thể và không có sự trùng kết quả thi đấu.
Lời giải
Số cách khác nhau để trao các huy chương là: [llatex]A_{8}^{3}[/latex] = 336 cách
Bài 4: Một đội bóng đá có 20 cầu thủ. Cần chọn ra 11 cầu thủ, phân vào 11 vị trí trên sân để thi đấu chính thức. Hỏi có mấy cách chọn nếu:
a) Ai cũng có thể chơi ở bất cứ vị trí nào?
b) Chỉ có một cầu thủ được chỉ định làm thủ môn, các cầu thủ khác chơi ở vị trí nào cũng được?
c) Có 3 cầu thủ chỉ có thể làm thủ môn được, các cầu thủ khác chơi ở vị trí nào cũng được?
Lời giải
a) Chọn ra 11 cầu thủ trong 20 cầu thủ đã cho, xếp vào 11 vị trí trên sân. Số cách chọn bằng chỉnh hợp chập 11 của 20 phần tử: \(A_{20}^{11}\).
b) Một cầu thủ đã chỉ định làm thủ môn, vậy ta cần chọn ra 10 cầu thủ trong 19 cầu thủ còn lại xếp vào 10 vị trí. Số cách chọn bằng chỉnh hợp chập 10 của 19 phần tử: \(A_{19}^{10}\).
c) Có 3 cách chọn 1 cầu thủ để làm thủ môn từ 3 cầu thủ. Sau khi ta chọn thủ môn xong, kế đến chọn 10 cầu thủ trong 17 cầu thủ con lại để xếp vào 10 vị trí: \(A_{17}^{10}\).
Theo nguyên lý nhân ta có: \(3.A_{17}^{10}\)
>>>Xem thêm: hệ thức truy hồi trong toán rời rạc
3. Các bài tập tổ hợp
Bài 1: Có bao nhiêu nhóm đại diện gồm ba sinh viên khác nhau có thể được thành lập từ một nhóm bốn sinh viên?
Lời giải
Số tập con gồm ba phần tử từ tập chứa bốn phần tử. Là tổ hợp chập 3 của 4 => có 4 cách
Bài 2: Gọi S là tập {1, 2, 3, 4}. Liệt kê các tổ hợp chập 3 từ S?
Lời giải
Các tổ hợp chập 3 của S là: 4
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2,3,4}
Bài 3: Hãy liệt kê các tổ hợp chập 2 của {a, b, c, d}
Lời giải
{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, và {c, d}.
Bài 4: Có bao nhiêu cách để người chơi lấy ra 5 lá bài đã được trộn từ bộ bài 52
quân bài? Và có bao nhiêu cách để chọn 47 lá bài từ bộ bài 52 quân bài.
Lời giải
Số cách lấy ra 5 lá bài đã được trộn từ bộ bài 52 quân bài: C(52,5)
Số cách để chọn 47 lá bài từ bộ bài 52 quân C(52,47)
Bài 5: Có bao nhiêu chuỗi bit độ dài n chứa đúng r bit 1?
Lời giải
Các vị trí của r bit 1 trong một chuỗi bit có độ dài n tạo thành một tổ hợp chập r của tập {1, 2, ., n}.
→ Số chuỗi bit có độ dài n chứa đúng r bit 1 là: C(n,r).
Bài 6: Giả sử rằng có 9 giảng viên thuộc bộ môn Toán và 11 giảng viên thuộc bộ môn Khoa học máy tính. Hỏi có thể có bao nhiêu cách lựa chọn một nhóm để giảng dạy môn học Toán rời rạc trong trường nếu nhóm bao gồm ba giảng viên Toán và bốn giảng viên Khoa học máy tính?
Lời giải
1. Chọn 3 giảng viên Toán.
2. Chọn 4 giảng viên Khoa học máy.
→ Số cách lựa chọn nhóm là C(9,3) * C(11,4) = 27,720.
Trên đây là một số bài tập về hoán vị chỉnh hợp tổ hợp có lời giải. Cảm ơn các bạn đã tham khảo trên ttnguyen.net
