Bài giảng Toán rời rạc - Chương 3: Phép đếm
Baøi giaûng moân
Raïc
Caùc nguyeân lyù
Nguyeãn Anh
Thi
Nguyeân lyù coäng: Giaû söû ñeå laøm coâng vieäc A ta coù theå choïn moät
trong hai bieän phaùp khaùc nhau (theo nghóa laø caùch thöïc hieän
bieän phaùp thöù nhaát luoân luoân khaùc caùch thöïc hieän bieän phaùp
thöù hai). Neáu bieän phaùp thöù nhaát coù m caùch, bieän phaùp thöù hai
coù n caùch, thì ta coù soá caùch laøm coâng vieäc A laø m + n.
Toång quaùt, giaû söû ñeå laøm coâng vieäc A ta coù theå choïn moät trong
k bieän phaùp khaùc nhau, moãi bieän phaùp coù mi caùch laøm vôùi
i = 1, 2, . . . , k, khi ñoù soá caùch laøm coâng vieäc A laø
hôïp
hôïp laëp
m1 + m2 + · · · + mk.
Ví duï
Ta choïn moät vieân bi baát kyø töø hai hoäp A vaø B. Bieát raèng hoäp A
chöùa 5 vieân bi maøu ñoû, hoäp B chöùa 3 vieân bi maøu xanh. Vaäy
soá caùch choïn laø 5 + 3 = 8.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Caùc nguyeân lyù
Nguyeãn Anh
Thi
Nguyeân lyù nhaân: Giaû söû chuùng ta phaûi thöïc hieän moät coâng vieäc
bao goàm hai coâng vieäc keá tieáp nhau. Ñeå thöïc hieän coâng vieäc
thöù nhaát chung ta coù m caùch, vaø öùng vôùi moãi caùch choïn thöïc
hieän coâng vieäc thöù nhaát ta coù n caùch thöïc hieän coâng vieäc thöù
hai.Vaäy ta coù soá caùch thöïc hieän coâng vieäc ñoù laø m.n.
Toång quaùt, Giaû söû moät coâng vieäc bao goàm k böôùc keá tieáp nhau,
neáu moãi böôùc ta coù ni caùch laøm vôùi i = 1, 2, . . . , k. Vaäy ta coù
n1.n2. . . . .nk caùch ñeå thöïc hieän coâng vieäc.
hôïp
hôïp laëp
Ví duï
Ta choïn hai vieân bi maøu khaùc nhau töø hai hoäp A vaø B. Bieát
raèng hoäp A chöùa 5 vieân bi maøu ñoû, hoäp B chöùa 3 vieân bi maøu
xanh. Vaäy soá caùch choïn laø 5.3 = 15.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Caùc nguyeân lyù
Nguyeãn Anh
Thi
Nguyeân lyù chuoàng boà caâu (Derichlet) Goïi dxe laø soá nguyeân nhoû
nhaát lôùn hôn hay baèng x. Giaû söû coù n chim boà caâu trong k
chuoàng. Khi ñoù toàn taïi ít nhaát moät chuoàng chöùa töø dn/ke boà
caâu trôû leân.
hôïp
hôïp laëp
Ví duï
Trong nhoùm coù 367 ngöôøi thì ít nhaát coù 2 ngöôøi sinh cuøng
ngaøy.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Caùc nguyeân lyù
Nguyeãn Anh
Thi
Nguyeân lyù buø tröø: Cho A vaø B laø hai taäp höõu haïn. Khi ñoù
|A ∪ B| = |A| + |B| − |A ∩ B|
hôïp
hôïp laëp
Ví duï
Trong lôùp coù 24 hoïc sinh hoïc tieáng Phaùp, 26 hoïc sinh hoïc
tieáng Anh, coù 15 hoïc sinh vöøa hoïc tieáng Anh, vöøa hoïc tieáng
Phaùp. Hoûi lôùp coù bao nhieâu hoïc sinh?
Goïi A laø taäp hôïp nhöõng hoïc sinh hoïc tieáng Phaùp, B laø taäp hôïp
nhöõng hoïc sinh hoïc tieáng Anh. Khi ñoù soá hoïc sinh cuûa lôùp laø
A ∪ B = |A| + |B| − |A ∩ B| = 24 + 26 − 15 = 35.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Nguyeân lyù buø tröø: Cho A, B vaø C laø caùc taäp höõu haïn. Khi ñoù
|A∪B∪C| = |A|+|B|+|C|−|A∩B|−|B∩C|−|A∩C|+|A∩B∩C|.
Ví duï
Nguyeãn Anh
Thi
ÔÛ moät tröôøng trung hoïc coù 14 hoïc sinh chôi boùng ñaù, 17 hoïc
sinh chôi boùng roå, 18 hoïc sinh chôi boùng baàu duïc. Trong ñoù coù
4 hoïc sinh chôi caû boùng ñaù vaø boùng roå, 3 hoïc sinh chôi caû
boùng ñaù vaø boùng baàu duïc, 5 hoïc sinh chôi caû boùng roå vaø boùng
baàu duïc, vaø coù 1 hoïc sinh chôi caû 3 moân. Hoûi coù bao nhieâu
hoïc sinh chôi ít nhaát moät trong nhöõng moân theå thao treân?
hôïp
hôïp laëp
Goïi A laø taäp hôïp nhöõng hoïc sinh chôi boùng ñaù, B laø taäp hôïp
nhöõng hoïc sinh chôi boùng roå, vaø C laø taäp hôïp nhöõng hoïc sinh
chôi boùng baàu duïc. Soá hoïc sinh chôi ít nhaát moät trong nhöõng
moân theå thao treân laø:
|A∪B∪C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C| =
14 + 17 + 18 − 4 − 3 − 5 + 1 = 38.
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Giaûi tích toå hôïp
Nguyeãn Anh
Thi
Ñònh nghóa
Cho taäp hôïp A coù n phaàn töû. Moãi caùch saép ñaët coù thöù töï n
phaàn töû cuûa A ñöôïc goïi laø moät hoaùn vò coù n phaàn töû. Soá caùc
hoaùn vò cuûa n phaàn töû kyù hieäu laø Pn, vaø
hôïp
Pn = n! = n.(n − 1).(n − 2)...2.1, quy öôùc 0! = 1.
hôïp laëp
Ví duï
•
•
•
Cho X laø taäp hôïp coù n phaàn töû thì soá song aùnh töø X vaøo X
laø n!
Cho A = {a, b, c}. Khi ñoù A coù caùc hoaùn vò sau: abc, acb,
bac, bca, cab, cba.
Cho X = {1, 2, 3, 4, 5}, hoûi coù bao nhieâu soá töï nhieân goàm
5 chöõ soá khaùc nhau ñöôïc taïo thaønh töø taäp X?
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Giaûi tích toå hôïp
Nguyeãn Anh
Thi
Ñònh nghóa
Cho A laø taäp hôïp goàm n phaàn töû. Moãi boä goàm k phaàn töû
(1 ≤ k ≤ n) saép thöù töï cuûa taäp hôïp A ñöôïc goïi laø moät chænh
hôïp chaäp k cuûa n phaàn töû. Soá caùc chænh hôïp chaäp k cuûa n, kyù
hôïp
n!
hieäu laø Akn. Ta coù coâng thöùc Akn =
(n−k)!
hôïp laëp
Ví duï
Cho X = {a, b, c}. Khi ñoù X coù caùc chænh hôïp chaäp 2 cuûa caùc
phaàn töû cuûa X laø: ab, ac, bc, ba, ca, cb.
Ví duï
Coù bao nhieâu soá töï nhieân goàm 3 chöõ soá khaùc nhau ñöôïc taïo
thaønh töø {1, 2, 3, 4, 5, 6} ?
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Giaûi tích toå hôïp
Nguyeãn Anh
Thi
Ñònh nghóa
Cho taäp hôïp A goàm n phaàn töû. Moãi taäp con goàm k phaàn töû cuûa
A ñöôïc goïi laø moät toå hôïp chaäp k cuûa n phaàn töû. Soá caùc toå hôïp
ꢀ ꢁ
n
hôïp
chaäp k cuûa n phaàn töû ñöôïc kyù hieäu laø Ckn hay
. Ta coù
k
hôïp laëp
coâng thöùc
n!
Ckn =
k!(n − k)!
Tính chaát
Cnn−k = Ckn
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Nguyeãn Anh
Thi
Ví duï
Cho X = {1, 2, 3, 4}. Toå hôïp chaäp 3 cuûa 4 phaàn töû cuûa X laø
hôïp
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}
hôïp laëp
Ví duï
Moät lôùp coù 30 hoïc sinh, hoûi coù bao nhieâu caùch choïn 10 baïn.
10
Soá caùch choïn laø toå hôïp chaäp 10 cuûa 30: C .
30
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Hoaùn vò laëp, toå hôïp laëp
Nguyeãn Anh
Thi
Ñònh nghóa
Cho n ñoái töôïng trong ñoù coù ni ñoái töôïng loaïi i gioáng heät nhau
(i = 1, 2, . . . , k; n1 + n2 + · · · + nk = n). Moãi caùch saép xeáp coù
thöù töï n ñoái töôïng ñaõ cho goïi laø moät hoaùn vò laëp cuûa n.
Soá hoaùn vò cuûa n ñoái töôïng, trong ñoù coù n1 ñoái töôïng gioáng
nhau thuoäc loaïi 1, n2 ñoái töôïng gioáng nhau thuoäc loaïi 2,. . . , nk
ñoái töôïng gioáng nhau thuoäc loaïi k, laø
hôïp
hôïp laëp
n!
n1!n2! . . . nk!
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Hoaùn vò laëp, toå hôïp laëp
Nguyeãn Anh
Thi
Ví duï
hôïp
Coù bao nhieâu chuoãi kyù töï khaùc nhau baèng caùch saép xeáp caùc
chöõ caùi cuûa töø SUCCESS?
Trong töø SUCCESS coù 3 chöõ S, 1 chöõ U, 2 chöõ C, vaø 1 chöõ E.
Do ñoù soá chuoãi coù ñöôïc laø
hôïp laëp
7!
= 420
3!1!2!1!
Nguyeãn Anh Thi
Baøi giaûng moân
Raïc
Hoaùn vò laëp, toå hôïp laëp
Nguyeãn Anh
Thi
Ñònh nghóa
Moãi caùch choïn ra k vaät töø n loaïi vaät khaùc nhau (trong ñoù moãi
loaïi vaät coù theå ñöôïc choïn laïi nhieàu laàn) ñöôïc goïi laø toå hôïp laëp
hôïp
chaäp k cuûa n. Soá caùc toå hôïp laëp chaäp k cuûa n ñöôïc kyù hieäu laø
Kkn.
hôïp laëp
Kkn = Ckn+k−1
Ví duï
Coù 3 loaïi noùn A, B, C. An mua 2 caùi noùn. Hoûi An coù bao nhieâu
caùch choïn?
Moãi caùch choïn laø moät toå hôïp laëp chaäp 2 cuûa 3. Cuï theå
AA, AB, BB, BC, CC, AC, K23 = C32+2−1 = C42 = 6.
Nguyeãn Anh Thi
16 trang
15/01/2024
6700
Free
Bạn đang xem tài liệu "Bài giảng Toán rời rạc - Chương 3: Phép đếm", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_chuong_3_phep_dem.pdf
