S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn
ĐạI HọC THáI NGUYÊN
Tr-ờng Đại học KHOA học

nguyễn THị NGọC áNH
Một số chuyên đề về tổ hợp dành
cho học sinh có năng khiếu toán
bậc trung học phổ thông

luận văn thạc sỹ TOáN học THáI NGUYÊN - 2009 THáI NGUYÊN - 2009 ▲ê✐ ❝➯♠ ➡♥
▲✉❐♥ ✈➝♥ ♥➭② ➤➢î❝ ❤♦➭♥ t❤➭♥❤ ❞➢í✐ sù ❤➢í♥❣ ❞➱♥ t❐♥ t×♥❤ ✈➭ ♥❣❤✐➟♠ ❦❤➽❝
❝ñ❛ ❚❙ ✳ ◆❣✉②Ô♥ ➜ø❝ ❍♦➭♥❣✳ ❚➠✐ ①✐♥ ❜➭② tá ❧ß♥❣ ❦Ý♥❤ trä♥❣ ✈➭ ❜✐Õt ➡♥ s➞✉
s➽❝ tí✐ ❚❤➬② ✈➭ ❣✐❛ ➤×♥❤✳
❚➠✐ ①✐♥ ❝❤➞♥ t❤➭♥❤ ❝➯♠ ➡♥ ❇❛♥ ❣✐➳♠ ❤✐Ö✉ tr➢ê♥❣ ➜➵✐ ❤ä❝ ❑❤♦❛ ❤ä❝✱ P❤ß♥❣
➤➭♦ t➵♦ ✈➭ ♥❣❤✐➟♥ ❝ø✉ ❦❤♦❛ ❤ä❝ ➤➲ q✉❛♥ t➞♠ ❣✐ó♣ ➤ì✱ t➵♦ ♠ä✐ ➤✐Ò✉ ❦✐Ö♥ t❤✉❐♥
❧î✐ ❝❤♦ t➠✐ ➤➢î❝ ❤ä❝ t❐♣ tèt✳
❚➠✐ ①✐♥ ❝❤➞♥ t❤➭♥❤ ❝➯♠ ➡♥ ❙ë ●✐➳♦ ❞ô❝ ✈➭ ➜➭♦ t➵♦ ❚Ø♥❤ ❚❤➳✐ ◆❣✉②➟♥✱
❚r➢ê♥❣ ❚r✉♥❣ ❤ä❝ ♣❤æ t❤➠♥❣ ❈❤✉②➟♥ ❚❤➳✐ ◆❣✉②➟♥✱ ➤➷❝ ❜✐Öt ❧➭ tæ ❚♦➳♥ ➤➲
❣✐ó♣ ➤ì t➠✐ ✈Ò t✐♥❤ t❤➬♥ ✈➭ ✈❐t ❝❤✃t tr♦♥❣ s✉èt q✉➳ tr×♥❤ ❤ä❝ t❐♣✳
✶
▼ô❝ ❧ô❝
▲ê✐ ❝➯♠ ➡♥ ✶
▼ë ➤➬✉ ✸
❈❤➢➡♥❣ ✶✳ ❑✐Õ♥ t❤ø❝ ❝➡ ❜➯♥ ✻
✶✳✶✳ ◗✉② t➽❝ ❝é♥❣ ✈➭ q✉② t➽❝ ♥❤➞♥ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✻
✶✳✷✳ ❍♦➳♥ ✈Þ ✈➭ tæ ❤î♣ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✼
✶✳✸✳ ◆❣✉②➟♥ ❧ý ❝❤✉å♥❣ ❝❤✐♠ ❜å ❝➞✉ ✭◆❣✉②➟♥ ❧ý ❉✐r✐❝❤❧❡t✮ ✳ ✳ ✳ ✳ ✾
✶✳✹✳ ❍♦➳♥ ✈Þ ✈➭ tæ ❤î♣ tæ♥❣ q✉➳t ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✶
✶✳✺✳ ❈➠♥❣ t❤ø❝ ❜❛♦ ❤➭♠ ✈➭ ❧♦➵✐ trõ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✹
❈❤➢➡♥❣ ✷✳ ▼ét sè ❝❤✉②➟♥ ➤Ò ✈Ò tæ ❤î♣ ❞➭♥❤ ❝❤♦ ❤ä❝ s✐♥❤ ❝ã ♥➝♥❣
❦❤✐Õ✉ t♦➳♥ ❜❐❝ tr✉♥❣ ❤ä❝ ♣❤æ t❤➠♥❣ ✶✼
✷✳✶✳ ❈❤✉②➟♥ ➤Ò ✶✿ ◗✉② t➽❝ ❝é♥❣ ✈➭ q✉② t➽❝ ♥❤➞♥ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✽

ết ề tổ ợ ề ó sẽ t ột t
ệ ề tổ ợ ọ s ổ t ệt ữ ọ
s ó ế t ú t ọ sẽ ứ
ợ ò tí t ọ ủ ồ tờ
ũ ột t ệ ể ồ ệ t
ồ ột ú t trì ột số ế

tứ ủ tổ ợ t ột s ớ s ổ t
sự ớ ọ s trọ t ủ r
ọ s ợ tì ể ờ ề
ề 1 t ộ q t
ề 2 ị tổ ợ
ề 3 ý ồ ồ
ề 4 số s
ề 5 số t
ề 6 số tr
ề 7 ị tổ ợ tổ qt
ề 8 ý trừ
ề 9 ữ sự trộ ữ sự s t trớ
ề 10 ợ t ế
r ỗ ề t tờ ợ t t ữ ủ ề
t ị ó ọ s tự tì t ì ữ ế tứ q
ế ủ ề ợ ồ tờ ỗ ề ó ờ tết ọ
s t t ờ ờ ít tr t ệ ề tổ ợ ó
tr tị trờ ọ í ề í tí sự ể ết
ò s ủ ọ s ó ế t ó ộ
ữ t ề ị ợ ọ ự ĩ ỡ ú ụ
ữ ế tứ t ợ từ trớ ể ỹ t
tổ ợ ủ ì
ột tờ ứ ợ t sẽ

◗✉② t➽❝ ♥❤➞♥✿ ◆Õ✉ E
i
(i = 1, ..., k) ❧➭ k sù ❦✐Ö♥ ✈➭ E
1
❝ã t❤Ó ①➯② r❛ t❤❡♦
n
1
❝➳❝❤❀ E
2
❝ã t❤Ó ①➯② r❛ t❤❡♦ n
2
❝➳❝❤ ✭❦❤➠♥❣ ♣❤ô t❤✉é❝ ➤Õ♥ ✈✐Ö❝ E
1
①➯②
r❛ ♥❤➢ t❤Õ ♥➭♦✮❀ E
3
❝ã t❤Ó ①➯② r❛ t❤❡♦ n
3
❝➳❝❤ ✭❦❤➠♥❣ ♣❤ô t❤✉é❝ ➤Õ♥ ✈✐Ö❝
E
1
✈➭ E
2
①➯② r❛ ♥❤➢ t❤Õ ♥➭♦✮✱✳✳✳✱E
k
❝ã t❤Ó ①➯② r❛ t❤❡♦ n
k
❝➳❝❤ ✭❦❤➠♥❣ ♣❤ô
t❤✉é❝ ➤Õ♥ ✭k− 1✮ sù ❦✐Ö♥ tr➢í❝ ①➯② r❛ ♥❤➢ t❤Õ ♥➭♦✮✱ t❤× k sù ❦✐Ö♥ ❝ã t❤Ó ①➯②
r❛ ➤å♥❣ t❤ê✐ t❤❡♦ n

ị ĩ ột rtổ ợ ủ X ột t ồ r tử ủ X
ố rtổ ợ ủ ột t ợ n tử ợ ý ệ C(n, r)
ị ý (i) P (n, r) =
n!
(n r)!
(ii) C(n, r) =
P (n, r)
r!
=
n!
r!(n r)!
= C(n, n r)
ở ú t r từ
m! (1).(2)...(m) 0! 1
ứ (i) ó n ọ ột tử t ỳ ủ X ị trí
t tr r ị trí ó (n 1) ọ ột tử từ ó (n 1)
tử ò ể ế ị trí tứ tr số r ị trí ú ý r số ọ
tử ế ị trí tứ ụ tộ ọ tử ế ở
ị trí tứ t tế

ó t q t ị trí t ó tể ở n(n 1)
tt r ị trí ó tể ở
P (n, r) = n(n 1)...(n r + 1) =
n!
(n r)!

(ii) ể C(n, r) ú ý r ột r ị ủ t ợ n tử X
ị ủ ột rt ó ủ X
ữ ữ rt ệt s r rtổ ợ ệt ó
q t ộ t ó

ế tt ì tr ể ợ 2 ế ù


ỗ ột ợ ột ồ ồ n = 3 ó ế
n + 1 = 4 ế tt tì ít t ó ế tt ù ột tổ qt
ủ ý ồ ồ s
ế n ồ ồ trú ủ kn + 1 ồ ớ
k ột số tì ít t ó ột ồ ứ từ k + 1
ồ trở
í ụ tự í ụ 1.3.1 ế 6 ế tt ù tì t
ó n = 3 ể r ột ề tr số ồ
ó ứ k + 1 = 6 ề ồ tì ú t
kn + 1 = 16 ó số 16 ế tt
í ụ ột tủ ứ 20 ế s tr ó ó 4 ế ỏ 7
ế tr 9 ế ỏ r ít t ế
ợ ì tủ ể ợ r = 4, 5, 6, 7, 8, 9 ế

ù

) rờ ợ 1 r = 4 = k + 1 r k = 3 ó 3 n = 3 ó
r ít t kn + 1 = 3.3 + 1 = 10 ế s
) rờ ợ 2 r = 5 = k + 1 r k = 4 P tí t
ú t tở tợ r ữ ế ợ r từ tủ ột t tự
ì ố í sự ể t 4 ế t t ù
ỏ ó ế ò r ó tr
ể r = 5 ế r ó ù tì n = 2 ố ợ ít
t ó tr r kn + 1 = 4.2 + 1 = 9 t
ý ồ ồ r ít t 4 + 9 = 13 ế
) rờ ợ 3 r = 6 = k + 1 r k = 5 tự trờ ợ
2 ết q 4 + kn + 1 = 4 + 5.2 + 1 = 15 ế r

v
r
=























n(r 1) + 1, r x
1
(n 1)(r 1) + 1 + x
1


.
ứ sử ợ tt ồ ề ứ ề t p
số ồ ỏ np n

m 1
n

= m1 < m
t
í ụ sử ó 26 s m = 26 7 ế t ể ở ọ
ó p =

25
7

= 3 ó ó ít t ột ế t ở từ 4 s trở
ị tổ ợ tổ qt
ị ĩ ế X ột t ồ n t tết
ệt t ỳ ột sự s ế ủ r n t từ t X ợ ọ
ột r ị tổ qt ủ X ế r = n ú t ọ ị
tổ qt ủ X
í ụ t X = {A, A, B, B, B, C, C} ó AABCBBC ột
ị tổ qt ủ
ế n
i
(i = 1, 2, ..., k) r n k + 2 số t n
1
+ n
2

1
, n
2
, ..., n
k
, n r)
í ụ P (18; 3, 4, 6) =
P (18, 3 + 4 + 6)
3!4!6!
=
P (18, 13)
3!4!6!
=
18!
3!4!6!5!
=
P (18; 3 + 4 + 6 + 5)
3!4!6!5!
= P (18; 3, 4, 6, 5) ợ tứ số
ị ủ ột t ở ị ý s
ị ý ố ị tổ qt ủ ột t X ồ n
i
t
ố ó ù ệ i (i = 1, 2, ..., k) P (n; n
1
, n
2
, ..., n
k
) ở

P (n, n)
q
= P (n; n
1
, n
2
, ..., n
k
)
í ụ X = {C, E, E, I, M, M, O, T, T} tì số ị tổ qt ủ
X
P (9, 1, 2, 1, 2, 1, 2) =
9!
1!2!1!2!1!2!
= 45360
ét r trì ổ t ị tổ qt ọ
ị
í ụ ỏ ó ế ết 4 q ó ỏ ố
3 q ó tr ố 5 q ó ố 18
ị trí t trớ ỗ ị trí ó ề t 1 ó


ố ế
P (18; 4, 3, 5) =
18!
4!3!5!6!
= 514594080
sử r X t ợ n tử S ột t t ỳ ủ X ó
r tử ột sự ó q t ế tứ tự ủ S ợ ọ ột
rtổ ợ tổ qt ủ X ế r = n ú t ó ệ tổ ợ tổ

)C(n n
1
, n
2
)....C(n n
1
n
2
... n
k1
)
=
n!
n
1
!n
2
!...n
k
!(n r)!
=
P (n, r)
n
1
!n
2
!...n
k
!


1
p
2
t ó ự ợ
n
2
p
k
t ó ự ợ n
k
tr ó n
i
(i = 1, 2, ..., k) ệt

k

i=1
p
i
n
i
= n ợ ở tứ
C(n;
p
1
số

n
1
, ...n

1
!(n
1
!)
p
1
][p
2
!(n
2
!)
p
2
]...[p
k
!(n
k
!)
p
k
]

í ụ sử ó s t trì ế sứ ù
t ọ ó t t ột ế
(i) ố s ệ ổ s ề
tố ỗ ổ ờ C(12; 4, 4, 4)
(ii) ố s t ó ỗ ó ó ờ
C(12; 4, 4, 4)/3!
(ii) ố s ứ ử ỗ ử ột s



(A B)


= n(X) n(A B) = n(X) [n(A) + n(B) + n(A B)]
(A B)

= A

B

ó
n(A

B

) = n(X) [n(A) + n(B)] + n(A B)
ị ĩ ế x ột tử t ỳ ủ X A ột t
ó ủ X tì é ế ủ x tr A 1 ế x ở tr A
0 ế x ở tr A
ứ ột ị ý tổ qt s
ị ý tứ ế A
1
, A
2
, ..., A
m
ữ t ủ
ột t ữ X tì
n(A

=

i,j=1,m
i=j
n(A
i
A
j
), ....)
ứ x ột tử tỳ ý ủ t ợ X ỉ r r é
ế ủ x ó ết q ố ở ế ủ trì tr ú
t q t tớ 2 trờ ợ
(i) x tử ủ t ỳ t ợ tr số m t ợ tr
(ii) x tử ủ ú r t ợ tr số m t ợ tr r 1 ú
t ó tể tết A
1
, A
2
, ..., A
r

r trờ ợ é ế ủ x 1 ở ế ủ trì
r trờ ợ s é ế ủ x ở ế tr 0 ố ớ ế
ú t ó
S
k
=

n(A
i

❈❤ø♥❣ ♠✐♥❤✿ ❚❛ ❝ã n(A
1
∪ A
2
∪ ...∪ A
m
) = n(X)−n(A

1
∩ A

2
∩ ...∩ A

m
)
s✉② r❛ ➤✐Ò✉ ♣❤➯✐ ❝❤ø♥❣ ♠✐♥❤✳
✶✻
❈❤➢➡♥❣ ✷
▼ét sè ❝❤✉②➟♥ ➤Ò ✈Ò tæ ❤î♣ ❞➭♥❤ ❝❤♦ ❤ä❝
s✐♥❤ ❝ã ♥➝♥❣ ❦❤✐Õ✉ t♦➳♥ ❜❐❝ tr✉♥❣ ❤ä❝ ♣❤æ
t❤➠♥❣
❚r♦♥❣ ❝❤➢➡♥❣ ♥➭② t➳❝ ❣✐➯ ①✐♥ tr×♥❤ ❜➭② ✶✵ ✈✃♥ ➤Ò✿
❈❤✉②➟♥ ➤Ò 1✿ ◗✉② t➽❝ ❝é♥❣ ✈➭ q✉② t➽❝ ♥❤➞♥✳
❈❤✉②➟♥ ➤Ò 2✿ ❍♦➳♥ ✈Þ ✈➭ tæ ❤î♣✳
❈❤✉②➟♥ ➤Ò 3✿ ◆❣✉②➟♥ ❧ý ❝❤✉å♥❣ ❝❤✐♠ ❜å ❝➞✉✳
❈❤✉②➟♥ ➤Ò 4✿ ❈➳❝ sè ❘❛♠s❡②✳
❈❤✉②➟♥ ➤Ò 5✿ ❈➳❝ sè ❈❛t❛❧❛♥✳
❈❤✉②➟♥ ➤Ò 6✿ ❈➳❝ sè ❙t✐r❧✐♥❣✳
❈❤✉②➟♥ ➤Ò 7✿ ❍♦➳♥ ✈Þ ✈➭ tæ ❤î♣ tæ♥❣ q✉➳t✳

ị trí t ụ tể tr t ỉ q
t ế 4 ị trí ị trí t 0 ó 9 ọ ó 9
ọ ị trí tứ 2 8 ọ ị trí tứ 3 7 ọ ị
trí tứ 4 ó ó (9).(9).(8).(7) = 4536 số r t
t
ị í ứ r ột số r ó ộ tì
ết 11 (1)
ứ t ế ỏ ữ số t ữ số ố ù ủ
ột số r tì t ợ ột số r ớ ó t ứ
(1) t q
sử N ột số r ó ộ 2k
ế k = 1 tì (1) ể ú
ế k 2 t ó

N = a
2k1
.10
2k1
+ a
2k2
.10
2k2
+ ... + a
k
.10
k
+ a
k
.10
k1


2k2ữ số
Q = a
2k2
.10
2k2
+ ... + a
2k2
.10
1
tết q Q ết 11 n ết 11
t r ột số r ị ữ số ứ 1
ữ ữ số tế t ó tể 0 1 ế tt số r
ị ó ộ n
2.1.2 ú t ỉ q t ế

n + 1
2

1 =

n 1
2

ị trí ỗ ị trí ó tể ữ số 1 ữ số 0 ó tt
2
[
n1
2
]

).(3
b
).(5
c
).(7
d
) tr ó
0 a 3; 0 b 2; 0 c 3; 0 d 2 r ể ễ a
ó 4 ọ b ó 3 ọ c ó 4 ọ d ó 3 ọ
q t tổ số ớ tự sự t sẽ
(4).(3).(4).(3) 2 = 142 số
t ế số ớ tự sự ủ ột số N ết N ó ết q
tí r từ số tố s
N = p
n
1
1
p
n
2
2
...p
n
k
k
tr ó p
1
, p
2
, ..., p

số tố ù
ét t ợ X = {2
3
; 3
2
; 5
3
; 7
2
} q ế sự tí r từ
số tố ủ 441000 õ r r ỗ tử ủ X t ệ
tr sự tí r từ số tố ủ m ủ n ợ
t ệ ồ tờ ở 2 số ữ sự tí ủ m n ợ
t X ứ số tí 441000 t m, n ớ số

X t 2 t rỗ q t ế tứ tự ì m.n
n.m sự tí ố ết q t X tí
tứ tự t
X = {2
3
} + {3
2
, 5
3
, 7
2
} = {3
2
} + {2
3

}
= {2
3
, 7
2
} + {3
2
, 5
3
}
ó ết q ủ t 4 + 3 = 7 = 2
41
1
t ổ qt 2.1.9 t ó ế N = p
n
1
1
p
n
2
2
...p
n
k
k
p
1
, p
2
, ..., p

}
{a
k
} W
ờ tết q W ó 2
k2
1 t
ứ ớ ỗ ó t t a
k
ột tr tì ợ
ủ Z í t ở tr t ó ết q số
Z t t
1 + (2
k2
1).2 = 2
k1
1().
ị ĩ r ột ỗ ị tử 0
1 X ột t ợ tt ỗ ị ó ộ n ột

í ủ n ế ột từ X tớ t ợ Y = {0, 1}
t ì số í ệt ủ n ế
ự ợ ủ X r = 2
n
ó số í t 2
r

ị ĩ ột í ợ ọ tự ố ế trị ủ
f t ổ ế ỗ tử tộ ề ị ủ f t
ổ ữ số 0 ổ t số 1 ợ

3
(10) = 1
d)f
4
(00) = f
4
(11) = f
4
(01) = f
4
(10) = 0
t ì số ợ í tự ố ủ n ế
2.1.12 X ó tể t
r
2
= 2
n1
(,

) tr ó
ỗ

ó ợ từ t 0 t 1 ợ ố ớ ỗ
tì trị ủ í tự ố ó tể 0 1 ó ó 2
r
2
í ủ tổ số í
t ột ớ ồ út ợ số từ 0
ế n t ề từ tr s từ 0 ế m t ề từ ớ tr
ỏ ó ờ từ út ế út ế ỉ

r n 2
m

ú t ết ỗ tử x tr ớ ột ị ó m
ữ số a(x) = (x
1
, x
2
, ..., x
m
) tỏ x
i
= 1 ế x ở tr A
i
x
i
= 0
ế x ở tr A
i
ự ột số
f : S T = {(x
1
, x
2
, ..., x
m
) | x
i
{0, 1}}