Chương 1. Phương pháp đếm Số các phân hoạch của n bao gồm các phân hoạch chứa ít nhất một phần bằng 1 và các phân hoạch mỗi phần ít nhất bằng 2, tức là p(n) = p(n − 1) + q(n) ⇔ q(n) = p(n) − p(n − 1). Để tiện so sánh đối chiếu giữa các công thức đếm ta có bảng các công thức đếm dưới đây Tên Tham số của bài toán Công thức Hoán vị n phần tử phân biệt p(n) = n! n! Hoán vị lặp n phần tử, có ai đối tượng loại i, a1 !.ak ! 1, k n! Chỉnh hợp k phần tử phân biệt của n phần Akn = (n − k)! tử Chỉnh hợp lặp k phần tử của n phần tử, các nk phần tử có thể có mặt nhiều lần n! Tổ hợp tập con có k phần tử của tập n Cnk = k! (n − k)! phần tử k−1 Phân hoạch yếu số nguyên n đối tượng giống nhau, k hộp Cn+k−1 dương thành k phần khác nhau k−1 Phân hoạch số nguyên n đối tượng giống nhau, k hộp Cn−1 dương thành k phần, mỗi khác nhau phần ít nhất 1 n đối tượng khác nhau, một số 2n−1 hộp khác nhau Phân hoạch tập hợp n đối tượng khác nhau, k hộp S(n, k) giống nhau n P n đối tượng khác nhau, số hộp B(n) = S (n, k) giống nhau tùy ý k=0 Phân hoạch số nguyên n đối tượng giống nhau, k hộp pk (n) giống nhau n P n đối tượng giống nhau, một số p(n) = pk (n) hộp giống nhau k=1 Các hàm toán học n đối tượng khác nhau, k hộp k!S(n, k) khác nhau n P n đối tượng khác nhau, số hộp S (n, i)i! tùy ý, khác nhau i=1 Bảng 1.1: Bảng công thức đếm.3 Công thức Sieve Công thức Sieve là công thức quen thuộc khi học sinh học về các phép toán tập hợp. Trong phần này ta xem xét công thức tổng quát và một vài áp dụng công 18 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 1.
Phương pháp đếm thức để chứng minh công thức tính S(n,k) và số xáo trộn của tập hợp. Trong một lớp có 14 học sinh thích văn, 17 học sinh thích toán, 18 học sinh thích hóa, 4 học sinh thích văn và hóa, 3 học sinh thích văn và toán, 5 học sinh thích toán và hóa, 1 học sinh thích cả ba môn. Hỏi có bao nhiêu học sinh thích ít nhất một môn? Lời giải. Ta có thể dùng sơ đồ Ven biểu diễn tập hợp.
Số học sinh thích ít nhất một môn là 14 + 17 + 18 − 3 − 4 − 5 + 1 = 38 (học sinh). Trong trường hợp tồng quát công thức Sieve được phát biểu và chứng minh như sau Định lý 1., An là các tập con của tập A hữu hạn. ∪ An | = (−1)j Ai1 ∩ Ai2 ∩ .<ij Với n = 2 ta có |A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 | Với n = 3 ta có |A1 ∪ A2 ∪ A3 | = |A1 | + |A2 | + |A3 | − |A1 ∩ A2 | − |A2 ∩ A3 | − |A1 ∩ A3 | + |A1 ∩ A2 ∩ A3 | 19 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 1. Phương pháp đếm Chứng minh.
Mỗi một phần tử không thuộc |A1 ∪ A2 ∪. ∪ An | cũng không thuộc bất kỳ tập nào trong vế phải của (1. Ta cần chứng minh mỗi phần tử x thuộc A1 ∪ A2 ∪. ∪ An được đếm đúng một lần bên vế phải của (1.
∪ An nên tồn tại Ai1 , Ai3 ,. Khi đó số lần x được đếm bên vế phải của (1.10) là t − Ct2 + Ct3 + .Ctt = Ct1 − Ct2 +. Tìm các hoán vị của A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Trong đó a) Không chứa các "khối" 23; 45; 678.
b) Không chứa các "khối" 34; 45; 738. Gọi X là tập hợp tất cả các hoán vị của A thì X = n!. a) Gọi A, B, C lần lượt là các tập con của X chứa các khối 23; 45; 678. Vậy kết quả cần tìm là 9! − (8! + 8! + 8!) + (7! + 6! + 6!) − 5! = 283560.
b) Gọi A, B, C lần lượt là các tập con của X chứa các khối 34; 45; 738. Vậy kết quả cần tìm là 9! − (8! + 8! + 7!) + (7! + 0 + 6!) − 0 = 282960. 20 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 1. Phương pháp đếm Ví dụ 1.
Tìm các số nguyên dương nhỏ hơn 601 thỏa mãn không có ước là 3 hoặc 5 hoặc 7., 600} thì n(X) = 600, gọi A, B, C là các tập con của X tương ứng chứa các số chia hết cho 3, 5, 7. 3 5 7 Do cứ ba số có một số chia hết cho 3, cứ năm số có một số chia hết cho 5, cứ bảy số có một số chia hết cho 7 nên 600 600 600 |A ∩ B| + |B ∩ C| + |A ∩ C| = + + = 85; 15 21 35 600 |A ∩ B ∩ C| = = 5. 105 Vậy số các số cần tìm là: 600 - 405 +85 - 5 = 275. Có 30 sinh viên trong ký túc xá có 15 sinh viên học lớp hội họa, 8 sinh viên học lớp sinh học, 6 sinh viên học lớp hóa học.
Biết có 3 sinh viên tham gia cả ba lớp trên. Chứng minh có ít nhất 7 sinh viên không tham gia lớp nào. Gọi A, B, C lần lượt là tập các sinh viên lần lượt tham gia các lớp hội họa, sinh học và hóa hoc. Ta có |A| + |B| + |C| = 15 + 8 + 6 = 29; |A ∩ B ∩ C| = 3; Gọi X là tập các sinh viên không tham gia lớp nào.
Trên cơ sở công thức Sieve ta giải quyết được bài toán về sự xáo trộn, một bài toán đếm khá phức tạp. Ta cũng tìm được công thức tính cho các số S(n, k). 21 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 1. Phương pháp đếm Định nghĩa 1.
Một hoán vị p của tập A = {a1 , a2 , ., an } được gọi là một sự xáo trộn nếu p(ai ) 6= ai , i = 1, n. Gọi D(n) là số xáo trộn của tập A. Số các xáo trộn của tập A có n phần tử là n X n! D (n) = (−1)i−1. Gọi Ai là tập hợp tất cả các hoán vị của A = {a1 , a2 , .an } mà phần tử i ở vị trí thứ i, tức là ∀p ∈ Ai , p(ai ) = ai.
Ai ∩ Aj là tập hợp chứa tất cả hoán vị p của A mà p(ai ) = ai và p(aj ) = aj. Khi đó |Ai ∩ Aj | = (n − 2)! n X n! |Ai ∩ Aj | = Cn2 (n − 2)! =. 2! i,j=1,i6=j Tương tự ta có n! |Ai1 ∩ Ai2 ∩. t! Theo công thức Sieve ta có n (−1)j−1 P P |A1 ∪ A2 ∪.
∪ Ait | = Ai1 ∩ Ai2 ∩. Số hoán vị của A = {a1 , a2 , .an } có ít nhất một phần tử bất động (p(ai ) = ai ) bằng số hoán vị của A trừ đi số xáo trộn của A. Lập bảng tính D(n) với n = 1, 10 n 1 2 3 4 5 6 7 8 9 10 D(n) 0 1 2 9 44 265 1854 14833 133469 1334961 22 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 1. Phương pháp đếm Ví dụ 1.
Trong lớp học có n học sinh và n quyển sách phân biệt. Giáo viên phát ngẫu nhiên cho mỗi học sinh một quyển sách và yêu cầu học sinh nộp lại sau một tuần. Tuần sau những quyển sách đó lại được phát lại cho n học sinh một cách ngẫu nhiên. Hỏi có bao nhiêu cách phân phối sao cho không học sinh nào nhận 2 lần cùng một quyển sách? Lời giải.
Tuần đầu mỗi quyển sách có thể phát theo n! cách. Ứng với mỗi cách phân phát đó có D(n) cách phân phát của tuần thứ hai sao cho không học sinh nào nhận một quyển sách hai lần. Vậy kết quả cần tìm là n!D(n). Có n phụ nữ tham gia một buổi tiệc, khi đến mỗi người đều mang một chiếc mũ, một chiếc áo khoác và gửi ở phòng tiếp tân.
Khi ra về mỗi người sẽ lấy ngẫu nhiên một chiếc mũ, một chiếc áo khoác. Tìm số cách lấy những chiếc mũ và áo khoác này nếu a) Không người phụ nữ nào nhận đúng mũ hoặc áo khoác của cô ấy. b) Không người phụ nữ nào nhận đúng mũ và áo khoác của cô ấy. a) Những chiếc áo bị xáo trộn theo D(n) cách, những chiếc mũ bị xáo trộn theo D(n) cách.
Nên có 2(D(n)) cách để lấy những chiếc mũ và những chiếc áo thỏa mãn yêu cầu. b) Gọi A là tập con của tập X tất cả các sự phân phối, trong đó người phụ nữ thứ i, i = 1, n nhận đúng cả mũ và áo khoác của cô ấy. Gọi Sr là số cách phân phối có r người nhận đúng mũ và áo thì Sr = Cnr (Dn−r )2. Vậy kết quả cần tìm là |X| − S1 + S2 +.
Có n bức thư gửi cho n người khác nhau. Tìm số cách phân phối n bức thư tới n người sao cho ít nhất một bức thư đến tay người nhận. Số cách đưa n bức thư cho n người là n!. Số cách đưa n bức thư cho n người mà không ai nhận đúng bức thư của mình là D(n).
Vậy số cách thỏa mãn bài toán là n! − D(n). 23 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 1. Phương pháp đếm Định lý 1. Với mọi số nguyên dương n, k ta có k k 1 X X 1 S (n, k) = (−1)i Cki (k − i)n = (−1)i (k − i)n.
Ta sẽ đi chứng minh công thức cho k!S(n, k) để suy ra công thức trong định lý. Gọi M là tập hợp các ánh xạ từ tập X tới tập Y , X = {x1 , x2 ,. Gọi Ai là tập con của M bao gồm các ánh xạ mà trong tập giá trị không có yi , i = 1. Ta dễ chứng minh các toàn ánh trong M là: k n − Ck1 (k − 1)n +.
Một lớp có 15 học sinh, có bao nhiêu cách chia 15 học sinh thành bốn nhóm đi thực hiện các công việc khác nhau. Biết rằng mỗi nhóm có ít nhất hai học sinh. Số cách chia 15 học sinh thành bốn nhóm, mỗi nhóm có ít nhất một học sinh, để thực hiện các công việc khác nhau là " 4 # X 1 4!.S(15, 4) = 4!