Bài tập chương 3 đại số tổ hợp

Trong đề mục này chúng ta sẽ dùng định nghĩa truyền thống của hoán vị: một hoán vị là một bộ có thứ tự không lặp, có thể thiếu một số phần tử. Có thể dễ dàng đếm được số hoán vị có kích thước r khi chọn từ một tập hợp có kích thước n (với r≤n).
Nội dung trích xuất từ tài liệu:
Bài tập chương 3 đại số tổ hợp ÑAÏI SOÁ TOÅ HÔÏPChöông III CHÆNH HÔÏPCoù n vaät khaùc nhau, choïn ra k vaät khaùc nhau (1 ≤ k ≤ n), saép vaøo k choã khaùcnhau. Moãi caùch choïn roài saép nhö vaäy goïi laø moät chænh hôïp chaäp k cuûa n phaàntöû.Choã thöù nhaát coù n caùch choïn (do coù n vaät), choã thöù 2 coù (n – 1) caùch choïn (docoøn n – 1 vaät), choã thöù 3 coù n – 2 caùch choïn (do coøn n – 2 vaät), …, choã thöù k coùn – (k – 1) caùch choïn (do coøn n – (k – 1) vaät). Vaäy, theo qui taéc nhaân, soá caùchchoïn laø : n! n × (n – 1) × (n – 2) × … × (n – k + 1) = (n − k)!Neáu kí hieäu soá chænh hôïp chaäp k cuûa n phaàn töû laø A k , ta coù : n n! Ak = (n − k)! nVí duï 1. Moät nhaø haøng coù 5 moùn aên chuû löïc, caàn choïn 2 moùn aên chuû löïc khaùcnhau cho moãi ngaøy, moät moùn buoåi tröa vaø moät moùn buoåi chieàu. Hoûi coù maáycaùch choïn ? GiaûiÑaây laø chænh hôïp chaäp 2 cuûa 5 phaàn töû, coù : 5! A5 = 2 = 4.5 = 20 caùch choïn. (5 − 2)!(Giaû söû 5 moùn aên ñöôïc ñaùnh soá 1, 2, 3, 4, 5; ta coù caùc caùch choïn sau ñaây :(1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 4), (3, 5),(4, 1), (4, 2), (4, 3), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)).Ví duï 2. Trong moät tröôøng ñaïi hoïc, ngoaøi caùc moân hoïc baét buoäc, coù 3 moân töïchoïn, sinh vieân phaûi choïn ra 2 moân trong 3 moân ñoù, 1 moân chính vaø 1 moân phuï.Hoûi coù maáy caùch choïn ? GiaûiÑaây laø chænh hôïp chaäp 2 cuûa 3 phaàn töû. Vaäy coù : 3! A3 = 2 = 6 caùch choïn. (3 − 2)! (Giaû söû 3 moân töï choïn laø a, b, c thì 6 caùch choïn theo yeâu caàu laø (a, b), (a, c), (b, a), (b, c), (c, a), (c, b)). Ví duï 3. Töø 5 chöõ soá 1, 2, 3, 4, 5 coù theå taïo ra bao nhieâu soá goàm 2 chöõ soá khaùc nhau ? Giaûi Ñaây laø chænh hôïp chaäp 2 cuûa 5 phaàn töû. Vaäy coù : 5! 5! A5 = 2 = = 5 × 4 = 20 soá (5 − 2)! 3! (Caùc soá ñoù laø : 12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54) .Baøi 35. Chöùng minh vôùi n, k ∈ ¥ vaø 2 ≤ k < n a) A n = A n −1 + k A n −1 k k k −1 b) A n + 2 + A n + 1 = k2 A n + k n+k n+k n Giaûi a) Ta coù : (n − 1)! (n − 1) ! A n −1 + k A n −1 = k k −1 + k. (n − 1 − k) ! (n − k) ! ⎡ 1 k ⎤ = (n – 1)! ⎢ + ⎥ ⎣ (n − k − 1)! (n − k)(n − k − 1)! ⎦ (n − 1) ! ⎛ k ⎞ (n − 1) ! n = ⎜1 + ⎟ = . (n − k − 1) ! ⎝ n − k ⎠ (n − k − 1) ! n − k n! = = An . k (n − k) ! (n + k) ! (n + k) ! (n + k) ! (n + k)! b) A n + 2 + A n +1 = n+k n+k + = + (k − 2) ! (k − 1)! (k − 2) ! (k − 1)(k − 2)! (n + k) ! ⎡ 1 ⎤ = ⎢1 + k − 1 ⎥ (k − 2) ! ⎣ ⎦ (n + k) ! k (n + k)!k 2 = . = = A n + k .k2. n ...