Đại số tổ hợp - Toán học

ÑAÏI SOÁ TOÅ HÔÏP

Chöông III

CHÆNH HÔÏP

Coù 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ùc

nhau. 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àn

töû.

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 (do

coø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ùch

choïn laø :

n × (n – 1) × (n – 2) × … × (n – k + 1) = n!

(n k)! −

Neáu kí hieäu soá chænh hôïp chaäp k cuûa n phaàn töû laø , ta coù : k An

=

k An

n!

(n k)! −

Ví 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ùc

nhau 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áy

caùch choïn ?

Giaûi

Ñaây laø chænh hôïp chaäp 2 cuûa 5 phaàn töû, coù :

=

2 A5

5!

(5 2)! − = 4.5 = 20 caùch choïn.

(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ù :