10/1/14 1
GVC, ThS. Võ Minh Đ c, CĐSP Đăklăkứ
c¸c ph¬ng ph¸p ®Õm vµ nguyªn lý dirichlet
Ch¬ng II
10/1/14 2
GVC, ThS. Võ Minh Đ c, CĐSP Đăklăkứ
I. CÁC NGUYÊN LÝ Đ M C B NẾ Ơ Ả
II. M T S BÀI TOÁN Đ M C B NỘ Ố Ế Ơ Ả
III. SINH CÁC HOÁN V VÀ T H PỊ Ổ Ợ
IV. NGUYÊN LÝ DIRICHLET.
N I DUNGỘ
10/1/14 3
GVC, ThS. Võ Minh Đ c, CĐSP Đăklăkứ
I. CÁC NGUYÊN LÝ Đ M C B NẾ Ơ Ả
1.Nguyên lý c ng ộ
2.Nguyên lý nhân
3.Nguyên lý bù trừ
10/1/14 4
GVC, ThS. Võ Minh Đ c, CĐSP Đăklăkứ
I. CÁC NGUYÊN LÝ Đ M C B NẾ Ơ Ả
1.Nguyên lý c ngộ
Gi s có k công vi c T1, T2, …, Tk . Các ả ử ệ
công vi c này có th làm b ng n1, n2, …, nk ệ ể ằ
cách t ng ng và gi s r ng không có ươ ứ ả ử ằ
hai vi c nào có th làm đ ng th i. Khi đó s ệ ể ồ ờ ố
cách đ làm m t trong k công vi c đó là:ể ộ ệ
n1+ n2+ …+ nk
10/1/14 5
GVC, ThS. Võ Minh Đ c, CĐSP Đăklăkứ
I. CÁC NGUYÊN LÝ Đ M C B N (2)Ế Ơ Ả
Ví d 1ụ: M t SV c n ch n m t bài t p ộ ầ ọ ộ ậ
trong ba danh sách t ng ng có 23, 15 và ươ ứ
39 bài.
S cách ch n s là: (?)ố ọ ẽ
23+15+39 =77 cách. (theo nguyên lý
c ng )ộ