Bài giảng Toán rời rạc: Phép đếm - Nguyễn Thành Nhựt

Bài giảng này cung cấp cho người học những kiến thức về phép đếm. Chương này trình bày những nội dung chính sau: Một số nguyên lý cơ bản của phép đếm, giải tích tổ hợp, hoán vị lặp, tổ hợp lặp, và hệ thức đệ qui. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Phép đếm - Nguyễn Thành Nhựt LOGO2 ChươngTOÁN RỜI RẠCChương 2. Phép đếm 1Nộ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 2I. Các nguyên lý1. Nguyên lý cộngGiả 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ụ. 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 Phép đếmI. Các nguyên lý2. 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 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 2Giải. Gọi số có 3 chữ số là abcTH1 . c=0. Khi đó c có 1 cách chọn a có 5 cách chọn ( a∈X\{0} ) TH1 có 1.4.5 =20 b có 4 cách chọn ( b∈X\{a, 0} )TH2 . c≠0. Khi đó c có 2 cách chọn a có 4 cách chọn ( a∈X\{c, 0} ) TH2 có 2.4.4 =32 b có 4 cách chọn ( b∈X\{a, c} ) 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  x  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 ítnhất một chuồng chứa từ n / k  bồ câu trở lên.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 6I. Các nguyên lýVí dụ. Cho tập X ={1,2,3,4,5,6,7,8,9}. Lấy A là tập hợp concủ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. 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 7I. Các nguyên lý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| A A∩B B 8I. Các nguyên lý C A∩C B∩C A∩B∩C A B A∩B |A ∪ B ∪ C|=? 9I. Các nguyên lý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ườiGiả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 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=35 10II. Giải tích tổ hợp1. 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! =1Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau abc,acb, bac,bca, cab,cba 11Ví dụ. Nếu A là tập hợp n phần tử thì số song ánh từ A vàoA 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 5! 12 II. Giải tích tổ hợp2. 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 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ử. k ASố các chỉnh hợp chập k của n ký hiệu là n- 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 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ạothành từ 1,2,3,4,5,6. Kết quả: A63 14 II. Giải tích tổ hợp3.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ử. 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 k !( n − k )! n Tính chất C n−k n =C k n Cnk + Cnk −1 = Cnk+1 15 II. Giải tích tổ hợpVí dụ. Cho X = {1,2,3,4}. Tổ hợp chập 3 của 4 phần tử củaX 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 10 - Số cách chọn là tổ hợp chập 10 của 30. C30 16III. Hoán vị lặp, tổ hợp lặp1. 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, n! n2 đối tượng giống nhau thuộc loại 2,n, n1 !n2 !...nk ! nk đối tượng giống nhau thuộc loại k, là 17 II. Giải tích tổ hợpVí dụ. Có bao n ...