LOGO Chương 2
TOÁN RỜI RẠC
Chương 2 (tt). Phép đếm
GV: Võ Tấn Dũng
1
NGUYÊN LÝ CỘNG
Mệnh đề Cho A và B là hai tập hữu hạn rời nhau. Khi đó
|A B|= |A|+|B|
2
B A
NGUYÊN LÝ CỘNG
Nguyên lý cộng: Giả sử để thực hiện một công việc ta có 2 phương án
- Phương án 1 có n cách làm - Phương án 2 có m cách làm
Khi đó số cách làm công việc A là n+m
3
Ví dụ. An có 3 áo tay dài, 5 áo tay ngắn. Để chọn 1 cái áo thì An có mấy cách
Bài tập:
Thầy giáo có 3 danh sách bài tập:
- Danh sách thứ nhất có 23 bài. - Danh sách thứ hai có 15 bài. - Danh sách thứ ba có 19 bài.
Một sinh viên phải chọn một bài tập để làm. Hỏi sinh
4
viên đó có bao nhiêu cách chọn bài tập?
Giải:
Ta có:
- 23 cách chọn bài tập từ danh sách thứ nhất. - 15 cách chọn bài tập từ danh sách thứ hai. - 19 cách chọn bài tập từ danh sách thứ ba.
Vì vậy:
5
- Theo nguyên lý cộng, sinh viên đó có 23+15+19=57 cách chọn bài tập.
Phép đếm
NGUYÊN LÝ NHÂN
Nguyên lý nhân: Giả sử để làm một công việc, ta cần thực hiện 2 bước
- Bước 1 có n cách làm - Bước 2 có m cách làm
Khi đó số cách làm công việc A là n.m
A
B
C
Ví dụ:
6
Có 3.2 =6 con đường đi từ A đến C
Bài tập:
Cho tập X ={1,2,3,4,5,0} Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia
abc
hết cho 2
7
Gợi ý: Gọi số có 3 chữ số là Thì c phải bằng 2 hoặc 4 hoặc 0
Giải
Cho tập X ={1,2,3,4,5,0} Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia
hết cho 2
Giải. Gọi số có 3 chữ số là abc TH1 . c=0. Khi đó
TH1 có 1.4.5 =20
c có 1 cách chọn a có 5 cách chọn ( aX\{0} ) b có 4 cách chọn ( bX\{a, 0} )
TH2 . c≠0. Khi đó
TH2 có 2.4.4 =32
8
c có 2 cách chọn a có 4 cách chọn ( aX\{c, 0} ) b có 4 cách chọn ( bX\{a, c} ) Vậy có 20+32 =52
Bài tập
9
Một dãy số XXXYYY có độ dài 6. Mỗi X có thể gán bởi một chữ cái. Mỗi Y có thể gán một chữ số. Hỏi có bao nhiêu dãy số được thành lập theo cách trên?
Giải
Một dãy số XXXYYY có độ dài 6. Mỗi X có thể gán bởi một chữ cái. Mỗi Y có thể gán một chữ số. Hỏi có bao nhiêu dãy số được thành lập theo cách trên?
Có 26 chữ cái và 10 chữ số. Vậy dãy số được thành lập theo cách trên là:
10
26^3*10^3 =17.576.000
Bài tập
11
Có bao nhiêu xâu nhị phân có độ dài 10 bit sao cho bit đầu tiên và bit cuối cùng là 1?
Bài tập
Có bao nhiêu xâu nhị phân có độ dài 10 bit sao cho bit đầu tiên và bit cuối cùng là 1?
Xâu nhị phân có dạng 1a1a2a3a4a5a6a7a81 thuộc về tập {0,1}
12
Có 28 xâu nhị phân như vậy.
NGUYÊN LÝ BÙ TRỪ
Nguyên lý bù trừ. Cho A và B là hai tập hữu hạn. Khi đó
A B
|A B|= |A|+|B| - |A B|
13
A B
Bài tập
BC
A C
A B C
C
A B
A B
14
|A B C|=?
Bài tập
15
Bài tập: Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu người
Bài tập
Bài tập: Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu người
Giải. Gọi A là những học sinh học Tiếng Pháp B là những học sinh học Tiếng Anh
16
Khi đó. Số học sinh của lớp là |A B |. Theo nguyên lý bù trừ ta có |A B|= |A|+|B| - |A B|=24+26-15=35
Bài tập
Bài tập: Trong một lớp học có 45 sinh viên học tiếng Anh, 30 sinh viên học tiếng Pháp và 10 sinh viên học cả Anh và Pháp.
1) Nếu trong lớp đó, không ai không biết một
trong hai thứ tiếng trên, hãy tính số sinh viên của lớp.
2) Nếu sĩ số của lớp là 70. Hỏi có bao nhiêu sinh
17
viên không biết ngoại ngữ Anh, Pháp?
Bài tập
Giải: Đặt A là số sinh viên học tiếng Anh thì |A| = 45 Đặt B là số sinh viên học tiếng Pháp thì |B| = 30 A B là số SV học tiếng Anh và Pháp |A B| = 10
1) Theo nguyên lý bù trừ ta có:
|A B|= |A|+|B| - |A B|=45+30-10=65
Vậy số sinh viên của lớp là 65
18
2) |A B| = 65 là số SV học tiếng Anh hoặc tiếng Pháp hoặc học cả hai. Vậy, nếu sỉ số lớp là 70 thì ta có 70-65=5 SV không học tiếng Anh hoặc Pháp.
HOÁN VỊ
Hoán vị Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Số các hoán vị của n phần tử ký hiệu là Pn
Pn = n! = n.(n-1).(n-2)…1 Quy ước 0! =1
Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau
19
abc,acb, bac,bca, cab,cba
Bài tập.
Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm
Giải: 5!
20
5 chữ số khác nhau được tạo từ tập X?
Bài tập.
Giả sử một vận động viên đi xe đạp dự định đi qua 8
21
thành phố. Vận động viên này bắt đầu cuộc hành trình từ một thành phố nào đó và có thể đến thành phố tiếp theo theo bất kỳ một thứ tự nào mà anh ta muốn. Hỏi vận động viên có thể đi qua 8 thành phố này theo bao nhiêu lộ trình khác nhau?
Giải.
Số lộ trình khác nhau có thể có của vận động viên này
Giải: 5!
22
bằng số hoán vị của 7 thành phố còn lại vì thành phố đầu tiên đã được xác định rồi. Bảy thành phố còn lại có thứ tự tùy chọn. Do đó số lộ trình khác nhau là 7! = 5040.
CHỈNH HỢP
Chỉnh hợp. Định nghĩa. Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử (1 k n) sắp thứ tự của tập hợp A được gọi là một
k
chỉnh hợp chập k của n phần tử.
nA
Số các chỉnh hợp chập k của n ký hiệu là
k A n
n ! n k
!
- Công thức
23
Ví dụ. Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb.
Bài tập
3
Bài tập: Có bao nhiêu số tự nhiên gồm 3 chữ số được tạo thành từ 1,2,3,4,5,6.
6A
24
Kết quả:
Bài tập.
Có bao nhiêu cách chọn có thứ tự 4 cầu thủ khác
25
nhau trong 10 cầu thủ của đội bóng quần vợt để chơi bốn trận đấu đơn, các trận đấu là có thứ tự?
Giải:
Có bao nhiêu cách chọn có thứ tự 4 cầu thủ khác
nhau trong 10 cầu thủ của đội bóng quần vợt để chơi bốn trận đấu đơn, các trận đấu là có thứ tự?
26
Một cách chọn có thứ tự bốn cầu thủ của đội bóng là một chỉnh hợp chập 4 của 10 phần tử. Theo công thức của chỉnh hợp, ta có:
TỔ HỢP
k
Tổ hợp. Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử.
nC
n k
C
k n
!
! n k n k !
Số tổ hợp chập k của n phần tử được kí hiệu là hay
27
Bài tập
Bài tập. Cho X = {1,2,3,4}. Tổ hợp chập 3 của 4 phần tử của X là {1,2,3}, {1,2,4}, {1,3,4} , {2,3,4}
10
Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn
30C
28
- Số cách chọn là tổ hợp chập 10 của 30.
Bài tập.
Có 100 vé số được đánh số từ 1 đến 100 được bán
cho 100 người khác nhau. Người ta sẽ trao 4 giải thưởng kể cả giải độc đắc. Hỏi: 1) Có bao nhiêu cách trao thưởng? 2) Có bao nhiêu cách trao giải thưởng nếu người giữ vé 47
29
trúng giải độc đắc?
Giải:
Có 100 vé số được đánh số từ 1 đến 100 được bán
cho 100 người khác nhau. Người ta sẽ trao 4 giải thưởng kể cả giải độc đắc. Hỏi: 1) Có bao nhiêu cách trao thưởng? 2) Có bao nhiêu cách trao giải thưởng nếu người giữ vé 47
trúng giải độc đắc?
1) Số cách trao thưởng là:
30
2) Số cách trao thưởng là:
HOÁN VỊ LẶP
Hoán vị lặp Định nghĩa. Cho n đối tượng trong đó có ni đối tượng loại i
giống hệt nhau (i =1,2,…,k ; n1+ n2,…+ nk= n).
Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một
hoán vị lặp của n.
Số hoán vị của n đối tượng, trong đó có n1 đối tượng giống nhau thuộc loại 1, n2 đối tượng giống nhau thuộc loại 2,…,
n ! n !... !k
n n ! 1 2
31
nk đối tượng giống nhau thuộc loại k, là
BÀI TẬP
Bài tập. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ SUCCESS?
420
7! 3!1!2!1!
32
Giải. Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 1 chữ E. Do đó số chuỗi có được là .
Bài tập
Hãy tính xem có bao nhiêu cách sắp
xếp khác nhau của 6 mẫu tự trong từ PEPPER
33
TỔ HỢP LẶP
k
Tổ hợp lặp Định nghĩa. Mỗi cách chọn ra k vật từ n loại vật khác nhau (trong đó mỗi loại vật có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp chập k của n
nK
Số các tổ hợp lặp chập k của n được ký hiệu là
K
k n
C
k n k
1
34
Bài tập
Bài tập. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn.
Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể AA, AB, AC, BB, BC, CC
K
C
C
6
2 3
2 3 2 1
2 4
35
Bài tập
Bài tập: Một người vào một cửa hàng ăn uống muốn chọn mua 7 phần ăn, mỗi phần ăn sẽ được chọn một trong 4 loại khác nhau: A, B, C, D. Hỏi có bao nhiêu cách chọn 7 phần ăn.
36
Giải
37
