Bài giảng môn Toán tin - Chương 4: Phép đếm

Bài giảng môn "Toán tin - Chương 4: Phép đếm" trình bày các nội dung: Các nguyên lý của phép đếm, giải tích tổ hợp, hoán vị lặp, tổ hợp lặp. Hi vọng đây sẽ là một tài liệu tham khảo hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu tham khảo phục vụ học tập và nghiên cứu.
Nội dung trích xuất từ tài liệu:
Bài giảng môn Toán tin - Chương 4: Phép đếm1. Các nguyên lý2. Giải tích tổ hợp3. Hoán vị lặp, tổ hợp lặp1. 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àmKhi đó số cách làm công việc A là n+mVí dụ : Danh bạ điện thoại có 3 số ở sim 1. 5 số ở sim 2.Vậy có bao nhiêu cách để gọi một số bất kỳ từ danh bạtrên ?Cho A1, A2,.., An là các tập hữu hạn, không giao nhau từng đôi một. Khi đó :  n  n N UA    N ( Ai ) i  i 1  i 1 Company Logo2. Nguyên lý nhânGiả 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àmKhi đó số cách làm công việc A là n.mVí dụ: A B C Có 3.2 =6 con đường đi từ A đến CVí 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 2Giải. Gọi số có 3 chữ số là abcTH1 . c=0. Khi đó c có 1 cách chọn TH1 có 1.4.5 =20 a có 5 cách chọn ( aX{0} ) b có 4 cách chọn ( bX{a, 0} )TH2 . c≠0. Khi đó TH2 có 2.4.4 =32 c có 2 cách chọn a có 4 cách chọn ( aX{c, 0} ) Vậy có 20+32 =52 b có 4 cách chọn ( bX{a, c} ) Một hệ thống yêu cầu đăng ký password dạng như sau :  Từ 4 – 8 chữ cái  Phân biệt chữ hoa và thường Hỏi ?  Có bao nhiêu passwords có thể ?  Sử dụng nguyên lý gì ?  Nếu password có 4 ký tự thì tỷ lệ phần trăm là bao nhiêu ?Gọi Pi là tập hợp các password gồm i chữ cái. Và P là tập hợptất cả các passwords có thể P  P4  P5  P6  P7  P8 8Ta có Pi rời nhau : | P |  | Pi | i 4Với mỗi Pi ta có 52 chữ cái (26 hoa và 26 thường). Ta có : 52iTập hợp tất cả passwords có thể : 524 + 525 + 526 + 527 + 5283. Nguyên lý chuồng bồ câu (Derichlet) Giả sử có n chim bồ câu ở trong k chuồng đặt vào k hộp.Khi đó tồn tại ít nhất một chuồng chứa từ  n / k  bồ câu trở lên,trong đó  n / k  là số nguyên nhỏ nhất lớn hơn hay bằng n/k. 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ày4. Nguyên lý bù trừ.Cho A và B là hai tập hữu hạn. Khi đó |A  B|= |A|+|B| - |A  B| A AB B  Định nghĩa : Cho A1, A2,.., An là các tập hữu hạn. Khi đó : n nN ( Ai )   N ( Ai )   N ( A  A )   N ( A  A  A )  ...  i j i j k i 1 i 1 1i  j  n 1i  j  n n(1) n 1 N ( Ai i 1 C AC BC ABC A B AB|A  B  C|=?Ví dụ. Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS họcTiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh họcTiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu ngườiGọ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 AnhKhi đó. 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=351. Hoán vị : 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)…1 Quy ước 0! =1Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau abc, acb, bac, bca, cab, cba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ồm5 chữ số khác nhau được tạo từ tập X?2. Chỉnh hợp : Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm kphầ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ử. kSố các chỉnh hợp chập k của n ký hiệu là An- Công thức n! A  k n  n  k ! Ví dụ : Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2của 3 là: ab, ba, ac, ca, bc, cb. Ví dụ. Có bao nhiêu số tự nhiên gồm 3 chữ số được tạothành từ 1,2,3,4,5,6. Kết quả: A633.Tổ hợp : 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ử. k n Số tổ hợp chập k của n phần tử được kí hiệu là C hay   n   k n! C  k ...