Hệ quả. Số nghiệm nguyên không âm [x1,x2,n,xn] [mỗi xi đều nguyên không âm] của phương trình Số cách chia k vật đồng chất nhau vào n hộp phân biệt cũng chính bằng số tổ hợp lặp chập k của n
Bạn đang xem trước 20 trang tài liệu Toán rời rạc - Chương 2: Phép đếm, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
LOGO Chương 2. Phép đếm TOÁN RỜI RẠC Chương 2 1 Nội dung - Các nguyên lý - Giải tích tổ hợp - Hoán vị lặp, tổ hợp lặp - Hệ thức đệ qui 2 I. Các nguyên lý 1. Nguyên lý cộng Giả sử để làm công việc A có 2 phương pháp - Phương pháp 1 có n cách làm - Phương pháp 2 có m cách làm Khi đó số cách làm công việc A là n+m Ví dụ. An có 3 áo tay dài, 5 áo tay ngắn. Để chọn 1 cái áo thì An có mấy cách 3 I. Các nguyên lý 2. Nguyên lý nhân Giả sử để làm công việc A cần thực hiện 2 bước - Bước 1 có n cách làm - Bước 2 có m cách làm Khi đó số cách làm công việc A là n.m Phép đếm Ví dụ: A B C Có 3.2 =6 con đường đi từ A đến C 4 I. Các nguyên lý Ví dụ: Cho tập X ={1,2,3,4,5,0} Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia hết cho 2 Giải. Gọi số có 3 chữ số là abc TH1 . c=0. Khi đó c có 1 cách chọn a có 5 cách chọn [ a∈X\{0} ] b có 4 cách chọn [ b∈X\{a, 0} ] TH1 có 1.4.5 =20 TH2 . c≠0. Khi đó c có 2 cách chọn a có 4 cách chọn [ a∈X\{c, 0} ] b có 4 cách chọn [ b∈X\{a, c} ] TH2 có 2.4.4 =32 Vậy có 20+32 =52 5 I. Các nguyên lý 3. Nguyên lý chuồng bồ câu [Derichlet] Gọi là số nguyên nhỏ nhất lớn hơn hay bằng x. Giả sử có n chim bồ câu ở trong k chuồng. Khi đó tồn tại ít nhất một chuồng chứa từ bồ câu trở lên. /n k x Ví dụ. Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên - Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày 6 Ví dụ. Cho tập X ={1,2,3,4,5,6,7,8,9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ có hai phần tử có tổng bằng 10. Giải. I. Các nguyên lý Ta lập các chuồng như sau: {1,9} {2,8} {3,7} {4,6} {5} Do A có 6 phần tử nên trong 6 phần tử đó sẽ có 2 phần tử trong 1 chuồng. Suy ra đpcm 7 4. Nguyên lý bù trừ. Cho A và B là hai tập hữu hạn. Khi đó |A ∪ B|= |A|+|B| - |A ∩ B| I. Các nguyên lý A∩ B BA 8 I. Các nguyên lý A∩ C B∩C A∩ B ∩ C C A∩ B A B |A∪ B ∪ C|=? 9 I. Các nguyên lý Ví dụ. Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu người Giải. Gọi A là những học sinh học Tiếng Pháp B là những học sinh học Tiếng Anh Khi đó. Số học sinh của lớp là |A∪ B |. Theo nguyên lý bù trừ ta có |A∪ B|= |A|+|B| - |A∩ B|=24+26-15=35 10 II. Giải tích tổ hợp 1. Hoán vị Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Số các hoán vị của n phần tử ký hiệu là Pn Pn = n! = n.[n-1].[n-2]n1 Quy ước 0! =1 Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau abc,acb, bac,bca, cab,cba 11 Ví dụ. Nếu A là tập hợp n phần tử thì số song ánh từ A vào A là n! Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau được tạo từ tập X 5! 12 II. Giải tích tổ hợp 2. Chỉnh hợp. Định nghĩa. Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử [1 ≤ k ≤n] sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử. Số các chỉnh hợp chập k của n ký hiệu là k nA - Công thức [ ] ! ! k n n A n k = − Ví dụ. Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb. 13 II. Giải tích tổ hợp Ví dụ. Có bao nhiêu số tự nhiên gồm 3 chữ số được tạo thành từ 1,2,3,4,5,6. Kết quả: 3 6 A 14 II. Giải tích tổ hợp 3.Tổ hợp. Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử. Số tổ hợp chập k của n phần tử được kí hiệu là hay k nC k n [ ] ! ! ! k n n C k n k = − Tính chất n k k n nC C − = 1 1 k k k n n nC C C − ++ = 15 II. Giải tích tổ hợp Ví dụ. Cho X = {1,2,3,4}. Tổ hợp chập 3 của 4 phần tử của X là {1,2,3}, {1,2,4}, {1,3,4} , {2,3,4} Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn 10C- Số cách chọn là tổ hợp chập 10 của 30. 30 16 III. Hoán vị lặp, tổ hợp lặp 1. Hoán vị lặp Định nghĩa. Cho n đối tượng trong đó có ni đối tượng loại i giống hệt nhau [i =1,2,n,k ; n1+ n2,n+ nk= n]. Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một hoán vị lặp của n. Số hoán vị của n đối tượng, trong đó có n1 đối tượng giống nhau thuộc loại 1, n2 đối tượng giống nhau thuộc loại 2,n, nk đối tượng giống nhau thuộc loại k, là 1 2 ! ! !... !k n n n n 17 II. Giải tích tổ hợp Ví dụ. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ SUCCESS? Giải. Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 1 chữ E. Do đó số chuỗi có được là . 7! 420 3!1!2!1! = 18 III. Hoán vị lặp, tổ hợp lặp 2. Tổ hợp lặp Định nghĩa. Mỗi cách chọn ra k vật từ n loại vật khác nhau [trong đó mỗi loại vật có thể được chọn lại nhiều lần] được gọi là tổ hợp lặp chập k của n Số các tổ hợp lặp chập k của n được ký hiệu là kKn 1 k k n n kK C + −= 19 Ví dụ. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn. Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể AA, AB, AC, BB, BC, CC 2 2 2 6K C C= = = III. Hoán vị lặp, tổ hợp lặp 3 3 2 1 4+ − 20 Hệ quả. Số nghiệm nguyên không âm [x1,x2,n,xn] [mỗi xi đều nguyên không âm] của phương trình x1+ x2+n+ xn = k là 1 k k n n kK C + −= Số cách chia k vật đồng chất nhau vào n hộp phân biệt cũng chính bằng số tổ hợp lặp chập k của n 1 k k n n kK C + −= 21 Ví dụ. Tìm số nghiệm nguyên không âm của phương trình x1+ x2 + x3 + x4 = 20 [1] Thỏa điều kiện x1 ≤ 3; x2 ≥ 2; x3 > 4 [∗]. Giải. Ta viết điều kiện đã cho thành x1 ≤ 3; x2 ≥ 2; x3 ≥ 5. III. Hoán vị lặp, tổ hợp lặp Xét các điều kiện sau: x2 ≥ 2; x3 ≥ 5 [∗∗] x1 ≥ 4; x2 ≥ 2; x3 ≥ 5 [∗∗∗] Gọi p, q, r lần lượt là các số nghiệm nguyên không âm của phương trình [1] thỏa các điều kiện [∗], [∗∗], [∗∗∗]. Ta có: 22 p = q – r. Trước hết ta tìm q. Đặt x1’ = x1; x2’ = x2 – 2; x3’ = x3 - 5; x4’ = x4 Phương trình [1] trở thành x ’+ x ’ + x ’ + x ’ = 13 [2] III. Hoán vị lặp, tổ hợp lặp 1 2 3 4 Số nghiệm nguyên không âm của phương trình [1] thỏa điều kiện [∗∗] bằng số nghiệm nguyên không âm của phương trình [2] 23 Số nghiệm đó là Vậy . Lý luận tương tự, ta có . 13 13 13 4 4 13 1 16 K C C+ −= = 13 16 q C= 9 9 9 4 4 9 1 12 r K C C+ −= = = III. Hoán vị lặp, tổ hợp lặp Suy ra. Vậy số nghiệm nguyên không âm của phương trình [1] thỏa điều kiện [∗] là 340 13 9 16 12 560 220 340.p q r C C= − = − = − = 24
Các file đính kèm theo tài liệu này:
- 06_phepdem_1089.pdf
Bài này có thể đưa về dạng toán đã biết trước là đếm số nghiệm nguyên không âm của phương trình x1+x2+x3+x4=30 với x1>=a,x2>=b,x3>=c x+y+z+t=30-a-b-c=m với x=x1-a,y=x2-b,z=x3-c
thì số nghiệm là C[m+3,3] { C là tổ hợp } [1]
đặt F[a,b,c] tương ứng là kết quả của bài toán trên. Thì kết của của bài toán đề ra F[0,0,0]-F[18,0,0]-F[0,11,0]-F[0,0,9]+F[18,11,0]+F[18,0,9]+F[0,11,9]-F[18,11,9]
tính kết quả dựa trên công thức [1] thì kết quả bài toán = C[33,3]-C[33-18,3]-C[33-11,3]-C[33-9,3]+C[33-18-11,3]+C[33-18-9,3]+C[33-11-9,3] =1747
Toán rời rạc 2 counting
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [842.19 KB, 81 trang ]
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 1
Bài toán đếm
Ngô Xuân Bách
Nội dung
Giới thiệu bài toán
Các nguyên lý đếm cơ bản
Quy về bài toán con
Hệ thức truy hồi
Phương pháp hàm sinh
Bài tập
2
//www.ptit.edu.vn
Giới thiệu bài toán đếm
Bài toán đếm
o
o
Là bài toán đếm xem có bao nhiêu cấu hình tổ hợp có thể được
tạo ra với những quy tắc đã nêu?
Lời giải thường phụ thuộc vào một số tham số ban đầu và người
ta cố gắng biều diễn những phụ thuộc này bằng những công thức
toán học
Nguyên tắc chung giải bài toán đếm
o
Để đếm các cấu hình đã cho, người ta tìm cách đưa về các cấu
hình quen thuộc bằng cách thiếp lập một quan hệ 1-1 giữa chúng
Ứng dụng của bài toán đếm trong khoa học máy tính
o
o
3
Ước lượng số phép toán thực hiện trong một giải thuật, chương
trình máy tính
Ước lượng độ phức tạp thời gian và không gian của giải thuật
//www.ptit.edu.vn
Các phương pháp giải quyết bài toán đếm
Sử dụng các nguyên lý đếm cơ bản: nguyên lý cộng,
nguyên lý nhân, nguyên lý bù trừ
Qui về các bài toán con: Phân tích lời giải bài toán
đếm phức tạp thành những bài toán con. Trong đó, mỗi
bài toán con có thể giải được bằng các nguyên lý đếm cơ
bản
Sử dụng hệ thức truy hồi: Xây dựng công thức tính số
nghiệm tổng quát bất kỳ dựa vào biểu diễn các số hạng
biết trước
Phương pháp hàm sinh: Sử dụng hàm sinh của một
dãy số để đếm các cấu hình tổ hợp
4
//www.ptit.edu.vn
Nội dung
Giới thiệu bài toán
Các nguyên lý đếm cơ bản
Quy về bài toán con
Hệ thức truy hồi
Phương pháp hàm sinh
Bài tập
5
//www.ptit.edu.vn
Nguyên lý cộng [nhắc lại]
Nếu 𝐴 và 𝐵 là hai tập rời nhau thì
𝐴∪𝐵 = 𝐴 + 𝐵
Nếu *𝐴1 , 𝐴2 , … , 𝐴𝑘 + là một phân hoạch của tập hợp 𝑋 thì
𝑋 = 𝐴1 + 𝐴2 + ⋯ + 𝐴𝑘
Nếu có 𝐾 việc, việc thứ 𝑖 thực hiện bằng 𝑛𝑖 cách và thực
hiện một cách tuần tự. Khi đó sẽ có 𝑛1 + 𝑛2 +. . + 𝑛𝐾 cách
thực hiện một trong 𝐾 việc nêu trên.
6
//www.ptit.edu.vn
Ví dụ 1
Bài toán: Giả sử 𝑁, 𝑀 là hai số tự nhiên đã xác định giá
trị. Hãy cho biết giá trị của 𝑆 sau khi thực hiện đoạn
chương trình.
𝑆 = 0;
for [𝑖 = 1; 𝑖