Bài giảng Toán học sơ cấp - Phần III: Tập hợp, ánh xạ, phép đếm - Nguyễn Viết Đông

?
?
?
A cool example
2k
2k 2k
2k
2k+1
OK!! 
(by 
IH)
OK!! 
(by 
IH)
OK!! 
(by 
IH)
OK!! 
(by 
IH)
A cool example A cool example
9A cool example 5.2.Strong Mathematical Induction
If
• P(0) and
• n  0 (P(0)  P(1)    P(n))  P(n +1)
Then
• n  0 P(n)
In our proofs, to show P(k+1), our 
inductive hypothesis assures that ALL 
of P(0), P(1),  P(k) are true, so we can 
use ANY of them to make the 
inference.
34
5.2.Strong Mathematical Induction
• Theorem . Every integer n > 1 is a product of 
primes.
Proof. Let pn denote the statement of the theorem. Then 
p2 is clearly true.
If p2, p3, . . . , pk are all true, consider the integer k + 1. 
If k + 1 is a prime,there is nothing to prove. 
Otherwise, k + 1 = ab, where 2  a, b  k
But then each of a and b are products of primes because
pa and pb are both true by the (strong) induction
assumption. Hence ab = k + 1 is also a product of
primes, as required. 35
5.3. Inductive Definitions
We completely understand the function f(n) = n !,
right?
Inductive (Recursive) Definition
But equivalently, we could define it like this:

n!
n  (n 1)!, if n 1
1, if n 1



Recursive Case
Base Case
As a reminder, here’s the definition:
n ! = 1 · 2 · 3 ·  · (n –1) · n, n  1
36
10
Another VERY common example:
Fibonacci Numbers
Recursive Case
Base Cases

f (n) 
0 if n  0
1 if n 1
f (n 1)  f (n  2) if n 1





Is there a non-recursive definition for the 
Fibonacci Numbers?

f (n) 
1
5
1 5
2






n

1 5
2






n







5.4. Inductive Definitions
37
Our examples so far have been inductively 
defined functions.
Sets can be defined inductively, too.
Recursive Cases
Base Case
Give an inductive definition of S = {x: x is a multiple of 3}
x, y  S  x + y  S 
x, y  S  x – y  S
5.4. Inductive Definitions
3  S
No other numbers are in S.
38
Let  be a finite set called an alphabet. 
The set of strings on , denoted * is 
defined as: 
–   *, where  denotes the null or 
empty string.
– If x  , and w  *, then wx  *, 
where wx is the concatenation of string 
w with symbol x.
5.5. Inductive Definitions of Strings
39
5.5. Inductive Definitions of Strings
If x  , and w  *, then wx  *, where wx is the 
concatenation of string w with symbol x.
Infinite
Example: Let  = {a, b, c}. Then 
* = {, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab,}
How big is *?
Are there any infinite strings in *? No.
Is there a largest string in *? No.
40
11
Inductive definition of the length of strings (the 
length of string w is denoted by |w|.):
• || = 0
• If x  , and w  *, then |wx| = |w| + 1
I point this out because 
the length of strings is something 
we might like to use for an 
inductive argument.
5.5. Inductive Definitions of Strings
41
Inductive definition of the reversal of a string (the 
reversal of string w is denoted by wR.):
• R = 
• If x  , and w  *, then (wx)R = ?
For example (abc)R = cba
x(w)R
because (abc)R = c(ab)R
= cb(a)R
= cba()R
= cba = cba
5.5. Inductive Definitions of Strings
42
43
Phép đếm
1. Nguyên lý cộng và nguyên lý nhân
1.1. Nguyên lý cộng
Nếu có m cách chọn x, n cách chọn đối tượng y và nếu
cách chọn đối tượng x không trùng với bất kỳ cách chọn
đối tượng y nào, thì có m+n cách chọn 1 trong các đối
tượng đã cho.
1.2. Nguyên lý nhân
Nếu có m cách chọn đối tượng x và cứ mỗi cách chọn x
luôn luôn có n cách chọn đối tượng y thì có m.n cách
chọn cặp đối tượng (x, y).
44
12
Phép đếm
Ví dụ.
Cho A và B là hai tập hợp.Tập hợp các ánh xạ 
từ A vào B được ký hiệu bởi BA.Giả sử A=m ,
B= n thì BA= nm.Thật vậy, mỗi phần tử ai thuộc
A có n cách chọn ảnh f(a i) của nó trong tập B.
Theo qui tắc nhân ta có n.n. n = nm cách chọn
bộ (f(a1), f(a2), , f(an)).Tức là ta có n
m ánh xạf.
45
Phép đếm
2. Hoán vị.
a) Đị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ầntử 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 
b) Pn = n!
c) Ví dụ:Nếu A là tập hợp n phần tử thì số song 
ánh từ A vào A là n!
46
Phép đếm
3. Chỉnh hợp.
a) Đị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 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à
b)Công thức 
k
nA
 
!
!
k
n
n
A
n k


47
Phép đếm
4.Tổ hợp.
a) Đị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ử. Số các tổ hợp chập k
của n phần tử đựơc ký hiệu là
hay k
nC 





k
n
48
13
Phép đếm
b) Công thức
c) Tính chất 
 
!
! !
k
n
n
C
k n k


n k k
n nC C
 
1
1
k k k
n n nC C C

 
49
Phép đếm
5. Hoán vị lặp.
a) Đị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.
50
Phép đếm
b) Số hoán vị của n đối tượng, trong đó có n1 đối 
tượng giống nhau thuộc loại1, 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
51
Phép đếm
• Ví dụ: Có bao nhiêu chuỗi kí tự khác nhau bằng cách
sắp xếpp 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!

52
14
Phép đếm
6.Tổ hợp lặp.
a) Đị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. Số các
tổ hợp lặp chập k của n được ký hiệu là
k
nK
53
Phép đếm
b) Công thức
c)Hệ quả. Số nghiệm nguyên không âm(x1,x2,,xn) 
(mỗi xi đều nguyên không âm) của phương trình
x1+ x2++ xn = k là
1
k k
n n kK C  
1
k k
n n kK C  
54
Phép đếm
Số cách chia k vật đồng chất nhau vào n hộp 
phân biệt cũng chính bằng số tổ hợp lặp chập 
k của n
1
k k
n n kK C  
55
Phép đếm
Ví dụ: Tìm số nghiệm nguyên không âm của phương trình
x1+ x2 + x3 + x4 = 20 (1)
thỏa x1  3; x2 2; x3 > 4 ().
Giải.
Ta viết điều kiện đã cho thành x1  3; x2  2; x3  5.
Xét các điều kiện sau:
• x2  2; x3  5 ()
• x1  4; x2  2; x3  5 ()
• Gọi p, q, r lần lượt là số nghiệm nguyên không âm của phương
trình (1) thỏa các điều kiện (), (), (). Ta có:
56
15
Phép đếm
p = q – r.
Trước hết ta tìm q.
Đặt
x1’ = x1; x2’ = x2 – 2; x3’ = x3 - 5; x4’ = x4
Phương trình (1) trở thành
x1’+ x2’ + x3’ + x4’ = 13 (2)
Số nghiệm nguyên không âm của(1) thỏa() bằng số
nghiệm nguyên không âm của(2)
57
Phép đếm
Số nghiệm là .
Vậy .
Lý luận tương tự, ta có .
Suy ra
Vậy số nghiệm nguyên không âm của phương
trình (1) thỏa điều kiện () là 340
13 13 13
4 4 13 1 16K C C  
13
16q C
9 9 9
4 4 9 1 12r K C C   
13 9
16 12 560 220 340.p q r C C      
58
Phép đếm
Ví dụ: Tìm số cách xếp 30 viên bi giống nhau vào 5
hộp khác nhau sao cho hộp 1 có ít nhất 5 bi, biết rằng
hộp 2 và 3 chứa không quá 6 bi.
Giải.
Trước hết ta tìm số cách xếp 30 viên bi giống nhau vào
5 hộp khác nhau sao cho hộp 1 có ít nhất 5 bi. Nhận
xét rằng ta cần lấy 5 bi để xếp trước vào hộp 1, do đó
số bi còn lại chỉ là 25. Suy ra số cách xếp trong
trường hợp này bằng số cách xếp 25 bi vào 5 hộp mà
không có điều kiển gì thêm. Số đó là
59
Phép đếm
Tương tự ta có
Số cách xếp 30 viên bi giống nhau vào 5 hộp
khác nhau sao cho hộp 1 chứa ít nhất 5 bi, hộp 2
chứa ít nhất 7 bi là
25 25 25
5 5 25 1 29 23751.   K C C
18 18 18
5 5 18 1 22K C C  
60
16
Phép đếm
• - Số cách xếp 30 viên bi giống nhau vào 5 hộp 
khác nhau sao cho hộp 1 chứa ít nhất 5 bi, hộp 
3 chứa ít nhất 7 bi là 
-
18 18 18
5 5 18 1 22K C C  
61
Phép đếm
• Số cách xếp 30 viên bi giống nhau vào 5 hộp 
khác nhau sao cho hộp 1 chứa ít nhất 5 bi, mỗi 
hộp 2 và 3 chứa ít nhất 7 bi là:
11 11 11
5 5 11 1 15K C C  
62
Phép đếm
• Sử dụng công thức
Ta suy ra số cách xếp 30 viên bi giống nhau vào
5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi,
đồng thời hộp 2 hay hộp 3 chứa ít nhất 7 bi là
| | | | | | | |A B A B A B    
18 18 11 18 18 11
5 5 5 22 22 15 13265.     K K K C C C
63
Phép đếm
• Theo yêu cầu của bài toán, khi xếp 30 viên bi 
vào 5 hộp thì hộp 1 phải có ít nhất 5 bi còn
mỗi hộp 2 và 3 phỉa có không quá 6 bi. Do đó
số cách xếp này sẽ bằng hiệu của số cách xếp
(1) và (2), tức là bằng
23751 13265 10486. 
64
17
Phép đếm
• 7. NGUYÊN LÝ DIRICHLET
• Giả sử có n vật cần đặt vào k hộp. Khi đó tồn
tại ít nhất một hộp chứa từ vật trở lên.
Trong đó là số nguyên dương nhỏ nhất
không bé hơn n/k
/n k  
/n k  
65
Phép đếm
• Ví dụ. Trong số 100 người luôn luôn có ít nhất
là người có sinh nhật trong cùng một
tháng.
• Ví dụ. Cần tạo ít nhất bao nhiêu mã vùng để
đảm bảo cho 84 triệu máy điện thoại mỗi máy
một số thuê bao biết rằng mỗi số thuê bao
gồm 7 chữ số, trong đó chữ số đầu khác 0?
100/12 9  
66
Phép đếm
• Giải. Theo Nguyên lý nhân, có 9 triệu số thuê
bao khác nhau có đúng 7 chữ số, trong đó chữ 
số đầu khác 0. Theo nguyên lý Dirichlet, trong 
số 84 triệu máy điện thoại có ít nhất là 
máy có cùng một số thuê bao. Do đó để đảm
bảo mỗi máy một số thuê bao cần tạo ra ít nhất là
10 mã vùng.
84/9 10  
67
Isaac Newton 
(1643-1727)
68
18
Khai triển nhị thức Newton
•
• Với x, y  R và n là số nguyên dương ta có
0
( )
n
n k n k k
n
k
x y C x y

 
69
Mở rộngKhai triển nhị thức Newton
.
Với các số nguyên không âm n1,n2,,nk thoả 
n1+n2++nk = n, ký hiệu
!!...!
!
,...,,
2121 kk nnn
n
nnn
n






70
Mở rộng Khai triển nhị thức Newton









nnnn
n
k
nn
k
n
k
k
kaaa
nn
n
aaa
...
21
1
21
21
21 ...
,...,
)...(
71