Bài giảng "Toán rời rạc: Đếm các phần tử" cung cấp cho người học các kiến thức: Các nguyên lí cơ bản; hoán vị và tổ hợp; hệ số nhị thức, nguyên lý lồng chim bồ câu, thuật toán chia để trị, thuật toán quy hoạch động. Mời các bạn cùng tham khảo. | Đếm các phần tử Các nguyên lí cơ bản Hoán vị và tổ hợp Hệ số nhị thức Nguyên lý lồng chim bồ câu Thuật toán chia để trị Thuật toán quy hoạch động Lý thuyết tổ hợp Lý thuyết tổ hợp là một phần quan trọng của toán rời rạc chuyên nghiên cứu sự sắp xếp các đối tượng. Liệt kê đếm các đối tượng có những tính chất nào đó. Đếm các phần tử xuất hiện nhiều trong toán học cũng như tin học được dùng để giải quyết nhiều vấn đề cũng như được dùng nhiều khi tính xác suất của các biến cố. Ví dụ cần đếm số cách khác nhau đặt mật khẩu thỏa mãn các điều kiện Độ dài ít nhất 6 ký tự và không vượt quá 8 ký tự và mỗi ký tư lấy từ tập 0 . 9 a . z Tạo ra một cách sắp xếp các đối tượng thỏa mãn tính chất nào đó. Ví dụ xây dựng thời khóa biểu lịch thi hay phương án sản xuất Các nguyên lí cơ bản của phép đếm 1 Quy tắc cộng Quy tắc cộng Giả sử có hai công việc. Việc thứ nhất có thể làm bằng 1 cách việc thứ hai có thể làm bằng 2 cách khi đó có 1 2 cách làm một trong hai công việc đó. Ví dụ Cần chọn một đại biểu là nam sinh viên có điểm trung bình từ trở lên hoặc là nữ sinh viên có điểm trung bình từ trở lên. Biết rằng có 20 sinh viên nam thỏa mãn tiêu chuẩn 25 nữ sinh viên thỏa mãn tiêu chuẩn. Như vậy có 20 25 cách chọn đại biểu. Quy tắc này có thể phát biểu dưới dạng ngôn ngữ tập hợp như sau Nếu 1 2 là các tập rời nhau khi đó số phần tử của hợp các tập này bằng tổng số các phần tử của các tập thành phần. 1 2 1 2 Các nguyên lí cơ bản của phép đếm 2 Quy tắc nhân Quy tắc nhân Giả sử có một nhiệm vụ được tách ra làm hai công việc. Việc thứ nhất có thể làm bằng 1 cách việc thứ hai có thể làm bằng 2 cách khi đó có 1 2 cách làm nhiệm vụ đó. Ví dụ Cần chọn hai đại biểu một là nam sinh viên có điểm trung bình từ trở lên và một là nữ sinh viên có điểm trung bình từ trở lên. Biết rằng có 20 sinh viên nam thỏa mãn tiêu chuẩn 25 nữ sinh viên thỏa mãn tiêu chuẩn. Như vậy có 20 25 cách chọn đại biểu. Quy tắc này có thể phát biểu dưới dạng ngôn ngữ tập hợp như sau Chọn một phần tử của tích .
