BÀI 2
BÀI TOÁN ĐẾM
Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn
1
Nhắc lại
Quy tắc nhân
Quy tắc cộng
Hoán vị
Chỉnh hợp (lặp)
Tổ hợp (không lặp)
Tổ hợp lặp ???
2
Nôi dung
2.1. Ví dụ đếm cơ bản 2.2. Nguyên lý bù trừ 2.3. Hoán vị lặp 2.4. Tổ hợp lặp 2.5. Bài tập
2.1. Ví dụ đếm cơ bản
Ví dụ 2.1
4 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.1. Ví dụ đếm cơ bản
Ví dụ 2.1 (tổng quát)
A
B
5 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.1. Ví dụ đếm cơ bản
Ví dụ 2.1 (tổng quát)
A,B
--
--
n!
n-1!
n-1!
AB
BA
6 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.1. Ví dụ đếm cơ bản
Ví dụ 2.2
7 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.1. Ví dụ đếm cơ bản
Ví dụ 2.3 < kiến tha mồi>
(2 x 2)
(2 x 3)
8 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.1. Ví dụ đếm cơ bản
Ví dụ 2.3 (tổng quát)
Sang phải - 1 Đi xuống - 0
Số đoạn sang phải: n Số đoạn đi xuống: m
n
Dãy nhị phân độ dài n+m và có đúng m bit 0
Số tập con của m phần tử của tập n+m phần tử
m
9 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.2.Nguyên lý bù trừ
• A1và A2 là hai tập hưu hạn, A1 A2 ≠
N(A1 A2 ) = N(A1) + N(A2) – N(A1 A2)
A2
A1
A2
A1
N1= N(A1 ) + N(A2)
N(A1 ) + N(A2) – N(A1 A2 )
• Tổng quát: khi Ai Aj ≠ mọi i, j
•
N(A1…An) = N1 - N2 + … +(-1)n-1 Nn Nk là tổng phần tử của tất cả các giao của k tập lấy từ n tập.
N1 = N(A1) + …+ N(Am) , …. Nm= N(A1 A2 … Am).
10 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.2.Nguyên lý bù trừ
• Nguyên lý bù trừ
– Ak tính chất nào đó cho trên X – tổng số phần tử của X không thỏa mản bất cứ tính chất Ak
N(X) - N(A1A2…An)
• Ni - là tổng số phần tử của X thỏa mản i tính chất.
Tổng số phần tử thỏa mản ít nhất một tính chất Ak nào đó
11 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.2.Nguyên lý bù trừ
N(A1 A2 A3) = ?
1
A1
1
A1
1
1
2
2
0
3
1
2
A2
A3
A2
A3
1
1
1
1
1
A1
N1
N1 - N2
b)
1
1
1
1
A2
A3
1
1
N1 - N2 + N3
c)
12 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.2.Nguyên lý bù trừ
• Ví dụ 2.2.1 Hỏi tập X={1,2,…50} có bao nhiêu số không chia hết cho bất các số 2, 3, 4 ?
Ai = { x € X: x % i ==0 } i=2,3,4.
A2A3A4 là tập chia hết ít nhất 1 trong 3 số
N (X) - N(A2A3A4) = N- (N1 - N2 + N3 )
13 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.2.Nguyên lý bù trừ
Ta có: • N = 50 số. • N1 = N(A2) + N(A3) + N(A4) = [50/2] + [50/3] + [50/4] = 25 + 16 + 12 =53. • N2 = N(A2 A3) + N(A3 A4) + N(A2 A4) = [50/6] + [50/12] + [50/4] = 8 + 4 + 12 = 24. • N3 = N(A2 A3 A4) = [50/12] = 4. • Suy ra 50 – ( 53 – 24 + 4 ) = 17 số.
14 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.2.Nguyên lý bù trừ
Ví dụ 2.2.2 Có bao nhiêu xâu nhị phân độ dài 10 hoặc bắt đầu bởi
00 hoặc kết thúc bởi 11?
0
0
1
1
HD:
0
0
1
1
256 + 265 - 64 ------ 448
15 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.2.Nguyên lý bù trừ
• Ví dụ 2.2.3 (bài toán bỏ thư) Có n lá thư và n phong bì ghi sẳn địa chỉ. Bỏ ngẫu
nhiên các lá thư vào phong bì.
Hỏi xác suất để không một lá thư bỏ đúng địa chỉ.
– HD:
X – là tập hợp tất cả các cách bỏ thư. A k – là tính chất lá thư thứ k bỏ đúng địa chỉ.
16 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.2.Nguyên lý bù trừ
= N - (N1 - N2 + … +(-1)n-1 Nn )
• • N = n! • Nk - là số tất cả các cách bỏ thư sao cho có k lá thư
n (n-k)! = n!/k!
đúng địa chỉ. Nk = Ck = n! - (n!/1! – n!/2! + … +(-1)n-1 n!/n! ) = n!(1 - 1/1! +1/2! + … +(-1)n-1/n! ) • Xác suất cần tìm: 1 - 1/1! +1/2! + … +(-1)n-1/n!
17 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.2.Nguyên lý bù trừ
Ví dụ 2.2.4
Ví dụ 2.2.5< Số người tham gia tất cả khóa học>
Ví dụ 2.2.6
2.3. Hoán vị lặp
Bài toán: Số hoán vị của n pt:
– có n1 phần tử như nhau thuộc loại 1, – có n2 phần tử như nhau thuộc loại 2, – ………………………………………. , – có nk phần tử như nhau thuộc lại k.
ĐN: Một cách sắp xếp n pt trên gọi là một hoán vi
lặp.
Tổng số hoán vị lặp của n phần là:
19 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.3. Hoán vị lặp
•Ví dụ 2.3.1. SUCCESS
SUCCESS.
• 3 S • 2 C • 1 U • 1 E
7!
• C(7,3)- chọn 3 chổ cho kí tự S, còn lại 4 chổ • C(4,2) – chọn 2 chổ cho kí tự C, còn 2 chổ • C(2,1)- chọn 1 chổ cho kí tự U, còn lại 1 chổ • C(1,1)- chọn 1 chổ cho kí tự S
20 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.3. Hoán vị lặp
Ví dụ 2.3.2. MISSISSIPPI
21 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.4. Phân bố đồ vật vào túi
Ví dụ 2.3.3. Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong 4 người chơi từ một cỗ bài chuẩn 52 quân?
Tổng quát: Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau sao cho có ni vật được đặt vào trong hộp thứ i, với i = 1, 2, ..., k
2.4. Tổ hợp lặp
Cho n loại, mỗi loại có không ít hơn k phần tử:
Một tổ hợp lặp chập k từ n loại – một bộ không có thứ tự k phần tử lấy từ n loại (các phần tử có thể lặp, k >n )
Số tổ hợp lặp chập k của n loại:
23 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.4. Tổ hợp lặp
Ví dụ 2.4.1.
Đếm cách mua mâm ngũ quả từ 3 loại: Cam, Quýt, Xoài.
24 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.4. Tổ hợp lặp
Ví dụ 2.4.2.
đ 0 0 0 0 0 5
đ 0 0 0 0 5
đ 0 0 0 0 1
đ 0 0 0 0 2
đ 0 0 0 0 0 1
đ 0 0 0 5
đ 0 0 0 0 0 2
•
•
•
•
•
•
•
25 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.4. Tổ hợp lặp
đ 0 0 0
đ 0 0 0
đ 0 0 0
.
.
.
đ 0 0 0
đ 0 0 0
đ 0 0 0
.
.
.
0 0 5
0 5
0 1
0 2
0 0 1
đ 0 0 0 5
0 0 2
•
•
•
•
•
•
•
26 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.3. Tổ hợp lặp
C(7+5−1,5) = 462.
đ 0 0 0
đ 0 0 0
đ 0 0 0
.
.
.
đ 0 0 0
đ 0 0 0
đ 0 0 0
.
.
.
0 0 5
0 5
0 1
0 2
0 0 1
đ 0 0 0 5
0 0 2
•
•
•
•
•
•
•
27 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.4. Tổ hợp lặp
Ví dụ 2.4.3
Phương trình x1 + x2 + x3 = 15 với x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0.
Loai 2 x2≤15
Loại 3 x3≤15
Loai 1 x1≤15
C(3+15−1, 15) = C(3+15−1, 2) = 136
28 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.4. Tổ hợp lặp
Ví dụ 2.4.4- 2.3.6
Ví dụ 2.4.4: x1 + x2 + x3 = 12 với x1 ≥ 1 , x2 ≥ -2 , x3 ≥3 .
Ví dụ 2.4.5: x1 + x2 + x3 ≤ 12 với x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 .
Ví dụ 2.4.6: x1 + x2 + x3 = 11 với 3 ≥ x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 .
29 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.3. Tổ hợp lặp
• Ví dụ 2.4.4: Đặt:
`x1 = x1 – 1 ≥ 0, `x2 = x2 + 2 ≥ 0 , `x3 = x3 -3 ≥ 0,
Bài toán gốc tương đương:
`x1 + `x2 + `x3 = 10 với `x1 ≥ 0 , `x2 ≥ 0 , `x3 ≥0 . Kết quả: C(3+10−1, 10) = C(3+10−1, 2) = 66.
30 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.4. Tổ hợp lặp
Giải Ví dụ 2.4.5: • Đặt ẩn phụ x4 ≥ 0 , • Bài toán gốc tương đương: x1 + x2 + x3 + x4 = 12 với x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 , x4 ≥ 0 , .
• Kết quả:
C(12+4-1,12) = C(12+4-1,3)=455
31 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.4. Tổ hợp lặp Giải Ví dụ 2.4.6:
x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0
3 ≥ x1 ≥ 0,x2 ≥ 0,x3 ≥ 0
x1 ≥ 4 , x2 ≥ 0 , x3 ≥ 0
32 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.5. Bài tập
• Bài tập 2.5.1: Ngôn ngữ C chuẩn qui định đặt tên biến không quá 8 ký tự. Các ký tự trong tên biến chỉ được phép là các chữ cai (từ A đến Z) hoặc là các chữ số (từ 0 đến 9) và phải bắt đầu bằng chữ cái.
Hỏi có thể định nghĩa bao nhiêu biến khác nhau
34 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.5. Bài tập
• Bài tập 2.5.2:
35 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
2.5. Bài tập
• Bài tập 2.5.3:
36 Nguyễn Văn Hiệu, 2012, Discrete Mathematics
