ế
ậ
ạ
ợ
ầ Ph n III. T p h p, ánh x , phép đ m
Biên so n:ạ ế
ễ
TS.Nguy n Vi
t Đông
1
ệ
ả Tài li u tham kh o
•
ễ
ờ ạ
•
ầ
ọ
ộ
ữ [1]GS.TS Nguy n H u Anh, Toán r i r c, NXB Giáo d cụ ờ ạ [2]TS. Tr n Ng c H i, Toán r i r c
2
ậ
ợ
T p h p
B (cid:0) B (cid:0) x(cid:0) A (cid:0) x(cid:0) B.
B (cid:0) x(cid:0)
A (cid:0)
B .
ậ ợ . 1.Các phép toán trên t p h p x(cid:0) A (cid:0) x(cid:0) B. (cid:0) A (cid:0) Phép h p: xợ x(cid:0) A (cid:0) x(cid:0) B. Phép giao : x(cid:0) A (cid:0) (cid:0) A \ B (cid:0) ệ Hi u : x ố ứ ệ Hi u đ i x ng x(cid:0) B (cid:0) x(cid:0) A (cid:0) ầ Ph n bù :Cho A
A (cid:0) (cid:0) E thì =
A E A
\
3
ậ
ợ
T p h p
B = {(a,b) (cid:0) a(cid:0) A,b (cid:0) B}
Tích Descartes: A(cid:0) A1(cid:0) A2(cid:0) …(cid:0) An = {(a1,a2,…,an) (cid:0) ai(cid:0) A i , i = 1,2,…,n}
4
(cid:0)
ậ
ợ
T p h p
A
i
A
(x ) i i
I , x i
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) i I i
5
(cid:0) i I
ậ
ợ
T p h p
ậ ợ
A = A
B = B (cid:0)
B = B (cid:0)
A.
(B (cid:0)
B) (cid:0)
ấ ủ 2.Tính ch t c a phép toán trên t p h p ỹ ẳ 2.1) Tính lu đ ng: A (cid:0) A = A và A (cid:0) 2.2) Tính giao hoán: A và A (cid:0) A (cid:0) ế ợ 2.3) Tính k t h p: C = A (cid:0) (A (cid:0) và (A (cid:0)
C) (B (cid:0)
C = A (cid:0)
B) (cid:0)
C)
6
ậ
ợ
T p h p
(B (cid:0) B) (cid:0) C) = (A (cid:0) (A (cid:0)
�
�
�
�
(B (cid:0) C) (A (cid:0) C)
= A B A B
,
2.4) Tính phân ph i: ố A (cid:0) B) (cid:0) và A (cid:0) C) = (A (cid:0) ứ 2.5) Công th c De Morgan: = A B A B
C) = (A \ B) (cid:0) (A \ C)
7
Suy ra: A \ (B (cid:0) và A \ (B (cid:0) C) = (A \ B) (cid:0) (A \ C).
ậ
ợ
T p h p
{x i
I, x A }
i
i
ở ộ M r ng I A
(cid:0) (cid:0) (cid:0) (cid:0)
i
I
(cid:0)
A
{x i
I, x A }
i
i
U
(cid:0) (cid:0) (cid:0) (cid:0)
i
I
(cid:0)
A
i
i
I A
(cid:0)
i
I
i
I
(cid:0) (cid:0)
A
i
i
(cid:0)
I A
i
I
i
I
8
(cid:0) (cid:0)
ậ
ợ
T p h p
ố
ầ ử ủ ậ
c a t p
1)
ố ầ ử ủ ậ ợ ữ ạ 3.S ph n t c a t p h p h u h n. ợ ữ ạ ậ Cho A là t p h p h u h n.S ph n t (cid:0) A(cid:0) .Ta có: ệ A ký hi u là (cid:0) A(cid:0) B(cid:0) = (cid:0) A(cid:0) + (cid:0) B(cid:0) (cid:0) A(cid:0) B(cid:0) .
ủ
ậ
ậ
2) (cid:0) A(cid:0) B(cid:0) = (cid:0) A(cid:0) (cid:0) B(cid:0) 3) (cid:0) P (A)(cid:0) = 2 (cid:0) A(cid:0) ,P (A) là t p các t p con c a
A
9
Ánh xạ
ị ệ
ị
(cid:0) ừ ậ . M t ộ ánh x ạ f t X vào Y là
ủ ớ
x c a X v i môt ọ ệ ầ ử duy nh t y c a Y mà ta ký hi u là f(x) và g i là
ủ ạ
Y
10
1.Đ nh nghĩa và ký hi u 1.1. Đ nh nghĩa (cid:0) ơ Cho hai t p h p X, Y ỗ ắ ặ ươ ứ ng ng m i ph n t qui t c đ t t ấ ầ ử ph n t nhả c a x qua ánh x f. Ta viêt: ủ f : X (cid:0) a x f(x)
Ánh x ạ
ừ
ượ ọ
b ng ằ
X vào Y đ
c g i là
(cid:0)
ượ c X vào Y và A
X, B (cid:0)
Y. Ta
ị
ạ ằ 1.2. Ánh x b ng nhau ạ Hai ánh x f và g t nhau n u ế (cid:0) x (cid:0) X, f(x) = g(x). ả Ả 1.3. nh và nh ng ạ ừ Cho ánh x f t đ nh nghĩa:
11
Ánh xạ
A, y = f(x)} (cid:0) x (cid:0) (cid:0) x (cid:0)
A, y = f(x); A, y (cid:0) f(x).
f(A) = {f(x) (cid:0) x (cid:0) = {y (cid:0) Y, y (cid:0) (cid:0) y (cid:0) Y, y (cid:0) (cid:0) y (cid:0) f–1(B) = {x (cid:0) X, x (cid:0) (cid:0) x (cid:0) X, x (cid:0) (cid:0) x (cid:0)
A} Y (cid:0) (cid:0) x (cid:0) f(A) (cid:0) f(A) (cid:0) X (cid:0) f(x) (cid:0) f–1(B) (cid:0) f–1(B) (cid:0)
B} f(x) (cid:0) f(x) (cid:0)
B; B.
12
Ánh xạ
ở ở ng ký hi u f(X) b i Imf và f1({y}) b i
ủ ạ ệ ượ ọ c g i là nhả c a ánh x f.
f(A2); f(A2);
f–1(B2); f–1(B2);
13
ườ Ta th f1(y). Imf đ Tính ch t:ấ A2) = f(A1) (cid:0) f(A1 (cid:0) f(A1) (cid:0) A2) (cid:0) f(A1 (cid:0) f(A1 \ A2) (cid:0) f(A1) \ f(A2); B2) = f–1(B1) (cid:0) f–1(B1 (cid:0) B2) = f–1(B1) (cid:0) f–1(B1 (cid:0) f–1(B1 \ B2) = f–1(B1) \ f–1(B2).
Ánh xạ
Ạ
ơ
n u hai ph n
ế ả
ề
Ạ ầ Y là m t ộ đ n ánh ấ ỳ ủ khác nhau b t k c a X đ u có nh khác
2. PHÂN LO I ÁNH X ơ 2.1. Đ n ánh Ta nói f : X (cid:0) ử t nhau, nghĩa là: X, x (cid:0) (cid:0) x, x' (cid:0)
f(x) (cid:0)
f(x' )
x' (cid:0)
14
Ánh xạ
•
(cid:0) ộ ơ Y là m t đ n ánh X, f(x) = f(x') (cid:0)
(cid:0) x = x'). ấ
(cid:0) ượ Y, f–1(y) có nhi u nh t m t ph n t ). Y, ph
(cid:0) ươ ề ệ ấ ộ ầ ử ư c xem nh X.
ộ ơ f : X (cid:0) ((cid:0) x, x' (cid:0) ((cid:0) y (cid:0) ộ ề ((cid:0) y (cid:0) ng trình f(x) = y (y đ ố tham s ) có nhi u nh t m t nghi m x • Suy ra: f : X (cid:0) Y không là m t đ n ánh
(cid:0)
(cid:0) ượ Y, ph ư c xem nh
15
(cid:0) ((cid:0) x, x' (cid:0) ((cid:0) y (cid:0) ố X, x (cid:0) x' và f(x) = f(x')). ươ ng trình f(x) = y (y đ ệ ấ X tham s ) có ít nh t hai nghi m x
Ánh xạ
ế
Y là m t ộ toàn ánh n u Imf = Y. ấ
ự ế ừ ị
c suy tr c ti p t
đ nh nghĩa.
2.2. Toàn ánh: Ta nói f : X (cid:0) ữ Nh ng tính ch t sau đ f : X (cid:0)
ượ Y là môt toàn ánh
(cid:0)
X, y = f(x)) );
(cid:0)
(cid:0)
ượ
ư
ng trình f(x) = y (y đ
c xem nh tham
(cid:0)
Y, (cid:0) x (cid:0) Y, f–1(y) (cid:0) Y, ph ệ
X.
((cid:0) y (cid:0) ((cid:0) y (cid:0) (cid:0) y (cid:0) ươ ố s ) có nghi m x Suy ra: f : X (cid:0)
(cid:0)
f(x));
(cid:0)
ộ Y không là m t toàn ánh X, y (cid:0) (cid:0)
Y, (cid:0) x (cid:0) Y, f–1(y) (cid:0)
);
((cid:0) y (cid:0) ((cid:0) y (cid:0)
16
(cid:0)
Ánh xạ
ừ ế ơ ạ ượ c: Y là m t ộ song ánh n u f v a là đ n
2.3. Song ánh và ánh x ng Ta nói f : X (cid:0) ừ ánh v a là toàn ánh. Tính ch t.ấ f : X (cid:0) Y là m t song ánh
(cid:0)
(cid:0)
(cid:0) ươ ộ Y, (cid:0) !x (cid:0) X, y = f(x)); ộ Y, f–1(y) có đúng m t ph n t ); Y, ph ư c xem nh
17
(cid:0) ệ ấ ộ ((cid:0) y (cid:0) ((cid:0) y (cid:0) (cid:0) y (cid:0) ố ng trình f(x) = y (y đ tham s ) có duy nh t m t nghi m x ầ ử ượ X.
Ánh xạ
ộ
Y là m t song ánh. Khi đó, theo
ọ
i duy
ấ
Y, t n t ỏ
c
(cid:0)
• Xét f : X (cid:0) ớ ấ ồ ạ tính ch t trên, v i m i y ầ ử (cid:0) ộ nh t m t ph n t x X th a f(x) = y. Do đó a ạ ừ ộ ươ ứ ng ngy x là m t ánh x t t Y vào X. ệ ủ ạ ượ c a f và ký hi u ọ Ta g i đây là ánh x ng f–1. Nh v y:
ư ậ X
ớ
f–1 : Y (cid:0) a y f–1(y) = x v i f(x) = y.
18
Ánh xạ
ị
) (cid:0) [1, +(cid:0) ) (cid:0)
ở ị R đ nh b i g(x) = P(x); ị ) đ nh b i h(x) = P(x); [1, +(cid:0)
) đ nh b i k(x) = P(x);
ạ
ườ
ở ơ ạ ượ c trong tr
ng h p
Cho P(x) = x2 – 4x + 5 và các ánh xạ f : R (cid:0) R đ nh b i f(x) = P(x); g : [2, +(cid:0) ở h : R (cid:0) ở k : [2, +(cid:0) ị Hãy xét xem ánh x nào là đ n ánh, toàn ánh, ợ song ánh và tìm ánh x ng là song ánh.
19
Ánh xạ
Ạ Ủ Ợ
ị Cho hai ánh xạ
Y và g : Y' (cid:0)
ủ h c a f và g là ánh x t ạ ừ
Z ạ Y'. Ánh x tích ị ở
Z
t:ế
Z
a
20
3. TÍCH (H P THÀNH)C ACÁC ÁNH X 3.1. Đ nh nghĩa: f : X (cid:0) trong đó Y (cid:0) X vào Z xác đ nh b i: h : X (cid:0) a x h(x) = g(f(x)) • Ta vi Y (cid:0) h = g o f : X (cid:0) a x f(x) h(x) = g(f(x))
Ánh xạ
ộ
Y là m t song ánh. Khi đó:
ạ ồ
ệ
ấ
ở
ánh
ọ X; ta g i IdX là
(cid:0) x (cid:0)
ươ
ự
ạ ồ
ấ trên X, t
ng t
IdY là ánh x đ ng 21
ấ
(cid:0)
ị 3.2. Đ nh lý: Xét f : X (cid:0) f o f–1 = IdY f–1 o f = IdX trong đó ký hi u IdX là ánh x đ ng nh t X X ị đ nh b i IdX(x) = x, xạ ồ đ ng nh t nh t trên Y.
Ánh xạ
ủ ậ ợ . ng c a t p h p ặ ươ ứ
ộ ố
ớ ng ng v i m t đ i
ự ượ l c l
ng c a t p
ủ ậ A , sao cho (cid:0) A(cid:0) =
ồ ạ
i song ánh t ượ ọ
ng c a t p A còn đ
ừ c g i là
ự A vào B. L c ả ố ủ A b n s c a
ệ
ự ượ
ủ ậ ỗ
ố ng c a t p r ng là s 22
ự ượ 4.L c l ỗ ậ M i t p A ta đ t t ngượ t (cid:0) A(cid:0) g i là ọ (cid:0) B(cid:0) ỉ khi và ch khi t n t ủ ậ ượ l và ký hi u là cardA. L c l 0
ự ượ
ủ ậ
L c l
ng c a t p {1,2,…,n} là n.
Ánh xạ
N0
ng c a t p s t
ệ ủ ậ ố ự nhiên ký hi u là ế ự ượ ọ ng đ m l c l c g i
ự ượ
N (alep).
ậ ố , t p h p s nguyên, t p s
ự ượ
ậ ẵ
ủ ậ ố ự ượ ọ ng c a t p s th c đ ệ và ký hi u là ợ ố ượ c.
ự ượ
ng
ự ượ L c l ọ (đ c là alép không) và g i là ự ượ cượ , còn l c l đ ng continum là l c l ợ ố ữ ỷ ậ T p h p s h u t ế ng đ m đ ch n có l c l ạ ả Kho ng (0 ; 1), đo n [0 ; 1 ] có l c l continum
23
5. Mathematical Induction(Qui n pTHạ
)
5.1. Mathematical Induction
Prove that if a set S has |S| = n, then |P(S)| = 2n
Base case (n=0): S = ø, P(S) = {ø} and |P(S)| = 1 = 20
Assume P(k): If |S| = k, then |P(S)| = 2k
Inductive hypothesis Prove that if |S’| = k+1, then |P(S’)| = 2k+1
S’ = S (cid:0) {a} for some S (cid:0) S’ with |S| = k, and a (cid:0) S’.
24
Partition the power set of S’ into the sets containing a and those not.
We count these sets separately.
5.1.Mathematical Induction
Assume P(k): If |S| = k, then |P(S)| = 2k
Prove that if |S’| = k+1, then |P(S’)| = 2k+1
S’ = S (cid:0) {a} for some S (cid:0) S’ with |S| = k, and a (cid:0) S’.
Partition the power set of S’ into the sets containing a and those not. P(S’) = {X : a (cid:0) {X : a (cid:0) X} (cid:0) X}
P(S’) = {X : a (cid:0) X} (cid:0) P(S)
25
Since the elements of the 2nd set are the subsets of S.
5.1.Mathematical Induction
S’ with |S| = k, and a (cid:0) S’.
{a} for some S (cid:0) X} (cid:0) X} = {{a} (cid:0) P(S) X ' : a (cid:0) X'}
Prove that if |S’| = k+1, then |P(S’)| = 2k+1 S’ = S (cid:0) P(S’) = {X : a (cid:0) {X : a (cid:0) So |{X : a (cid:0) X}| = |P(S)|
|P(S’)| = |{X : a (cid:0) X}| + |P(S)| Subsets containing a are made by taking any set from P(S), and inserting a.
26
= 2 |P(S)| = 2(cid:0) 2k = 2k+1
A cool example
Deficient Tiling
2n
2n
A 2n x 2n sized grid is deficient if all but one cell is tiled.
A cool example
We want to show that all 2n x 2n sized deficient grids can be tiled with tiles shaped like:
A cool example
Base case
Yes
Is it true for 21 x 21 grids?
Inductive Hypothesis: We can tile a 2k x 2k deficient board using our fancy designer tiles. Use this to prove: We can tile a 2k+1 x 2k+1 deficient board using our fancy designer tiles.
A cool example
2k
2k
2k
?
?
2k+1
OK!! (by IH)
2k
?
A cool example
2k
2k
OK!! (by IH)
OK!! (by IH)
2k
2k+1
OK!! (by IH)
OK!! (by IH)
2k
A cool example
A cool example
5.2.Strong Mathematical Induction
•
•
If
P(0) and (cid:0) n (cid:0) 0 (P(0) (cid:0) P(1) (cid:0) … (cid:0) P(n)) (cid:0) P(n +1)
•
Then
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
(cid:0) n (cid:0) 0 P(n)
5.2.Strong Mathematical Induction
• Theorem . Every integer n > 1 is a product of
primes.
35
a, b (cid:0) k
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 (cid:0) 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.
5.3. Inductive Definitions
We completely understand the function f(n) = n !, right?
As a reminder, here’s the definition:
n ! = 1 ∙ 2 ∙ 3 ∙ … ∙ (n –1) ∙ n, n (cid:0) 1
Recursive Case
(cid:0) (cid:0)
n!(cid:0)
(cid:0) (cid:0)
Base Case
But equivalently, we could define it like this: n (cid:0) (n (cid:0) 1)!, if n (cid:0) 1 1, if n (cid:0) 1
Inductive (Recursive) Definition
36
(cid:0) (cid:0)
(cid:0) (cid:0)
5.4. Inductive Definitions
Another VERY common example: Fibonacci Numbers
(cid:0) (cid:0)
Base Cases
(cid:0) (cid:0)
f (n) (cid:0)
(cid:0) (cid:0)
(cid:0) (cid:0)
0 if n (cid:0) 0 1 if n (cid:0) 1 f (n (cid:0) 2) if n (cid:0) 1 f (n (cid:0) 1) (cid:0)
Recursive Case
(cid:0) (cid:0)
Is there a nonrecursive definition for the Fibonacci Numbers?
n
n
(cid:0) (cid:0)
1 (cid:0)
5
1 (cid:0)
5
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
f (n) (cid:0)
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
2
2
1 5
37
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
(cid:0) (cid:0)
5.4. Inductive Definitions
Give an inductive definition of S = {x: x is a multiple of 3} Base Case
Our examples so far have been inductively defined functions. Sets can be defined inductively, too.
Recursive Cases
3 (cid:0) S
x, y (cid:0) x, y (cid:0) S (cid:0) S (cid:0) x + y (cid:0) x – y (cid:0) S S
38
No other numbers are in S.
5.5. Inductive Definitions of Strings
be a finite set called an alphabet.
Let (cid:0) The set of strings on (cid:0)
, denoted (cid:0) * is
defined as: – (cid:0)
(cid:0) *, where (cid:0)
denotes the null or
(cid:0) empty string. (cid:0)
, and w (cid:0)
– If x (cid:0)
(cid:0) *, then wx (cid:0)
(cid:0) *,
where wx is the concatenation of string w with symbol x.
39
5.5. Inductive Definitions of Strings
If x (cid:0) (cid:0) , and w (cid:0) (cid:0) *, where wx is the
(cid:0) *, then wx (cid:0) concatenation of string w with symbol x.
= {a, b, c}. Then
Example: Let (cid:0) (cid:0) * = {(cid:0) , a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab,…}
How big is (cid:0) *? Infinite
No. Are there any infinite strings in (cid:0) *?
40
No. Is there a largest string in (cid:0) *?
5.5. Inductive Definitions of Strings
Inductive definition of the length of strings (the
•
•
length of string w is denoted by |w|.): |(cid:0) If x (cid:0)
(cid:0) *, then |wx| = |w| + 1
| = 0 (cid:0)
, and w (cid:0)
I point this out because the length of strings is something we might like to use for an inductive argument.
41
5.5. Inductive Definitions of Strings
•
•
Inductive definition of the reversal of a string (the
reversal of string w is denoted by wR.): (cid:0) R = (cid:0) If x (cid:0) (cid:0) *, then (wx)R = ? , and w (cid:0) (cid:0) x(w)R
For example (abc)R = cba
42
because (abc)R = c(ab)R = cb(a)R = cba((cid:0) )R = cba(cid:0) = cba
43
Phép đ mế
ộ
ọ ế y và n uế
ố ượ ng ớ ấ ỳ ố ượ x không trùng v i b t k cách ng
ọ ố y nào, thì có m+n cách ch n 1 trong các đ i
ố ượ ế ứ ỗ ọ m cách ch n đ i t ng x và c m i cách ch n
ố ượ ng y thì có m.n cách
44
ọ ặ ọ (x, y). 1. Nguyên lý c ng và nguyên lý nhân 1.1. Nguyên lý c ngộ m cách ch n ọ x, n cách ch n đ i t N u có ọ cách ch n đ i t ch nọ ố ượ ng đ i t ượ t ng đã cho. 1.2. Nguyên lý nhân ọ N u có x luôn luôn có n cách ch n đ i t ố ượ ch n c p đ i t ng
Phép đ mế
ợ
ậ
ượ
ậ ở
A vào B đ
c ký hi u b i BA.Gi
ầ ử
ậ ậ
ỗ
ai
ọ ả
ủ
ậ
ắ
45
ứ
Ví d .ụ ạ ợ Cho A và B là hai t p h p.T p h p các ánh x ả ử (cid:0) A(cid:0) =m ệ ừ s t , (cid:0) B(cid:0) = n thì (cid:0) BA(cid:0) = nm.Th t v y, m i ph n t 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ó nm ánh
x f.ạ
Phép đ mế
ầ ử
ầ ử
ậ
ố thì s
ụ ế ừ
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 ị ủ ầ ử ố ị ủ ph n t . S các hoán v c a n hoán v c a n ệ ầ ử ký hi u là Pn ph n t b) Pn = n! ợ c) Ví d :N u A là t p h p n ph n t A vào A là n! song ánh t
46
Phép đ mế
ị
ồ
ậ
ầ ử
ỗ ộ ồ . M i b g m
ứ ự ủ ậ
k (cid:0) n)s p th t ắ
(cid:0)
ợ
ậ
ỉ
ợ c a t p h p A k nA ủ ph n t ầ ử .
k A n
= ậ
ệ
ộ ch nh h p ch p k c a n n ! ) ủ n k
!
-
ợ . ỉ 3. Ch nh h p a) Đ nh nghĩa . ợ Cho A là t p h p g m n ph n t k ầ ử (cid:0) ph n t (1 cượ đ ọ g i là m t Số ( ợ ỉ các ch nh h p ch p k c a n ký hi u là b)Công th c ứ
47
Phép đ mế
ổ ợ
ậ
đ
(cid:0) (cid:0)
(cid:0) (cid:0)
ổ ợ . 4.T h p ị a) Đ nh nghĩa. ỗ ậ ợ ậ ầ ử ồ n ph n t Cho t p h p A g m . M i t p con ổ ợ ộ t ượ ọ g m ồ k ph n t ầ ử ủ c a A đ c g i là m t h p ậ k ố ầ ử S các t ủ h p ch p ch p k c a n ph n t . ệ ầ ử ựơ c a ủ n ph n t c ký hi u là k hay nC
(cid:0) (cid:0)
n k
48
(cid:0) (cid:0)
Phép đ mế
b) Công th cứ
!
=
C
k n
)
n ( k n k !
!
c) Tính ch t ấ
-
C
- = n k k C C n n = + k 1 C C n
k n
k + n 1
49
-
Phép đ mế
ố ượ ng trong đó có ng lo i
ố
ố ượ ỗ ọ ứ ự n đ i t ng đã cho g i
ị ặ . 5. Hoán v l p ị a) Đ nh nghĩa ố ượ ạ i Cho n đ i t ni đ i t ệ i =1,2,…,k ; n1+ n2+…+ nk= n). gi ng h t nhau ( ế ắ M i cách s p x p có th t ị ặ c a ủ n. là m t ộ hoán v l p
50
Phép đ mế
n1
ạ
ị ủ n đ i t ố
ng, trong đó có n2 đ i ố nk đ i ố
ố b) S hoán v c a ố ượ đ i t ượ t ượ t
ố ượ ộ ng gi ng nhau thu c lo i1, ộ ố ạ ng gi ng nhau thu c lo i 2,…, ạ k, là ộ ố ng gi ng nhau thu c lo i n ! n !k !...
n n ! 1 2
51
Phép đ mế
ự ằ khác nhau b ng
ắ ỗ ủ ừ ữ ế SUCCESS?
• Gi
• Ví dụ: Có bao nhiêu chu i kí t cách s p x p các ch cái c a t ừ ữ
ữ
=
420
7! 3!1!2!1!
52
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à
Phép đ mế
ỗ
k v t t
ạ ậ ậ ừ n lo i v t khác nhau
ạ ậ
ể ượ
ọ ạ
c ch n l
i
ượ ọ
ủ
c g i là
S ố
t
ậ h p l p ch p k c a n.
ệ
ổ ợ ặ . 6.T h p l p ị a) Đ nh nghĩa. ọ M i cách ch n ra ỗ (trong đó m i lo i v t có th đ nhi uề ầ l n) đ các ổ ợ ặ t
ổ ợ ặ k nK ậ k c a ủ n đ ượ
h p l p ch p
c ký hi u là
53
Phép đ mế
b) Công th cứ
=
k n
k C + - n k
1
ố
ả. S nghi m nguyên không âm( ươ ủ x1,x2,…,xn) ng trình
K ệ c)H quệ (m i ỗ xi đ u nguyên không âm) c a ph ề x1+ x2+…+ xn = k là
=
K
k n
k C + - n k
1
54
Phép đ mế
ấ k v t đ ng ch t nhau vào ố ổ ợ ặ
ằ
ậ ồ t cũng chính b ng s t
n h p ộ ậ h p l p ch p
ố S cách chia ệ phân bi k c a ủ n
=
K
k n
k C + - n k
1
55
Phép đ mế
ủ
ệ
ố
ươ
ng trình
Ví dụ: Tìm s nghi m nguyên không âm c a ph
x1+ x2 + x3 + x4 = 20
(1)
2; x3 > 4 ((cid:0) ).
3; x2 (cid:0)
(cid:0)
t đi u ki n đã cho thành x1
3; x2 (cid:0)
2; x3 (cid:0)
5.
ệ ệ
ỏ th a x1 iả . Gi ề ế Ta vi ề Xét các đi u ki n sau: • x2 (cid:0)
2; x3 (cid:0)
((cid:0)
(cid:0) )
(cid:0)
(cid:0) )
5
ố
(cid:0)
(cid:0) ), ((cid:0)
5 2; x3 (cid:0) ệ ệ ((cid:0) ), ((cid:0)
ề
• x1 (cid:0) ầ ượ • G i p, q, r l n l ỏ ng trình (1) th a các đi u ki n
4; x2 (cid:0) ((cid:0) ủ t là s nghi m nguyên không âm c a (cid:0) ). Ta có:
ọ ươ ph
56
(cid:0)
Phép đ mế
p = q – r.
ướ ế c h t ta tìm q.
Tr Đ t ặ
ở ươ x1’ = x1; x2’ = x2 – 2; x3’ = x3 5; x4’ = x4 ng trình (1) tr thành Ph
x1’+ x2’ + x3’ + x4’ = 13
ố ệ (2) ố (cid:0) ) b ng s ằ
57
ủ ệ ỏ (cid:0) ủ S nghi m nguyên không âm c a(1) th a( nghi m nguyên không âm c a(2)
Phép đ mế
=
=
C
K
C
13 4
13 16
ố ậ
=
=
C
C
9 4
9 12
9 + - 4 9 1 =
p
560 220 340.
= r K , ta có . = 9 13 C 12 16
ủ
ươ
ng
ề
13 ệ S nghi m là . + - 4 13 1 q C= 13 V y . 16 ự ậ ươ ng t Lý lu n t = - = Suy ra q r C ệ ậ ố V y s nghi m nguyên không âm c a ph ỏ trình (1) th a đi u ki n (
ệ (cid:0) ) là 340
58
- -
Phép đ mế
ố ố
ộ ấ ế ằ
ứ
i.ả ướ ế ế ố ố
ấ
ộ ể ế ướ ậ ằ ộ
ế
ườ ế ố ộ
59
ề Ví dụ: Tìm s cách x p 30 viên bi gi ng nhau vào 5 ế ộ t r ng h p khác nhau sao cho h p 1 có ít nh t 5 bi, bi ộ h p 2 và 3 ch a không quá 6 bi. Gi c h t ta tìm s cách x p 30 viên bi gi ng nhau Tr ộ vào 5 h p khác nhau sao cho h p 1 có ít nh t 5 bi. ầ ấ c vào h p 1, Nh n xét r ng ta c n l y 5 bi đ x p tr ố ỉ ạ ố do đó s bi còn l i ch là 25. Suy ra s cách x p trong ằ ợ ng h p này b ng s cách x p 25 bi vào 5 h p mà tr ố ể không có đi u ki n gì thêm. S đó là
Phép đ mế
=
=
=
K
C
C
23751.
25 5
25 + - 5 25 1
25 29
ự
ng t
ố
ươ ố
ta có ế
ộ
ứ
ấ
ộ
ứ
T 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à =
=
C
C
K
18 + - 5 18 1
18 22
18 5
60
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à
-
=
=
K
C
C
18 5
18 + - 5 18 1
18 22
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à
ấ :
=
=
K
C
C
11 5
11 + - 5 11 1
11 15
62
Phép đ mế
+
ử ụ
A
B
� A B
� A B
|
|
|
|
= | |
ứ ế
ộ
ố ứ
ấ
ộ
ờ ộ
ứ
+
-
• 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à C K
K
C
K
13265.
ấ = 11 C 15
= 11 5
+ 18 22
18 5
18 5
18 22
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 i 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
-
Phép đ mế
ộ
ả ử
ậ ầ
ứ ừ
ấ
ươ
ố
ặ s có n v t c n đ t vào k h p. Khi đó /n k� �� � ậ ở v t tr lên. ấ ỏ ng nh nh t
ơ
• 7. NGUYÊN LÝ DIRICHLET • Gi t nồ ộ ộ ạ i ít nh t m t h p ch a t t /n k� �� � Trong đó là s nguyên d không bé h n n/k
65
Phép đ mế
ố
ườ i luôn luôn có ít ậ i có sinh nh t trong
• Ví d . ụ Trong s 100 ng 9= ấ ườ nh t là ng 100/12 � � � � ộ 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 t r ng m i s thuê máy m t s thuê bao bi ữ ố ầ bao g m 7 ch s , trong đó ch s đ u khác 0?
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à
10=
ố ệ 84 / 9 � �� � ộ ố ộ ố
ầ ạ
ể ả 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.
67
Isaac Newton (16431727)
68
ị ứ
ể
Khai tri n nh th c Newton
•
ươ
ớ • V i x, y
ng ta có
ố R và n là s nguyên d
n
(cid:0)
n
n k
k
+
= (cid:0)
x
y
y
(
)
k C x n
=
k
0
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
(cid:0) (cid:0)
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
,...,
!
n k
n nn , 1 2
n ! n !... k
nn ! 1 2
70
(cid:0) (cid:0)
ị ứ
ở ộ
ể M r ng Khai tri n nh th c Newton
n
a
a
(
...
)
a 1
2
(cid:0) (cid:0) (cid:0) (cid:0)
k n
n
2
(cid:0) (cid:0)
...
n ka k
n aa 1 1
2
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
,...,
n
n
n
...
n k
n 1
k
n 1
2
71
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
Bài t pậ
(cid:0) ơ (cid:0) và A, B, C (cid:0) ứ X. Ch ng minh
C); (B \ C);
C) = B \ (A (cid:0) B) \ (A (cid:0) C) = A (cid:0) B) \ (A (cid:0) B) \ C = (A \ C) (cid:0) B) \ C = (A \ C) (cid:0) (B \ C); (B \ C);
(cid:0) (cid:0) C) = (A \ C) \ (B \ C). và A, B (cid:0) X; C, D (cid:0) Y.
72
ứ ậ 1. Cho t p h p X r ng:ằ a) (A (cid:0) b) (A (cid:0) c) (A (cid:0) d) (A (cid:0) e) (A \ B) \ C = A \ (B (cid:0) ợ ậ 2. Cho các t p h pX, Y ằ Ch ng minh r ng:
Bài t pậ
(A (cid:0) (D (cid:0) (A (cid:0) (D (cid:0) D); A); D); A);
D) = (A (cid:0) (C (cid:0) A = (C (cid:0) D) (cid:0) D) = (A (cid:0) (C (cid:0) A = (C (cid:0) D) (cid:0) (C \ D) = (A (cid:0) A = (C (cid:0) D); A);
C) (cid:0) A) (cid:0) C) (cid:0) A) (cid:0) C) \ (A (cid:0) A) \ (D (cid:0) D) = [(A \ B) (cid:0) C] (cid:0) [A (cid:0) (C \ D)];
(B (cid:0) D) (cid:0) B) (cid:0) D);
73
a) A (cid:0) b) (C (cid:0) c) A (cid:0) d) (C (cid:0) e) A (cid:0) f) (C \ D) (cid:0) g) (A (cid:0) h) (A (cid:0) i) (A (cid:0) C) \ (B (cid:0) C) (cid:0) C) \ (B (cid:0) D) (cid:0) (A (cid:0) (A \ B) (cid:0) (C (cid:0) (C \ D )
Bài t pậ
ạ
ợ
ườ
ng h p sau hãy xem xét xem ánh x nào là ạ ượ c cho các song ánh
) đ nh b i f(x) = ln2x – 2lnx + 3;
ở
) (cid:0) ) (cid:0) ) (cid:0) ) (cid:0)
) đ nh b i f(x) = ln2x – 2lnx + 3;
3. Trong các tr ơ đ n ánh, toàn ánh, song ánh.Tìm ánh x ng a) f : (0, +(cid:0) b) f : (0, +(cid:0) c) f : (e, +(cid:0) d) f : (e, +(cid:0) e) f : R (cid:0) f) f : R (cid:0) g) f : (0, +(cid:0)
ở ị ở ị ị R đ nh b i f(x) = e2x + 2ex + 3; (3, +(cid:0) ở ) (cid:0) ị
ị R đ nh b i f(x) = ln2x – 2lnx + 3; [2, +(cid:0) ở ị R đ nh b i f(x) = ln2x – 2lnx + 3; (2, +(cid:0) ở ị ) đ nh b i f(x) = e2x + 2ex + 3; (3, +(cid:0) ở
) đ nh b i f(x) = e2x + 2ex + 3;
74
Bài t pậ
(cid:0) ở ị ạ ) đ nh b i : ) (cid:0) [9/2, +(cid:0)
ứ ằ
75
ở ị 4. Cho ánh x f : [ln2, + f(x) = 2ex – e–x + 1. a) Ch ng minh r ng f là song ánh và tìm f–1. ạ ỏ b) Tìm ánh x h th a f o h o f = f o g trong đó [ln2, +(cid:0) ) (cid:0) g : [ln2, +(cid:0) đ nh b i g(x) = ex.
Bài t pậ
5)
ố
ệ
ủ
ươ
ng trình x1 + x2 + x3 + x4 = 40
ợ ng h p sau:
trong m i tr 3, x2 (cid:0)
Tìm s nghi m nguyên không âm c a ph ỗ ườ a) x1 (cid:0) 4. b) x1 > 3, x2 < 4. 8, x2 (cid:0) x1 (cid:0) c) 2 (cid:0)
4, x3 > 3, x4 < 6
76
Bài t p ậ
ủ ệ ố
6. a) Tìm s nghi m nguyên không âm c a b t ấ ph
ươ ng trình
x1 + x2 + x3 (cid:0) 11
ộ x1, x2, x3)
ề b) (Bài 2 Đ thi 2007) ố Có bao nhiêu b ba s nguyên không âm ( th a:ỏ
x1 + x2 + x3 ≤ 15
77
trong đó x1 > 2, x2 <4
Bài t pậ
• 8.
Chöùng minh raèng vôùi moïi soá nguyeân döông n ta coù:
...
1
;
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
1 !2
2 !3
n )!1n(
1 )!1n(
(cid:0) (cid:0)
(cid:0)
...
;
(cid:0) (cid:0) (cid:0) (cid:0)
1 3.2.1
1 4.3.2
1 )2n)(1n(n
)3n(n )2n)(1n(4
78
(cid:0) (cid:0) (cid:0) (cid:0)
