TOÁN RỜI RẠC
(Discrete Mathematics)
Chương 2
Phép đếm
Phép đếm


1.Tập hợp và các phép toán tập hợp
2 Ánh xạ
3. Phép đếm
4. Giải tích tổ hợp
5. Nguyên lý Dirichlet(nguyên lý chuồng bồ câu)
1.1) Định nghĩa 2.1.1:
Tập hợp A gồm các phần tử x thỏa tính chất p(x):
A = xU / p(x)
U: gọi là tập vũ trụ
Hay: A = x / p(x) (U: được hiểu ngầm)
Tập hợp có thể được biểu diễn bằng cách liệt kê (nếu có thể):
Ví dụ 2.1.1: A = { nN/ (n>3)  (n7)}
Có thể viết lại bằng cách liệt kê: A = {4, 5, 6, 7}
Ví dụ 2.1.2: Tập các nguyên âm trong bảng chữ cái tiếng Anh
V={a,e, i, o,u}
1. Tập hợp và các phép toán tập hợp
 Một tập hợp có thể gồm những phần tử chẳng liên quan gì
với nhau
Tập rỗng, kí hiệu : là tập hợp không có phần tử nào.
Ví dụ 2.1.3: A= {xR/ x2+4x+6=0} là tập 
1.2) Định nghĩa 2.1.2: Tập hợp A gọi là con của tập hợp B (kí hiệu AB) nếu:
xA  x  B


Ví dụ 2.1.4: Với A = {5,8}; B = {1,4,8;6,5,12} thì AB
Chú ý:
Ta có:   A và A  A với mọi tập hợp A.
Tập A có n phần tử sẽ có 2n tập con và 2n-1 tập con khác rỗng.

1. Tập hợp và các phép toán tập hợp (tiếp theo)
1. Tập hợp và các phép toán tập hợp (tiếp theo)
Ví dụ 2.1.5: Cho tập A = {1,4;7}
Có 23=8 tập con của A:
P(A)=(, {1}, {4}, {7}, {1,4}, {1,7}, {4,7},{1,4,7}
1.3) Định nghĩa 2.1.3: Hai tập hợp A và B được gọi là bằng nhau khi và chỉ khi AB và BA.
Ví dụ 2.1.6: A = {1,3,7} và B = {7, 1, 3}
 A = B
Ví dụ 2.1.7: A = {f,c,e,a, b} và B = {a, b, c, f}
 A  B
Ví dụ 2.1.8: A = {xR/ x2-3x+2=0}
và B = {xR/ x4-3x3+3x2-3x+2=0}
 A = B

1. Tập hợp và các phép toán tập hợp (tiếp theo)
Ví dụ 2.1.9: Giả sử A={a, b, c, {c}, {a,c}}. Chỉ ra các khẳng định đúng trong các khẳng định dưới đây:
i) bA ii) cA
iii) {c}A iv){c}A
v) {a,b}A vi) {{c}}A
Trả lời: i, ii, iii, iv, v, vi
Ví dụ 2.1.10: Chỉ ra các khẳng định đúng:
i)  ii) 
iii) {} iv) {}
Trả lời: ii, iii, iv
1.4) Một số phép toán tập hợp
Phép giao: A  B ={x U/ (xA)(xB)}
Phép hợp: A B ={x  U/ (xA)(xB)}
Phép trừ: A B ={x  U/ (x  A)  (xB)}
Lấy phần bù:




1. Tập hợp và các phép toán tập hợp (tiếp theo)
1. Tập hợp và các phép toán tập hợp (tiếp theo)
Ví dụ 2.1.10: Cho tập hợp U = {a, b, c, e, f, 1, 5, 7} và các tập con của U
A = { b, c, 5}, B = {c, 5, f, 7}
Ta có:
AB = {c, 5}
AB = {b, c,5, f, 7}
AB = {b}
BA={f, 7}

1. Tập hợp và các phép toán tập hợp (tiếp theo)
Ví dụ 2.3.11: Cho U = {1,2,3,4,5,6,7,8,9}; A = {1,5,6;9}; B={4;5;7;9}
Ta có: AB ={5,9};
AB ={1;4;5;6;7;9};
AB = {1,6}
A = {2,3,4,7,8}
5) Phần tử trung hòa
A=A
AU=A
6) Phần bù



7) Tính thống trị
A = 
AU = U



1. Tập hợp và các phép toán tập hợp (tiếp theo)
1) Tính giao hoán
AB = BA
AB = BA
2) Tính kết hợp
(AB)C = A(BC)
(A B)C = A(BC)
3) Luật De Morgan


4) Tính phân bố
A(BC) = (AB)(AC)
A (BC) = (AB)(AC)
1.5) Định lý 2.1.1: Cho tập hợp U và A, B, C là các tập con của U.
Ta có
Chú ý: Các tính chất này tương tự như các luật logic
1. Tập hợp và các phép toán tập hợp (tiếp theo)
Ví dụ 2.1.12: Dùng các quy luật của lý thuyết tập hợp để chứng minh:

Giải:
Ta có
2. Ánh xạ
2.1) Định nghĩa 2.2.1:
Ánh xạ f từ tập hợp A vào tập hợp B là phép tương ứng liên kết mỗi phần tử x của A với một phần tử duy nhất y của B, kí hiệu y=f(x). f(x) gọi là ảnh của x cho bởi ánh xạ f
g: có phải là ánh xạ?
f có phải là ánh xạ?
Kí hiệu:
2. Ánh xạ (tiếp theo)
2.2) Định nghĩa 2.2.2: Hai ánh xạ f và g từ A vào B gọi là bằng nhau nếu: xA, f(x)=g(x).
Ví dụ 2.2.1: Cho 2 ánh xạ:
Ta có: xR, cos(x)=cos(x+2). Vậy f = g
2. Ánh xạ (tiếp theo)
2.3) Định nghĩa 2.2.3: Cho f là ánh xạ từ tập hợp A vào tập hợp B. Ta có:
Với E  A, ảnh của E cho bởi f, kí hiệu f(E) được định nghĩa:
f(E) = {y B/x  A, y = f(x)}
Với F B, ảnh ngược (tạo ảnh) của F bởi f, kí hiệu f-1(F) được định nghĩa:
f-1(F) = {x A/ f(x)  F}
Ví dụ 2.2.2: Cho ánh xạ

Xác định f(A), f-1(A) trong các trường hợp
a) A = {2, 3}; b) A={-3, -2, 2, 3} c) A = [1, 5]
Giải: ??????
Ví dụ 2.2.3: Cho ánh xạ


a) Xác định f(A) trong các trường hợp
A = [-1, 4]; A={-3, -2, 0, 1}
b) Xác định f-1(A) trong các trường hợp:
A=(0,5); A={-1, 0,4}
Giải: ?????

2.4) Định nghĩa 2.2.4: Cho ánh xạ


idA gọi là ánh xạ đồng nhất trên A
2. Ánh xạ (tiếp theo)
2. Ánh xạ (tiếp theo)
2.5) Định lý 2.2.1: Cho ánh xạ f: A  B, E1,E2A; F1,F2B. Ta có:

f(E1E2) = f(E1)f(E2)
f(E1E2)  f(E1)f(E2)
f-1(F1F2) = f-1(F1)f-1(F2)
f-1(F1F2) = f-1(F1)f-1(F2)

Chứng minh
a)Ta có:y  f(E1E2)  x (E1E2), y = f(x)
 (x E1, y=f(x))  (xE2, y = f(x))
  (yf(E1))  (y  f(E2))
  y f(E1)  f(E2)
Vậy f(E1E2) = f(E1)  f(E2)
2. Ánh xạ (tiếp theo)
Ví dụ 2.2.4:
2. Ánh xạ (tiếp theo)
2.6) Ánh xạ hợp: Cho 2 ánh xạ:


Ánh xạ hợp h = gof được định nghĩa:
f
g
h=gof
x
y=f(x)
g(y)
A
B
C
Và
2. Ánh xạ (tiếp theo)
Ví dụ 2.2.5: Cho 2 ánh xạ:
Ánh xạ hợp h=gf:
Với h(x)=g(f(x))=g(xcos(x+1))=2xcos(x+1)-3
1.7) Định nghĩa 2.2.5:
Ánh xạ f: AB gọi là toàn ánh nếu f(A)=B
Ánh xạ f: AB gọi là đơn ánh nếu:x1,x2A, x1x2f(x1)f(x2)
Ánh xạ f: AB gọi là song ánh nếu f vừa toàn ánh, vừa đơn ánh. (Kí hiệu f: AB)


2. Ánh xạ (tt)
f không đơn ánh, không toàn ánh
f Toàn ánh, không đơn ánh
f đơn ánh, không toàn ánh
f: Toàn ánh, đơn ánh nên f song ánh
2. Ánh xạ (tt)
Để chứng minh f: A  B là toàn ánh, ta chứng minh mệnh đề sau là hằng đúng:
yB xA, y=f(x)
Để chứng minh f: A  B không là toàn ánh, ta chứng minh mệnh đề sau là hằng đúng:
yBxA, yf(x)
Để chứng minh f: A  B là đơn ánh, ta chứng minh mệnh đề sau là hằng đúng:
x1A x2A, x1x2  f(x1)  f(x2)
Để chứng minh f: A  B không là đơn ánh, ta chứng minh mệnh đề sau là hằng đúng:
x1A x2A, x1x2  f(x1) = f(x2)
Ví dụ 2.2.6: Với mỗi ánh xạ f : Z  Z dưới đây, xét xem có phải là đơn ánh, toàn ánh, song ánh không?
a) f(x) = x + 7 b) f(x) = 2x – 3
c) f(x) = - x +5 d) f(x)=x2
e) f(x) = x2 + x f) f(x) = x3
Giải:?????
Ví dụ 2.2.7: Tương tự như ví dụ 2.2.2 nhưng ánh xạ f: R  R
Giải:????

2. Ánh xạ (tiếp theo)
3. Phép đếm
3.1) Định nghĩa 2.3.1.:
i) Tập A hữu hạn và có n phần tử (|A|=n) nếu tồn tại song ánh từ A vào tập con các số tự nhiên {1,2,…, n}.
ii) Nếu Tập A không hữu hạn, ta nói A vô hạn
3.2) Định nghĩa 2.3.2:
Lực lượng của tập hợp A bé hơn lực lượng của tập hợp B nếu tồn tại một đơn ánh từ A vào B.
Hai tập A và B có cùng lực lượng B nếu tồn tại một song ánh giữa A và B
3.3) Mệnh đề 2.3.1: Lực lượng của B nhỏ hơn hay bằng lực lượng của A khi và chỉ khi tồn tại một toàn ánh từ A lên B.

3. Phép đếm (tiếp theo)
3.4) Nguyên lý cộng:
Một quá trình có thể được thực hiện bằng 2 cách loại trừ lẫn nhau, cách thứ nhất cho m kết quả, cách thứ 2 cho n kết quả. Thực hiện tòan bộ quá trình sẽ cho m+n kết quả.
Phát biểu ở dạng tập hợp:với AB =  thì |AB| = |A|+|B|
Ví dụ 2.3.1:Giả sử có 20 công nhân làm việc trong phân xưởng 1, 30 công nhân làm việc trong phân xưởng 2. Một công nhân không thể làm việc trong cả 2 phân xưởng. Theo nguyên lý cộng, số công nhân trong cả 2 phân xưởng là: 20+30 = 50
Nguyên lý cộng mở rộng:
Nếu AB thì |AB| = |A| + |B| - |AB|
Cho tập hữu hạn C = C1C2…Cn, và Ci Cj= , ij
Thì: |C| = |C1| + |C2| + … + |Cn|
3. Phép đếm (tiếp theo)
Ví dụ 2.3.2:
Có 50 sinh viên đăng ký học phần Toán cao cấp và 40 sinh viên đăng ký học phần kế toán đại cương. Trong đó, 10 sinh viên đăng ký cả 2 học phần. Theo nguyên lý cộng mở rộng, số sinh viên đã đăng ký trong 2 học phần là:50 + 40 – 10 = 80
Ví dụ 2.3.4:
Trường ĐH Nông lâm Tp.HCM tham gia chiến dịch mùa hè xanh trên 3 tỉnh: Bình phước, Cà mau, Bến tre. Có 150 sinh viên tham gia tại Bình Phước, 300 sinh viên tham gia tại Cà mau và 80 sinh viên tham gia tại Bến tre. Mỗi sinh viên chỉ tham gia tại một tỉnh duy nhất.
Theo nguyên lý cộng, số sinh viên của trường tham gia mùa hè xanh là: 150+80+300 = 530
3. Phép đếm (tiếp theo)
3.5) Nguyên lý nhân:
Nếu một quá trình được thực hiện gồm 2 giai đọan độc lập với nhau. Giai đọan 1 có m cách thực hiện, giai đọan 2 có n cách thực hiện thì có m.n cách thực hiện khác nhau trên toàn bộ quá trình .
Ví dụ 2.3.5: Một lớp học có 5 sinh viên nữ, 10 sinh viên nam. Có bao nhiêu cách chọn ra 2 sinh viên bao gồm 1 nam và 1 nữ tham gia vào đại hội sinh viên?
Giải:
Có 5 cách chọn ra một sinh viên nữ trong 5 sinh viên nữ
Có 10 cách chọn ra 1 sinh viên nam
Theo nguyên lý nhân, có 510 = 50 cách chọn ra một nam và một nữ để tham gia đại hội.
Ví dụ 2.3.6: Cho A = {1,2,3,4,5,6,7,8,9}
Có bao nhiêu tập con của A có chứa ít nhất 1 số lẻ?
Giải: Đặt B = {1,3,5,7,9} và C ={2,4,6,8}. Ta có: A = BC
Gọi X là tập con cần tìm. X có dạng:
X = E1  E2 với E1P(B){}. E2P(C).
Mà: |(P(B){}|=25-1 = 31
|P(C)| = 24 = 16
Theo nguyên lý nhân, có 31 16 tập con X thỏa điều kiện

Ví dụ 2.3.7: Cho U = {1,2,3,4,5,6,7,8,9}
A = { 1,5,7}; B={1,2,3,5,7,9}
Có bao nhiêu tập con X của U để AX = B ?
Giải:????
3. Phép đếm (tiếp theo)
-

Ví dụ 2.3.8: Cho A = {1,2,3,4,5,6,7,8,9}. Có bao nhiêu tập con của A có chứa phần tử 1?
Giải: Gọi X là tập con thỏa điều kiện cần tìm. X phải có dạng:
X = {1}Y, với Y  A{1}
Có 28 tập con của A{1}, vậy cũng có 28 tập X cần tìm.
Ví dụ 2.3.9: Người ta dự định đánh mã số cho các ghế ngồi trong một rạp hát theo phương án: Mỗi ghế được đánh mã gồm 2 kí tự XY, trong đó X là một chữ cái trong tiếng anh và Y là một kí số (khác không). SỐ lượng tối đa có thể đánh mã là bao nhiêu?
3. Phép đếm (tiếp theo)
-
3. Phép đếm (tiếp theo)
3.6) Định lý 2.3.1:
Giả sử A và B là 2 tập hữu hạn. Nếu tồn tại một đơn ánh từ A vào B và một đơn ánh từ B vào A thì A và B có cùng số phần tử. Hơn nữa, mọi đơn ánh (toàn ánh) từ A vào B là một song ánh.
C/m:
Gọi f là đơn ánh từ A vào B và f(A)=E  B, Phần bù của E trong B. Ta có
Gọi g là đơn ánh từ B vào A và f(B)=CA, Phần bù của C trong A.
(*)
(*)
Từ (*) và (**)  |A| = |B|
3. Phép đếm (tiếp theo)
3.7) Tích Descartes:
Tích Descartes của 2 tập A và B (kí hiệu AB) là tập tất cả các cặp thứ tự (a,b) với a  A và b B
(a,b) = (c,d)  a = c và b = d
Tích Descartes của n tập khác rỗng A1, A2, …, An, được định nghĩa:


(a1, a2,…,an) = (b1, b2, …, bn)  a1=b1 và a2=b2 và … và an=bn

3. Phép đếm (tiếp theo)
Ví dụ 2.3.9:
A = {1,5}
B = {a, b, c, d}
AB = {(1,a), (1,b), (1,c), (1,d), (5,a), (5,b), (5,c), (5, d)}
3.8) Định lý 2.3.2:
Nếu A và B là 2 tập hữu hạn thì AB cũng hữu hạn và
|AB| = |A||B|
b) Nếu A1, A2, …, An là các tập hữu hạn thì cũng hữu hạn, và:
Chứng minh: Gợi ý, Sử dụng nguyên lý nhân
4. Giải tích tổ hợp
Gọi BA là tập các ánh xạ từ A vào B, với |A| = m.
4.1) Mệnh đề 2.4.1: |BA|=|B||A|
C/m: Xét f BA, f được xác định nếu biết (b1, b2,...,bm) Bm sao cho: b1=f(a1), b2=f(a2),…, bm= f(am).
Xét ánh xạ:

: song ánh (chứng minh?) nên: |BA| = |B||A|
4.2) Mệnh đề 2.4.2: Giả sử |B|=n (mn), số đơn ánh từ A vào B là:
n(n-1)(n-2)…(n-m+1)

Chứng minh?
a
Ví dụ: A={1,2}; B={a,b}. Số lượng ánh xạ từ A vào B là 22
f1
f2
f3
f4
4. Giải tích tổ hợp
Hệ quả: Nếu |A|=|B|=n, số song ánh giữa A và B là n!
Chứng minh: Thay m bởi n trong mệnh đề 2.4.2, ta được đều pcm.
4.3) Định nghĩa 4.1:
Hoán vị của một tập hợp các đối tượng khác nhau là một cách sắp xếp có thứ tự của các đối tượng trong tập hợp đó.
Một đơn ánh từ A vào A là một phép hóan vị của A




f
Ví dụ 2.4.1: (1,2,3,4), (2,1,3,4), (4,3,1,2) là 3 hoán vị từ tập {1, 2, 3, 4}
4. Giải tích tổ hợp
4.4) Định lý 4.1: Số phép hóan vị của tập hợp A gồm n phần tử là n!

Chứng minh: Số phép hoán vị của A = số đơn ánh (song ánh) từ (giữa) A và A là n!

Ví dụ 2.4.2: Số hoán vị của tập A={1,2,3} là 3!=6
Ví dụ 2.4.3: Có bao nhiêu cách sắp 5 đại biểu vào 5 chổ ngồi trong một buổi họp.
Giải: Mỗi cách sắp xếp là một hoán vị của 5 phần tử. Vậy số cách xếp là 5!=120

4.5) Định nghĩa 4.2: Một cách chọn ra m phần tử khác nhau theo một thứ tự nào đó từ n phần tử gọi là chỉnh hợp của n phần tử chọn m.

Ví dụ 2.4.4: Cho tập A={a,b,c,d}, (a,b), (b,a) là 2 chỉnh hợp của 4 phần tử chọn 2
4. Giải tích tổ hợp
4.6) Định lý 4.2: Số chỉnh hợp của n phần tử chọn m là:


Chứng minh:
Gọi B : tập n phần tử
A ={a1, a2, …, am}: Tập gồm m phần tử.

Số chỉnh hợp của n phần tử chọn m = số đơn ánh từ A vào B
Theo mệnh đề 2.4.2, số song ánh này là = n(n-1).(n-2)…(n-m+1)
(đcm)
4. Giải tích tổ hợp
Ví dụ 2.4.5: Có bao nhiêu cách xếp 4 công nhân từ 10 công nhân vào 4 công việc khác nhau?

Giải: Mỗi cách xếp 4 công nhân vào 4 công việc khác nhau là một chỉnh hợp của 10 phần tử chọn 4.
Vậy số cách xếp sẽ là:
4. Giải tích tổ hợp
4.7) Định nghĩa 4.3: Một tổ hợp của n phần tử chọn m (còn gọi là số tổ hợp chặp m của n phần tử) là một tập gồm m phần tử khác nhau chọn từ n phần tử không phân biệt thứ tự.
Ví dụ: Cho A={1,2,3,4}. Ta có {1,3,4} và {3,1,4} cùng là một tổ hợp của 4 phần tử chọn 3
4.8) Định lý 4.3: Số tổ hợp của n phần tử chọn m là:
Chứng minh: Bắt đầu bằng việc tính số chỉnh hợp của n phần tử chọn m. Quá trình được thực hiện bằng 2 bước:
Bước 1. Tính số tổ hợp của n phần tử chọn m. Số cách
Bước 2. Thực hiện các hoán vị trên mỗi tổ hợp để được các chỉnh hợp. Có m! hoán vị.
Theo nguyên lý nhân, số chỉnh hợp có được trên toàn bộ quá trình là:
4. Giải tích tổ hợp (tiếp theo)

Ví dụ 2.4.6: Có bao nhiêu cách chọn ra một đội bóng gồm 11 người từ danh sách gồm 30 cầu thủ (không quan tâm đến thứ tự).
Giải: Mỗi cách chọn là một tổ hợp của 30 phần tử chọn 11. Vậy số cách chọn là:
4.8) Định lý 4.4:
Chứng minh: Ta có
4. Giải tích tổ hợp (tiếp theo)
Định lý (Khai triển nhị thức):
Ví dụ 2.4.7:
Ví dụ 2.4.8: Cho biết hệ số của số hạng có chứa x3 trong phép khai triển của nhị thức: (x+y)100.
Giải:
Bài tập
Bài tập1: Cho biết hệ số của số hạng có chứa y51 trong phép khai triển của nhị thức: (x+2y)101.
Bài tập2: Cho biết hệ số của số hạng có chứa x50 trong phép khai triển của nhị thức: (2x2+y)56.

4. Giải tích tổ hợp (tiếp theo)
4.9) Hoán vị có lặp:
Ví dụ 2.4.9: Có bao nhiêu xâu chữ khác nhau có được từ việc sắp xếp lại các chữ cái SASSUNA?
Giải: Ta thấy có một số kí tự giống nhau trong các chữ cái trên: 3 kí tự S, 2 kí tự A, một kí tự U và 1 kí tự N. Phép hoán vị giữa các kí tự trong cùng loại là không tạo nên chuỗi mới.
Số cách xếp 3 kí tự S vào 3 trong 7 vị trí. Số cách xếp:
Số cách xếp 2 kí tự A vào 2 trong 4 vị trí còn lại. Số cách xếp:
Số cách xếp 1 kí tự U vào 1 trong 2 vị trí còn lại. Số cách xếp:
Số cách xếp 1 kí tự N vào 1 trong 1 vị trí còn lại. Số cách xếp:
Theo nguyên lý nhân, số xâu chữ khác nhau có được sẽ là:
4. Giải tích tổ hợp (tiếp theo)
Định lý 4.5: Số phép hoán vị của n phần tử, trong đó có n1 phần tử giống nhau thuộc loại 1, n2 phần tử giống nhau loại 2, …, nk phần tử giống nhau loại k là:


Chứng minh: Bài tập
Định lý 4.6: Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau, sao cho ni đồ vật được đặt vào hộp i (i=1,2,..,k) là:
4. Giải tích tổ hợp (tiếp theo)
4.10) Chỉnh hợp có lặp:
Ví dụ 2.4.10: Có bao nhiêu cách khác nhau để cách lấy ra 3 viên bi liên tiếp từ hộp đựng 5 viên bi thuộc 5 màu khác nhau? Biết rằng: Sau khi lấy một viên bi, viên bi phải được trả lại vào trong hộp.
Giải: -Số cách khác nhau để lấy viên bi thứ nhất là 5
-Vì viên bi được bỏ lại vào hộp sau khi lấy, do đó số cách khác nhau để lấy viên bi thứ hai và ba cũng là 5.
- Theo nguyên lý nhân, số cách khác nhau để chọn 3 viên bi là: 53

Định lý 4.7: Chỉnh hợp của n phần tử chọn m cho phép các phần tử được chọn có thể lặp lại là nm.


4. Giải tích tổ hợp (tiếp theo)
4.11) Tổ hợp có lặp:
Ví dụ 2.4.11: Có bao nhiêu cách chọn ra 4 tờ bạc từ 3 loại tờ bạc: 1000, 2000 và 5000. Biết rằng: Thứ tự các tờ bạc được chọn là không quan trọng và mỗi tờ bạc có thể chọn nhiều hơn 1 lần.
Giải: Có thể tìm số cách chọn bằng cách liệt kê tất cả các trường hợp có thể:
- Chọn 4 tờ 1000
- Chọn 4 tờ 2000
- Chọn 4 tờ 50000
- Chọn 3 tờ 1000, 1 tờ 2000
- Chọn 3 tờ 1000, 1 tờ 5000
- Chọn 2 tờ 1000, 2 tờ 2000
- Chọn 2 tờ 1000, 2 tờ 5000
…..
Khó có thể liệt kê đầy đủ tất cả các trường hợp khi số lượng phần tử lớn.
4. Giải tích tổ hợp (tiếp theo)
Một cách giải khác:
Tủ gồm 3 ngăn
Loại 1000
Loại 2000
Loại 5000
*
*
*
*
2 tờ 1000
1 tờ 2000
1 tờ 5000
một cách chọn 4 tờ bạc
chọn
chọn
chọn
Nhận xét: Bằng cách thay đổi vị trí của 2 vạch ngăn trong 6 vị trí, ta có được cách chọn mới.
4. Giải tích tổ hợp (tiếp theo)
Một số cách chọn có được bằng cách thay đổi vị trí của các vạch ngăn:
Vậy số cách chọn ra 4 tờ bạc = số cách chọn ra các vị trí của 2 vạch ngăn trong 4+3-1=6 vị trí và bằng:
4. Giải tích tổ hợp (tiếp theo)
Định lý 4.8: Số cách chọn ra m đồ vật (không thứ tự và cho phép lặp lại) từ n loại đồ vật khác nhau là:
Ví dụ 2.4.12: Có bao nhiêu cách xếp 6 trái cây từ 3 loại: Cam, lê và xoài vào một đĩa.
Ví dụ 2.4.13: Tìm số nghiệm nguyên không âm của phương trình:
x1+x2+x3+x4 = 7
Ví dụ 2.4.14: Tìm số nghiệm nguyên của phương trình:
x1+x2+x3=10
Biết rằng: x1>=0, x2>=2, x3>=1
Ví dụ 2.14.15: Có bao nhiêu nghiệm nguyên không âm của bất phương trình: x1+x2+x311
Ví dụ 2.14.16: Đề thi trắc nghiệm có 10 câu. Có bao nhiêu cách gán điểm cho các câu hỏi để tổng điểm là 100. Biết rằng, mỗi câu có ít nhất là 5 điểm.
5. Nguyên lý Dirichet (nguyên lý chuồng bồ câu)
5.1) Định lý 5.1 (nguyên lý chuồng bồ câu): Nếu có từ k+1 vật khác nhau được bỏ vào k hộp thì có ít nhất 1 hộp chứa nhiều hơn một đồ vật
Tổng quát: Nếu có N vật đặt vào k hộp, phải tồn tại ít nhất một hộp chứa ít nhất N/k đồ vật.
5. Nguyên lý Dirichet (nguyên lý chuồng bồ câu)
Ví dụ 2.4.7: Trong 100 người có ít nhất 100/12 = 9 người sinh cùng tháng
Ví dụ 2.4.8: Trong một tháng 30 ngày, một đội bóng thi đấu ít nhất mỗi ngày một trận và không quá 45 trận. Chứng tỏ rằng có một thời gian gồm một số ngày liên tiếp, đội bóng phải đấu tất cả 14 trận.
Ví dụ 2.4.9: Chứng minh rằng trong một buổi họp có n người thì luôn luôn tìm được ít nhất là 2 người có số người quen bằng nhau?
Bài tập
1. Cho các tập hợp con A, B, C, D của tập vũ trụ U. Hãy chứng minh các khẳng định sau đây là đúng:
Nếu A  B và C  D thì:
A  C  B  D và A  C  B  D
Nếu A  C và B  C thì A  B C và A  B  C
A  B khi và chỉ khi A  B = 
A  B khi và chỉ khi Ā  B = U

Bài tập
2) Trong số các khẳng định dưới đây, khẳng định nào đúng:
a) A, B, C  P(U), (A  C = B  C)  (A = B)
b) A, B, C  P(U), (A  C = B  C)  (A = B)
c) A, B, C  P(U),(AC = BC)  (AC = BC)  (A=B)
3)Dùng các quy luật của lý thuyết tập hợp để đơn giản các biểu thức sau:
a) A  (B  A)
b) (A  B)  (A  B  C  D)  (A  B)
c) A  B  (A  B  C)






Bài tập
4) Với mỗi ánh xạ f: A → B sau đây, cho biết nó có phải là đơn ánh, tòan ánh hoặc song ánh không? Nếu là song ánh thì tìm ánh xạ ngược?
a) A = B = R, f(x) = x2+2x-3
b) A = [4,9], B=[21,96], f(x)= x2+2x-3
c) A=B = R, f(x) = 3x – 2|x|
d) A=R, B=(0,+), f(x)=ex+1
e) A=B=N, f(x)=x(x+1)
Bài tập
5) Xét 2 ánh xạ f,g: R → R, f(x)=ax+b, g(x)=x2-x+1. Giả sử (g°f)(x)=9x2-9x+3, x R. Tìm a,b?

6) Cho S = {0,1,2,3,4,5,6,7,8,9,10}. Có bao nhiêu tập con A của S thỏa:
a) Số phần tử của A (|A|)=6
b) |A| = 6 và phần tử bé nhất của A là 2
c) |A|=5 và phần tử bé nhất của A bé hơn hay bằng 3
d) A có nhất nhất 1 số chẳn


Bài tập
7) Một lớp học gồm 10 sinh viên nam và 15 sinh viên nữ. Có bao nhiêu cách chọn ra 12 sinh viên từ 25 sinh viên của lớp. Biết rằng:
a) Không có hạn chế nào cả
b) Phải có 6 nam và 6 nữ
c) Số nữ là số chẵn
d) Phải có số nữ nhiều hơn nam
c) Có ít nhất 8 nam
Bài tập
8) Có bao nhiêu cách để xếp 5 sinh viên từ 30 sinh viên vào một bàn (thứ tự của các sinh viên được xếp cũng là quan trọng)
9) Một lớp học có 50 sinh viên. Có bao nhiêu cách chia lớp thành 10 tổ
10) Tìm số nghiệm nguyên không âm của phương trình:
x1+x2+x3+x4 = 12
Biết rằng: x2  2, x4>0
11) Có bao nhiêu cách khác nhau để chia 12 quyển sinh cho 4 đứa trẻ? Biết rằng
a) Mỗi đứa trẻ được 3 quyển sách
b) Hai đứa lớn nhất được 4 quyển mỗi đứa và 2 đứa bé nhất được 2 quyển mỗi đứa.
Bài tập
12) Tìm hệ số có chứa x9 trong:
a) (x+y)12 b) (2x+3y)15 c) (3x-4y)11
c) (x+y+z)10
13) Chứng minh rằng trong 14 phần tử khác nhau tùy ý của
S = {1,2,3,…,25} có ít nhất 2 phần tử có tổng là 26