Đại số tổ hợp - Chương II: Hoán vị

Bài 23. Tên 12 tháng trong năm được liệt kê theo thứ tự tuỳ ý sao cho tháng 5 và tháng

6 không đứng kế nhau. Hỏi có mấy cách ?

Giải

Tên 12 tháng trong năm được liệt kê tùy ý, có : 12! cách.

Nếu tháng 5 và tháng 6 đứng kế nhau, ta xem tháng 5 và tháng 6 là một phần

tử, ta có hoán vị của 11 phần tử, có 11! cách. Ngoài ra, trong mỗi cách này, thứ

tự của tháng 5 và tháng 6 có thể đổi cho nhau, nên có : 2 × 11! cách.

Vậy số cách để hai tháng 5 và tháng 6 không đứng kế nhau là :

12! – 2.11! = 10.11! cách.

 

pdf9 trang | Chia sẻ: tuanbinh | Ngày: 15/08/2018 | Lượt xem: 56 | Lượt tải: 0download
Bạn đang xem nội dung Đại số tổ hợp - Chương II: Hoán vị, để tải tài liệu về máy bạn hãy click vào nút TẢI VỀ
ĐẠI SỐ TỔ HỢP 
 Chương II 
HOÁN VỊ 
1. Giai thừa 
Với số nguyên dương n, ta định nghĩa n giai thừa, kí hiệu n!, là tích các số 
nguyên liên tiếp từ 1 đến n. 
 n! = 1.2.3(n – 2) (n – 1)n. 
Vì tiện lợi, người ta qui ước : 
 0! = 1. 
Từ định nghĩa, ta có : 
 n(n – 1)  (n – r + 1) = n!
(n r)!− và (n – 1)!n = n! 
Ví dụ : a) 5! = 1.2.3.4.5 = 120; 
 b) 9!
5!
 = 9.8.7.6 = 3024; 
 c) 3!4 = 4! = 1.2.3.4 = 24; 
 d) (n 2)!
(n 3)!
+
− = (n + 2)(n + 1)n(n – 1)(n – 2). 
2. Hoán vị 
Có n vật khác nhau, sắp vào n chỗ khác nhau. Mỗi cách sắp được gọi là 1 hoán 
vị của n phần tử. 
Theo qui tắc nhân, chỗ thứ nhất có n cách sắp (do có n vật), chỗ thứ nhì có n 
– 1 cách sắp (do còn n – 1 vật), chỗ thứ ba có n – 2 cách sắp (do còn n – 2 vật), 
, chỗ thứ n có 1 cách sắp (do còn 1 vật). 
Vậy, số hoán vị của n phần tử, kí hiệu Pn, là : 
 Pn = n(n – 1)(n – 2) × 1 = n! 
Ví dụ 1. Từ 3 chữ số 1, 2, 3 có thể tạo được bao nhiêu số gồm 3 chữ số khác 
nhau ? 
Giải 
Mỗi số gồm 3 chữ số khác nhau tạo ra từ 1, 2, 3 là một hoán vị của 3 phần tử. 
Vậy có : P3 = 3! = 6 số. 
(các số đó là : 123, 132, 213, 231, 312, 321) 
Ví dụ 2. Trong một lớp học, thầy giáo phát phiếu thăm dò yêu cầu học sinh ghi 
thứ tự 3 môn Toán, Lý, Hóa đang học theo mức độ yêu thích giảm dần. Hỏi có 
bao nhiêu cách ghi khác nhau ? 
Giải 
Đây là hoán vị của 3 phần tử. Vậy có: P3 = 3! = 6 cách, khi đó có 6 cách ghi là: 
 (T,L,H), (T,H,L), (L,T,H), (L,H,T), (H,T,L), (H,L,T). 
Ví dụ 3. Có 2 sách toán khác nhau, 3 sách lý khác nhau và 4 sách hóa khác 
nhau. Cần sắp xếp các sách thành một hàng sao cho các sách cùng môn đứng 
kế nhau. Hỏi có bao nhiêu cách sắp ? 
Giải 
Trước tiên, ta sắp theo môn thì có P3 = 3! = 6 cách. 
Tiếp đến, các sách từng môn đổi chỗ cho nhau, toán có P2 = 2! = 2 cách, lý có 
P3 = 3! = 6 cách, hóa có P4 = 4! = 24 cách. Vậy, theo qui tắc nhân, có : 
 6 × 2 × 6 × 24 = 1728 cách. 
Bài 18. Giải phương trình : x! (x 1)!
(x 1)!
− −
+ = 
1
6
 với x ∈ ¥ * 
Giải 
 x! (x 1)!
(x 1)!
− −
+ = 
1
6
 6[x! – (x – 1)!] = (x + 1)! ⇔
 6[x(x – 1)! – (x – 1)!] = (x + 1)! ⇔
 6(x – 1)!(x – 1) = (x + 1)x(x – 1)! ⇔
 6(x – 1) = x(x + 1) ⇔
 x2 – 5x + 6 = 0 ⇔ ⇔ x 2
x 3
=⎡⎢ =⎣ 
 Nhận do x ∈ ¥ *. 
Bài 19. Giải bất phương trình : n 4
n n 2
P
P .P
+
+
 < 
n 1
15
P −
 (*) 
 Điều kiện n > 1, n ∈ . ¥
 Ta có : (*) ⇔ (n 4)!
n!(n 2)!
+
+ < 
15
(n 1)!− 
 ⇔ (n 4)(n 3)(n 2)!
n(n 1)!(n 2)!
+ + +
− + < 
15
(n 1)!− 
 ⇔ (n 4)(n 3)
n
+ + < 15 
 n2 + 7n + 12 < 15n ⇔
 n2 – 8n + 12 < 0 ⇔ ⇔ 2 < n < 6 
 Do điều kiện nên n ∈ { }3, 4, 5 . 
Bài 20. Gọi Pn là số hoán vị của n phần tử. Chứng minh : 
a) Pn – Pn-1 = (n – 1)Pn-1 
b) 1 + P1 + 2P2 + 3P3 +  + (n – 1)Pn-1 = Pn. 
Giải 
a) Ta có Pn – Pn-1 = n! – (n – 1)! 
 = n(n – 1)! – (n – 1)!. 
 = (n – 1)(n – 1)! 
 = (n – 1)Pn-1. 
b) Từ kết quả trên, ta có : 
2 1 1
3 2 2
4 3 3
n n 1 n
P P (2 1)P
P P (3 1)P
P P (4 1)P
: : : :
: : : :
P P (n 1)P− −
− = −⎧⎪ − = −⎪⎪ − = −⎪+⎨⎪⎪⎪ − = −⎪⎩ 1
 Vậy : Pn – P1 = P1 + 2P2 + 3P3 +  + (n – 1)Pn-1 
 Pn = 1 + P1 + 2P2 +  + (n – 1)Pn-1. ⇔
Bài 21. Chứng minh với mọi n∈ : n! ¥ ≤
nn 1
2
+⎛ ⎞⎜ ⎟⎝ ⎠ . 
Giải 
 Theo bất đẳng thức Cauchy 
 1 + 2 + 3 +  + n ≥ n n 1 2 ... n× × × 
 mà 1, 2, , n tạo một cấp số cộng nên 
 1 + 2 + 3 +  + n = n(n 1)
2
+ . 
 Do đó : n(n 1)
2
+ ≥ n n n! ⇔ n 1
2
+ ≥ n n! ⇔ 
nn 1
2
+⎛ ⎞⎟ ≥⎜⎝ ⎠ n!. 
Bài 22. Một tạp chí thể thao định cho ra 22 kì báo chuyên đề về 22 đội bóng, mỗi kì 
một đội. Hỏi có bao nhiêu cách sao cho : 
a) Kì báo đầu tiên nói về đội bóng A ? 
b) Hai kì báo liên tiếp nói về hai đội bóng A và B ? 
Giải 
a) Còn lại 21 kì báo cho 21 đội bóng. Đây là hoán vị của 21 phần tử. 
 Vậy có : 21! cách. 
b) Xem hai đội A và B là một phần tử. Ta có hoán vị của 21 phần tử, có 21! cách. 
Ngoài ra, trong mỗi cách trên, có thể đổi thứ tự của A và B, có 2 cách. 
 Vậy, có : 2 × 21! cách. 
Bài 23. Tên 12 tháng trong năm được liệt kê theo thứ tự tuỳ ý sao cho tháng 5 và tháng 
6 không đứng kế nhau. Hỏi có mấy cách ? 
Giải 
 Tên 12 tháng trong năm được liệt kê tùy ý, có : 12! cách. 
 Nếu tháng 5 và tháng 6 đứng kế nhau, ta xem tháng 5 và tháng 6 là một phần 
tử, ta có hoán vị của 11 phần tử, có 11! cách. Ngoài ra, trong mỗi cách này, thứ 
tự của tháng 5 và tháng 6 có thể đổi cho nhau, nên có : 2 × 11! cách. 
 Vậy số cách để hai tháng 5 và tháng 6 không đứng kế nhau là : 
 12! – 2.11! = 10.11! cách. 
Bài 24. Người ta cần soạn một đề thi trắc nghiệm gồm 50 câu hỏi, chia thành 5 chủ đề, 
mỗi chủ đề gồm 10 câu. Cần sắp thứ tự 50 câu hỏi sao cho các câu cùng một 
chủ đề đứng gần nhau, chủ đề 1 đứng đầu và chủ đề 2, 3 không đứng kế nhau. 
 Hỏi có bao nhiêu cách sắp ? 
Giải 
 Chủ đề 2, 3 đứng tùy ý : Trước tiên, sắp theo chủ đề, đây là hoán vị của bốn 
chủ đề 2, 3, 4, 5, có 4! cách. Tiếp đến, sắp các câu trong từng chủ đề, mỗi chủ 
đề có 10! cách. 
 Vậy có : 4!5.10! cách = 120.10! cách. 
 Chủ đề 2, 3 đứng kế nhau : xem chủ đề 2 và 3 là một phần tử, ta có hoán vị của 
3 phần tử (2, 3), 4, 5 hay (3, 2), 4, 5, có : 2.3! cách. Tiếp đến, sắp các câu trong 
từng chủ đề, có : 5.10! cách. Nên có : 60.10! cách. 
 Vậy số cách sắp theo yêu cầu là : 
 120.10! – 60.10! = 60.10! = 217728000 cách. 
Bài 25. Một công ty cần thực hiện một cuộc điều tra thăm dò thị hiếu người tiêu dùng 
về sản phẩm của mình. Công ty đưa ra 10 tính chất của sản phẩm và yêu cầu 
khách hàng sắp thứ tự theo mức độ quan trọng giảm dần. Giả sử tính chất 1 và 
tính chất 10 đã được xếp hạng. 
 Hỏi có mấy cách xếp ? 
Giải 
 Còn lại 8 tính chất cần xếp hạng. Đây là hoán vị của 8 phần tử. 
 Vậy, có : 8! = 40320 cách. 
Bài 26. Có 5 bi đỏ và 5 bi trắng có kích thước khác nhau đôi một bao nhiêu cách sắp 
các bi này thành 1 hàng dài sao cho hai bi cùng màu không được nằm kề nhau. 
Giải 
 Xét một hộc đựng bi có 10 ô trống, mỗi ô được đánh số theo thứ tự từ 1 đến 10. 
• Lấy 5 bi đỏ bỏ vào vị trí ô mang số chẵn 2, 4, 6, 8, 10 ta có 5! cách. Sau đó lấy 
5 bi trắng bỏ vào 5 ô còn lại ta cũng có 5! cách. 
Vậy trường hợp này ta có 5! × 5! cách. 
• Lập luận tương tự lấy 5 bi đỏ bỏ vào các ô mang số lẻ; lấy 5 bi trắng bỏ vào ô 
số chẵn ta cũng có 5! × 5! cách. 
• Do đó số cách thỏa yêu cầu bài toán là : 
2(5!)2 = 2(120)2 = 28 800 cách. 
Bài 27. Có bao nhiêu cách xếp 5 học sinh A, B, C, D, E vào 1 ghế dài sao cho : 
 a) C ngồi chính giữa b) A, E ngồi hai đầu ghế. 
Đại học Hàng hải 1999 
Giải 
a) Số cách xếp 4 học sinh A, B, D, E vào 4 ghế là : 4! = 24. 
b) Số cách xếp A, E ngồi hai đầu ghế là : 2! 
 Số cách xếp 3 học sinh còn lại : 3! 
 Vậy số cách xếp thỏa yêu cầu bài toán : 2! × 3! = 2 × 6 = 12. 
Bài 28. Trong một phòng có 2 bàn dài, mỗi bàn có 5 ghế. Người ta muốn xếp chỗ ngồi 
cho 10 học sinh gồm 5 nam và 5 nữ. Hỏi có bao nhiêu cách xếp chỗ ngồi nếu 
a) Các học sinh ngồi tùy ý. 
b) Các học sinh nam ngồi 1 bàn, học sinh nữ ngồi 1 bàn. 
Đại học Cần Thơ 1999 
Giải 
a) Số cách xếp 10 học sinh ngồi tùy ý là : 10! = 3628800. 
b) Số cách xếp nam sinh ngồi 1 bàn : 5! 
 Số cách nữ sinh ngồi 1 bàn : 5! 
 Số cách xếp 2 bàn : 2! 
 Số cách xếp thỏa yêu cầu bài toán : 2! × 5! × 5! = 28800. 
Bài 29. Một học sinh có 12 cuốn sách đôi một khác nhau trong đó có 4 sách Văn, 2 
sách Toán, 6 sách Anh văn. Hỏi có bao nhiêu cách sắp các cuốn sách lên 1 kệ 
dài nếu các cuốn cùng môn sắp kề nhau. 
Đại học Quốc gia TP. HCM khối D 1999 
Giải 
 Số cách sắp 4 sách Văn kề nhau : 4! 
 Số cách sắp 2 sách Toán kề nhau : 2! 
 Số cách sắp 6 sách Anh kề nhau : 6! 
 Số cách sắp 3 loại sách Văn, Toán, Anh lên kệ : 3! 
 Số cách sắp thỏa yêu cầu bài toán : 4! × 2! × 6! × 3! = 207360. 
Bài 30. Từ X = { }1, 2, 3, 4, 5, 6 thiết lập các số có 6 chữ số khác nhau. Hỏi trong 
các số lập được có bao nhiêu số mà hai chữ số 1 và 6 không đứng cạnh nhau. 
Đại học Ngoại thương khối A 2001 
Giải 
 Gọi n = 1 6a ...a . 
 Số các số có 6 chữ số được lập từ X : 6! 
 Đặt a = 16 . Số các số tạo nên bởi hoán vị a và 2, 3, 4, 5 là 5! 
 Đặt b = 61 . Số các số tạo nên bởi hoán vị b và 2, 3, 4, 5 là 5! 
 Số cách xếp thỏa yêu cầu bài toán : 6! – 2 × 5! = 480. 
Bài 31. Xét các số gồm 9 chữ số trong đó có 5 số 1 và 4 chữ số còn lại là 2, 3, 4, 5. Hỏi 
có bao nhiêu số mà 
a) Năm chữ số 1 sắp kề nhau. b) Các chữ số được xếp tùy ý. 
Học viện Ngân hàng khối D 1999 
Giải 
a) Đặt a = 11111 
 Để sắp số a và 2, 3, 4, 5 có 5! = 120 cách. 
b) Số các số có 9 chữ số được lấy từ 9 số trên : 9! 
 Do 5 chữ số 1 như nhau nên số lần sắp trùng lặp lại là 5! 
 Số cách xếp thỏa yêu cầu bài toán : 9!
5!
 = 9 8 7 6 5!
5!
× × × × = 3024. 
Bài 32. Có bao nhiêu số gồm 7 chữ số đôi một khác nhau được lập từ 7 chữ số 1, 2, 3, 
4, 5, 7, 9 sao cho hai chữ số chẵn không nằm liền nhau. 
Cao đẳng Kinh tế Đối ngoại 2000 
Giải 
 Số các số có 7 chữ số khác nhau được lập từ 7 chữ số trên là P7 = 7! 
 Trong các chữ số 1, 2, 3, 4, 5, 7, 9 chỉ có hai chữ số chẵn là 2 và 4. 
 Gọi a = 24 . 
 Số hoán vị của a và 1, 3, 5, 7, 9 là 6! 
 Gọi b = 42 . 
 Số hoán vị của b và 1, 3, 5, 7, 9 là 6! 
 Số cách xếp thỏa yêu cầu bài toán : 7! – 2(6!) = 3600 số. 
Bài 33. Có bao nhiêu số tự nhiên gồm 5 chữ số đều lớn hơn 4 và đôi một khác nhau. 
Tính tổng các số trên. 
Đại học Huế khối D 1997 
Giải 
 Gọi n = 1 2 3 4 5a a a a a và X = { }5, 6, 7, 8, 9 
 Số các số n chọn từ X là 5! = 120. 
 Xét các chữ số hàng đơn vị. 
 Do số lần xuất hiện của 5 loại chữ số bằng nhau nên mỗi chữ số xuất hiện 120
5
= 24 lần. 
 Vậy tổng các chữ số hàng đơn vị là : 
 24(5 + 6 + 7 + 8 + 9) = 24 × 35 = 840 
 Tương tự, tổng các chữ số hàng chục là 840 × 10 
 tổng các chữ số hàng trăm là 840 × 102 
 tổng các chữ số hàng nghìn là 840 × 103 
 tổng các chữ số hàng vạn là 840 × 104. 
 Do đó S = 840 + 840 × 10 + 840 × 102 + 840 × 103 + 840 × 104 
 S = 840 (1 + 10 + 100 + 1000 + 10000) 
 S = 840 (11111) = 9333240. 
 Chú ý : Ta có thể tính S qua công thức tổng n số hạng của cấp số cộng. 
 S = 1
2
(nmax + nmin) × 120 
 = 1
2
(98 765 + 56 789) × 120 = 9333240. 
Bài 34. Trong các chữ số 0, 1, 2, 3, 4 có thể lập được bao nhiêu số có 7 chữ số trong đó 
chữ số 4 có mặt đúng 3 lần còn các chữ số khác có mặt đúng 1 lần. 
Đại học An ninh khối D 2001 
Giải 
 Cách 1 : Gọi n = 1 2 7a a ...a 
 Số các số n bất kì (a1 có thể là 0) mà 4 có mặt đúng 3 lần và các chữ số khác 
đúng 1 lần : 7!
3!
. 
 Số các số n mà a1 = 0; 4 có mặt đúng 3 lần và các chữ số 1, 2, 3, có mặt đúng 1 
lần : 6!
3!
. 
 Số các số thỏa yêu cầu bài toán : 
 7!
3!
 – 6!
3!
 = 7 × 6 × 5 × 4 – 6 × 5 × 4 = 720. 
 Cách 2 : Xét hộc có 7 ô trống. 
 Lấy số 0 bỏ vào hộc có 6 cách 
 Lấy số 1 bỏ vào hộc có 6 cách 
 Lấy số 2 bỏ vào hộc có 5 cách 
 Lấy số 3 bỏ vào hộc có 4 cách 
 Lấy 3 số 4 bỏ vào hộc có 1 cách. 
 Lấy các số thỏa yêu cầu bài toán : 6 × 6 × 5 × 4 = 720. 
(còn tiếp) 
PHẠM HỒNG DANH - NGUYỄN VĂN NHÂN - TRẦN MINH QUANG 
(Trung tâm Bồi dưỡng văn hóa và luyện thi đại học Vĩnh Viễn) 

File đính kèm:

  • pdfToan-daisotohop-chuong2.pdf