Thuyết trình - Phép điếm potx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.76 MB, 69 trang )
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
1
Nội dung:
I. Các nguyên lí
II. Hoán vị, Chỉnh hợp và Tổ hợp. Nhị thức Newton
III. Hoán vị lặp, Chỉnh hợp lặp và Tổ hợp lặp. Đa thức Newton
IV. Đệ quy
2
I. Các nguyên lí:
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.
3
Ví dụ: Nam có 3 áo tay dài, 5 áo tay ngắn. Để chọn 1 cái áo thì Nam có mấy cách?
Đáp án: Áp dụng nguyên lí cộng thì:
Phương pháp 1: Có 3 cách chọn áo dài tay
Phương pháp 2: Có 5 cách chọn áo ngắn tay
Vậy để chọn một áo thì Nam có 3 + 5 cách chọn.
I. Các nguyên lí:
4
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
I. Các nguyên lí:
5
Ví dụ:
Đáp án:
Có 3.2 =6 con đường đi từ A đến C
I. Các nguyên lí:
6
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
Đáp án: 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 ( a € X\{0} ) TH1 có 1.4.5 = 20.
b có 4 cách chọn ( b € X\{ a, 0})
TH2 . c≠0. Khi đó
c có 2 cách chọn
a có 4 cách chọn ( a € X\{c, 0} )
TH2 có 2.4.4 = 32.
b có 4 cách chọn ( b € X\{ a, c})
Vậy có 20+32 = 52.
I. Các nguyên lí:
7
3. Nguyên lý chuồng bồ câu (Derichlet)
Nguyên lý Dirichlet do nhà toán học người Đức là
Dirichlet đề xuất từ thế kỉ XX đã được áp dụng để chứng
minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp.
Nguyên lý này được phát triển từ mệnh đề gọi là nguyên
lý “nguyên lý quả cam” hay là nguyên lý “chuồng chim
bồ câ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ì chắc chắn có
ít nhất một ngăn có nhiều hơn một con chim.
8
I. Các nguyên lí:
3. Nguyên lý chuồng bồ câu (Derichlet)
Giả sử có n chim bồ câu ở trong k chuồng. Khi đó tồn
tại ít nhất một chuồng chứa từ [n/ k]
bồ câu trở lên.
Ví dụ: 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
I. Các nguyên lí:
9
Ví dụ: Cho tập X ={1,2,3,4,5,6,7,8,9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi
đó trong A sẽ có hai phần tử có tổng bằng 10
Đáp án: Ta lập các chuồng như sau: {1,9} {2,8} {3,7} {4,6} {5} Do A có 6 phần tử nên
trong 6 phần tử đó sẽ có 2 phần tử trong 1 chuồng. Suy ra đpcm
I. Các nguyên lí:
10
A
B
B
A
I. Các nguyên lí:
11
I. Các nguyên lí:
12
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
2.1 Hoán vị
Bài toán: Trong giờ học môn Giáo dục quốc phòng, một tiểu đội
học sinh gồm 10 người được xếp thành một hàng dọc. Hỏi có bao
nhiêu cách xếp?
13
2.1 Hoán vị
Định nghĩa 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à 1 hoán vị của n phần
tử.
Áp dụng vào bài toán:
A= { 10 học sinh } ; n =10 >0
Số cách sắp xếp = hoán vị của 10h/s
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
14
2.1 Hoán vị
Định lý:
Số các Hoán vị của một tập hợp có n phần tử là: P
n
= n!=n(n-1) 2.1
Quy ước : 0! = 1
AD: số cách sắp xếp = P
10 =
10! = 10.9….2.1 =?
VD: Sắp xếp 6 học sinh vào 6 cái ghế. Hỏi có bao nhiêu cách sắp xếp?
Đáp án: P
6
= 6!=1.2.3…6=720
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
15
2.1 Hoán vị
Ví dụ 1: Cho A ={a,b,c}. Khi đó A có các hoán vị sau:
abc, acb,
bac, bca,
cab, cba
Ví dụ 2:
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?
Đáp án: 5!
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
16
2.2 Chỉnh hợp
Bài toán: Trong trận chung kết bóng đá phải phân
định thắng thua bằng đá luân lưu 11m . Huấn luyện
viên của mỗi đội cần trình với trọng tài một danh
sách sắp thứ tự 5 cầu thủ trong số 11 cầu thủ của đội
để tham gia đá. Có bao nhiêu cách sắp xếp danh
sách thứ tự 5 cầu thủ?
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
17
2.2 Chỉnh hợp
Định nghĩa chỉnh hợp :
Cho A là tập hợp gồm n phần tử (khác
nhau). Mỗi bộ gồm k phần tử(0<=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 phần tử ký
hiệu là:
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
18
k
n
A
)!(
!
kn
n
A
k
n
−
=
2.2 Chỉnh hợp
Áp dụng vào bài toán: Số cách sắp
xếp chính là chỉnh hợp chập 5 của 11
.
= = ?
)!511(
!11
−
A
5
11
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
19
2.2 Chỉnh hợp
Nhận xét:
Hai Chỉnh hợp khác nhau khi và chỉ khi hoặc có ít
nhất một phần tử của Chỉnh hợp này không là
phần tử của Chỉnh hợp kia hoặc các phần tử của
Chỉnh hợp giống nhau nhưng được sắp xếp theo
thứ tự khác nhau.
TH: n =k : chính là hoán vị của n.
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
20
ab, ba, ac, ca, bc, cb
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
21
2.3 Tổ hợp
Bài toán:
Một nhóm có 8 thành viên, chọn
3 người lên thuyết trình. Hỏi có
bao nhiêu cách chọn????
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
22
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
)!(!
!
knk
n
−
C
k
n
23
2.3 Tổ hợp
Áp dụng vào bài toán:
Số cách chọn : = tổ hợp chập 3 của 8 .
= =?
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
)!38(!3
!8
−
C
3
8
24
2.3 Tổ hợp
Khác nhau của chỉnh hợp và tổ hợp??
Chỉnh hợp : quan tâm đến thứ tự của các phần tử, còn tổ hợp thì không
II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức
Newton
Tính chất:
C
kn
n
−
C
k
n
1−
=
C
k
n
C
n
0
C
n
n
C
n
1
C
n
n
1−
= = 1
C
k
n 1+
C
k
n
≥
= = n
= + k
1)
25
