tailieunhanh - Bài giảng Toán rời rạc 1: Chương 3 - ThS. Võ Văn Phúc

Bài giảng Toán rời rạc 1: Chương 3 Phép đếm cung cấp cho người học những kiến thức như: Những cơ sở của phép đếm; Nguyên lý Dirichlet; Chỉnh hợp và tổ hợp suy rộng. Mời các bạn cùng tham khảo để nắm chi tiết nội dung bài giảng! | GV Ths. Võ Văn Phúc Email Vphucvo@ CHƯƠNG III PHÉP ĐẾM 1. Những cơ sở của phép đếm 2. Nguyên lý Dirichlet 3. Chỉnh hợp và tổ hợp suy rộng Những cơ sở của phép đếm Các nguyên lý đếm a. Nguyên lý cộng Giả sử công việc a được phân thành 2 trường hợp riêng biệt T1 và T2. Công việc thứ nhất T1 thực hiện bằng n1 cách công việc thứ hai T2 thực hiện bằng n2 cách. Trong trường hợp hai việc không thực hiện đồng thời khi đó sẽ có n1 n2 cách thực hiện công việc a. Ví dụ Một lớp học có 30 sinh viên nam và 20 sinh viên nữ. Khi đó ta có 30 20 50 cách chọn 1 sinh viên. Những cơ sở của phép đếm a. Nguyên lý cộng tt Tổng quát Giả sử một công việc a được phân thành k trường hợp riêng biệt T1 T2 Tk. Công việc Ti i 1 k có thể thực hiện tương ứng bằng ni i 1 k cách và giả sử không có 2 công việc nào làm đồng thời. Khi đó số cách thực hiện công việc a là n1 n2 . nK cách. Ví dụ Một ngân hàng đề thi có 410 đề loại A 220 đề loại B và 100 đề loại C. Khi đó một sinh viên có thể chọn 1 đề thi từ ngân hàng đề thi và số cách chọn một đề thi là 410 220 100 730 cách. Những cơ sở của phép đếm Nhận xét Nguyên lý cộng có thể phát biểu bằng ngôn ngữ tập hợp như sau Giả sử A và B là hai tập hợp rời nhau. Khi đó A B A B Tổng quát nếu A1 A2 . AK là K tập hợp đôi một rời nhau. Khi đó A1 A2 . AK A1 A2 . AK Ký hiệu A là số phần tử của một tập hợp hữu hạn A Những cơ sở của phép đếm Ví dụ Tính giá trị m theo nguyên lý cộng cho đoạn mã Kết quả m n1 n2 nk Những cơ sở của phép đếm Các nguyên lý đếm tt b. Nguyên Lý nhân Giả sử một công việc a có k bước thực hiện liên tiếp T1 T2 Tk. Trong mỗi cách thực hiện bước Ti-1 có ni cách thực hiện bước Ti i 2 3 .k . Khi đó số cách thực hiện công việc a là nk cách. Những cơ sở của phép đếm b. Nguyên Lý nhân tt Ví dụ 1 Hỏi có bao nhiêu số tự nhiên gồm 3 chữ số khác nhau được lập từ các chữ số 0 1 2 3 Giải - Ta thấy số hàng trăm có 3 cách chọn một số từ các số trên vì không chọn số 0 . - Số hàng chục có 3 cách chọn một con .