1
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG TRƯƠNG NHẬT LÝ

BÀI TOÁN ĐẾM NÂNG CAO
TRONG TỔ HỢP VÀ ỨNG DỤNG

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 60.46.40

Phản biện 2:
Luận văn ñược bảo vệ trước Hội ñồng chấm Luận văn tốt
nghiệp Thạc sĩ Khoa học, họp tại Đại học Đà Nẵng vào 22 ngày
tháng 10 năm 2011 Có thể tìm hiểu luận văn tại:
- Trung tâm Thông tin – Học liệu, Đại học Đà Nẵng
-
Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng

3

MỞ ĐẦU

1. LÝ DO CHỌN ĐỀ TÀI
Tổ hợp có vị trí ñặc biệt trong toán học không chỉ như là những ñối tượng ñể

Phương pháp giải bài toán ñếm và các bài toán áp dụng.

•
Ứng dụng của bài toán ñếm tổ hợp.
5. PHƯƠNG PHÁP NGHIÊN CỨU
Sử dụng phương pháp nghiên cứu tài liệu liên quan ñến luận văn ñể thu thập
thông tin, từ ñó phân tích, hệ thống và phân loại các phương pháp giải cũng như một
số ứng dụng ñiển hình liên quan ñến bài toán ñếm trong tổ hợp.
4

6. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI
Đề tài hệ thống kiến thức về các nguyên lý ñếm, các cấu hình tổ hợp, lý thuyết
hàm sinh, hệ thức truy hồi và các kiến thức liên quan ñến bài toán ñếm tổ hợp. Từ ñó
hình thành các phương pháp từ cơ bản ñến nâng cao và một số ứng dụng liên quan
ñến bài toán ñếm. Qua ñó bổ sung thêm cho các em học sinh, sinh viên về các
phương pháp giải các bài toán ñếm tổ hợp từ cơ bản ñến khó và rất khó, ñặc biệt là
trước các kì thi học sinh giỏi từ cấp tỉnh, cấp quốc gia ñến thi Olympic quốc tế và các
kỳ thi khác. Đề tài còn có thể làm nguồn tham khảo cho những ai quan tâm ñến lý
thuyết tổ hợp mà cụ thể là phương pháp giải và ứng dụng của bài toán ñếm tổ hợp.
7. CẤU TRÚC CỦA LUẬN VĂN
Luận văn ñược cấu trúc bởi 3 chương:
Chương 1: Tổng quan về tổ hợp
Chương 2: Một số phương pháp ñếm nâng cao
Chương 3: Một số ứng dụng

Chương 1
TỔNG QUAN VỀ TỔ HỢP

1.3.2.2. Hoán vị lặp
1.3.2.3. Chỉnh hợp không lặp
1.3.2.4. Chỉnh hợp lặp
Định nghĩa 1.4: Chỉnh hợp lặp chập k của n phần tử khác nhau là một bộ có thứ tự
gồm k thành phần lấy từ n phần tử ñã cho, các phần tử có thể ñược lặp lại.
Định lí 1.2: Số lượng các chỉnh hợp lặp chập k của n phần tử ñược kí hiệu và xác
ñịnh bởi công thức sau:
k
n
A
= AR(n, k) = n
k
.
1.3.2.5. Tổ hợp không lặp
1.3.2.6. Tổ hợp lặp
Định nghĩa 1.6: Tổ hợp lặp chập k của n phần tử khác nhau là một nhóm không phân
biệt thứ tự gồm k phần tử trích từ n phần tử ñã cho, trong ñó các phần tử có thể ñựợc
lặp lại.
Định lý 1.3: Giả sử X có n phần tử khác nhau. Khi ñó số tổ hợp lặp chập k của n
phần tử của X, ñược ký hiệu và xác ñịnh bởi công thức sau:
CR(n, k) = C(k + n - 1, n - 1) = C(k + n - 1, k).
Ví dụ 1.56. Bất phương trình x
1
+ x
2
+ x
3
≤ 11 (1) có mấy nghiệm nguyên không âm ?
Lời giải: Số nghiệm của bất phương trình (1) chính bằng số nghiệm nguyên của
phương trình: x

và
S X
⊂
có r phần tử.
Một phân hoạch
{
}
1 2 k
S , S , , S

có thứ tự của S gọi là một phân hoạch thứ tự tổ hợp
chập r của X. Nếu r = n thì gọi là phân hoạch thứ tự của X.
Cho các số nguyên dương
1 2 k
n , n , , n

thỏa
1 2 k
n n n r.
+ + + =
Số các phân
hoạch thứ tự tổ hợp chập r của X dạng
{
}
1 2 k
S , S , , S

có
2
S
, có C(
1 2
n n ,n
−
) khả năng.
…
Bước k: Chọn
k
n
phần tử từ X\
1 2 k 1
(S S S )
−
∪ ∪ ∪
cho
k
S
, có
C(
1 2 k 1 k
n n n n ,n
−
− − − −
) khả năng.
Theo nguyên lý nhân suy ra:
1 2 k
C(n; n ,n , ,n )


n!
P(n;n ,n , n ,n r);
n !n ! n !(n r)!

= −
−
1 2 k
C(n;n ,n , ,n )

ñược gọi là hệ số ña thức.
Ví dụ 1.57. 17 sinh viên ñi dạ hội bằng 5 xe khác nhau theo thứ tự có số chỗ ngồi
tương ứng là 4, 3, 3, 4, 1. Hãy xác ñịnh số cách chở 17 sinh viên bằng 5 xe, trong ñó
có 2 sinh viên phải ñi bằng phương tiện khác.
Lời giải: Mỗi cách chở là một phân hoạch thứ tự tổ hợp chập 15 của 17 với số phần
tử trong mỗi tập con tương ứng là 4, 3, 3, 4, 1. Vì vậy số cách chở là:
C(17;4,3,3,4,1)
=
17!
4!3!3!4!1!
= 8576568000.
1.3.3.2. Phân hoạch không thứ tự
Định nghĩa 1.8: Cho X là tập gồm n phần tử khác nhau, các số nguyên dương
1 2 k
n ,n , ,n
và
1 2 k
p ,p , ,p
thỏa
1 1 2 2 k k
n p n p n p n.

p
tập lực
lượng
2
n
, …,
k
p
tập lực lượng
k
n
là:

1 2 k
1 1 2 2 k k
p p p
1 2 k
1 1 2 2 k k
C(n; n , , n , n , , n , , n , , n ) n!
p !p ! p !
p !(n !) p !(n !) p !(n !)=

Trong tử số
1 1 2 2 k k
C(n; n , , n , n , , n , , n , , n )

số

n n n n

+ + + =
7

Hỏi có bao nhiêu cách phân phối khác nhau, không kể thứ tự cầu trong mỗi hộp.
Lời giải: Có thể phân phối bằng m bước như sau:
Bước 1: Chọn
1
n
phần tử từ n cầu cho hộp 1, có C(
1
n,n
) cách
Bước 2: Chọn
2
n
phần tử từ n -
1
n
cho hộp 2, có C(
1 2
n n ,n
−
) cách
…
Bước m: Chọn

n !n ! n !
.

Chương 2
MỘT SỐ PHƯƠNG PHÁP ĐẾM NÂNG CAO

2.1. NGUYÊN LÝ BÙ TRỪ
Với n tập hữu hạn A
1
, A
2
, , A
n
ta có ñịnh lý tổng quát sau:
Định lý 2.1: Với n tập hợp A
1
, , A
n
bất kỳ ta có công thức
|A
1
∪ ∪ A
n
| =
n
i
i=1
A
∑
-

n-1
N
n

trong ñó N
m
(1 ≤ m ≤ n) là tổng phần tử của tất cả các giao m tập lấy từ n tập ñã cho,
nghĩa là: N
m
=
1 2 m
1 2 m
i i i
1 i i i n
| A A A |
≤ < < < ≤
∩ ∩ ∩
∑

Ví dụ 2.6. Có bao nhiêu cách xếp 8 con xe lên bàn cờ quốc tế ñã bị gạch ñi một
ñường chéo chính sao cho không có con nào ăn con nào.
Lời giải: Có 8! cách xếp 8 con xe lên bàn cờ quốc tế sao cho không có con nào ăn
con nào. Ta cần ñếm số cách xếp không hợp lệ, tức là số cách xếp có ít nhất một con
xe nằm trên ñường chéo.
Gọi A
i
là tập hợp các cách xếp có quân xe nằm ở ô (i, i). Ta cần tìm
|A
1
∪ ∪A

8
8
C
.0!
=
8! 8! 8!
8!
2! 3! 8!
− + − −
.
Như vậy số cách xếp 8 con xe lên bàn cờ quốc tế ñã bị gạch ñi một ñường chéo chính
sao cho không có con nào ăn con nào bằng: 88!
– (
8! 8! 8!
8!
2! 3! 8!
− + − −
) =
8!
(

2! 3! 8!
1 1 1
+

280 280 280 280
| A | 140; | A | 93; | A | 56; | A | 40
2 3 5 7

       
= = = = = = = =
       
       
;
1 2 1 3 1 4
2 3 2 4 3 4
280 280 280
| A A | 46; | A A | 28; | A A | 20;
2.3 2.5 2.7
280 280 280
| A A | 18; | A A | 13; | A A | 8;
15 21 35     
∩ = = ∩ = = ∩ = =
     
     
     
∩ = = ∩ = = ∩ = =
     
     

1 2 3 1 2 4
1 3 4 2 3 4

| = 216.
Vậy trong tập S có 280 – 216 = 64 số không chia hết cho 2, 3, 5, 7.
2.2. PHƯƠNG PHÁP SONG ÁNH
2.2.1. Định nghĩa 2.1
Cho ánh xạ f: A
→
B.
•
Ánh xạ f ñược gọi là một ñơn ánh nếu với hai phần tử bất kì a
1
, a
2

∈
A mà a
1
≠ a
2

thì f(a
1
) ≠ f(a
2
), tức là f(a
1
) = f(a
2
)
⇔
a

Nếu có một song ánh f: A
→
B thì |A| = |B|. 9

Phương pháp song ánh dựa vào một ý tưởng rất ñơn giản: Nếu tồn tại một song
ánh từ A vào B thì |A| = |B|. Do ñó, muốn chứng minh hai tập hợp có cùng số phần
tử, chỉ cần xây dựng một song ánh giữa chúng. Hơn nữa, ta có thể ñếm ñược số phần
tử của một tập hợp A (kí hiệu |A|), ta có thể xây dựng song ánh từ A vào một tập hợp
B mà ta ñã biết cách ñếm số phần tử. Bởi B có cùng số phần tử với A nhưng có cấu
trúc ñược mô tả khác A nên ta có thể ñếm ñược số phần tử của B dễ dàng hơn việc
ñếm số phần tử của A.
Ví dụ 2.14 (APMO 1998).
Giả sử F
k
là tập hợp tất cả các bộ (A
1
, A
2
, , A
k
), trong ñó A
i
(i = 1, 2, , k) là
một tập con của tập E = {1, 2, , 1998}. Kí hiệu |A| là số phần tử của tập A.
Hãy tính:
1 2 k k
k 1 2 k

i
thuộc {1, 2, , n} ta ñếm xem có bao nhiêu bộ
(A
1
, A
2
, , A
k
) thỏa mãn ñiều kiện
1 2 k
A A A
∪ ∪ ∪
= {n
1
, n
2
, , n
i
} (2), từ ñó tính
ñược T(i, k) và S
k
.
Ta cho các phần tử n
1
, n
2
, , n
i
“ñăng ký” có mặt trong các tập hợp A
i

2
, , A
k
). Dễ thấy
rằng với hai bộ phiếu ñăng kí khác nhau, ta có hai bộ tập hợp (A
1
, A
2
, , A
k
) khác
nhau và như vậy số bộ (A
1
, A
2
, , A
k
) thỏa mãn (2) bằng số bộ phiếu ñăng kí hợp lệ.
Vì phiếu ñăng kí của n
p
, p = 1, 2, , i gồm k số 0 hoặc 1 và phải có ít nhất một số 1
nên n
p
có 2
k
– 1 cách ghi phiếu ñăng kí (do trừ ra xâu (0, 0, , 0) và như vậy theo
nguyên lý nhân có tất cả (2
k
– 1)
i

– 1).2
k(n-1)
.
(nhờ khai triển (1 + x)
n
và lấy ñạo hàm, cho x = 2
k
– 1 và nhân hai vế với 2
k
– 1).
Ví dụ 2.15 (Vô ñịch Liên Xô). Có một nhóm người mà trong ñó, mỗi cặp không
quen nhau có ñúng hai người quen chung, còn mỗi cặp quen nhau thì không có người
quen chung. Chứng minh rằng số người quen của mỗi người là như nhau. 10

Lời giải:
Nếu a quen b và tập các người quen của a và b (không kể a, b) lần lượt là A và
B. Mỗi người a’ thuộc A sẽ quen với duy nhất một người thuộc B (do a’ và b không
quen nhau, hơn nữa họ ñã có một người quen chung là a). Tương tự, mỗi người thuộc
B cũng quen với duy nhất một người thuộc A. Vậy tồn tại một song ánh ñi từ A tới B,
tức a và b có số người quen bằng nhau.
Nếu a không quen b thì tồn tại c quen cả a và b. Do ñó, số người quen của a và
b bằng nhau do cùng bằng số người quen của c (suy ra từ trên).
2.3. HỆ THỨC TRUY HỒI
2.3.1. Khái niệm mở ñầu và mô hình hóa bằng hệ thức truy hồi
Định nghĩa 2.2: Hệ thức truy hồi (hay công thức truy hồi) ñối với dãy số {a
n
} là

2.3.2.1. Giải hệ thức truy hồi bằng phương pháp lặp
Ta có thể dùng một trong hai phương án sau:
Hoặc ta ñi thay thế liên tiếp công thức truy hồi vào chính nó, mỗi lần thay như
vậy bậc n sẽ giảm ít nhất 1 ñơn vị, cho ñến khi ñạt giá trị ban ñầu.
Hoặc là ta xuất phát từ ñiều kiện ñầu ta sẽ tính một số số hạng ñầu và nhận ra
qui luật, sau ñó dự ñoán số hạng tổng quát và dùng phương pháp chứng minh qui nạp
ñể chứng minh tính ñúng ñắn của công thức vừa dự ñoán ñó.
Ví dụ 2.22 (Bài toán tháp Hà Nội) ‘‘Có ba cọc 1, 2, 3. Ở cọc 1 có n ñĩa xếp chồng
lên nhau sao cho ñĩa nằm dưới lớn hơn ñĩa nằm trên. Hãy chuyển tất cả các ñĩa từ cọc
1 sang cọc 3 có thể dùng cọc 2 làm cọc trung gian với ñiều kiện mỗi lần chỉ ñược
chuyển 1 ñĩa từ cọc này sang cọc khác và luôn ñảm bảo ñĩa nằm dưới lớn hơn ñĩa
nằm trên’’. Bài toán ñặt ra là: Tìm số lần di chuyển ñĩa ít nhất cần thực hiện ñể giải
xong bài toán trên.
Lời giải: Phương pháp di chuyển như sau: Gọi s
n
là số lần di chuyển ñĩa ít nhất cần
thực hiện.
•
Chuyển n-1 ñĩa từ cọc 1 sang cọc 2 (lấy cọc 3 làm trung gian) ta có s
n-1
phép
chuyển.
•
Chuyển ñĩa lớn nhất ở cọc 1 sang cọc số 3: ta có 1 phép chuyển. 11

•
Chuyển n-1 ñĩa ở cọc số 2 về cọc số 3 (lấy cọc 1 làm trung gian) ta có s

= 2s
n-1
+ 1 = 2(2s
n-2
+1) + 1 = 2
2
.s
n-2
+ 2 + 1= 2
2
(2s
n-3
+1)+2+1
= 2
3
s
n-3
+ 2
2
+ 2 + 1= … = 2
n-1
.s
1
+ 2
n-2
+ 2
n-3
+ … + 2 + 1
= 2
n-1

> a
i+1
.
Lời giải: Gọi S
n
là số các hoán vị thỏa mãn ñiều kiện bài toán. Để ý rằng số các hoán
vị mà a
n
= n là S
n-1
(Bởi vì S
n-1
là số các hoán vị (a
1
, a
2
, , a
n-1
) của 1, 2, …, n-1 sao
cho tồn tại duy nhất một chỉ số i
∈
{1, 2, …, n - 2} thỏa mãn a
i
> a
i+1
). Còn số các
hoán vị (a
1
, a
2

n-1
– 1. (Do
n
i 1 n 1
n 1
i 1
C 2
− −
−
=
=
∑
).
Hiển nhiên: S
2
= 1, tương tự ví dụ 2.22 ta sẽ có: S
n
= 2
n
- n - 1.
2.3.2.2. Giải hệ thức truy hồi tuyến tính hệ số hằng
Định nghĩa 2.3: Hệ thức truy hồi tuyến tính bậc k là hệ thức truy hồi có dạng:
a
n
= c
1
(n).

a
n-1

1
(n).

a
n-1
+ c
2
(n).

a
n-2
+ + c
k
(n).

a
n-k
(T
0
)
ñược gọi là hệ thức truy hồi tuyến tính thuần nhất bậc k ứng với (T).
•
Nếu c
i
(n) = c
i
, i = 1, 2, , k , ñều là các hằng số, c
k
(n) ≠ 0 thì (T) ñược gọi là hệ
thức truy hồi tuyến tính hệ số hằng bậc k và (T

k-1
− c
2
r
k-2
− − c
k-1
r – c
k
= 0 (1)
Phương trình (1) ñược gọi là phương trình ñặc trưng của hệ thức truy hồi (T
0
),
nghiệm của nó gọi là nghiệm ñặc trưng của hệ thức truy hồi. Nghiệm của phương
trình ñặc trưng dùng ñể biểu diễn công thức tất cả các nghiệm (nghiệm tổng quát) của
hệ thức truy hồi (T
0
). 12

∗
Các ñịnh lý sau ta xét các hệ thức truy hồi (T) và (T
0
) ở trên với hệ số hằng:
Định lý 2.3: Nếu a
1
, a
2

, nr
n
,
n
2
r
n
, …, n
m-1
r
n
là các nghiệm của (T
0
), và khi ñó (c
0
+c
1
n+c
2
n
2
+…+ c
m-1
n
m-1
)

.r
n
, (c

= a
1
(n) + a
2
(n) + + a
q
(n), trong ñó:
a
i
(n) = (C
i,0
+ nC
i,1
+ n
2
C
i,2
+…+
i
i
m 1
i,m 1
n .C
−
−
).
n
i
r
,

1
, r
2
, , r
k
(có thể phức).
Khi ñó dãy {a
n
} là nghiệm của hệ thức truy hồi (T
0
) thì nghiệm ñó có dạng
a
n
= α
1
r
1
n
+ α
2
r
2
n
+ + α
k
r
k
n
, trong ñó α
1

n-2
+ + C
k
.a
n-k
= f(n) (T)
trong ñó f(n) = P
s
(n) (là ña thức bậc s của n)
Phương trình ñặc trưng của (T) là: r
k
+ C
1
r
k-1
+ C
2
r
k-2
+ + C
k-1
r + C
k
= 0 (1)
•
Nếu phương trình ñặc trưng (1) không có nghiệm r = 1 thì nghiệm riêng của (T) có
dạng
*
n
a

= f(n) (T)
trong ñó f(n) = P
s
(n).
n
β
(là ña thức bậc s của n, và
β
là một hằng số)
Phương trình ñặc trưng của (T) là: r
k
+ C
1
r
k-1
+ C
2
r
k-2
+ + C
k-1
r + C
k
= 0 (1)
•
Nếu
β
không phải là nghiệm của phương trình ñặc trưng (1) thì nghiệm riêng của
(T) có dạng
*
13

Định lý 2.8: (Nguyên lý chồng chất nghiệm)
Cho hệ thức truy hồi tuyến tính không thuần nhất hệ số hằng bậc k:
a
n
= C
1
.a
n-1
+ C
2
.a
n-2
+ + C
k
.a
n-k
+ f(n) (T)
Nếu thành phần không thuần nhất f(n) của (T) có dạng
f(n) = p
1
(n) + p
2
(n) + + p
m
(n) thì nghiệm riêng của (T) có dạng
g

i 1,m
=
.
Ví dụ 2.33. Giải công thức truy hồi a
n
= 4a
n-1
– 4a
n-2
+ n2
n
+ 3
n
+ 4 , n ≥ 2 (T)
Lời giải:
•
Phương trình thuần nhất tương ứng có nghiệm tổng quát là h
n
= c
1
.2
n
+ c
2
.n2
n
•
Ta có thành phần không thuần nhất là f(n) = n2
n
+ 3

= 4a
n-1
– 4a
n-2
+ 4 (T
1
)
Ta có thành phần không thuần nhất là f
1
(n) = 4 = 4.1
n
và do 1 không là nghiệm của
phương trình ñặc trưng nên nghiệm riêng của (T
1
) có dạng c.1
n
, thay vào (T
1
) ta ñược
c = 4. Vậy nghiệm riêng của (T
1
) là 4.
* Với hệ thức a
n
= 4a
n-1
– 4a
n-2
+ 3
n

n
(T
3
)
Ta có thành phần không thuần nhất là f
3
(n) = n.2
n
và 2 là nghiệm bội 2 của phương
trình ñặc trưng nên nghiệm riêng của (T
3
) có dạng n
2
(c
1
n + c
2
)2
n
, thay vào (T
3
) ta có:
n
2
(c
1
n + c
2
)2
n

=
1
6
, c
2
=
1
2
. Vậy nghiệm riêng của (T
3
) là n
2
(
1
6
n +
1
2
)2
n
.
Từ ba trường hợp trên suy ra nghiệm riêng của hệ thức truy hồi (T) là
g
n
= 4 + 9.3
n
+ n
2
(
1

14

2.4. PHƯƠNG PHÁP ĐẾM BẰNG HÀM SINH
Có rất nhiều bài toán tổ hợp như bài toán phân hoạch tập hợp, bài toán ñếm,
tìm dãy số trong các ñề thi học sinh giỏi quốc gia, quốc tế là các bài toán rất khó.
Hàm sinh là một công cụ hiệu lực ñể giải quyết dạng bài tập này. Khái niệm hàm sinh
khá ñơn giản, dễ hiểu nhưng lại có ứng dụng rất hay vào việc giải các dạng bài toán
trên.
2.4.1. Định nghĩa 2.4
Cho dãy số {a
n
}. Chuỗi lũy thừa hình thức vô hạn F(x) =
n
n
n 0
a x
≥
∑
gọi là hàm sinh
thường sinh bởi dãy số {a
n
}. Kí hiệu: {a
n
}

α
ñược ñịnh nghĩa như sau:
k
( 1) ( k 1)
, k 0
C
k!
1, k 0
α
α α − α − +

>

=


=


•
Cho x là số thực với |x| < 1 và
α
là một số thực. Lúc ñó:
k k
k 0
(1 x) C x .
∞
α
α
=

n
}
↔
kF(x) ,
∀
k
∈
R
(3) {(n+1)a
n+1
}
↔
F’(x)
(4) {a
n
-a
n-1
}
↔
(1-x)F(x)
(5) {na
n
}
↔
xF’(x)
(6) {a
n+h
}
↔


1 x
−

(9) {c
n
} = {
i j
i j n
a b
+ =
∑
} = {
n
k n k
k 0
a b
−
=
∑
}
↔
F(x).G(x)
15

2.4.5. Một số khai triển ñại số thường dùng trong việc sử dụng hàm sinh
(1)
2 k

n
+…
(4) (1 + x)
n
=
1 2 2 n n
n n n
1 C x C x C x
+ + + +

(5)
n 1 k
n k 1
n
k 0
1
C x
(1 x)
∞
−
+ −
=
=
−
∑
=
2 3
n(n 1) n(n 1)(n 2)
1 nx x x
2 3!

1 x x x
1 x
= + + + +
−

(9)
2 4 6 3 5 7
2
x
x(1 x x x ) x x x x
1 x
= + + + + = + + + +
−

(10)
2
2
1
1 2x 3x
(1 x)
= + + +
−
+ (n+1)x
n
+
(11)
2 n
2
1 x
1 3x 5x (2n 1)x

− − = + + + + +

(15)
n k k k
n
n 0
(1 ax) C a x
∞
=
+ =
∑

2.4.6. Phương pháp ñếm bằng hàm sinh
Hàm sinh có thể ñược áp dụng trong các bài toán ñếm. Nói riêng, các bài toán
chọn các phần tử từ một tập hợp thông thường sẽ dẫn ñến các hàm sinh. Khi hàm sinh
ñược áp dụng theo cách này, hệ số của x
n
chính là số cách chọn n phần tử.
2.4.6.1. Chọn các phần tử khác nhau
Hàm sinh cho dãy các hệ số nhị thức ñược suy ra trực tiếp từ ñịnh lý nhị thức
i 0 1 k k k
k k k k
{C } C C x C x (1 x)
↔ + + + = +
16

Như vậy hệ số của x

n
1
(1 x)
−
.
Như vậy theo công thức Taylor số cách chọn k phần tử có lặp từ n phần tử bằng
k
n k 1
C .
+ −

Một cách tiếp cận khác, ta lập luận như sau:
Với k > 0, ta có
n
n k 1
{C , n 0, 1, 2, }

+ −
=
↔
F(x) =
k
1
(1 x)
−

Thậy vậy, ta có
k
1
(1 x)

+ −
. Như
vậy hệ số của x
n
chính bằng số cách chọn n vật từ tập có k loại ñồ vật.
Nhận xét 2.7: Ví dụ trên ñã áp dụng qui tắc xoắn gợi ý cho ta phương pháp giải
nhiều bài toán ñếm. Chẳng hạn với hàm sinh:
F(x) = (1 + x + x
2
+ x
3
+ x
4
+ x
5
)(1 + x + x
2
)(1 + x + x
2
+ x
3
)
Giả sử
3
1 2
x
x x
x , x , x

tương ứng là các số hạng lấy từ các thừa số thứ nhất, thứ

3
≤ 3. Như vậy hệ số này cũng cho ta số cách chọn n vật
từ tập có 3 loại vật, gồm 5 vật loại 1, 2 vật loại 2 và 3 vật loại 3.
17

Ví dụ 2.41. Bây giờ ta xét một bài toán ñếm rất khó chịu. Có bao nhiêu nhiêu cách
sắp một giỏ n trái cây thoả mãn các ñiều kiện ràng buộc sau:
•
Số táo phải chẵn
•
Chỉ có thể có nhiều nhất 4 quả cam
•
Số chuối phải chia hết cho 5
•
Chỉ có thể có nhiều nhất 1 quả ñào
Chẳng hạn, ta có 7 cách sắp giỏ trái cây có 6 trái:
Táo 6 4 4 2 2 0 0
Chuối 0 0 0 0 0 5 5
Cam 0 2 1 4 3 1 0
Đào 0 0 1 0 1 0 1
Lời giải: Các ñiều kiện ràng buộc này quá phức tạp và có cảm giác như việc ñi tìm
lời giải là vô vọng. Nhưng ta hãy xem hàm sinh sẽ xử lý bài toán này thế nào.
Trước hết, ta ñi tìm hàm sinh cho số cách chọn táo. Có 1 cách chọn 0 quả táo,
có 0 cách chọn 1 quả táo (vì số táo phải chẵn), có 1 cách chọn 2 quả táo, có 0 cách
chọn 3 quả táo …
Như thế ta có hàm sinh cho số cách chọn táo là A(x) = 1 + x
2

1 x
1 x
−
−

Và tương tự, hàm sinh cho số cách chọn ñào là D(x) = 1 + x =
2
.
1 x
1 x
−
−

Theo quy tắc xoắn, hàm sinh cho cách chọn từ cả 4 loại trái cây bằng
5 2
2 3
2 5 2
1 1 1 x 1 x 1
A(x).B(x).C(x).D(x) . . . 1 2x 3x 4x
1 x 1 x
1 x 1 x (1 x)
− −
= = = + + + +
− −
− − −

Gần như tất cả ñược giản ước với nhau! Chỉ còn lại
2
1
(1 x)

x 1 x x x
 
+ + + +
 
=
k
2
1 x
x
 
 
−
 
=
k
2 k
(1 x )
x
−
.
18

Chương 3
MỘT SỐ ỨNG DỤNG

3.1. MỘT SỐ ỨNG DỤNG CỦA HỆ THỨC TRUY HỒI
3.1.1. Ứng dụng bài toán tìm số hạng tổng quát của hệ thức truy hồi vào giải một

r =
1
2004

Nghiệm tổng quát của hệ thức truy hồi thuần nhất tương ứng là
n
n 1
1
b C . .
2004
 
=
 
 

f(n) = (-1)
n
nên chọn
*
n
b
= C
2
.(-1)
n
. Thay vào hệ thức truy hồi ở ñề bài ta ñược:
C
2
=
2004

n
1
−
.
Đề cho b
0
= 0
⇒
0 =
1
C
+
2004
2005

⇒

1
C
=
2004
2005
−

Vậy công thức tổng quát của dãy số cần tìm là:
b
n
=
n
2004 1

→+∞
=
( )
( )
( )
( )
2 2
n n
2
n n
n 1 n 1
n n
1 2004 1 1 (2004) 1
2004
lim lim .
2005
2005. 2004 2005. 2004
− −
→+∞ →+∞
   
− − − −
 
   
= =
 
 
   
   

Bài toán 3.7. (IMO 1967) Trong một cuộc thi ñấu thể thao có m huy chương, ñược

k
6 6k
a -
7 7
(Do ngày thứ k phát ñi k huy chương và
1
7
huy
chương còn lại). Giải hệ thức truy hồi này ta ñược:
k 1
k
6
a (m 36) 6k 42
7
−
 
= − − +
 
 
.
Theo giả thiết ta có a
n
= n =
n 1 n 1
6 7
(m 36) 6n 42 m 36 7(n 6)
7 6
− −
   
− − + ⇒ − = −

= +


= +

, với
α
,
β
, p, q, r, s là các hằng số thực.
Giải hệ trên là ñi xác ñịnh số hạng tổng quát của các dãy số (a
n
) và (b
n
) thỏa
mãn hệ thức truy hồi ñó. Bằng cách biến ñổi ñưa về giải hệ thức truy hồi tuyến tính
thuần nhất cấp hai. Muốn vậy ta thay n bởi n + 1 vào phương trình thứ hai của hệ trên
ta có:

n 2 n 1 n 1 n 1 n n n 1 n n 1 n
a pa qb pa q(ra sb ) pa qra s(a pa )
+ + + + + +
= + = + + = + + −

Suy ra
n 2 n 1 n
a (p s)a (qr ps)a
+ +
= + + −


n 1
n
px q
x
rx s
+
+
=
+
, trong ñó: x
0
= a cho trước và p, q, r, s
là các hằng số. Tìm số hạng tổng quát
n
x
. Giả sử y
n
và z
n
là nghiệm của hệ:

n 1 n n
n 1 n n
y py qz
z ry sz
+
+
= +



n
n 1 n n n
n
n 1
n
n 1 n n n
n
y
p q
y py qz px q
z
x
y
z ry sz rx s
r s
z
+
+
+
+
+ +
= = = =
+ +
+
ñúng. 20

3.1.3.2. Dạng 2

n 1 n 1 n n 1 n n 1
1 au bu 1 1 1
1 a. b.
u u .u u u u
−
+ − + −
+
⇒ = ⇔ = +

Đặt
n
n
1
v
u
=
ta có:
n 1 n n 1
v av bv 0
+ −
− − =
(Đây là hệ thức truy hồi tuyến tính thuần
nhất hệ số hằng).
3.1.3.3. Dạng 3
Cho dãy số (u
n
) xác ñịnh như sau:
2
n n 1 n 1
u a.u bu c

u 2au u u c 0
− −
⇔ − + − =
(3)
Thay n bởi n – 1 ta có:
2 2
n 2 n 1 n 2 n 1
u 2au u u c 0
− − − −
− + − =
(4)
Từ (3) và (4) ta có u
n
và u
n-2
là 2 nghiệm của phương trình:
2 2
n 1 n 1
t 2au .t u c 0
− −
− + − =
.
Áp dụng ñịnh lý Viet, ta có: u
n
+ u
n-2
= 2a.u
n-1
. Từ ñó suy ra u
n

n n 1
n 1
1 a b
c
u u
u
−
−
⇔ = + +
và ñặt
n
n
1
x
u
=
ta ñược:
2
n n 1 n 1
x a.x b.x c
− −
= + +
ñây là bài toán dạng 3, nên ta tìm ñược x
n
, từ ñó suy ra u
n
.
3.2. MỘT SỐ ỨNG DỤNG CỦA PHƯƠNG PHÁP SONG ÁNH
Dùng song ánh ñể thiết lập hệ thức truy hồi, dựa trên ý tưởng: Nếu tồn tại một
song ánh từ tập A ñến tập B thì số phần tử của A và B sẽ bằng nhau. Từ ñó ứng dụng


M (a ,a , ,a )
n n
f: S P

→
a
sao cho
i
i
a 1
a 0
khi i M
khi i M
= ∈


= ∉


Dễ dàng kiểm tra ñược rằng f là song ánh nên |S
n
| = |P
n
|,
n 1
∀ ≥

•
Xét ánh xạ g:

n-1
| + |P
n-2
| ,
n 3
∀ ≥
suy ra |S
n
| = |S
n-1
| + |S
n-2
| ,
n 3
∀ ≥

Vì |S
1
| = 2 ; |S
2
| = 3 nên |S
n
| = |F
n+2
|
n 1
∀ ≥
với {F
n
} là dãy Fibonacci.

   
 
   
 
.
Mà tập
n
S
∅ ⊄
nên số tập con cần tìm bằng
n 2 n 2
1 1 5 1 5
2 2
5
+ +
 
   
+ −
 
−
   
 
   
 
- 1.
Bài toán 3.17. (VMO 1996) Cho n, k, m
*
∈

thỏa mãn ñiều kiện 1 < k ≤ n, m >1.

n
A
.
A* là tập gồm các chỉnh hợp thỏa mãn giả thiết.
B =
{
}
1 2 k 1 2 k i
(a ,a , ,a ) A |a a a i) m 1, k
, (a i =
∈ < < < − ∀M

Dễ thấy A* = A\B.
•
Xét ánh xạ f:
1 2 k 1 2 k
B'
(a ,a , ,a ) (a 1 m,a 2 2m, ,a k km)
f: B →
− + − + − +a

Khi ñó f là song ánh từ B ñến B’ 22

với B’ =

C C C
− + − −
     
+ +
     
     
= =
).
Vậy |A
*
| = |A| - |B| =
k
n
A
-
k
n k
k
m
C
−
 
+
 
 
.
3.2.2. Tính tổng tổ hợp và chứng minh ñẳng thức tổ hợp
Một ứng dụng khác của phương pháp song ánh là dùng ñể tính tổng các phần tử
của một tập hợp nào ñó. Có thể xem như ý tưởng này ñã ñược ñề xuất ngay trong bài
toán quen thuộc: “Tính tổng 1 + 2 + + n”, với cách giải quyết tuyệt vời mà tương

∑
.
Lời giải: Xét ánh xạ f:

{ }
T T
X f(X) n 1 x | x X
f:

→
= + − ∈a

Dễ thấy f là song ánh nên
X T X T
m(X) m(f (X)) n 1 , X T
m(X) m(f(X))

∈ ∈
+ = + ∀ ∈



=


∑ ∑

Suy ra:
[
]

= 9 – a
i
,
i 1,2002
∀ =
23

Do N + f(N) =
{
2002
99 9
cs 9
99
M
nên f : M
→
M là song ánh. (kí hiêu: cs là “chữ số”)
Từ ñó ta có:
{ {
2002 2002
N M N M N M
1
2 N (N f(N)) | M| 99 9 N | M| 99 9
2
cs 9 cs 9
=
∈ ∈ ∈

n k
n
k k n
2
n 2n 1
n k
k 0
2 C C C , n
−
 
 
+
 
+
−
=
= ∀ ∈
∑


Lời giải: Ta chọn ra n số không lặp từ 2n+1 số, khi ñó số cách chọn bằng
n
2n 1
C
+
.
Mặt khác, ta có thể chọn chọn ra n số từ 2n + 1 số bằng cách khác như sau:
Trước hết, từ 2n+1 số, ta chia ra n cặp và còn lại một số gọi là a không thuộc n cặp
ñó. Sau ñó ta thực hiện liên tiếp hai bước chọn như sau:
Bước 1: Ta chọn ra k cặp từ n cặp ấy rồi từ mỗi cặp chọn ra một số. Trường hợp này

Vậy theo nhận xét 3.2 suy ra ñiều phải chứng minh.
3.3. MỘT SỐ ỨNG DỤNG CỦA HÀM SINH
3.3.1. Ứng dụng hàm sinh vào bài toán tìm dãy số
3.3.1.1. Phương pháp
•
Để tìm dãy số {a
n
}. Ta xét hàm sinh sinh bởi dãy {a
n
} là F(x) =
n
n
n 0
a x
≥
∑
.
•
Dựa vào ñặc ñiểm của dãy {a
n
} và hệ thức truy hồi ta tìm hàm F(x).
•
Khai triển F(x) theo lũy thừa x (Khai triển Taylor), ta tìm ñược a
n
với mọi n.

24

n+2
+
Áp dụng tính chất của hàm sinh: Nếu {a
n
}
↔
F(x) thì
{a
n+h
}
↔

2 3 h 1
0 1 2 3 h 1
h
F(x) a a x a x a x a x
,
x
h
−
−
− − − − − −
∈


Ta suy ra: {F
n+2
}
↔


x
−
=
F(x)
x
+ F(x) hay
n n
n
2
n 0
x 1 1 1 1 1 5 1 5
F(x) ( ) x
2 2
1 x x 5 1 5 1 5 5
1 x 1 x
2 2
∞
=
 
   
+ −
 
= = + = −
   
 
− − + −
   
 
− −
∑

n-1
+ n với p
1
= 2, p
0
= 1 và ñã tìm ñược công thức tường minh cho p
n

bằng 2 cách. Bây giờ ta ñi tìm công thức hiện của p
n
dưới cách nhìn từ hàm sinh.
Lời giải:
Hàm sinh cho dãy p
1
, p
2
, là p(x) =
i
i
i 0
p x
∞
=
∑
=
2
0 1 2
p p x p x
+ + +
(1)

n-1
= n, do vậy ta thay vào (3) ta có
(1 - x).p(x) = 1 + x + 2x
2
+ 3x
3
+ = 1 + x(1 + 2x + 3x
2
+ ) = 1 + x.
2
1
(1 x)
−
25

Suy ra: p(x) =
3
1 1
x.
1 x
(1 x)
+
−
−
, khai triển lũy thừa vế phải ta ñược:
p(x) =
n 2 m n 2 m 1

+
=
2
n(n 1) n n 2
1
2 2

+ + +
+ =

3.3.2. Tính tổng tổ hợp và chứng minh ñẳng thức tổ hợp
3.3.2.1. Phương pháp: Để tính tổng
m
m
S(n) h (n)
=
∑
ta xét hàm sinh:
n n
m
n n m
F(x) = S(n).x = ( h (n)).x
∑ ∑ ∑
(*)
Sau ñó sử dụng phương pháp ñổi tổng ñể tính vế phải của (*) rồi ñồng nhất
thức hai vế ta thu ñược S(n).
3.3.2.2. Bài tập ứng dụng
Bài toán 3.32. Tính tổng sau:
n
k k m

− = −
∑ ∑ ∑ ∑

=
k k k n n k k k n n n n
n n
k n k n
( 1) C .(1 x) ( 1) ( 1) C .(1 x) ( 1) ( 1 1 x) ( 1) x
−
≤ ≤
− + = − − + = − − + + = −
∑ ∑

Đồng nhất thức ta có:
n
(-1) khi m = n
S(m)
0 khi m < n


=




Bài toán 3.34. Hãy tính tổng sau: f(n) =
n
2k n k
n k
k 0

2 .(2x) .(2x) C (2x)
− − − −
+ + − −
= − ≥
=
∑ ∑
=
n
k k
2k 1
k 0
1
2 .(2x) .
(1 2x)
−
+
=
−
∑