Toán Rời Rạc: Phương Pháp đếm - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (37 trang)

Trang chủ

Giáo án - Bài giảng

Toán học

Toán rời rạc: phương pháp đếm

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 (40 KB, 37 trang )

TOÁN RỜI RẠC - HK1 - NĂM 2016 -2017Chương 3PHƯƠNG PHÁP ĐẾM />FB: fb.com/trr2016Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh− − −− Tháng 10 năm 2016 − − −−Chương 3. Phương pháp đếmTháng 10 - 20161/37Nội dungChương 3. PHƯƠNG PHÁP ĐẾM1. Các nguyên lý đếm cơ bản2. Giải tích tổ hợp3. Tổ hợp lặpChương 3. Phương pháp đếmTháng 10 - 20162/373.1. Các nguyên lý đếm cơ bản1Nguyên lý cộng2Nguyên lý nhân3Nguyên lý bù trừ4Nguyên lý DirichletChương 3. Phương pháp đếmTháng 10 - 20163/373.1.1. Nguyên lý cộngGiả sử để làm công việc A ta có 2 phương phápPhương pháp 1: có n cách làmPhương pháp 2: có m cách làmKhi đó 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 một cái áo thì Ancó mấy cách?Đáp án. 3+5 =8 cách.Ví dụ. Nhà trường cần chọn một sinh viên khoa CNTT năm hai, nămba hoặc năm tư đi tham gia hội nghị sinh viên thành phố. Biết rằngtrường có 501 sinh viên năm hai, 402 sinh viên năm ba, 345 sinh viênnăm tư. Hỏi có bao nhiêu cách chọn?Đáp án. 501 + 402 + 345 = 1248 cách.Chương 3. Phương pháp đếmTháng 10 - 20164/373.1.2. Nguyên lý nhânGiả sử để làm công việc A cần thực hiện 2 bướcBước 1 có n cách làmBước 2 có m cách làmKhi đó số cách làm công việc A là n × m.Ví dụ.Hỏi có nhiêu cách đi từ A đến C?Đáp án. 3 × 2 = 6 cách.Chương 3. Phương pháp đếmTháng 10 - 20165/37Ví dụ. Có bao nhiêu chuỗi bit có độ dài 8?Giải. Mỗi bit có thể chọn 1 trong 2 cách: 0 hoặc 1. Theo nguyên lýnhân ta có số lượng chuỗi là 28 = 256.Ví dụ. Cho tập A gồm 6 phần tử và tập B gồm 10 phần tử. Hỏia) Có bao nhiêu ánh xạ từ A vào B?b) Có bao nhiêu đơn ánh từ A vào B?Giải. a) Với mỗi phần tử x của A ta có 10 cách chọn ảnh của x (vì Bcó 10 phần tử). Theo nguyên lý nhân, ta có 106 ánh xạ.b) Giải sử A = {x1 , x2 , . . . , x6 }. Ta chia bài toán thành 6 bước:Bước 1. Chọn ảnh của x1 có 10 cách.Bước 2. Chọn ảnh của x2 có 10 − 1 = 9 cách.................Bước 6. Chọn ảnh của x6 có 10 − 5 = 5 cách.Vậy số đơn ánh là: 10 × 9 × 8 × 7 × 6 × 5 = 151200.Chương 3. Phương pháp đếmTháng 10 - 20166/37Ví dụ. Từ các chữ số 0,1,2,3,4,5 ta có thể lập được bao nhiêu số tựnhiên có ba chữ số khác nhau mà chia hết cho 2?Giải. Gọi số có ba chữ số là abc.Trường hợp 1. c = 0. Khi đóc có 1 cách chọna có 5 cách chọn ( a = X \ {0} )b có 4 cách chọn ( b = X \ {a, 0} )Trường hợp 1 có 1 × 4 × 5 = 20 số.Trường hợp 2. c = 0. Khi đóc có 2 cách chọna có 4 cách chọn ( a = X \ {c, 0} )b có 4 cách chọn ( b = X \ {a, c} )Trường hợp 2 có 2 × 4 × 4 = 32 số.Như vậy có 20 + 32 = 52 số.Chương 3. Phương pháp đếmTháng 10 - 20167/373.1.3. Nguyên lý bù trừVí dụ. Có bao nhiêu chuỗi bit có độ dài 8 hoặc được bắt đầu bằng 1hoặc được kết thúc bằng 00?Cho A và B là hai tập hữu hạn. Khi đó|A ∪ B| = |A| + |B| − |A ∩ B|Giải ví dụ trên.Số lượng chuỗi bit bắt đầu bằng 1 là 27 = 128.Số lượng chuỗi bit kết thúc bằng 00 là 26 = 64.Số lượng chuỗi bit bắt đầu bằng 1 và kết thúc bằng 00 là 25 = 32.Số lượng chuỗi bit thỏa đề bài là 128 + 64 − 32 = 160.Chương 3. Phương pháp đếmTháng 10 - 20168/37Ví dụ. Có 2 bài toán kiểm tra. Trong lớp có 30 sinh viên làm được bàithứ nhất và 20 sinh viên làm được bài thứ hai và chỉ có 10 sinh viênlàm được cả 2 bài. Biết rằng mỗi sinh viên đều làm ít nhất một bài, hỏilớp có bao nhiêu sinh viên?Giải. Ta gọiA là những sinh viên giải được bài 1B là những sinh viên giải được bài 2Khi đó A ∩ B là những sinh viên giải được cả 2 bài toán. Bài toán đặtra là tính số phần tử A ∪ B. Ta có|A ∪ B| = |A| + |B| − |A ∩ B|= 30 + 20 − 10 = 40.Như vậy lớp có 40 sinh viên.Chương 3. Phương pháp đếmTháng 10 - 20169/37|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |A ∩ C| + |A ∩ B ∩ C|Ví dụ.(tự làm) Bài kiểm tra Toán rời rạc có 3 bài. Biết rằng, mỗi sinhviên làm được ít nhất 1 bài, trong đó có20 sinh viên làm được bài 1.14 sinh viên làm được bài 2.10 sinh viên làm được bài 3.6 sinh viên giải được bài 1 và 3.5 sinh viên giải được bài 2 và bài 3.2 sinh viên giải được bài 1 và 2.1 sinh viên giải được cả 3 bài.Hỏi lớp có bao nhiêu sinh viên?Chương 3. Phương pháp đếmTháng 10 - 201610/373.1.4. Nguyên lý Dirichlet (chuồng bồ câu)Ví dụ.Trong 1 nhóm 367 người thì có ít nhất 2 người có cùng ngày sinh.Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1chuồng có 3 con bồ câu trở lên.Định nghĩa. Giá trị trần của x, ký hiệu là x , là số nguyên nhỏnhất mà lớn hơn hay bằng x.Ví dụ. 2.1 = 3; 1.9 = 2; 4 = 4;−1.1 = −1. −2.9 = −2; −4 = −4.Nguyên lý DirichletGiả sử có n chim bồ câu ở trong k chuồng. Khi đó tồn tại ít nhất mộtnchuồng chứa từbồ câu trở lên.kChương 3. Phương pháp đếmTháng 10 - 201611/37Ví dụ. Trong 100 người thì có ít nhất100= 9 cùng tháng sinh.12Ví dụ. Chứng minh rằng trong 10 số tự nhiên bất kỳ luôn chọn đượchai số có hiệu chia hết cho 9.Giải. Khi chia 10 số bất kỳ cho 9 ta sẽ có mỗi số có một số dư trong 9số dư: 0, 1, 2, . . . , 7, 8. Do đó theo nguyên lý Dirichlet phải tồn tại ítnhất hai số có cùng số dư. Khi đó hiệu của hai số đó sẽ chia hết cho 9.Ví dụ. Trong một lớp học phải có ít nhất bao nhiêu học sinh để có ítnhất 6 học sinh có cùng thứ bậc học tập, biết rằng có 5 loại thứ bậcA, B, C, D và E?Giải. Gọi số học sinh của lớp là N . Theo nguyên lý Dirichlet ta cóN5 = 6. Khi đó25 < N ≤ 30.Do đó ta chọn N = 26. Vậy lớp phải có ít nhất 26 học sinh.Chương 3. Phương pháp đếmTháng 10 - 201612/373.2. Giải tích tổ hợp1Hoán vị2Chỉnh hợp3Tổ hợpChương 3. Phương pháp đếmTháng 10 - 201613/373.2.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ử.Ví dụ. Cho A = {1, 2, 3}. Khi đó A có các hoán vị sau:123, 132, 213, 231, 312, 321Định lý. Số các hoán vị của n phần tử, ký hiệu Pn , làPn = n! = n × (n − 1) × (n − 2) × . . . × 1Quy ước 0! = 1.Ví dụ.(tự làm) Cho X = {1, 2, 3, 4, 5}. Hỏi có bao nhiêu số tự nhiêngồm 5 chữ số khác nhau được tạo từ tập X?Chương 3. Phương pháp đếmTháng 10 - 201614/37Ví dụ. Cần sắp xếp 5 học sinh A, B, C, D, E thành một dãy hàng dọca) Hỏi có bao nhiêu cách sắp xếp?b) Hỏi có bao nhiêu cách sắp xếp sao cho hai học sinh A và B luônđứng ở hai đầu hàng ?Giải. a) Để xếp 5 học sinh theo một dãy hàng dọc ta chỉ cần xếp 5 họcsinh theo thứ tự. Vậy có P5 = 5! = 120 cách.b) Do 2 bạn A, B đứng đầu hàng nên có 2! cách xếp 2 bạn đứngđầu. Ba vị trí còn lại ta chọn 3 học sinh còn lại và xếp theo thứ tự nêncó 3! cách. Vậy theo nguyên lý nhân ta có: 2! × 3! = 2 × 6 = 12 cách.Ví dụ. Từ 6 chữ số 1, 2, 3, 4, 5, 6 có thể lập được bao nhiêu số tự nhiêngồm 6 chữ số khác nhau, trong đó có bao nhiêu số lẻ? bao nhiêu sốkhông chia hết cho 5?Chương 3. Phương pháp đếmTháng 10 - 201615/37Giải. Để có số tự nhiên có 6 chữ số khác nhau ta chọn sắp xếp 6 chữsố đã cho theo thứ tự. Nên có P6 = 6! = 720 số.Gọi x = abcdef là số có 6 chữ số khác nhau.Nếu x là số lẻ thì f ∈ {1, 3, 5} nên f có 3 cách chọn. Năm số cònlại a b c d e là hoán vị của 5 chữ số còn lại (vì đã loại đi số f ). Nêncó 5! cách chọn. Vậy theo qui tắc nhân ta có 3 × 5! = 360 số lẻTương tự như lý luận trên, ta có 5! số chia hết cho 5. Như vậy sốkhông chia hết cho 5 là 6! − 5! = 600.Ví dụ.(tự làm) Cần sắp xếp 3 sinh viên nữ và 5 sinh viên nam thànhmột hàng dọc.a) Hỏi có bao nhiêu cách sắp xếp nếu 3 sinh viên nữ luôn đứng liềnnhau ?b) Hỏi có bao nhiêu cách sắp xếp nếu sinh viên đứng đầu hàng là sinhviên nữ và sinh viên cuối hàng là sinh viên nam ?Đáp án. a) 5! × 6 × 3! = 4320 cáchb) 3 × 5 × 6! = 10800 cáchChương 3. Phương pháp đếmTháng 10 - 201616/373.2.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ợpchập k của n phần tử.Ví dụ. Cho X = {a, b, c}. Khi đó X có các chỉnh hợp chập 2 của 3 là:ab, ba, ac, ca, bc, cbĐịnh lý. Số các chỉnh hợp chập k của n, ký hiệu Akn , làAkn = n × (n − 1) × · · · × (n − k + 1) =n!(n − k)!Ví dụ. Có bao nhiêu số tự nhiên ngồm 3 chữ số khác nhau được tạothành từ 1, 2, 3, 4, 5, 6.Đáp án. A36 số.Chương 3. Phương pháp đếmTháng 10 - 201617/37Ví dụ.(tự làm) Một lớp có 15 học sinh nam và 20 nữ. Trong buổi tậptrung lớp đầu năm, giáo viên chọn 3 học sinh làm ban cán sự lớp gồm:1 lớp trưởng, 1 lớp phó và 1 thủ quỹ.a) Hỏi có bao nhiêu cách chọn ?b) Hỏi có bao nhiêu cách chọn nếu lớp trưởng là nam?c) Hỏi có bao nhiêu cách chọn nếu trong 3 bạn được chọn phải có ítnhất 1 nữ?Đáp án. a) A335b) 15 × A234c) A335 − A315Chương 3. Phương pháp đếmTháng 10 - 201618/373.2.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ầntử của A được gọi là một tổ hợp chập k của n phần tử.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}Định lý. Số tổ hợp chập k của n phần tử, kí hiệuCnk =nkhay Cnk , làAknn!=k!k!(n − k)!Ví dụ. Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn?10 cách.Đáp án. C30Chương 3. Phương pháp đếmTháng 10 - 201619/37Ví dụ.(tự làm) Cho 20 điểm khác nhau nằm trên mặt phẳng, không cóbất cứ 3 điểm nào trong số đó thẳng hàng. Hỏi có thể lập được baonhiêu tam giác, tứ giác có đỉnh là một trong các điểm đã cho?3 tam giácĐáp án. C204 tứ giácC20Ví dụ.(tự làm) Một lớp có 40 sinh viên gồm 25 nam và 15 nữ. Ta cầnchọn ra 6 sinh viên tham gia hội nghị của trường. Hỏi có bao nhiêucách chọn nếu:a) Không phân biệt nam nữ ?b) Có 4 nam và 2 nữ ?c) Có ít nhất là 4 sinh viên nam ?6Đáp án. a) C404 × C2b) C25154 × C2 + C5 × C1 + C6 × C0c) C251525152515Chương 3. Phương pháp đếmTháng 10 - 201620/37Ví dụ.(tự làm) Cho T = {a, b, c, d, e, f, g, h, i, j, k}. Ký hiệu |X| để chỉsố phần tử của tập hợp X.a) T có bao nhiêu tập hợp con A thỏa |A| = 6?b) T có bao nhiêu tập hợp con A thỏa |A| = 6 và d ∈ A?c) T có bao nhiêu tập hợp con A thỏa |A| = 6 và d ∈/A6Đáp án. a) C115b) C106 − C5c) C1110Ví dụ.(tự làm) Có bao nhiêu cách sắp xếp 5 bác sĩ, 4 kỹ sư, 3 luật sưvào một bàn dài có 12 chỗ ngồi (được đánh số từ 1 đến 12) trong mỗitrường hợp sau:a) không có điều kiện gì thêm?b) các đồng nghiệp ngồi cạnh nhau?c) các bác sĩ ngồi cạnh nhau ở một đầu bàn, còn các kỹ sư, luật sưngồi xen kẻ ở đầu bàn còn lại?Đáp án. a) 12! b) 3! × 5! × 4! × 3! c) 2 × 5! × 4! × 3!Chương 3. Phương pháp đếmTháng 10 - 201621/37Ví dụ.(tự làm) Có bao nhiêu số tự nhiên N = abcdef gh gồm 8 chữ sốhệ thập phân a, b, c, d, e, f, g, h thỏa các điều kiện a lẻ, b = 4, g > 6, hchia hết cho 3 và c, d, e, f tùy ý ?Đáp án. 5 × 1 × 104 × 3 × 4Ví dụ.(tự làm) Có bao nhiêu cách sắp 7 nam và 6 nữ thành 1 hàngdọc mà nam và nữ đứng xen kẽ ?Có bao nhiêu cách sắp 6 nam và 6 nữ thành 1 hàng dọc mà nam và nữđứng xen kẽ ?Có bao nhiêu cách sắp 6 nam và 6 nữ thành 1 hàng dọc mà 6 namđứng gần nhau ?Có bao nhiêu cách sắp 7 nam và 6 nữ thành 1 hàng dọc mà 7 namđứng gần nhau và 6 nữ đứng gần nhau ?Đáp án. 7! × 6!6! × 6! + 6! × 6!6! × 7 × 6!Chương 3. Phương pháp đếm2! × 7! × 6!Tháng 10 - 201622/37Ví dụ.(tự làm) Từ 9 sinh viên nam và 8 sinh viên nữ, ta muốn chọn ramột đội gồm 10 người sao cho trong đội đó có ít nhất 4 nam và 4 nữ.Hỏi có bao nhiêu cách chọn ?Đáp án. C94 × C86 + C95 × C85 + C96 × C84Ví dụ.(tự làm) Cho S = {1, 2, . . . , 9, 10}.a) Có bao nhiêu tập hợp con ?b) Có bao nhiêu tập hợp con mà mỗi tập có đúng 5 phần tử ?c) Có bao nhiêu tập hợp con mà mỗi tập có không quá 4 phần tử ?Đáp án. a) 2105b)C100 + C1 + C2 + C3 + C4c) C1010101010Ví dụ.(tự làm) Từ 9 nam và 11 nữ, ta muốn chọn ra một đội văn nghệgồm 10 người sao cho số nam và số nữ trong đội chênh lệch nhau khôngquá 2. Hỏi có tất cả bao nhiêu cách chọn đội?6 + C5 × C5 + C6 × C4Đáp án. C94 × C11911911Chương 3. Phương pháp đếmTháng 10 - 201623/37Ví dụ.(tự làm) Từ các chữ số 1, 2, 3, 4, 5, 6, 7 và 8, ta có thể tạo raa) bao nhiêu số tự nhiên có 4 chữ số khác nhau?b) bao nhiêu số tự nhiên có 3 chữ số khác nhau trong đó có chữ số 5?Đáp án. a) A48b) A38 − A37Ví dụ.(tự làm) Có 3 luật sư, 4 bác sĩ và 5 kỹ sư xếp thành một hàngdọc sao cho các đồng nghiệp phải đứng cạnh nhau. Hỏi có tất cả baonhiêu cách xếp? Nếu yêu cầu thêm các luật sư không đứng ở đầu hàngthì có tất cả bao nhiêu cách xếp ?Đáp án. 3! × 3! × 4! × 5!2 × 2! × 3! × 4! × 5!Chương 3. Phương pháp đếmTháng 10 - 201624/373.3. Tổ hợp lặp1Hoán vị lặp2Chỉnh hợp lặp3Tổ hợp lặp4Khai triển lũy thừa của đa thứcChương 3. Phương pháp đếmTháng 10 - 201625/37