zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Elysale Elysale | Ngày: | Loại File: PDF | Số trang:42

Báo xấu

32
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

GV: Ths. Võ Văn Phúc Email: Vphucvo@gmail.com
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
1.1 Những cơ sở của phép đếm 1.1.1 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.
1.1 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.
1.1 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
1.1 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
1.1 Những cơ sở của phép đếm 1.1.1 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à n1.n2…nk cách.
1.1 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 số. - Số hàng đơn vị có 2 cách chọn một con số. Vậy, số các con số có 3 chữ số khác nhau, được lập từ các chữ số trên là: 3.3.2 = 18 (số).
1.1 Những cơ sở của phép đếm Ví dụ 2: Có bao nhiêu xâu nhị phân có độ dài n? - Ta có n bit ký tự trong xâu nhị phân có độ dài n. - Mỗi bit ký tự chỉ có thể là 0 hoặc 1. Số cách chọn cho một bit ký tự là 2. - Theo nguyên lý nhân, ta có tổng cộng 2n xâu nhị phân khác nhau có độ dài bằng n.
1.1 Những cơ sở của phép đếm  Nhận xét: Nguyên lý nhân được phát biểu bằng ngôn ngữ tập hợp như sau:  Nếu A1, A2, …,Ak là các tập hợp hữu hạn, khi đó ta có: | A1  A2  ..  Ak || A1 | . | A2 | ... | Ak |
1.1 Những cơ sở của phép đếm Ví dụ: Đoạn mã tính giá trị m theo nguyên lý nhân như sau: Kết quả: m=n1.n2…nk
1.1 Những cơ sở của phép đếm Một số ví dụ về nguyên lý nhân: Ví dụ 1. Đếm số chỉnh hợp không lặp. Một chỉnh hợp không lặp chập k của n phần tử là một bộ có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các phần tử không được phép lặp lại.  Lời giải.  Để xây dựng các chỉnh hợp không lặp ta xây dựng từ thành phần đầu tiên, thành phần này có n cách lựa chọn.  Ứng với mỗi cách lựa chọn của thành phần đầu tiên ta xây dựng tiếp thành phần thứ 2, thành phần này có (n-1) cách lựa chọn.  Tương tự như vậy, thành phần thứ k có (n-k+1) cách lựa chọn. Như vậy, theo nguyên lý nhân số các chỉnh hợp không lặp chập k của n phần tử là: n! n(n-1)(n-2)..(n-k+1) =( (n  k )! )
1.1 Những cơ sở của phép đếm Ví dụ 2. Đếm số chỉnh hợp lặp. Một chỉnh hợp lặp chập k của n phần tử là một bộ có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các phần tử được phép lặp lại.  Lời giải. Gọi |A|=n là số cách chọn một phần tử trong k phần tử lấy từ bộ n phần tử. Số cách chọn bộ k phần tử theo nguyên lý nhân là tích đề các: |A||A|..|A| với k lần. Ta có số cách là: |A||A|..|A| = |Ak|= nk.
1.1 Những cơ sở của phép đếm 1.1.2 Nguyên lý bù trừ  Nguyên lý bù trừ là một mở rộng của nguyên lý cộng đã được trình bày trong mục 1.1.1. Trong nguyên lý này, nếu không có giả thiết về tính rời nhau của các tập hợp thì: |AB| = |A| + |B| - |AB|  Tổng quát, giả sử A1, A2,..,An là các tập hợp hữu hạn. Khi đó, | A1  A2  ..  An |  | Ai |  1i  n  1i j  n | Ai  Aj |   1i j  k  n | Ai  Aj  Ak | ..  (1)n1 | A1  A2 ..  An |
1.1 Những cơ sở của phép đếm Ví dụ: Có tất cả 52 sinh viên. Trong đó có 11 sinh viên học tiếng Anh; 10 sinh viên học tiếng Pháp; 12 sinh viên học tiếng Nga; 7 sinh viên học hai thứ tiếng Anh và Pháp; 4 sinh viên học học hai thứ tiếng Pháp và Nga; 2 sinh viên học hai thứ tiếng Nga và Anh. Có duy nhất 1 sinh viên học cả ba thứ tiếng trên. Hỏi có bao nhiêu sinh viên không học thứ tiếng nào trong các thứ tiếng trên?
1.1 Những cơ sở của phép đếm  Giải: Gọi A1, A2, và A3 lần lượt là các tập hợp các sinh viên học tiếng Anh, Pháp, và Nga. Khi đó ta có:  |A1|=11, |A2|=10, |A3|=12 (số sinh viên học 1 thứ tiếng)  |A1  A2|=7, |A2  A3|=4,|A1  A3|=2 (số sinh viên học 2 thứ tiếng)  |A1  A2  A3|=1 (số sinh viên học 3 thứ tiếng) Khi đó số sinh viên có học một trong các thứ tiếng trên là: | A1  A2  A3 |=21 Do đó, số sinh viên không học thứ tiếng nào trong các thứ tiếng trên là: 52-21=31
1.2 Nguyên lý Dirichlet 1.2.1 Mở đầu Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì có ít nhất một ngăn có nhiều hơn một con chim bồ câu. Ta có mệnh đề sau: Mệnh đề: Nếu có k+1 (hoặc nhiều hơn) đồ vật được đặt vào trong k hộp thì tồn tại một hộp có ít nhất hai đồ vật.
1.2 Nguyên lý Dirichlet Chứng minh mệnh đề: Giả sử không có hộp nào trong k hộp chứa nhiều hơn một đồ vật. Khi đó, tổng số vật được chứa trong các hợp nhiều nhất là bằng k. Điều này trái giả thiết là có ít nhất k+1 vật.
1.2 Nguyên lý Dirichlet  Ví dụ 1: Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất 2 người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh khác nhau.  Ví dụ 2: Trong kỳ thi học sinh giỏi, điểm bài thi được đánh giá bởi một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất có bao nhiêu học sinh dự thi để cho chắc chắn tìm được hai học sinh có kết quả giống nhau? Theo nguyên lý Dirichlet, số học sinh cần tìm là 102, vì ta có 101 kết quả điểm thi khác nhau.

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.