Bài giảng Toán rời rạc: Chương 3 Một số công thức tổ hợp cung cấp cho người học những kiến thức như: Đánh giá số điện thoại nhiều nhất có thể có trong Hà Nội; Xác định số mật khẩu, mỗi mật khẩu gồm sáu, bảy, hoặc tám ký tự; mỗi ký tự có thể chữ hoặc số; mỗi mật khẩu chứa ít nhất một chữ; Một số công thức tổ hợp; .Mời các bạn cùng tham khảo! | TOÁN RỜI RẠC DISCRETE MATHEMATICS Bùi Thị Thủy Đặng Xuân Thọ Support 2 Full name Đặng Xuân Thọ Mobile Email thodx@ Website http tho Toán Rời Rạc - ĐHSPHN NỘI DUNG 3 Chương 1. Logic mệnh đề Chương 2. Lý thuyết tập hợp Chương 3. Một số công thức tổ hợp Chương 4. Suy luận và kiểm chứng chương trình Chương 5. Đại số Boole và cấu trúc mạch logic Chương 6. Thuật toán Chương 7. Lý thuyết đồ thị Toán Rời Rạc - ĐHSPHN Chương 3. Một số công thức tổ hợp 4 Đánh giá số điện thoại nhiều nhất có thể có trong Hà Nội. Xác định số mật khẩu mỗi mật khẩu gồm sáu bảy hoặc tám ký tự mỗi ký tự có thể chữ hoặc số mỗi mật khẩu chứa ít nhất một chữ. Một số công thức tổ hợp Chỉnh hợp Hoán vị Hoán vị trên đường tròn Toán Rời Rạc - ĐHSPHN 5 Cơ sở của phép đếm Toán Rời Rạc - ĐHSPHN Cơ sở của phép đếm 6 Phần này chúng ta chỉ giải quyết xác định lực lượng của tập hợp hữu hạn. Nếu tập hợp A là tập hợp hữu hạn thì lực lượng của nó là số lượng phần tử của nó ký hiệu là . Định lý Nếu Ai i 1 2 .n là một phân hoạch của tập hợp A thì ta có 1 . Toán Rời Rạc - ĐHSPHN Số phần tử của tích Đêcac 7 Ví dụ Cho tập hợp A a b . Tìm tất cả các dãy ký tự có ba phần tử được tạo thành từ A aaa aab bbb bba abb baa aba bab Định lý cho trước các tập hợp hữu hạn Ai i 1 . k trong đó tập hợp Ai có đúng ni phần tử. Khi đó tích Đêcac A1 x A2 x x Ak có đúng n1n2 nk phần tử. Nghĩa là 1 2 1 2 Đặc biệt ta có Toán Rời Rạc - ĐHSPHN Số phần tử của tích Đêcac 8 Ví dụ Có bao nhiêu số tự nhiên có chín chữ số mà trong biểu diễn thập phân của nó không có mặt chữ số nào trong tập hợp 0 3 7 9 Mỗi số tự nhiên có chín chữ số không được viết bởi các chữ số 0 3 7 9 là một dãy chín kí tự có lặp của tập hợp 1 2 4 5 6 8 . 69 Toán Rời Rạc - ĐHSPHN 9 Hai nguyên lý cơ bản Toán Rời Rạc - ĐHSPHN Cơ sở của phép đếm 1 2 10 Nguyên lý cộng Giả sử có các công đoạn E1 E2 Ek. Để thực hiện E ta chỉ cần thực hiện một trong những Ei i trong đó số cách thực hiện Ei là ni. Khi đó số cách thực hiện E là n1 n2 nk. Ví
