Toán học - Chương 2: Phương pháp đếm
BÀI TẬP
Bài 1: Có bao nhiêu chuỗi nhị phân dài tối đa 6 bit?
Bài 2: Có bao nhiêu chuỗi nhị phân dài 10 bit, sao cho bit đầu bằng 0 hay
bit cuối bằng 1.
Bài 3: Một mật khẩu phải có độ dài 6 ký tự (không phân biệt ký tự hoa, thường),
mỗi ký tự được lấy từ bảng 26 chữ cái và 10 chữ số. Tính số mật khẩu có thể tạo
ra trong mỗi trường hợp sau:
a)Không có điều kiện gì thêm.
b)Trong mật khẩu phải có ít nhất một ký tự số.
c) Trong mật khẩu phải có ít nhất một ký tự số và không có ký tự A.
Bài 4: Có bao nhiêu dãy nhị phân dài 12 bit, chứa ít nhất 3 bit 0 và 3 bit
1.
Bài 5: Cần bầu một ủy ban gồm 6 đại biểu, chọn từ 8 Bà và 8 Ông ứng
viên. Có bao nhiêu cách chọn trong mỗi trường hợp sau:
a)Chọn tùy ý?
b)Chọn số Bà bằng số Ông?
c) Chọn số Bà ít hơn số Ông?
Bài 6: Có bao nhiêu tam giác được tạo ra từ 9 điểm phân biệt
trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng.
Bài 7: 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 nhất, nhì, ba, tư. Hỏi
a)Có bao nhiêu cách trao giải?
b)Có bao nhiêu cách trao giải, nếu người có vé 50 trúng giải nhất?
c) Có bao nhiêu cách trao giải, nếu người có vé 50 không trúng giải
nào?
d)Có bao nhiêu cách trao giải, nếu 3 người có vé 10,15, 20 trúng giải?
e) Có bao nhiêu cách trao giải, nếu 2 người có vé 20,30 trúng giải,
nhưng người có vé 15 không trúng giải?
18 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 949 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Toán học - Chương 2: Phương pháp đếm, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Chương 2. Phương pháp đếm
I. TẬP HỢP
1. KHÁI NIỆM TẬP HỢP
Để chỉ một tập hợp ta dùng chữ in hoa, chẳng hạn như A, B, C,.,
X,Y,Z.
Để chỉ một phần tử ta dùng chữ thường, chẳng hạn như a, b, c,.,
x,y,z.
Để chỉ x là một phần tử của tập hợp A. Ký hiệu x A
Để chỉ x không là một phần tử của tập hợp A. Ký hiệu x A
Tập vũ trụ: Tập A nằm trong tập U thì U gọi là một vũ trụ của A.
Tập hợp rỗng: Tập hợp không có phần tử nào được gọi là tập hợp rỗng,
và được ký hiệu là .
Tập hợp bằng nhau:
A = B x A thì x B và x B thì x A
2.CÁCH XÁC ĐỊNH MỘT TẬP HỢP.
Cách liệt kê: Ta liệt kê tất cả các phần tử của tập hợp giữa 2 ký hiệu
ngoặc và .
Ví dụ:
A = a, b, c
Cách nêu đặc trưng của phần tử:
A = x U / p(x) với U là tập vũ trụ của tập A.
hay vắn tắt (khi hiểu ngầm tập vũ trụ U): A = x / p(x)
Ví dụ:
A = n N / n là số nguyên tố
B = n N / có một số tự nhiên m sao cho n = m2
a
b
c
3. QUAN HỆ "bao hàm trong" VÀ TẬP HỢP CON
Định nghĩa: A B (hay B A) x A thì x B
Ví dụ:
0, 1, 2 n N : n < 10
Các tập hợp số.
N Z Q R C, trong đó
N là tập hợp các số tự nhiên,
Z là tập hợp các số nguyên,
Q là tập hợp các số hữu tỉ,
R là tập hợp các số thực,
C là tập hợp các số phức.
Cho X là một tập hợp. Sưu tập tất cả các tập hợp con của X được ký
hiệu là P(X). Nói một cách khác, P(X) là một tập hợp mà mỗi phần tử của
nó là một tập hợp con của X.
Ví dụ: X= 0, 1, 2
Thì P(X)= 0, 1, 2
Tính chất:
A và A A, với mọi tập hợp A.
(A B) (B A) (A = B)
(A B) (B C) (A C)
X Y P(X) P(Y)
Nếu tập hợp X có n phần tử (n N) thì tập hợp P(X) có 2n phần tử.
4.CÁC PHÉP TÓAN TẬP HỢP.
Giao.
A B = x : (x A) (x B)
Hợp.
A B = x : (x A) (x B)
Hiệu.
A - B = x : (x A) (x B)
Phần bù.
Ac = U – A
Tích Descartes của 2 tập hợp.
A x B = (a,b) : a A b B
Trong trường hợp B = A, ta kỳ hiệu A x A = A2.
Các tính chất của các phép toán:
Tính giao hoán:
A B = B A
A B = B A
Tính kết hợp:
A (B C) = (A B) C
A (B C) = (A B) C
Tính phân bố:
A (B C) = (A B) (A C)
A (B C) = (A B) (A C)
Luật De Morgan:
(A B)c = Ac Bc
(A B)c = Ac Bc
Phần tử trung hòa:
A = A
A U = A
Phần bù:
A Ac = U
A Ac =
Tính thống trị:
A U = U
A =
II. ÁNH XẠ
2.1 Định nghĩa ánh xạ
Cho X và Y là các tập hợp khác rỗng. Một ánh xạ f từ tập hợp X vào tập
hợp Y là phép tương ứng sao cho bởi phép tương ứng nầy mỗi phần tử x
của X sẽ có một phần tử duy nhất y của Y tương ứng mà ta ký hiệu là f(x)
và gọi là ảnh của x. Ta viết
f : X Y
x f(x)
Ta thường minh họa ánh xạ f bởi sơ đồ sau đây:
Hai ánh xạ f và g từ X vào Y được gọi là bằng nhau khi ta có:
x X : f(x) = g(x)
Cách xác định một ánh xạ.
Ta có thể xác định ánh xạ f từ X vào Y bằng nhiều cách, chẳng hạn như
cách liệt kê tất cả các ảnh của từng phần tử của X, cách cho một công
thức để xác định ảnh f(x) của mỗi phần tử x, hoặc ta có thể đưa ra một
thủ tục xác định để tính ra (hay tìm ra) được phần tử f(x) ứng với mỗi
phần tử x X.
Ví dụ:
f : N N xác định bởi f(n) = 2(n+1).
Thì
f(1)=4
f(2)=6
.
2.2 Ảnh và ảnh ngược
Ảnh của tập hợp.
Cho f là một ánh xạ từ X vào Y. Giả sử A là một tập hợp con của X. Ảnh
của tập A qua ánh xạ f, ký hiểu bởi f(A), là tập hợp con của Y gồm tất cả
những phần tử y sao cho y là ảnh của ít nhất một phần tử x thuộc A.
f(A) = f(a) : a A
Ảnh ngược (hay tạo ảnh) của một tập hợp.
Cho f là một ánh xạ từ X vào Y. Giả sử B là một tập hợp con của Y. Aûnh
ngược của tập B bởi ánh xạ f, ký hiểu là f-1(B), là tập hợp con của X gồm
tất cả những phần tử x sao cho f(x) thuộc B.
f-1(B) = x X : f(x) B
Trong trường hợp tập B chỉ có một phần tử y thì ảnh ngược của B sẽ
được viết vắn tắt là f-1(y).
Ví dụ:
Cho ánh xạ f : Z N xác định bởi f(n) = n2+1. Đặt A = -2, -1, 0, 1, 2, 3
và B = 0, 1, 2, 3, 4, 5 . Ta có :
f(A) = 1, 2, 5, 10
f-1(B) = -2,-1, 0, 1,2
2.3 Các ánh xạ đặc biệt
Đơn ánh:
Ánh xạ f : X Y được gọi là một đơn ánh khi các ảnh của 2 phần tử
khác nhau tùy ý thì khác nhau, nghĩa là với mọi x và x' thuộc X ta có:
x x' f(x) f(x')
hay f(x) = f(x') x = x'
Toàn ánh:
Ánh xạ f : X Y được gọi là một toàn ánh khi mọi phần tử của Y đều là
ảnh của ít nhất một phần tử x thuộc X, nghĩa là
f(X) = Y.
Song ánh:
Aùnh xạ f : X Y được gọi là một song ánh khi nó vừa là đơn ánh vừa là
toàn ánh. Khi ấy với mỗi y Y, có duy nhất phần tử x X sao cho f(x) =
y. Như thế phép tương ứng liên kết y với x sẽ cho ta một ánh xạ từ Y vào
X. Ta gọi ánh xạ nầy là ánh xạ ngược của f và ký hiệu là f-1. Vậy ta có
f-1 : Y X, xác định bởi f-1(y) = x, với f(x) = y.
Ví dụ:
Ánh xạ f : Z N xác định bởi f(n) = n2+1 không phải là một đơn ánh vì
f(-1) = f(1) = 2 mà -1 1.
Ánh xạ f : N N xác định bởi f(n) = n2+1 là một đơn ánh vì ta có thể
thấy rằng với mọi n và n' thuộc N ta có: nếu f(n) = f(n') thì n = n'.
Cho a và b là 2 số thực tùy ý và a 0.
Ánh xạ f : R R xác định bởi
f(x) = a.x+b
là một song ánh vì với mọi số thực y thì phương trình
ax + b = y
có nghiệm thực x duy nhất là x = (y-b) / a. Từ đó ta cũng có ánh xạ ngược
được xác định bởi
f-1(y) = (y-b) / a.
III. CÁC NGUYÊN LÝ ĐẾM.
3.1 Phép Đếm
Định nghĩa:
Cho A là một tập hợp khác rỗng. Nếu tồn tại một số nguyên dương n và
một song ánh f từ A vào 1, 2, . . ., n thì ta nói A là một tập hợp hữu hạn
và A có n phần tử.
Khi đó song ánh f : A 1, 2, . . ., n được xem là một phép đếm tập
hợp A.
Tập hợp rỗng có số phần tử là 0, và cũng được xem là tập hữu hạn. Số
phần tử của một tập hợp hữu hạn A được ký hiệu là |A| (còn gọi là lực
lượng của tập hợp A).
Nếu tập hợp A không hữu hạn, ta nói A là vô hạn và viết |A| =
3.2 Nguyên lý cộng
Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau, nghĩa là A B =
. Khi ấy ta có: | A B | = | A | + | B |
Một cách tổng quát: Nếu A1, A2, ..., An là các tập hợp hữu hạn rời nhau
thì: | A1 A2 . . . An | = | A1 | + | A2 | + . . . + | An |
Nguyên lý bù trừ: Trong trường hợp đối với hai tập hợp hữu hạn A và
B tùy ý thì ta có:
| A B | = | A | + | B | - | A B |
Nguyên lý cộng : để thực hiện một công việc ta có thể chọn một trong hai
phương án khác nhau, cách thực hiện phương án thứ nhất luôn luôn khác
cách thực hiện phương án thứ hai. Phương án thứ nhất có m cách thực
hiện, và phương án thứ hai có n cách thực hiện. Thì tất cả sẽ có (m+n) cách
thực hiện công việc.
3.3 Nguyên lý nhân
Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau. Khi ấy ta có:
| A x B | = | A | . | B |
Một cách tổng quát: Nếu A1, A2, ..., An là các tập hợp hữu hạn thì số
phần tử của tích Descartes của các tập hợp trên bằng tích của các số
lượng phần tử của các tập hợp trên:
| A1 x A2 x . . . x An | = | A1 | . | A2 | . . . . . | An |
Nguyên lý nhân : Để thực hiện một công việc phải qua hai giai đọan kế
tiếp nhau. Giai đọan thứ nhất ta có m cách làm, và ứng với mỗi cách làm
giai đọan thứ nhất có n cách làm giai đọan thứ hai. Thì sẽ có (m*n) cách
thực hiện công việc.
Ví dụ: Các ghế ngồi trong một hội trường sẽ được ghi nhãn gồm một
mẫu tự và một số nguyên dương không lớn hơn 100. Hỏi số ghế tối đa có
thể được ghi nhãn khác nhau là bao nhiêu?
Lời giải. Thủ tục ghi nhãn cho một ghế gồm 2 giai đọan : ghi một trong 26
mẫu tự và kế tiếp là ghi một trong 100 số nguyên dương. Qui tắc nhân
cho thấy có 26 x 100 = 2600 cách khác nhau để ghi nhãn cho một ghế
ngồi. Do đó số ghế lớn nhất có thể được ghi nhãn khác nhau là 2600.
Ví dụ: Một mật khẩu bao gồm 6 ký tự, trong đó gồm 3 mẫu tự rồi đến 3
ký số thập phân. Hỏi có bao nhiêu mật khẩu khác nhau?
Lời giải. Có 26 cách chọn cho mỗi mẫu tự và có 10 cách chọn cho mỗi ký
số thập phân. Do đó, theo qui tắc nhân, có tất cả 26.26.26.10.10.10 = 17
576 000 mã khác nhau.
Ví dụ: Mỗi người sử dụng trên một hệ thống máy tính có một mật
khẩu, dài từ 6 đến 8 ký tự, trong đó mỗi ký tự là một chữ in hoa hoặc là
một ký số thập phân. Mỗi mật khẩu phải có chứa ít nhất một ký số. Hỏi
có bao nhiêu mật khẩu khác nhau?
Lời giải. Đặt P là số lượng tất cả các mật khẩu, và P6, P7, P8 lần lượt là số
các mật khẩu có độ dài 6, 7, 8. Do qui tắc cộng ta có P = P6 + P7 + P8.
Chúng ta sẽ tính P6, P7, và P8.
Tính trực tiếp P6 tương đối khó. Để tính P6 cho dễ, ta tính số chuỗi có độ
dài 6 gồm các chữ in hoa hay ký số thập phân (kể cả các chuỗi không có
ký số thập phân), và trừ cho số chuỗi (với độ dài 6) không có ký số thập
phân nào. Theo qui tắc nhân, số chuỗi gồm 6 ký tự là 366 và số chuỗi
không có ký số nào là 266. Suy ra
P6 = 36
6 - 266 = 2 176 782 336 - 308 915 776
= 1 867 866 560.
Tương tự, ta có thể tính ra được :
P7 = 36
7 - 267 = 78 364 164 096 - 8 031 810 176
= 70 332 353 920.
và
P8 = 36
8 - 268 = 2 821 109 907 456 - 208 827 064 576
= 2 612 282 842 880.
Từ đó ta tính được :
P = P6 + P7 + P8 = 2 684 483 063 360.
IV. GIẢI TÍCH TỔ HỢP.
LỌAI KÝ HIỆU CÔNG THỨC
Chỉnh
Hợp
Không
Lặp
k
nAhayknA ),( )!(
!
)1(*...*)1(*
kn
n
knnnAkn
Có
Lặp
k
nPhayknP ),(
kk
n nP
Hóan
vị
Không
Lặp
n
nAhaynnA ),( !nA
n
n
Có
Lặp
!*.....*!*!
!
21 knnn
n
Tổ
Hợp
Không
Lặp
k
nChayknC ),( )!(!
!
knk
n
C kn
Có
Lặp
)!1(!
)!1(
1
nk
kn
C k kn
Với mọi số thự nhiên n ta có:
C(n, 0) = 1
C(n, n) = 1
Cho n và r là 2 số nguyên không âm và k n. Ta có:
C(n,k) = C(n,n-k)
Cho n và k là 2 số nguyên sao cho 0 < k < n. Khi đó ta có:
C(n, k) = C(n-1, k) + C(n-1, k-1).
Ðịnh lý. Cho x và y là 2 biến thực, n là một số nguyên không ấm tùy ý.
Ta có:
Hệ quả 1. Cho n là một số nguyên không âm tùy ý. Ta có:
Hệ quả 2. Cho n là một số nguyên không âm. Ta có:
BÀI TẬP
Bài 1: Có bao nhiêu chuỗi nhị phân dài tối đa 6 bit?
Bài 2: Có bao nhiêu chuỗi nhị phân dài 10 bit, sao cho bit đầu bằng 0 hay
bit cuối bằng 1.
Bài 3: Một mật khẩu phải có độ dài 6 ký tự (không phân biệt ký tự hoa, thường),
mỗi ký tự được lấy từ bảng 26 chữ cái và 10 chữ số. Tính số mật khẩu có thể tạo
ra trong mỗi trường hợp sau:
a) Không có điều kiện gì thêm.
b) Trong mật khẩu phải có ít nhất một ký tự số.
c) Trong mật khẩu phải có ít nhất một ký tự số và không có ký tự A.
Bài 4: Có bao nhiêu dãy nhị phân dài 12 bit, chứa ít nhất 3 bit 0 và 3 bit
1.
Bài 5: Cần bầu một ủy ban gồm 6 đại biểu, chọn từ 8 Bà và 8 Ông ứng
viên. Có bao nhiêu cách chọn trong mỗi trường hợp sau:
a) Chọn tùy ý?
b) Chọn số Bà bằng số Ông?
c) Chọn số Bà ít hơn số Ông?
Bài 6: Có bao nhiêu tam giác được tạo ra từ 9 điểm phân biệt
trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng.
Bài 7: 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 nhất, nhì, ba, tư. Hỏi
a) Có bao nhiêu cách trao giải?
b) Có bao nhiêu cách trao giải, nếu người có vé 50 trúng giải nhất?
c) Có bao nhiêu cách trao giải, nếu người có vé 50 không trúng giải
nào?
d) Có bao nhiêu cách trao giải, nếu 3 người có vé 10,15, 20 trúng giải?
e) Có bao nhiêu cách trao giải, nếu 2 người có vé 20,30 trúng giải,
nhưng người có vé 15 không trúng giải?
Bài 8: Có 6 người vào tiệm ăn phở, trong tiệm có 4 lọai phở. Hỏi có bao
nhiêu cách gọi cho mỗi người 1 tô phở?
Bài 9: Cô dâu, chú rể, cùng chụp hình với 6 người bạn, có bao nhiêu cách
xếp thành 1 hàng ngang để chụp, trong mỗi trường hợp sau:
a) Xếp tùy í?
b) Xếp sao cho cô dâu, chú rể luôn bên nhau?
c) Xếp sao cho cô dâu luôn bên trái chú rể?
d) Xếp sao cho cô dâu, chú rể đứng đúng giữa hàng?
Các file đính kèm theo tài liệu này:
- bgc22011_2326.pdf