Bài giảng Toán tin - Phần 3 Phép đếm
Ví dụ. 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
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán tin - Phần 3 Phép đếm, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1. Các nguyên lý
2. Giải tích tổ hợp
3. Hoán vị lặp, tổ hợp lặp
1. Nguyên lý cộng :
Giả sử để làm công việc A có 2 phương pháp
- Phương pháp 1 có n cách làm
- Phương pháp 2 có m cách làm
Khi đó số cách làm công việc A là n+m
Ví dụ : Danh bạ điện thoại có 3 số ở sim 1. 5 số ở sim 2.
Vậy có bao nhiêu cách để gọi một số bất kỳ từ danh bạ
trên ?
Cho A1, A2,.., An là các tập hữu hạn, không giao
nhau từng đôi một. Khi đó :
Company Logo
n
i
i
n
i
AN
i
N UA
11
)(
2. Nguyên lý nhân
Giả sử để làm công việc A 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
Ví dụ:
A B C
Có 3.2 =6 con đường đi từ A đến C
Ví dụ: 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 đó
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} )
TH1 có 1.4.5 =20
TH2 . c≠0. Khi đó
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} )
TH2 có 2.4.4 =32
Vậy có 20+32 =52
Một hệ thống yêu cầu đăng ký password
dạng như sau :
Từ 4 – 8 chữ cái
Phân biệt chữ hoa và thường
Hỏi ?
Có bao nhiêu passwords có thể ?
Sử dụng nguyên lý gì ?
Nếu password có 4 ký tự thì tỷ lệ phần trăm là bao
nhiêu ?
87654 PPPPPP
Gọi Pi là tập hợp các password gồm i chữ cái. Và P là tập hợp
tất cả các passwords có thể
Ta có Pi rời nhau :
8
4
||||
i
iPP
Với mỗi Pi ta có 52 chữ cái (26 hoa và 26 thường). Ta có : 52
i
Tập hợp tất cả passwords có thể : 524 + 525 + 526 + 527 + 528
3. Nguyên lý chuồng bồ câu (Derichlet)
Giả sử có n chim bồ câu ở trong k chuồng đặt vào k hộp.
Khi đó tồn tại ít nhất một chuồng chứa từ bồ câu trở lên,
trong đó là số nguyên nhỏ nhất lớn hơn hay bằng n/k.
/n k
/n k
Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít
nhất 1 chuồng có 3 con bồ câu trở lên
Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh
cùng ngày
4. 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 B A
Định nghĩa : Cho A1, A2,.., An là các tập hữu
hạn. Khi đó :
n
i
i
n
k
nji
ji
nji
ji
n
i
i
n
i
i
AN
AAANAANANAN
1
1
1111
()1(
...)()()()(
A B
A C BC
A B C
A B
C
|A B C|=?
Ví dụ. 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
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
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
1. Hoán vị : 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
Phép đếm
Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau
abc, acb, bac, bca, cab, cba
Nếu A là tập hợp n phần tử thì số song ánh từ A vào A là
n!
Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm
5 chữ số khác nhau được tạo từ tập X?
2. Chỉnh hợp : 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
chỉnh hợp chập k của n phần tử.
Số các chỉnh hợp chập k của n ký hiệu là
- Công thức
!
!
k
n
n
A
n k
k
nA
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.
Ví dụ. 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.
Kết quả: 3
6A
3.Tổ hợp : 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ử.
Số tổ hợp chập k của n phần tử được kí hiệu là hay
k
nC
k
n
!
! !
k
n
n
C
k n k
Tính chất : n k k
n nC C
1
1
k k k
n n nC C C
Ví dụ : 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}
Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn
- Số cách chọn là tổ hợp chập 10 của 30.
10
30C
1. Hoán vị lặp : 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,,
nk đối tượng giống nhau thuộc loại k, là
1 2
!
! !... !k
n
n n n
Ví dụ : 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?
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à
.
7!
420
3!1!2!1!
2. Tổ hợp lặp : 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
Số các tổ hợp lặp chập k của n được ký hiệu là
k
nK
1
k k
n n kK C
Ví dụ. 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
2 2 2
3 3 2 1 4 6K C C
Các file đính kèm theo tài liệu này:
- bai_giang_mon_toan_tin_4_3032.pdf