Giới thiệu Phương pháp đếm

Chương III: Phép đếm Mục Lục : Phát biểu: Nếu một công việc có thể thực hiện bằng một trong hai phương án lọai trừ lẫn nhau: phương án thứ nhất có m cách thực hiện và phương án thứ hai có n cách thực hiện. Khi đó công việc đó có m+n cách thực hiện Theo thuật ngữ của nguyên lí tập hợp : - Nếu A, B là các tập hợp không giao nhau thì |A  B| = |A| +|B| Chứng minh Ví dụ 1: Chúng ta cần chọn một sinh viên UIT toán năm thứ 3 hay năm thứ 4 đi dự một hội nghị. Hỏi có bao nhiêu cách chọn lựa một sinh viên như thế biết rằng có 100 sinh viên toán học năm thứ 3 và 85 sinh viên toán học năm thứ tư ? Ví Dụ Nguyên lý cộng Lời giải : Ta có thể thực hiện một trong 2 việc chọn lựa khác nhau: chọn một sinh viên toán năm 3, hoặc chọn một sinh viên toán năm 4. Để thực hiện công việc thứ nhất ta có 100 cách, và để thực hiện công việc thứ 2 ta có 85 cách. Vậy để chọn một sinh viên toán theo yêu cầu ta có 100+85 = 185 cách. Ví dụ 2: 1 thầy giáo có thể chọn người hẹn hò từ ba danh sách, danh sách 1: gồm 10 cô có chiều cao trên 1m65 t , danh sách 2:có 5 cô trình độ cao đẳng trở lên , danh sách 3 :3 cô có «điều kiện».Hỏi bao có bao nhiêu cách chọn người hẹn hò. Ví dụ nguyên lý cộng Lời giải: Rõ ràng việc chọn người hẹn hò từ 3 danh sách là ko đồng thời(nếu dc thì tôi cũng đã làm rồi).áp dụng quy tắc cộng ta được: Có 10 + 5 + 3=18 cách chọn Vậy theo thầy nghĩ sao , còn các bạn nghĩ sao II.Nguyên lý nhân Phát biểu: Giả sử công việc nào đó được chia thành k giai đọan thực hiện: Giai đọan 1: có n1 cách thực hiện Giai đọan 2: có n2 cách thực hiện …………. Giai đọan k: có nk cách thực hiện Khi đó, số cách thực hiện cả công việc là: n1.n2…nk II.Nguyên lý nhân Nguyên lý nhân trên tập hợp: - Cho A và B là 2 tập hợp hữu hạn rời nhau. Khi ấy ta có: |AxB|=|A|.|B| - Một cách tổng quát: Nếu A1, A2, ..., An là các tập hợp hữu hạn thì số phần tử của tích Descartes của các tập hợp trên bằng tích của các số lượng phần tử của các tập hợp trên: | A1 x A2 x . . . x An | = | A1 | . | A2 | . . . . . | An | Chứng minh Ví dụ 4:đi từ A đến B có 3 con đường, đi từ B đến C có 2 con đường . Hỏi muốn đi từ A đến C có mấy con đường? Ví dụ Nguyên lý nhân Lời giải. Từ A đến C có 2 giai đoạn,A-> B và B-> C, theo quy tắc nhân ta có : số con đường đi từ A đến C là :n=2x3=6 Ví dụ 1: Các ghế ngồi trong một hội trường sẽ được ghi nhãn gồm một mẫu tự và một số nguyên dương không lớn hơn 100. Hỏi số ghế tối đa có thể được ghi nhãn khác nhau là bao nhiêu? Ví dụ Nguyên lý nhân Lời giải. Thủ tục ghi nhãn cho một ghế gồm 2 việc : ghi một trong 26 mẫu tự và kế tiếp là ghi một trong 100 số nguyên dương. Qui tắc nhân cho thấy có 26 x 100 = 2600 cách khác nhau để ghi nhãn cho một ghế ngồi. Do đó số ghế lớn nhất có thể được ghi nhãn khác nhau là 2600. Ví dụ 5: Có bao nhiêu ánh xạ đi từ một tập hợp gồm m phần tử vào một tập hợp gồm n phần tử ? Ví dụ Nguyên lý nhân Lời giải. Một ánh xạ đi từ tập A gồm m phần tử vào một tập hợp B gồm n phần tử tương ứng với việc chọn lựa một trong n phần tử của B cho mỗi phần tử của A. Do đó, theo qui tắc nhân, có n.n. ... .n = nm ánh xạ từ A vào B. III.Nguyên lý bù trừ Phát biểu: Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. III.Nguyên lý bù trừ 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? Ví dụ Nguyên lý bù trừ Lời giải: Gọi A là những học sinh học tiếng Pháp. Gọi B là những học sinh học tiếng Anh. Khí đó số học sinh học 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 Nguyên lý chim bồ câu Mệnh đề:nếu có k+1 con chim(hoặc nhiều hơn ) đồ vật được đặt trong k hộp thì tồn tại một hộp có ít nhất hai đồ vật Mở đầu : Giả sử có một đàn chim bay vào chuồng .Nếu số chim nhiều hơn sống ngăn chuồng thì ít nhất trong một ngăn có nhiều hơn một con chim Nguyên lý Dirichlet tổng quát Mệnh đề nếu có n đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất ]n/k[ Ví dụ: Trong 100 người có ít nhất 9 người sinh cùng 1 tháng Ví dụ 1: trong 367 người thế nào cũng có ít nhất có hai người cùng sinh nhật bởi vì chỉ có 366 người có sinh nhật khác nhau Ví dụ Nguyên lý chim bồ câu Vd: có 5 loại học bổng khác nhau. Hỏi rằng cần bao nhiêu sinh viên để có ít nhất 6 người cùng loại học bổng Ví dụ Nguyên lý chim bồ câu Lời giải: Gọi n là số sinh viên, Ta có n/5=6  5<n/5<= 6  n =26 vậy để có 6 người cùng loại học bổng thì cần có 25 sinh viên. Bài tập nâng cao