Xem mẫu
- 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ì:
|AB| = |A| + |B| - |AB|
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 |
1i n
1i j n
| Ai Aj |
1i j k n
| Ai Aj Ak | .. (1)n1 | 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.
nguon tai.lieu . vn