tailieunhanh - Bài giảng Toán rời rạc: Chương 3 - Dr. Ngô Hữu Phúc

Bài giảng Toán rời rạc: Chương 3 Bài toán đếm, cung cấp cho người đọc những kiến thức như: Giới thiệu bài toán; Nguyên lý Bù trừ; Biến đổi về bài toán đơn giản; Quan hệ giữa tập hợp và dãy nhị phân; Hệ thức truy hồi. Mời các bạn cùng tham khảo! | TOÁN RỜI RẠC CHƯƠNG 3 BÀI TOÁN ĐẾM Lecturer PhD. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@ 1 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University NỘI DUNG . Giới thiệu bài toán. . Nguyên lý Bù trừ. . Biến đổi về bài toán đơn giản. . Quan hệ giữa tập hợp và dãy nhị phân. . Hệ thức truy hồi. . Bài tập. 2 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Giới thiệu bài toán 1 3 Với một tập hợp nào đó cần đếm số phần tử trong tập đó. Sử dụng công thức toán học để biểu diễn. Nói chung để đếm thường đưa về dạng đã biết nhờ thiết lập quan hệ 1-1 giữa chúng. Để đếm có thể sử dụng nguyên lý cộng nguyên lý nhân hay nguyên lý bù trừ. 3 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Giới thiệu bài toán 2 3 Ví dụ 1 Có bao nhiêu cách xếp 5 người đứng thành một hàng ngang sao cho A không đứng cạnh B Giải Đếm số cách xếp A đứng cạnh B. Xem A và B như một vị trí ta có 4 24 cách xếp. Số này cần được nhân 2 vì A có thể đứng bên trái cũng như bên phải B nên số cách là 48. Mặt khác tổng số cách xếp 5 người thành một hàng ngang là 5 120 cách. Vậy số cách mà A không đứng cạnh B là 120 - 48 72 cách. 4 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Giới thiệu bài toán 3 3 Ví dụ 2 Trên tờ xổ số có Phần đầu gồm 2 chữ cái lấy từ A đến Z 26 chữ cái và Phần sau gồm 4 chữ số lấy từ 0 đến 9 10 chữ số . Hỏi xác suất để trúng giải độc đắc là bao nhiêu Giải Số tờ có thể phát hành 262 x 104 6 760 000. Xác suất để trúng giải độc đắc là nếu có 1 tờ độc đắc 1 6 760 000 1 48 10-7 5 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Nguyên lý Bù trừ 1 9 . Giới thiệu về nguyên lý bù trừ Giả sử có 2 tập A và B khi đó Số các phần tử trong hợp của hai tập A và B được tính Tổng các phần tử của tập A và tập B Trừ số phần tử của giao tập A và B. Công thức N A B N A N B - N A B . 6 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Nguyên lý Bù trừ