I HÅC THI NGUYN
TR×ÍNG I HÅC KHOA HÅC
NGUYN THÀ HU LINH
PH
N HOCH V HM SINH
LUN VN THC Sß TON HÅC
Th¡i Nguy¶n - 2014
I HÅC THI NGUYN
TR×ÍNG I HÅC KHOA HÅC
NGUYN THÀ HU LINH
PH
N HOCH V HM SINH
Chuy¶n ng nh: PH×ÌNG PHP TON SÌ CP
M¢ sè: 60.46.01.13
LUN VN THC Sß TON HÅC
Ng÷íi h÷îng d¨n khoa hå
PGS.TS. M VN NH
Th¡i Nguy¶n - 2014
1
Mö
lö
Líi nâi u
1 Ki¸n thù
hu©n bà
1.1.
1.2.
1.3.
1.4.
1.5.
1.6.
Quan h» t÷ìng ÷ìng . . . . . . . . . . . .
Tê hñp suy rëng . . . . . . . . . . . . . . .
Khai triºn a thù
. . . . . . . . . . . . .
Cæng thù
huyºn êi ng÷ñ
. . . . . . . .
Nguy¶n lþ Bò-Trø . . . . . . . . . . . . . .
Chuéi ly thøa h¼nh thù
. . . . . . . . . .
1.6.1. V nh
¡
huéi ly thøa h¼nh thù
1.6.2. ành lþ Fi
htenholz v· hëi tö . . .
2 Ph¥n ho¤
h tªp hñp húu h¤n
2.1. Ph÷ìng ph¡p ph¥n ho¤
h tªp hñp .
2.2. D¢y sè Stirling . . . . . . . . . . .
2.2.1. C¡
sè Stirling lo¤i hai . . .
2.2.2. C¡
sè Stirling lo¤i mët . .
2.3. Mët v i k¸t qu£ v· sè Bell . . . . .
2.3.1. Kh¡i ni»m sè Bell . . . . . .
2.3.2. Sè Bell
â i·u ki»n . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
4
4
5
7
11
14
17
17
19
20
20
24
25
31
34
34
37
3 Ph¥n ho¤
h sè nguy¶n d÷ìng
41
K¸t luªn
T i li»u tham kh£o
62
63
3.1. Ph¥n ho¤
h sè nguy¶n d÷ìng . . . . . . . . . . . . . . . .
3.2. Ph÷ìng ph¡p h m sinh
õa Euler . . . . . . . . . . . . . .
3.3. H m sinh th֒ng
õa sè Stirling v sè ph¥n ho¤
h . . . . .
41
56
59
2
Líi nâi u
B i to¡n ph¥n ho¤
h tªp hñp v ph¥n ho¤
h sè nguy¶n d÷ìng ¢ ÷ñ
bi¸t ¸n tø r§t l¥u v ng y nay nâ
â vai trá quan trång khæng
h¿ trong
l¾nh vü
to¡n hå
m nâ
án ÷ñ
¡p döng trong nhi·u ng nh khoa hå
kh¡
nh÷ Vªt Lþ, àa Lþ, ... Vªy th¸ n o l ph¥n ho¤
h tªp hñp v th¸ n o
l ph¥n ho¤
h sè nguy¶n d÷ìng.
Leibniz l ng÷íi u ti¶n quan t¥m ¸n b i to¡n ph¥n ho¤
h sè tü nhi¶n.
V o n«m 1674, trong mët bù
th÷ gûi J.Bernoulli, æng ¢ häi v·
¡
h
hia
mët sè nguy¶n khæng ¥m. Nâi theo thuªt ngú hi»n ¤i, Leibniz ¢ °t
¥u
häi u ti¶n v· sè ph¥n ho¤
h
õa mët sè tü nhi¶n. Æng ¢ ÷a ra mët v i
v½ dö
ö thº d÷îi ¥y:
(1) Sè 2
â hai ph¥n ho¤
h 2 = 2 = 1 + 1,
(2) Sè 3
â ba ph¥n ho¤
h 3 = 3 = 2 + 1 = 1 + 1 + 1,
(3) Sè 4
â n«m ph¥n ho¤
h 4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1.
Nhi·u b i to¡n sè hå
hay tê hñp s³ trð n¶n d¹ gi£i hìn khi sû döng
ph÷ìng ph¡p ph¥n ho¤
h tªp hñp. Ph¥n ho¤
h tªp hñp
ng ֖
¡p döng
r§t nhi·u trong l¾nh vü
to¡n sì
§p, °
bi»t l trong
¡
b i to¡n thi hå
sinh giäi.
Luªn v«n Ph¥n ho¤
h v h m sinh nh¬m h» thèng l¤i
¡
ki¸n thù
ì b£n v· ph¥n ho¤
h tªp hñp v ph¥n ho¤
h sè nguy¶n d÷ìng.
Luªn v«n ÷ñ
hia ra l m ba
h֓ng
Ch÷ìng 1 - Ki¸n thù
hu©n bà. Ch÷ìng n y tr¼nh b y
¡
v§n ·
v·: Quan h» t÷ìng ÷ìng, tê hñp suy rëng, khai triºn a thù
,
æng thù
huyºn êi ng÷ñ
, nguy¶n lþ Bò-trø,
huéi ly thøa h¼nh thù
.
Ch÷ìng 2 - Ph¥n ho¤
h tªp hñp húu h¤n. Tr¼nh b y v· ph÷ìng ph¡p
ph¥n ho¤
h tªp hñp, d¢y sè Stirling v mët v i k¸t qu£ v· sè Bell.
Ch÷ìng 3 - Tr¼nh b y
¡
kh¡i ni»m
ì b£n, mët sè ành lþ, h» qu£,
m»nh · v· ph¥n ho¤
h sè nguy¶n d÷ìng. Ph÷ìng ph¡p h m sinh
õa Eler.
3
H m sinh th֒ng
õa sè Stirling v sè ph¥n ho¤
h.
º ho n th nh luªn v«n n y, tr÷î
h¸t t¡
gi£ xin ÷ñ
gûi líi
£m ìn
s¥u s
tîi PGS. TS. m V«n Nh¿ ¢ d nh thíi gian h÷îng d¨n,
h¿ b£o
tªn t¼nh gióp ï trong suèt qu¡ tr¼nh x¥y düng · t i
ng nh÷ ho n thi»n
luªn v«n. Ti¸p theo, t¡
gi£
ng xin gûi líi
£m ìn
h¥n th nh tîi
¡
thy
æ ¢ å
, kiºm tra, ¡nh gi¡ v
ho nhúng þ ki¸n quþ b¡u º luªn
v«n ÷ñ
y õ hìn, phong phó hìn. Qua ¥y, t¡
gi£
ng xin ֖
gûi
líi
£m ìn tîi Ban gi¡m hi»u, pháng o t¤o, Khoa To¡n - Tin Tr÷íng
¤i hå
Khoa hå
- ¤i hå
Th¡i Nguy¶n v
¡
b¤n çng nghi»p ¢ t¤o
i·u ki»n thuªn lñi trong suèt qu¡ tr¼nh hå
tªp t¤i tr÷íng.
T¡
gi£ r§t mong nhªn ÷ñ
sü âng gâp þ ki¸n
õa
¡
thy
æ v
¡
b¤n çng nghi»p º luªn v«n ÷ñ
ho n thi»n hìn.
T¡
gi£ xin
h¥n th nh
£m ìn!
Th¡i Nguy¶n, th¡ng 9 n«m 2014
T¡
Gi£
Nguy¹n Thà Hu» Linh
4
Ch֓ng 1
Ki¸n thù
hu©n bà
1.1. Quan h» t÷ìng ÷ìng
Gi£ thi¸t tªp X 6= ∅. T½
h ·
¡
X × X ÷ñ
ành ngh¾a nh÷ d÷îi ¥y:
X × X = {(x, y)|x, y ∈ X}.
ành ngh¾a 1.1. Tªp
on S
õa X × X ÷ñ
gåi l mët quan h» hai ngæi
trong X. N¸u (x, y) ∈ S th¼ ta nâi x
â quan h» S vîi y v vi¸t xSy.
ành ngh¾a 1.2. Gi£ thi¸t X 6= ∅ v S 6= ∅ l mët quan h» hai ngæi trong
X. Quan h» S ÷ñ
gåi l mët quan h» t÷ìng ÷ìng trong X n¸u nâ thäa
m¢n ba i·u ki»n sau ¥y:
(i) (Ph£n x¤) Vîi måi x ∈ X
â xSx.
(ii) (èi xùng) Vîi måi x, y ∈ X, n¸u
â xSy th¼
ng
â ySx.
(iii) (B
u) Vîi måi x, y, z ∈ X, n¸u
â xSy v ySz th¼
ng
â xSz.
Khi S l mët quan h» t÷ìng ÷ìng trong X th¼ ta th÷íng kþ hi»u ∼ thay
ho S. °t C(x) = {y ∈ X|y ∼ x} v gåi nâ l mët lîp t÷ìng ÷ìng vîi x
l m ¤i di»n. D¹ d ng
h¿ ra
¡
t½nh
h§t sau:
T½nh
h§t 1.1. Gi£ sû ∼ l quan h» t÷ìng ÷ìng trong X 6= ∅. Khi â
(i) Vîi måi x ∈ X
â x ∈ C(x).
(ii) Vîi måi y, z ∈ C(x)
â y ∼ z v y, z ∼ x.
(iii) Vîi måi x, y ∈ X,
â ho°
C(x) ∩ C(y) = ∅ ho°
C(x) = C(y).
(iv) Tªp th÷ìng X/ ∼ l tªp
¡
lîp t÷ìng ÷ìng khæng giao nhau.
5
1.2. Tê hñp suy rëng
ành ngh¾a 1.3. Méi
¡
h sp x¸p
â thù tü k phn tû m
¡
phn tû
â thº l°p l¤i
õa tªp T gçm n phn tû kh¡
nhau ֖
gåi l mët
h¿nh
hñp l°p
hªp k
õa tªp n phn tû. Kþ hi»u sè
¡
h¿nh hñp l°p
hªp k
õa tªp gçm n phn tû kh¡
nhau l Akn. K¸t qu£ sau ¥y l hiºn nhi¶n.
M»nh · 1.1. Sè
¡
h¿nh hñp l°p
hªp k
õa mët tªp gçm n phn tû
kh¡
nhau l
k
A n = nk .
ành ngh¾a 1.4. Méi
¡
h l§y k phn tû m
¡
phn tû
â thº l°p l¤i
õa mët tªp n phn tû ÷ñ
gåi l mët tê hñp l°p hay tê hñp suy rëng
hªp k
õa tªp n phn tû.
Kþ hi»u sèk t§t
£
¡
tê hñp l°p
hªp k
õa mët tªp gçm n phn tû kh¡
nhau l Cn. Ta
â k¸t qu£ sau ¥y.
M»nh · 1.2. Sè
¡
ho¡n và l°p
õa n phn tû, trong â
â n
nh÷ nhau thuë
lo¤i 1,
n2
phn tû nh÷ nhau thuë
lo¤i 2,...,
nh÷ nhau thuë
lo¤i s, s³ óng b¬ng
n!
·
n1 !n2 ! . . . ns !
1 phn tû
ns
phn tû
Chùng minh. Kþ hi»u
¡
phn tû l a , a , . . . , a , trong â a xu§t hi»n
1
2
s
1
ln, a2 xu§t hi»n n2 ln,..., as xu§t hi»n ns ln. n1 phn tû b¬ng nhau a1
֖
kþ hi»u qua a11, . . . , a1n ; n2 phn tû b¬ng nhau a2 ÷ñ
kþ hi»u qua
a21 , . . . , a2n ; . . . ; ns phn tû b¬ng nhau as ÷ñ
kþ hi»u qua as1 , . . . , asn .
Vîi n = n1 + n2 + · · · + ns phn tû aij ta
â n! ho¡n và. Khi
è ành
¡
ai1 , . . . , ain , i 6= 1,
án n1 phn tû b¬ng nhau a11 , . . . , a1n ho¡n và vîi nhau
ta
ng
h¿ ÷ñ
mët ho¡n và. Trong tr÷íng hñp n y, thü
t¸ méi phn
tû ¢ ÷ñ
t½nh n1! ln. T÷ìng tü x²t
¡
tr÷íng hñp kh¡
. V¼
¡
tr֒ng
hñp l ë
lªp vîi nhau n¶n theo quy t
nh¥n ta th§y méi ho¡n và thü
t¸ ¢ ÷ñ
t½nh n1! . . . ns! ln. Vªy sè ho¡n và
n t½nh b¬ng n !n n!
·
!...n !
n1
1
s
2
1
i
1
2
s
M»nh · 1.3. Kþ hi»u T l sè
¡
h ph¥n
hia n ç vªt kh¡
nhau v o trong
k
hëp kh¡
nhau sao
ho
â
Khi â
n!
T =
·
n1 !n2 ! . . . nk !
ni
vªt ÷ñ
°t v o hëp thù
i vîi i = 1, 2, . . . , k.
Chùng minh. Ta
â C
¡
h
hån n vªt tø n vªt °t v o hëp thù nh§t,
n1
n
1
6
ti¸p theo
â Cnn−n
¡
h
hån n2 vªt tø n − n1 vªt °t v o hëp thù hai,...,
èi
òng l Cnn−n −···−n
¡
h
hån nk vªt tø n − n1 − · · · − nk−1 vªt °t v o
hëp thù k. V¼
¡
tr÷íng hñp
hån ð tr¶n l ë
lªp vîi nhau n¶n theo quy
t
nh¥n ta th§y T = Cnn Cnn−n . . . Cnn−n −···−n . Nh÷ vªy
hóng ta nhªn
֖
k¸t qu£ T = Cnn Cnn−n . . . Cnn−n −···−n . Bi¸n êi
2
1
k
1
k−1
1
2
k
1
1
2
1
k−1
k
1
1
k−1
n!
(n − n1 )!
(n − n1 − · · · − nk−1 )!
·
···
n1 !(n − n1 )! n2 !(n − n1 − n2 )!
nk !0!
n!
·
=
n1 !n2 ! . . . nk !
T =
Tâm l¤i T = n !n n!
·
!...n !
1
2
k
V½ dö 1.1. Gi£ sû m v k l nhúng sè nguy¶n d÷ìng v °t n = mk. Kþ
l sè
¡
h ph¥n
hia
n
ç vªt kh¡
nhau x¸p v o
sao
ho méi hëp
hùa óng
m
vªt. Khi â
hi»u
T
T =
n!
·
k!(m!)k
k
hëp gièng nhau
B i gi£i. Ta
oi k hëp l kh¡
nhau. Khi â sè
¡
h ph¥n
hia l
T =
n!
n!
·
=
m!m! . . . m!
(m!)k
Do k hëp gièng nhau n¶n méi
¡
h ph¥n
hia
n!
¢ xu§t hi»n k! ln. Vªy thü
t¸ sè
¡
h ph¥n
hia l T = k!(m!)
·
k
V½ dö 1.2. Gi£ sû
â s lo¤i hëp gçm m
1
hi¸
lo¤i thù nh§t,
m2
hi¸
lo¤i
ms
hi¸
lo¤i thù s, trong â nhúng
hi¸
òng lo¤i gièng h»t
nhau. Câ n = m1 n1 + m2 n2 + · · · + ms ns ç vªt x¸p h¸t v o
¡
hëp sao
ho méi hëp thuë
lo¤i thù i
hùa óng ni vªt. Kþ hi»u T l sè
¡
h ph¥n
hia n ç vªt kh¡
nhau x¸p v o s lo¤i hëp gçm m1 + m2 + · · · + ms
hi¸
thù hai,...,
â. Khi â
T =
(m1 n1 + m2 n2 + · · · + ms ns )!
·
m1 !m2 ! . . . ms !(n1!)m1 (n2 !)m2 · · · (ns!)ms
B i gi£i. Tr÷î
ti¶n ta
hia n vªt th nh s phn sao
ho phn thù i
â
mi ni
vªt. Khi â sè
¡
h ph¥n
hia l
T =
n!
·
(m1 n1 )!(m1 n2 )! . . . (ms ns)!
7
em phn thù i l mini vªt x¸p v o mi hëp gièng h»t nhau. Khi â sè
¡
h
ph¥n
hia l Ti = m(m!(nin!)i)!m · Do
¡
h
hia ð méi phn l ë
lªp vîi nhau
i
i
n¶n t§t
£ sè
¡
¡
h ph¥n
hia kh¡
nhau l T = S.T1.T2 . . . Ts hay
i
T =
(ms ns )!
(m1 n1 )!
n!
·
·
·
,
·
(m1 n1 )!(m1 n2 )! . . . (ms ns )! m1 !(n1 !)m1
ms !(ns!)ms
ho°
vi¸t gån l¤i
T =
(m1 n1 + m2 n2 + · · · + ms ns )!
·
m1 !m2 ! . . . ms !(n1!)m1 (n2 !)m2 · · · (ns!)ms
1.3. Khai triºn a thù
ành ngh¾a h» sè tê hñp a ìn thù
d÷îi ¥y nh÷ mët sü têng qu¡t
ho tê hñp v khai triºn Nhà thù
Newton.
ành ngh¾a 1.5. Vîi sè nguy¶n d÷ìng n v k, sè
n
r1 , r2 , . . . , rk
!
=
n!
,
r1 !r2 ! . . . rk !
trong â
¡
ri ∈ N v r1 + r2 + · · · + rk = n, ÷ñ
gåi l mët h» sè tê hñp
a ìn thù
.
Mët v i k¸t qu£ sau ¥y ÷ñ
suy trü
ti¸p tø ành ngh¾a.
M»nh · 1.4.
n
r1 , r2 , . . . , rk
!
=
n
r1
!
!
!
n − r1
n − r1 − r2 − · · · − rk−1
···
.
r2
rk
M»nh · 1.5.
n
r1 , r2 , . . . , rk
=
n−1
n−1
n−1
,
+· · ·+
+
r1 , r2 , . . . , rk − 1
r1 , r2 − 1, . . . , rk
r1 − 1, r2 , . . . , rk
trong â t§t
£
¡
ri
r1 + r2 + · · · + rk = n.
triºn a ìn thù
bª
n.
nguy¶n d÷ìng v
ành lþ sau ¥y
án ÷ñ
gåi l khai
8
ành l½ 1.1. Cæng thù
khai triºn
ho (x
(x1 + x2 + · · · + xk )n =
X
r1 +···+rk =n
1
+ x2 + · · · + xk )n
!
n
xr11 xr22 . . . xrkk ,
r1 , r2 , . . . , rk
r1 , . . . , rk ∈ N
trong â têng l§y theo t§t
£
¡
nh÷ sau
vîi
r1 + · · · + rr = n.
Chùng minh. Ta
hùng minh k¸t qu£ b¬ng ph÷ìng ph¡p qui n¤p theo
Vîi n = 1
æng thù
hiºn nhi¶n óng. Gi£ sû
æng thù
óng vîi n. Ta
h¿ ra nâ óng vîi n + 1. Thªt vªy, ta
â:
n.
(x1 + · · · + xk )n+1 =(x1 + · · · + xk )n (x1 + · · · + xk )
X
n!
=
xr11 xr22 . . . xrkk (x1 + · · · + xk )
r !r ! . . . rk !
r1 +r2 +···+rr =n 1 2
=
X
[
r1∗ +···+rk∗ =n+1
+ ··· +
Tø â suy ra
n!
n!
+
(r1∗ − 1)!r2∗ · · · rk∗ ! r1∗ !(r2∗ − 1)! · · · rk∗ !
n!
rk∗
r1∗
]
x
.
.
.
x
.
1
k
r1∗ ! . . . (rk∗ − 1)!
(x1 + · · · + xk )n+1 =
hay
(x1 + · · · + xk )n+1 =
n!(n + 1) r1∗
rk∗
x
·
·
·
x
k
r∗ ! · · · rk∗ ! 1
r ∗ +···+r ∗ =n+1 1
1
X
k
(n + 1)! r1∗
rk∗
x
.
.
.
x
,
1
k
∗
∗
r
!
·
·
·
r
!
k
r ∗ +···+r ∗ =n+1 1
1
X
k
trong â têng l§y theo r1∗, · · · , rk∗ ∈ N vîi P ri∗ = n + 1. Vªy ta suy ra
æng
i=1
thù
óng vîi n + 1. Tâm l¤i,
æng thù
óng vîi måi n.
k
V½ dö 1.3. Vîi b§t ký sè nguy¶n d÷ìng k luæn
â çng nh§t thù
kn =
X
r1 +···+rk =n
trong â têng l§y theo t§t
£
¡
B i gi£i. Ta
â k
n
!
n
,
r1 , r2 , . . . , rk
r1 , . . . , rk ∈ N
= (1 + 1 + · · · + 1)n =
vîi
P
r1 + · · · + rr = n.
r1 +···+rk =n
n
r1 , r2 , . . . , rk
!
theo
9
ành lþ 1.1.
Chó þ 1.1. Khi k = 2 ta nhªn ÷ñ
çng nh§t thù
Newton
(x1 + x2 )n =
X
r1 +r2 =n
!
n
xr11 xr22 .
r1 , r2
Tø â ta suy ra ÷ñ
çng nh§t thù
Vandermonde
!
m
0
!
!
n
m
+
k
1
!
!
n
m
+ ··· +
k−1
k
n
0
!
=
!
m+n
.
k
Bê · 1.1. Sè nghi»m
nguy¶n khæng ¥m
õa ph÷ìng tr¼nh x +· · ·+x
!
1
k
=n
n+k−1
.
k−1
b¬ng
Chùng minh. Kþ hi»u sè nghi»m nguy¶n khæng ¥m
õa ph÷ìng tr¼nh
l Nk (n). Ta
â N1(n) = 1. T½nh N2(n), tù
l t½nh sè nghi»m nguy¶n
khæng ¥m
õa ph÷ìng tr¼nh x1 + x2 = n. Ph÷ìng tr¼nh n y
â
¡
nghi»m
(0, n), (1, n − 1), ..., (n, 0) n¶n
N2 (n) = n + 1 =
!
n+1
.
1
º t½nh N3(n) ta x²t ph÷ìng tr¼nh x1 + x2 + x3 = n. Cho x3 = 0, 1, 2, ..., n,
ta
â
N3 (n) = N2 (n) + N2(n − 1) + · · ·+ N2 (2) + N2(1) + N2(0) = (n + 1) + · · ·+ 1.
Vªy N3(n) =
n¤p. Hiºn nhi¶n
!
n+2
.
2
Ta
hùng minh Nk (n) =
n+k−1
k−1
!
b¬ng qui
Nk (n) = Nk−1 (n) + Nk−1 (n − 1) + Nk−1 (n − 2) + · · · + Nk−1 (0).
Do â
Nk (n) =
!
!
n+k−2
n+k−3
k−2
+
+ ··· +
k−2
k−2
k−2
!
=
!
n+k−1
.
k−1
10
H» qu£ 1.1. Sè
¡
sè h¤ng trong khai
! triºn (x
ìn thù
bª
n
n+k−1
.
k−1
óng b¬ng
1
+ x2 + · · · + xk )n
hay sè
Chùng minh. Sè
¡
sè h¤ng trong khai triºn (x + x + · · · + x ) óng
1
2
k
n
b¬ng sè ìn thù
kh¡
nhau xr1 xr2 . . . xrk xu§t hi»n trong khai triºn. Sè â
óng b¬ng sè nghi»m nguy¶n! khæng ¥m
õa ph÷ìng tr¼nh r1 + · · · + rk = n.
Vªy sè â b¬ng n +k −k −1 1 theo Bê · 1.1.
1
2
k
Sû döng k¸t qu£ n y v o vi»
x²t
h¿nh hñp vîi tn sè l°p. Mët phn tû
xi
õa mët d¢y k phn tû
ho tr֔
x1 x2 . . . xk ֖
gåi l
â tn sè l°p ri
n¸u nâ xu§t hi»n trong d¢y óng ri ln. Kþ hi»u T (r1, r2, . . . , rk) l sè
¡
d¢y
â l°p (r1, r2, . . . , rk ) vîi ë d i
õa d¢y l r1 + r2 + · · · + rk = n
¡
phn tû
õa mët tªp A = {x1, x2, . . . , xk} vîi k phn tû
ho tr֔
sao
ho
trong méi d¢y ph£i
â phn tû thù i xu§t hi»n óng ri ln.
M»nh · 1.6. Tªp A vîi k phn tû
ho tr֔
. Sè
¡
d¢y k phn tû
â
l°p
(r1 , r2, . . . , rk )
vîi ë d i
õa d¢y l
r1 + r2 + · · · + rk = n
l
!
n
.
r1 , r2 , . . . , rk
T (r1 , r2 , . . . , rk ) =
Chùng minh. Sè d¢y k phn tû
â l°p (r , r , . . . , r ) vîi ë d i
õa d¢y
1
2
h½nh l h» sè
õa ìn thù
triºn (x1 + x2 + · · · + xk )n. Vªy T (r1, r2, . . . , rk) =
r1 + r2 + · · · + rk = n
k
r1 r2
x1 x2
. . . xrkk trong
!
n
.
r1 , r2 , . . . , rk
khai
V½ dö 1.4. Gi£ sû
â b£ng
hú
§u t¤o
h¿ vîi 3
hú
¡i a, b, c. T¼m sè
¡
tø bao gçm
n
hú m trong â
â
hùa mët sè
h®n
hú
¡i
a.
B i gi£i. N¸u trong
hú
â 2r
hú
¡i a th¼ ta
â thº °t theo C
¡
h;
2r
n
án trong n − 2r và tr½
án l¤i
ta
â 2n−2r
¡
h °t
ho b v c. Tâm l¤i
â
n
n−2r
C2r
¡
h. T§t
£ s³ l P C2rn 2n−2r . Tø
n 2
r=0
n
n
(1 + x) + (1 − x) = 2
n
X
r=0
2r
C2r
n x
11
ta suy ra
n
X
C2r
n
r=0
2
n−2r
1
3n + 1
1
2n
·
(1 + )n + (1 − )n =
=
2
2
2
2
1.4. Cæng thù
huyºn êi ng÷ñ
B¥y gií ta sû döng kþ hi»u h¼nh thù
º
hùng minh
æng thù
huyºn
êi ng÷ñ
v· têng qua tê hñp d÷îi ¥y:
ành l½ 1.2. Gi£ sû f (k) v g(k) l nhúng h m sè hå
thäa m¢n f (n) =
n
P
k=0
Ckn g(k)
vîi måi
n ∈ N.
Khi â ta
â
g(n) =
n
X
k=0
(−1)k Ckn f (n − k).
Chùng minh. Vi¸t mët
¡
h h¼nh thù
f (k) v g(k) qua f v g . Khi
k
k
â f n = P Ckn gk hay f n = (g + 1)n óng vîi ∀ n ∈ N. Vªy
n
k=0
(f + x)n = (g + 1 + x)n , ∀ x.
Nhî sau khi khai triºn ð hai v¸ s³ vi¸t fk v
gk thay
ho nhúng f k v g k .
n
Cho x = −1
â gn = (f − 1)n hay g(n) = P (−1)k Ckn f (n − k).
k=0
V½ dö 1.5. Cho d¢y Fibona
i F
Chùng minh r¬ng
B i gi£i. Vîi
n
X
0
= F1 = 1, Fn+1 = Fn + Fn−1 , n > 1.
!
n
(−1)j
Fn =
(F2j − 1).
j
j=1
√
√
1+ 5
1− 5
, x2 =
x1 =
â biºu di¹n
2
2
1
Fn = √ (xn+1
− xn+1
2
1 ).
5
12
Khi â
n
X
n
!
n
1 X n
!
Fj = √
(xj+1
− xj+1
2
1 )
j
5 j=0 j
1
= √ [x2(1 + x2 )n − x1 (1 + x1 )n ]
5
1
2n
= √ [x2x2n
2 − x1 x1 ],
5
j=0
v¼ 1 + x2 = x22, 1 + x1 = x21. Vªy
n
X
n
!
1
Fj = √ (x22n+1 − x12n+1 ) = F2n .
j
5
j=0
Theo ành lþ 1.2, ta nhªn ÷ñ
Fn =
n
X
(−1)j
j=0
!
n
g(j) =
j
vîi f (j) = Fj , g(n) = F2n. V¼ F0 = 1 = −
Fn =
n
X
n
X
(−1)j
j=1
!
n
F2j
j
(−1)j
j=0
n
P
(−1)j
j=1
n
j
!
n¶n
!
n
(F2j − 1).
j
V½ dö 1.6. X²t d¢y sè Lu
as L
n > 1.
Khi â ta
â
(ii) L2n =
(iii) Ln =
j=0
n
P
j=1
!
n
Lj .
j
(−1)j
= 2, L1 = 1
v
√
√
1+ 5
1− 5
, x2 =
·
x1 =
2
2
(i) Ln = xn1 + xn2 vîi
n
P
0
!
n
(L2j − 2).
j
Ln+2 = Ln+1 + Ln
vîi
13
B i √gi£i. B¬ng ph÷ìng ph¡p qui n¤p theo n, vîi
1+ 5
ta
â biºu di¹n Ln = xn2 + xn1 v ta
â (i).
2
(ii) V¼ 1 + x2 = x22, 1 + x1 = x21 n¶n
â bi¸n êi
n
X
n
j=0
j
!
n
X
n
Lj =
j=0
x2n
2
=
j
!
√
1− 5
, x2 =
x1 =
2
(xj2 + xj1 ) = (1 + x2 )n + (1 + x1 )n
+ x2n
1 = L2n .
!
n
Vªy
â
æng thù
L2n =
Lj .
j
j=0
(iii) Theo ành lþ 1.2, nhªn ÷ñ
n
P
Ln =
n
X
(−1)j
j=0
!
!
n
X
n
n
g(j) =
(−1)j
L2j
j
j
j=0
vîi f (j) = Lj , g(n) = L2n. V¼ L0 = 2 = −2 (−1)j
j=1
d ng suy ra ֖
æng thù
n
P
Ln =
n
X
(−1)j
j=1
n
j
!
n¶n
hóng ta d¹
!
n
(L2j − 2).
j
V½ dö 1.7. Cho d¢y
Dn =
n
X
(−1)k
k=0
!
n
(n − k)!
k
!
vîi
n > 1.
Chùng minh r¬ng
n! = 1 +
!
n
X
n
k=2
B i gi£i. Ta
â
(−1)nDn =
n
X
k=0
(−1)n−k
k
Dk
!
vîi måi
n > 2.
n
!
X
n
n
(n − k)! =
(−1)k
k!
n−k
k
k=0
14
vîi n > 1. °t fk = (−1)kDk v gk = (−1)kk!. Khi â
f (n) =
n
X
n
k=0
Theo ành lþ 1.2, ta nhªn ÷ñ
gn =
n
X
(−1)n−k
k=0
hay
(−1)nn! =
k
!
!
gk .
!
n
X
n
n
fk =
(−1)n
Dk
k
k
k=0
n
X
k=0
(−1)n
!
n
Dk .
k
V¼ D0 = 1 theo quy ÷î
v D1 = 0 n¶n n! = 1 +
n
P
k=2
(−1)n
!
n
Dk .
k
1.5. Nguy¶n lþ Bò-Trø
Khi x²t b i to¡n tê hñp, ta th÷íng ph£i ¸m xem
â bao nhi¶u
§u h¼nh
â thº t¤o ra vîi nhúng y¶u
u °t tr÷î
. Nâi
hung, º ¸m
¡
§u h¼nh
¢
ho ng÷íi ta t¼m
¡
h ÷a
¡
§u h¼nh v· lo¤i quen thuë
qua vi»
ph¥n ra th nh
¡
lîp º ¡p döng nguy¶n lþ
ëng d÷îi ¥y:
Card (A ∪ B) = Card (A) + Card (B) − Card (A ∩ B).
Têng qu¡t nguy¶n lþ
ëng ta
â Nguy¶n lþ Bò-Trø. C¡i khâ
õa vi»
vªn
döng nguy¶n lþ Bò-Trø l vi»
ph¥n lîp nh÷ th¸ n o º d¹ d ng
â ÷ñ
¡
sè ¸m.
Kþ hi»u lü
l֖ng
õa tªp A gçm mët sè húu h¤n
¡
phn tû qua |A|.
Gi£ sû A1, . . . , An l nhúng tªp
on
õa tªp A. C¡
sè sk ÷ñ
x¡
ành
15
qua
s0 = |A|
s1 = |A1 | + |A2 | + · · · + |An |
s2 = |A1 ∩ A2 | + |A1 ∩ A3 | + · · · + |An−1 ∩ An |
···
sk =
···
X
16i1
2 gi£ thi¸t k¸t luªn óng
ho n − 1 tªp. °t A = S Ai. Theo
i=1
æng thù
(1) ta
â
n
[
Ai = |A ∪ An | = |A| + |An | − |A ∩ An |.
i=1
Sû döng gi£ thi¸t qui n¤p
ho |A| v |A ∩ An| ta
â
æng thù
.
16
V½ dö 1.8. Câ bao nhi¶u sè tü nhi¶n n ∈ [1, 2005] m khæng
hia h¸t
ho
mët sè n o trong
¡
sè 2,3,11,13.
B i gi£i. Kþ hi»u A = {1, 2, . . . , 2005} v A l tªp
on
õa A gçm t§t
i
2005
= 1002, |A3| =
2
2005
2005
2005
= 668, |A11| =
= 182 v |A13 | =
= 154; ta l¤i
â
3
11
13
2005
2005
2005
|A2 ∩A3 | =
= 334, |A2 ∩A11 | =
= 91, |A2 ∩A13 | =
=
6
22
26
2005
2005
= 60, |A3 ∩ A13 | =
= 51, |A11 ∩ A13 | =
77, |A3 ∩ A11 | =
33
39
2005
2005
= 14. T½nh |A2 ∩ A3 ∩ A11 | =
= 30, |A2 ∩ A3 ∩ A13 | =
143
66
2005
2005
2005
= 25, |A2 ∩ A11 ∩ A13 | =
= 7, |A3 ∩ A11 ∩ A13 | =
= 4,
78
429
286
2005
|A2 ∩ A3 ∩ A11 ∩ A13 | =
= 2. Sè T
¡
sè thuë
A khæng
hia h¸t
858
ho 2, 3, 11, 13 l
£
¡
sè nguy¶n d÷ìng
hia h¸t
ho i. Ta
â |A2| =
T = |A| − |A2 ∪ A3 ∪ A11 ∪ A13 | = 2005 − (1002 + 668 + 182 + 154) +
+ (334 + 91 + 77 + 60 + 51 + 14) − (30 + 25 + 7 + 4) + 2 = 562.
Vªy T = 562.
V½ dö 1.9. N¸u sè nguy¶n d÷ìng n > 1
â sü ph¥n
ti¶u
hu©n th nh
t½
h
t½
h
n=
pα1 1 pα2 2
. . . pαs s th¼ h m Euler
l sè t§t
£
¡
sè nguy¶n
ϕ(n) = n
k ∈ {1, 2, . . . , n}
s
Q
i=1
1
, trong
pi
(k, n) = 1.
1−
sao
ho
Chùng minh. Vîi méi 1 6 i 6 s ta ành ngh¾a tªp A
â
ϕ(n)
= {pi , 2pi, . . . , npi} .
Khi â
¡
Ai l nhúng tªp
on
õa tªp T = {1, 2, . . . , n} v |Ai| = pn · Vîi
i
méi
°p i, j, i 6= j, tªpn Ai ∩ Aj bao gçm t§t
£
¡
sè thuë
T l bëi
õa
· T÷ìng tü t½nh lü
l֖ng
õa
¡
tªp giao kh¡
.
pi pj v |Ai ∩ Aj | =
pi pj
i
17
Theo nguy¶n lþ Bò-Trø, ành lþ 1.3, ta
â
n
[
ϕ(n) = n − Ai
i=1
s
X
n
X
n
n
−
p
pp
ppp
i=1 i
16i
- Xem thêm -