Lương Ngọc Huyên

THPT Chuyên Tuyên Quang

TRẠI HÈ HÙNG VƯƠNG LẦN THỨ XI
TRƯỜNG THPT CHUYÊN TUYÊN QUANG

CHUYÊN ĐỀ
MÔN: TOÁN

HÀM SINH
MỞ ĐẦU
Trong các kì thi chọn học sinh giỏi toán ngày nay, bài toán tổ hợp luôn gây ra
không ít khó khăn cho cả giáo viên và học sinh. Nhiều bài toán tổ hợp được phát biểu
dưới hình thức một bài toán đếm, đây cũng là dạng bài hay gặp nhất trong các kì thi chọn
học sinh giỏi thời gian gần đây. Có nhiều cách tiếp cận lời giải của một bài toán đếm
như: Sử dụng lực lượng tập hợp, sử dụng song ánh, sử dụng hệ thức truy hồi, sử dụng
hàm sinh,... Mỗi bài toán đếm có thể được giải với nhiều cách thức tiếp cận, mỗi cách
tiếp cận đó sẽ đem đến những sự thú vị và nét đẹp riêng của nó.
Hàm sinh là một trong những sáng tạo bất ngờ, nhiều ứng dụng của toán rời rạc.
Nói một cách đơn giản, hàm sinh chuyển những bài toán dãy số thành những bài toán về
hàm số. Điều này cho phép chúng ta sử dụng hàm sinh trong việc giải các dạng toán về
phép đếm bởi đa số các bài toán đếm là đi xác định một hàm số đếm f : ¥ → ¥ . Có cả
một ngành toán học lớn nghiên cứu về hàm sinh, tuy nhiên, trong khuôn khổ của chuyên
đề này, chúng ta chỉ tìm hiểu những ứng dụng của hàm sinh trong một số bài toán đếm.
Trong kì thi chọn học sinh giỏi quốc gia năm 2015, Bài toán số 3 là một bài toán
đếm mà đa số các thí sinh tiếp cận theo hai hướng: Sử dụng hệ thức truy hồi và sử dụng
hàm sinh. Số các thí sinh sử dụng hàm sinh không nhiều và có khá nhiều lỗi do chưa hiểu
chính xác về hàm sinh cùng các kĩ thuật sử dụng. Tuy nhiên, sử dụng hàm sinh là một
trong những lời giải đẹp nhất cho bài toán này.
Từ những lí do trên, một chuyên đề hệ thống những kiến thức cơ bản về hàm sinh

là rất cần thiết cho việc dạy và học các bài toán đếm. Mục đích chính của chuyên đề này
là cung cấp những kiến thức căn bản nhất về hàm sinh cùng các ví dụ minh họa trong một
số bài toán đếm. Qua đó, chúng tôi cũng mong muốn các thầy cô và các em tiếp tục phát
triển để chúng ta có một chuyên đề hoàn chỉnh và hữu ích hơn.
Nội dung của chuyên đề được chia thành hai chương. Chương 1 trình bày những
vấn đề cơ bản về hàm sinh. Chương 2 trình bày ứng dụng của hàm sinh trong một số bài
toán đếm. Chương 2 được chia thành hai phần chính: Hàm sinh là các đa thức và hàm
sinh là các hàm giải tích khai triển được thành chuỗi lũy thừa. Sở dĩ có sự phân chia này
là bởi khi chúng ta sử dụng chuỗi lũy thừa sẽ cần một số kiến thức của toán cao cấp. Điều
này thích hợp cho các em học sinh muốn khám phá thêm về hàm sinh nhưng sẽ phải rất
thận trọng khi vận dụng trong các kì thi vì những kiến thức vượt chương trình đó. Cũng
cần nói thêm rằng, chuyên đề là sự sưu tầm, sắp xếp những vấn đề cơ bản của hàm sinh
theo một mạch kiến thức nhất định từ một số nguồn tài liệu đã có cùng với một số kiến
thức, bài toán mà chúng tôi đưa thêm vào nhằm làm sáng tỏ cho những vấn đề nêu ra.

Chương 1. Hàm sinh
Trong chương này ta sẽ trình bày những kiến thức căn bản về hàm sinh bao gồm:
Định nghĩa hàm sinh, các phép toán của hàm sinh và một số ví dụ về hàm sinh.
1.1. Định nghĩa
n
Cho dãy (vô hạn) { an } . Tổng hình thức F ( x ) = ∑ an x gọi là hàm sinh sinh bởi dãy

{ an } .

n≥ 0

1


Lương Ngọc Huyên


Hai

hàm

sinh

ai = bi , ∀i = 0,1,...

THPT Chuyên Tuyên Quang

F ( x) = ∑ an x n ,
n≥ 0

G ( x) = ∑ bn x n

gọi

n ≥0

là

bằng

nhau

nếu

Ví dụ 1
1) Dãy {0,0,...,0,...} có hàm sinh tương ứng là F ( x) = 0 + 0.x + 0.x 2 + ... = 0 .

2) Dãy {1,0,...,0,...} có hàm sinh tương ứng là F ( x) = 1 + 0.x + 0.x 2 + ... = 1 .
3) Dãy {a0 , a1 ,..., an ,0,0,...} có hàm sinh tương ứng là
F ( x) = a0 + a1.x + a2 .x 2 + ... + an x n + 0.x n +1 + 0.x n + 2 + ... = a0 + a1.x + a2 .x 2 + ... + an x n .
Nhận xét
n
+ Ta gọi hàm sinh F ( x) = ∑ an x là chuỗi hình thức bởi vì thông thường ta sẽ chỉ
n≥ 0

coi x là một ký hiệu thay vì một số. Chỉ trong một vài trường hợp ta sẽ cho x nhận các
n
giá trị thực, vì thế ta gần như cũng không để ý đến sự hội tụ của các chuỗi ∑ an x .
n ≥0

2

+ Từ Ví dụ 1 ta thấy đa thức P( x) = a0 + a1.x + a2 .x + ... + an x

n

là một hàm sinh

được xác định bởi F ( x) = a0 + a1.x + a2 .x 2 + ... + an x n + 0.x n +1 + 0.x n+ 2 + ... Trong nhiều ví
dụ sau này ta sẽ xét các hàm sinh có dạng đa thức như trên.
Ví dụ 2. Với | x |< 1 , ta có công thức tính tổng của các số nhân lùi vô hạn là
1
1 + x + x 2 + x3 + ... =
.
1− x
Công thức này cho chúng ta công thức tường minh cho hàm sinh của một số dãy số
sau:

1
1) Dãy {1,1,...,1,...} có hàm sinh tương ứng là F ( x) = 1 + x + x 2 + x3 + ... =
.
1− x
1
2) Dãy {1, −1,1, −1,...} có hàm sinh tương ứng là F ( x) = 1 − x + x 2 − x3 + ... =
;
1+ x
1
3) Dãy {1, a, a 2 , a 3 ,...} có hàm sinh tương ứng là F ( x) = 1 + ax + a 2 x 2 + ... =
;
1 − ax
1
2
4
6
4) Dãy {1,0,1,0,...} có hàm sinh tương ứng là F ( x) = 1 + x + x + x + ... =
;
1 − x2
...
1.2. Tính chất
1.2.1. Tính duy nhất của hàm sinh: Mỗi dãy số { an } cho ta duy nhất một hàm sinh và
ngược lại.
1.2.2. Vành các chuỗi lũy thừa hình thức (một biến): Tập các chuỗi lũy thừa hình
thức với hệ số thực, kí hiệu là ¡ [[x]] , lập thành một vành giao hoán với phép toán cộng
“+” và nhân “.” được định nghĩa tương tự như đa thức
∑ an xn + ∑ bn xn = ∑ (an + bn ) x n và  ∑ an x n ÷. ∑ bn x n ÷ = ∑ cn x n ,
n≥ 0
n≥0
n≥0

 n ≥0
  n≥ 0
 n≥ 0
trong đó cn = a0bn + a1bn −1 + ... + an −1b1 + anb0 , ∀n ≥ 0
2


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang

1.2.3. Một số lớp hàm sinh quan trọng: Trong ¡ [[x]] có hai lớp hàm quan trọng sau
mà ta sẽ nghiên cứu khi áp dụng hàm sinh vào các bài toán đếm:
+ Lớp các đa thức ¡ [x] , đây là một vành con của vành ¡ [[x]] .
+ Trong ¡ [[x]] , có những chuỗi trùng với một hàm giải tích nào đó (chẳng hạn như
1
x x 2 x3
,1+ +
+ + ... = e x ). Tập các chuỗi như vậy lập thành một
1− x
1! 2! 3!
¡
[[
x
]]
vành con của
. Các phép toán đại số là hoàn toàn tương thích với nhau, theo nghĩa
với các hàm giải tích như thế nào thì với các chuỗi cũng như vậy.
1.2.4. Các phép toán trên hàm sinh
Các phép toán trên hàm sinh dưới đây có thể kiểm tra tính đúng đắn của nó một cách

đơn giản với các hàm sinh đa thức. Trong trường hợp tổng quát, người ta chứng minh
được rằng những phép toán đó là hoàn toàn hợp lí.
a) Phép nhân với hằng số: Giả sử F ( x) là hàm sinh của dãy { an } . Khi đó c.F ( x) là
1 + x + x 2 + x3 + ... =

hàm sinh của dãy { c.an } .

Ví dụ 3. Dãy {1,1,...,1,...} có hàm sinh tương ứng là F ( x) = 1 + x + x 2 + x3 + ... =

1
1− x

2
là hàm sinh tương ứng của dãy {2, 2,..., 2,...} .
1− x
b) Phép cộng các hàm sinh: Giả sử F ( x) và G ( x) lần lượt là hàm sinh của dãy { an }

. Khi đó, hàm 2 F ( x) =

và { bn } . Khi đó F ( x) + G ( x) là hàm sinh của dãy { an + bn } .

Ví dụ 4. Xét dãy {1,1,1,...} và {1, −1,1, −1,...} có các hàm sinh tương ứng là
1
1
2
1
1
+
=
F ( x) =

và G ( x) =
. Khi đó
là hàm sinh của dãy
1 − x 1 + x 1 − x2
1− x
1+ x
{2,0, 2,0,...} .
c) Phép dịch chuyển sang phải: Giả sử F ( x) là hàm sinh của dãy { an } . Khi đó
{0,0,...,0, a , a ,...}
.
x k .F ( x) là hàm sinh của dãy 14 2 43 0 1
k

Ví dụ 5. Dãy {1,1,...,1,...} có hàm sinh tương ứng là F ( x) = 1 + x + x 2 + x3 + ... =

1
1− x

{0,0,...,0,1,1,...}
xk
1
4
2
4
3
. Khi đó dãy
có hàm sinh là
.
k
1− x

d) Phép nhân các hàm sinh:
Giả sử F ( x) và G ( x) lần lượt là hàm sinh của dãy { an } và { bn } . Khi đó F ( x).G ( x)
là hàm sinh của dãy { cn } với cn = a0bn + a1bn −1 + ... + an −1b1 + anb0 , ∀n ≥ 0 .
Ví dụ 6. Xét dãy {1, −1,0,0,...} và {1,1,1,...} lần lượt có các hàm sinh là F ( x) = 1 − x
1
và G ( x) =
. Khi đó tích F ( x).G ( x) = 1 là hàm sinh của dãy {1,0,0,...} .
1− x
e) Phép lấy đạo hàm: Giả sử F ( x) là hàm sinh của dãy { an } . Khi đó F '( x ) là hàm
sinh của dãy {a1 , 2a2 ,3a3 ,...} .

3


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang

Ví dụ 6. Xét hàm sinh F ( x) =

1
1
của dãy {1,1,1,...} . Khi đó F '( x) =
là
(1 − x) 2
1− x

hàm sinh của dãy {1, 2,3,...} .
1.3. Các hàm sinh thường gặp
1.3.1. Định lý Taylor. Giả sử f ( x) là một hàm số liên tục, có đạo hàm mọi cấp trên

khoảng (a; b) và x0 ∈ (a; b) . Khi đó ta có công thức khai triển Taylor
f ( x) = ∑

n ≥0

Đặc biệt, khi 0 ∈ (a, b) ta có f ( x) = ∑

n≥ 0

1.3.2. Bảng các hàm sinh thường gặp
Hàm số
a0 + a1 x + ... + an x
1
1− x
1
1+ x
1
1 − ax
(1 + x) n
1
1 − xr
1
1 + xr
ln(1 + x)
e

x

n


f ( n ) ( x0 ) n
x .
n!
f ( n ) (0) n
x .
n!
Khai triển luỹ thừa

a0 + a1 x + ... + an x n + 0.x n +1 + 0.x n +2 + ...
1 + x + x 2 + x3 + ...
1 − x + x 2 − x 3 + ...
1 + ax + a 2 x 2 + a 3 x 3 + ...
1 + Cn1 x + Cn2 x 2 + ... + Cnn x n
1 + x r + x 2 r + x 3r + ...
1 − x r + x 2 r − x3r + ...
x x3 x 4
x − + − + ...
2 3
4
1+

x x 2 x3
+
+ + ...
1! 2! 3!

4


Lương Ngọc Huyên


THPT Chuyên Tuyên Quang

Chương 2. Ứng dụng của hàm sinh trong một số bài toán đếm
2.1. Ứng dụng của hàm sinh đa thức trong một số bài toán đếm
Trong phần này ta thường sử dụng bổ đề sau đây:
Bổ đề. Cho p > 2 là một số nguyên tố. Khi đó, nếu α là một nghiệm phức khác 1
của đa thức x p − 1 thì α, α 2 ,..., α p −1 , α p = 1 cũng nghiệm x p − 1 .
Chứng minh. Vì α p = 1, α ≠ 1 nên 1 + α + α 2 + ... + α p−1 = 0 . Xét một số nguyên
dương bất kì n . Khi đó tồn tại cặp q, r ∈ ¥ với r < p thỏa mãn n = p.q + r . Suy ra
α n = α p.q + r = (α p )q .α r = α r (1).
Với mọi j ∈ {1, 2,..., p − 1} thì {j , 2 j ,..., pj} là các hệ thặng dư thu gọn theo môđun p .
Theo tính chất (1) thì {α j , α 2 j ,..., α pj }={α, α 2 ,..., α p = 1} , do đó
1 + α j + α 2 j + ... + α ( p −1) j = α j + α 2 j + ... + α ( p −1) j + α pj = α + α 2 + ... + α p = 0 .
Suy ra α, α 2 ,..., α p −1, α p = 1 là các nghiệm của x p − 1 .
Dạng toán đếm đầu tiên chúng ta xét là đếm số các tổ hợp lặp của một tập cho trước
thỏa mãn điều kiện nào đó.
Bài toán 1 (PTNK 2009). Từ các chữ số 3, 4, 5, 6 có thể lập được bao nhiêu số tự
nhiên có n chữ số và các số này chia hết cho 3.
Lời giải. Gọi cn là số lượng các số tự nhiên có n chữ số lập từ các chữ số 3, 4, 5, 6
và các số này chia hết hết cho 3.
Xét các số a = a1a2 ...an với ai ∈ {3, 4,5,6} . Khi đó a M3 ⇔ a1 + a2 + ... + an M3 . Giả sử
trong các chữ số a1 , a2 ,..., an có k1 chữ số 3, k2 chữ số 4, k3 chữ số 5, k4 chữ số 6. Suy
k1 + k2 + k3 + k4 = n
(*) . Do đó mỗi bộ (k1 , k2 , k3 , k4 ) thỏa mãn (*) tương ướng
ra 
3
k
+
4

k
+
5
k
+
6
k
M
3
1
2
3
4


(

với một lũy thừa x3k1 +4 k2 +5k3 +6 k4 trong khai triển đa thức P( x) = x3 + x 4 + x5 + x 6

)

n

. Suy

ra số các bộ (k1 , k2 , k3 , k4 ) thỏa mãn (*) bằng hệ số của x3k1 +4 k2 +5k3 +6 k4 trong khai triển đa

(

thức P( x) = x3 + x 4 + x5 + x 6


)

n

, hay cn bằng tổng các hệ số của các x k , với k M3 , trong

P( x) .
Để tính cn ta gọi α là một nghiệm của phương trình α 2 + α + 1 = 0 . Khi đó α3 = 1 và
if k ≡ 0 (mod 3)
3

α 2 k + α k + 1 = α 2 + α + 1 = 0 if k ≡ 1 (mod 3) .

2
α + α + 1 = 0 if k ≡ 2 (mod 3)
Như vậy
6n

(

)

2n

P(1) + P (α) + P (α 2 ) = ∑ ak 1 + α + α 2 = 3∑ a3k = 3cn ⇒ cn =
k =0

2n


k =0

Vì P(1) = 4 , P(α) = P(α ) = 1 nên cn = ∑ a3k
n

2

k =0

P(1) + P(α) + P(α 2 )
.
3

4n + 2
=
.
3

5


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang

Nhận xét. Điều mấu chốt trong bài toán trên là cho tương ứng giữa số lượng các số
cần đếm với tổng hệ số của các x k (với k M3 ) trong khai triển P( x) . Đây là một kĩ thuật
hay được sử dụng trong các bài toán đếm dạng này.
Bài toán 2 (VMO 2015). Cho k ∈ ¥ * . Có bao nhiêu số tự nhiên n không vượt quá
k thỏa mãn đồng thời các điều kiện sau:

10
i) n chia hết cho 3.
ii) Tất cả các chữ số trong biểu diễn thập phân của n đều thuộc tập hợp
A = { 2,0,1,5} .
Lời giải. Vì 10k không chia hết cho 3 nên ta chỉ cần xét các số n thỏa mãn
0 < n < 10k . Bổ sung chữ số 0 vào trước nếu cần thiết, ta đưa về xét các số có dạng
n = a1a2 ...ak với ai ∈ { 2,0,1,5} . Ta cần đếm các số như vậy và chia hết cho 3.
Gọi ck là số lượng các số cần đếm. Tương tự Bài toán 1 ta xét đa thức

(

P( x) = x 2 + 1 + x + x5

)

k

.

P (1) + P(α) + P(α 2 ) 4k + α 2k + α 4 k
Khi đó ck =
, với α 2 + α + 1 = 0 .
=
3
3
Từ α 2 + α + 1 = 0 ta tính được: S =

4k − 1
4k + 2
nếu k không chia hết cho 3 và S =

nếu
3
3

k chia hết cho 3.
Lời bình. Sự có mặt của chữ số 0 trong tập các chữ số cho trước đã gây ra rất nhiều
khó khăn cho học sinh trong kì thi VMO 2015. Đã có rất nhiều lời giải sai vì thiếu sự
nhạy bén trong việc giải quyết khó khăn trên. Một trong những hướng giải quyết khó
khăn này là bổ sung các chữ số 0 vào trước nếu cần thiết để đưa tất cả các số cần đếm về
các số có k chữ số như lời giải trên. Có rất ít thí sinh làm được điều này, còn lại đều rơi
vào sai lầm khi đếm số các số có đúng m chữ số, 1 ≤ m ≤ k , bằng cả hàm sinh và truy
hồi.
Trong hai bài toán trên chúng ta xét các tổ hợp lặp của một tập thỏa mãn tính chất
nào đó. Khi ta làm việc với các tập con của một tập, tức là các tổ hợp không lặp của nó,
ta cần một đa thức dạng khác để áp dụng.
Bài toán 3. Cho tập hợp A = { 1, 2,3,..., 2009} . Tìm số các tập con của A mà tổng các
phần tử trong mỗi tập con đó chia hết cho 7.
Lời giải. Xét một tập con X = {a1 , a2 ,..., ak } ⊂ A thỏa mãn a1 + a2 + ... + ak M7 . Vì
các ai là đôi một phân biệt nên mỗi tập con X như trên tương ứng với một lũy thừa
2
2009
). Do vậy, số các tập con của
x a1 + a2 +...+ ak trong khai triển F ( x) = (1 + x)(1 + x )...(1 + x
A thỏa mãn bài toán (kí hiệu là S ( A) ) bằng tổng hệ số của x n , với n M7 trong khai triển
F ( x) = (1 + x)(1 + x 2 )...(1 + x 2009 ).
1
F (1) + F (α) + L + F (α 6 )  , với α là một nghiệm

7
7

phức khác 1 của phương trình x − 1 = 0 .
Tương tự trên ta tính được , S ( A) =

Ta thấy F (1) = 22009 . Mặt khác, vì 7 là số nguyên tố nên
{j , 2 j ,...,7 j}, {8 j,9 j,...,14 j}, {2003j, 2004 j,..., 2009 j}

6


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang

lập thành các hệ thặng dư thu gọn theo môđun 7. Bởi vậy
F (α j ) = (1 + α j )(1 + α 2 j )K (1 + α 2009 j )
= (1 + α j )K (1 + α 7 j )  . (1 + α8 j )K (1 + α14 j )  ... (1 + α 2003 j )K (1 + α 2009 j ) 
= (1 + α)(1 + α 2 )K (1 + α 7 ) 

287

= (1 + 1) 287 = 2 287.

22009 + 6.2287
.
7
Bài toán 4 (IMO 1995). Cho tập hợp A = {1, 2,..., 2 p} với p là một số nguyên tố.
Tìm số các tập con của A thỏa mãn:
i) Mỗi tập có đúng p phần tử.
ii) Tổng các phần tử của tập con đó chia hết cho p .
Lời giải. Để giải bài toán bằng phương pháp hàm sinh ta cần sử dụng 2 biến x và y ,

trong đó lũy thừa của biến x để tính tổng của các phần tử của tập con, lũy thừa của biến
y để tính số phần tử của tập con đó. Giả sử khi đã có một tập con của B , khi thêm một
phần tử m vào tập con đó thì tổng các phần tử sẽ tăng lên m đơn vị và số lượng phần tử
của tập sẽ tăng lên một đơn vị. Nhưng ta phải giữ lại những tập con không chứa m trước
khi thêm m vào, do đó trong hàm sinh sẽ chứa các nhân tử có dạng 1 + x m y .
Vậy P =

Xét hàm sinh F ( x, y ) = (1 + xy )(1 + x 2 y )...(1 + x 2 p y ). Khai triển F ( x, y ) dưới dạng tổng
n k
thành F ( x, y ) = ∑ a( n,k ) x y .
k ,n

Khi khai triển F ( x, y ) thành tổng thì các số mũ của x có dạng x1 + x2 + L + xk với
x1, x2 ,K , xk là các số đôi một phân biệt của tập A , số mũ tương ứng của y là k , như vậy
f n,k chính là số tập con của A có k phần tử mà tổng các phần tử là n . Như vậy số các
S = ∑ a( kp , p ) = ∑ a( n, p ) .
tập con cần đếm của A là
k ≥0

nMp

Gọi α là một nghiệm phức khác 1 của đa thức x p − 1 . Khi đó, tương tự các bài toán trên
1 p −1
k
a
y
=
F (α j , y ).
ta tính được ∑ ( n,k )
∑

p j =0
k ≥0,nMp
Ta có
F (1, y ) = (1 + y ) 2 p ;
F (α j , y ) = (1 + α j y )(1 + α 2 j y )...(1 + α 2 jp y ); ∀j ≥ 1.
Vì p là số nguyên tố nên {j , 2 j ,..., pj}, {( p + 1) j ,( p + 2) j ,..., 2 pj} là các hệ thặng dư thu
gọn môđun p , do đó
F (α j , y ) = (1 + α j y )(1 + α 2 j y )...(1 + α 2 jp y ) = [(1 + αy )(1 + α 2 y )…(1 + α p y )]2 ; ∀j ≥ 1.
Mặt khác, ta thấy đa thức y p + 1 = 0 có các nghiệm là −ε −1, −ε −2 ,K , −ε − p do đó

7


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang

(1 + αy )(1 + α 2 y )K (1 + α p y ) = 1 + y p ⇒

∑

k ≥0, nMp

⇒

∑ a(n, p ) =

C2pp + 2( p − 1)
p


nMp

Vậy S =

a( n,k ) y k =

1
(1 + y ) 2 p + ( p − 1)(1 + y p ) 2 

p

.

C2pp + 2( p − 1)

.
p
Ta có thể mở rộng Bài toán 4 thành bài toán sau:
Bài toán 5. Cho tập hợp A = {1, 2,..., m} và p là số nguyên tố. Tìm số các tập con
của A thỏa mãn:
i) Mỗi tập có đúng p phần tử.
ii) Tổng các phần tử của tập con đó chia hết cho p .
Lời giải. Tương tự như Bài toán 4, xét hàm sinh
F ( x, y ) = (1 + xy )(1 + x 2 y )...(1 + x m y ) = ∑ a( n,k ) x n y k .
k ,n

Ta cần phải tính tổng

S = ∑ a( kp , p ) = ∑ a( n, p ) .
k ≥0


nMp

Gọi α là một nghiệm phức khác 1 của đa thức x p − 1 . Khi đó

∑

k ≥0,nMp

a( n ,k ) y k =

1 p −1
F (α j , y ).
∑
p j =0

Ta có
F (1, y ) = (1 + y ) m ;
F (α j , y ) = (1 + α j y )(1 + α 2 j y )...(1 + α jm y ); ∀j ≥ 1.
Ta viết m = p.q + r với 0 ≤ r < p − 1 . Vì p là số nguyên tố nên các hệ {j , 2 j ,3 j ,..., pj} ,
{( p + 1) j ,..., 2 pj} ,..., {( p(q − 1) + 1) j ,..., pqj} là các hệ thặng dư thu gọn theo môđun p ,
do đó
F (α j , y ) = (1 + α j y )(1 + α 2 j y )...(1 + α mj y )
p

= (1 + αy )(1 + α 2 y ) …(1 + α p y )  (1 + α j y )(1 + α 2 j y ) …(1 + α rj y )  ; ∀j ≥ 1
= (1 + y p ) q (1 + α j y )(1 + α 2 j y ) …(1 + α rj y ).
Suy ra
p −1
1 p −1

1
1
j
p q
∑ a(n,k ) y = p ∑ F (α , y) = p (1 + y ) ∑ (1 + α j y)(1 + α 2 j y)…(1 + α rj y) + p (1 + y)n .
k ≥0,nMp
j =0
j =0
k

Đồng nhất hệ số của y p ta được
S = ∑ a( kp , p ) = ∑ a( n , p ) =
k ≥0

nMp

( p − 1)q + C m
p
p

m
( p − 1)   + Cmp
.
 p
=
p

Ngoài hai kĩ thuật sử dụng trong 5 bài toán trên, các hàm sinh đa thức có thể được sử
dụng linh hoạt trong một số bài toán tổ hợp khác như 2 bài toán dưới đây:


8


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang

Bài toán 6 (Việt Nam TST 2008). Cho M là tập hợp của 2008 số nguyên dương
đầu tiên, mỗi số đó được tô bởi một trong 3 màu xanh, đỏ, vàng và mỗi màu thì được tô ít
nhất một số, xét 2 tập
S1 = { ( x, y, z ) ∈ M 3 | x, y, z tô cùng màu: x + y + z ≡ 0 (mod 2008) };
S 2 = { ( x, y, z ) ∈ M 3 | x, y, z tô cùng màu}.
Chứng minh rẳng: 2 | S1 | > | S2 | .
Lời giải. Gọi A, B, C là 3 tập hợp tương ứng gồm các số màu xanh, đỏ, vàng thuộc

∑ x a , G ( x ) = ∑ x b , H ( x) = ∑ x c

M . Xét các hàm sinh: F ( x) =

a∈A

I ( x) = F 3 ( x) + G 3 ( x) + H 3 ( x) =

∑x

b∈B
a1 + a2 + a3

+


ai ∈A

∑x

c∈C
b1 + b2 + b3

+

bi∈B

và

∑ x c + c + c = ∑ an x n .
1

2

3

ci ∈C

n

Khi đó an chính là số bộ ( x, y, z ) có cùng một màu và có tổng là n . Gọi α của phương
trình x 2008 − 1 = 0 . Ta thấy
S1 =

1 2007
1 2007  3 k

k
I
(
α
)
=
F (α ) + G 3 (α k ) + H 3 (α k ) .
∑
∑

2008 k =0
2008 k =0

và
6 2007
2 2007
k
k
k
S2 =
F (α )G (α ) H (α ) =
3.F (α k )G (α k ) H (α k ).
∑
∑
2008 k =0
2008 k =0
Với k ≠ 0 thì F (α k ) + G (α k ) + H (α k ) = 0 , do đó
F 3 (α k ) + G 3 (α k ) + H 3 (α k ) = 3F (α k )G (α k ) H (α k ).
Vậy ta chỉ cần chứng minh F 3 (1) + G 3 (1) + H 3 (1) > 3F (1)G (1) H (1).
Theo bất đẳng thức AM-GM thì F 3 (1) + G 3 (1) + H 3 (1) ≥ 3F (1)G (1) H (1). Dấu bằng xảy ra

khi và chỉ khi F (1) = G (1) = H (1) , suy ra 3F (1) = 2008 , điều này vô lý vì 2008 không
chia hết cho 3. Vậy F 3 (1) + G 3 (1) + H 3 (1) > 3F (1)G (1) H (1). Do đó 2 | S1 | > | S2 | .
Bài toán 7. Giả sử với mỗi số tự nhiên n ta luôn có hai dãy số dương {a1 , a2 ,K , an }
và {b1 , b2 ,K , bn } sao cho dãy tổng {a1 + a2 , a1 + a3 ,K , an−1 + an } là một hoán vị của dãy
các tổng {b1 + b2 , b1 + b3 ,…, bn−1 + bn } . Chứng minh rằng n là lũy thừa của 2.
F ( x) =

Lời giải. Xét các hàm sinh

∑ x a , G( x) = ∑ xb .
i

i

ai ∈A

bi∈B

Ta có
[F ( x)]2 =

∑ x2a

∑

x

∑ x 2b + ∑

x


i

ai ∈A

[G( x)]2 =

+

= F ( x2 ) +

ai ,a j ∈A

i

bi ∈B

ai + a j

∑

x

ai + a j

ai ,a j ∈A
bi +b j

= G( x2 ) +


bi ,b j ∈B

∑

x

bi +b j

bi ,b j ∈B

Suy ra [F ( x)]2 − [G( x)]2 = F ( x 2 ) − G ( x 2 ).
Vì F (1) = G (1) = n nên 1 là nghiệm của F ( x) − G ( x) , do đó F ( x) − G ( x) = ( x − 1) k H ( x)
với k ∈ ¥ * . Vậy

9


Lương Ngọc Huyên

F ( x) + G ( x) =

THPT Chuyên Tuyên Quang

2
F 2 ( x) − G 2 ( x) F ( x 2 ) − G ( x 2 ) ( x 2 − 1) k H ( x 2 )
k H (x )
=
=
=
(

x
+
1)
.
F ( x) − G ( x)
F ( x) − G ( x)
H ( x)
( x − 1)k H ( x)

H (12 )
= 2k ⇒ n = 2k −1.
Chọn x = 1 ta nhận được 2n = F (1) + G (1) = (1 + 1)
H (1)
2.2. Ứng dụng của hàm sinh là các hàm giải tích trong một số bài toán đếm
Trong mục này chúng ta sẽ tìm hiểu ứng dụng của các hàm số khai triển được thành
chuỗi lũy thừa (mà ta tạm gọi là các hàm giải tích). Như đã nói ở trên, tập các hàm số này
lập thành một vành con của ¡ [[x]] ; hơn nữa các phép toán trên các hàm giải tích và trên
các chuỗi lũy thừa hình thức tương ứng là hoàn toàn tương thích nhau. Chú ý rằng kĩ
thuật lấy hàm sinh trong phần này tương tự như đối với hàm sinh là đa thức nên trong các
bài toán nêu ra chúng tôi chỉ trình bày lời giải; việc rút ra các nhận xét, bình luận xin
dành cho độc giả.
Bài toán 1. Có bao nhiêu cách chia 20 cái bút cho 4 em học sinh A, B, C và D biết số
bút nhận được của A chẵn, số bút của B chia hết cho 3, C được nhiều nhất 2 cái còn D
được nhiều nhất 1 cái.
Lời giải. Hàm sinh số bút nhận được của A, B, C và D lần lượt là
1
A( x) = 1 + x 2 + x 4 + ... =
,
1 − x2
1

B( x) = 1 + x3 + x 6 + ... =
,
1 − x3
k

C ( x) = 1 + x + x 2 =

1 − x3
,
1− x

1 − x2
D( x) = 1 + x =
.
1− x
Hàm sinh cho số cách chia n cái bút là F ( x) =

2

1
1 1 − x3 1 − x 2  1 
.
.
.
=
÷.
1 − x 2 1 − x3 1 − x 1 − x  1 − x 

'
2

1
1   1 

2
3
= 1 + x + x + x + ... suy ra F ( x) = 
Từ
=
= 1 + 2 x + 3 x 2 + ...
÷
÷
1− x
1− x  1− x 

Vậy số cách chia 20 cái bút thỏa mãn điều kiện trên là 21.
Bài toán 2. Tìm số nghiệm nguyên không âm của phương trình x1 + x2 + ... + xn = m
(*) với m, n là 2 số tự nhiên cho trước.

(

)

n

Lời giải. Xét hàm sinh F ( x) = 1 + x + x 2 + ... . Mỗi số hạng trong khai triển F ( x)
thành tổng có dạng x x1 + x2 +...+ xn trong đó xi ≥ 0, ∀i. Ta thấy tổng từ trái qua phải mỗi khi
gặp lũy thừa của x bằng m thì trong biểu thức khai triển thu gọn của F ( x) hệ số của x m
tăng thêm một đơn vị. Do vậy, hệ số của x m trong khai triển của F ( x) thành tổng chính
là số nghiệm của phương trình đã cho. Ta sẽ tìm hệ số của x m .


(

2

Từ F ( x) = 1 + x + x + ...

)

n

n

 1 
suy ra F ( x) = 
÷ . Khai triển Taylor hàm F ( x) ta được
1
−
x



hệ số của x m là

10


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang


F ( m ) (0) n(n + 1)...(n + m − 1) ( n + m − 1)!
=
=
= Cnm+ m−1.
m!
m!
m !(n − 1)!
Như vậy số nghiệm nguyên không âm của (*) bằng Cnk+ k −1.
Bài toán 3. Cho số nguyên dương n. Chứng minh tằng số các cách phân tích n thành
tổng các số nguyên dương lẻ bằng số cách phân tích n thành tổng của các số nguyên
dương khác nhau.
Lời giải. Xét hàm sinh

(

)(

)(

)

F ( x) = 1 + x + x 2 + ... 1 + x3 + x 6 + ... 1 + x5 + x10 + ... ...
Số mũ của số hạng trong phân tích thành tổng của F ( x) có dạng i1 + 3i2 + 5i3 + ... có
nghĩa là tổng của các số lẻ, mỗi số lẻ có thể lặp lại. Vậy số cách phân tích n thành tổng
các số nguyên dương lẻ chính là hệ số của x n trong khai triển của F ( x).
Tương tự, xét hàm sinh

(

)(


)

G ( x) = ( 1 + x ) 1 + x 2 1 + x3 ...
Số mũ của số hạng trong phân tích thành tổng của G ( x) có dạng i1 + i2 + i3 + ... với
i1 , i2 ,... là các số nguyên dương phân biệt. Như vậy hệ số của x n trong khai triển của
G ( x) chính là số cách phân tích n thành tổng của các số nguyên dương khác nhau.
Ta sẽ chứng minh F ( x) = G ( x). Thật vậy
F ( x) =

1
1
1
1
1 − x 2k
1
k
×
×
L
=
;
G
(
x
)
=
(1
+
x

)
=
=∏
.
∏
∏
∏
3
5
2 k +1
k
2 k +1
1− x 1− x 1− x
1
−
x
1
−
x
1
−
x
k ≥0
k ≥1
k ≥1
k ≥0

Bài toán 4. Cho n ∈ ¥ và giả sử rằng phương trình
x + 2 y = n có m1 nghiệm trong ¥ 20 ;
2 x + 3 y = n − 1 có m2 nghiệm trong ¥ 20 ;

............
nx + (n + 1) y = 1 có mn nghiệm trong ¥ 20 ;
(n + 1) x + (n + 2) y = 0 có mn+1 nghiệm trong ¥ 20 .
Chứng minh rằng

∑ mk = n + 1 .
k

1
1
×
.
1 − x 1 − x2
Khai triển F1 ( x) thành tổng thì các số hạng là các lũy thừa của x với số mũ có dạng
i + 2 j . Vậy m1 chính là hệ số của x n trong khai triển F1 ( x) thành tổng. Do đó ta có
2
2
4
Lời giải. Ta xét hàm sinh F1 ( x ) = (1 + x + x L )(1 + x + x L ) =

F1 ( x ) = L + m1x n + L
Lý luận tương tự ta có
Fk ( x) = L + mk x n+1−k + L ⇒ x k −1Fk ( x) = L + mk x n + L
k
2k
k +1
2( k +1)
L )=
Với Fk ( x) = (1 + x + x L )(1 + x + x


1
1
×
, ∀k = 1,L , n + 1 .
1 − x k 1 − x k +1

11


Lương Ngọc Huyên

Suy ra

THPT Chuyên Tuyên Quang

∑ x k −1Fk ( x) = L + ∑ mk x n + L
k

Mặt khác

k

∑x

k −1

k

x k −1
1

1 
1
 1
Fk ( x) = ∑
=
−
=
.
k
k +1
2 ∑
k
k +1 ÷
) x − x k  1 − x 1 − x  x(1 − x) 2
k (1 − x )(1 − x

Hệ số của x n trong khai triển

∑ x k −1Fk ( x)

thức

1
1
−
.
2
(1 − x)
(1 − x)(1 − x n+ 2 )


Vậy

∑ mk = C−n2+1 − C−n1+1 = n + 1 .

k

là hệ số của x n+1 trong khai triển của biểu

k

Bài toán 5. Cho hữu hạn cấp số cộng, sao cho mỗi số tự nhiên khác 0 là một phần tử
của đúng một cấp số. Chứng minh rằng có hai cấp số cộng trong số các cấp số cộng trên
có cùng công sai.
Lời giải. Giả sử có m cấp số cộng {a j + nb j }, j = 1,K , m mà mỗi số tự nhiên là phần
tử của đúng một cấp số. Ta có
m

∑∑ x

a j + nb j

m

=∑

x

aj

j =1 1 − x


j =1 n≥0

bj

.

Mặt khác
m

∑∑ x

a j + nb j

j =1 n≥0

a

m
x
x j
= ∑x ⇒
=∑
(*).
x − 1 j =1 1 − xb j
k ≥1
k

Giả sử không có hai cấp số cộng nào nói trên có cùng công sai, khi đó tập { b1, b2 ,K bn } là
hữu hạn, do đó tồn tại duy nhất phần tử lớn nhất, giả sử đó là b1 . Gọi ε là một nghiệm

khác 1 của phương trình xb1 = 1 thỏa mãn εbi ≠ 1, ∀i :1 < i ≤ m . Khi đó thay ε vào
phương trình (*) ta thấy vế trái là hằng số còn vế phải bằng ∞ . Vậy điều giả sử là sai.
Bài toán 6. Tìm số các hoán vị không có điểm cố định của tập hợp {1, 2,3,..., n} .
Lời giải. Gọi số các hoán vị với đúng k điểm cố định cho trước là Dn−k suy ra tổng
số các hoán vị với đúng k điểm cố định là Cnk Dn−k . Vì tổng số hoán vị là n ! nên ta có
n ! = ∑ Cnk Dn−k ⇔ ∑
k

k

Dn−k
H
D
= 1 ⇔ ∑ n −k = 1; H n−k = n −k .
k !(n − k )!
k!
(n − k )!
k

Áp dụng tính chất nhân hai hàm sinh ta có
1
e− x
(−1) m m
k
e H ( x) =
⇔ H ( x) =
= ∑x ∑
x .
1− x
1− x k

m!
m
x

Vậy ta có
n
Dn
(−1)k
1
1 1 1
=∑
⇒ Dn = n ! − + − L + (−1) n  .
n ! k =0 k !
n !
 2! 3! 4!

1 1 1
n 1
.
Số hoán vị cần tìm là Dn = n ! − + − L + (−1)
n !
 2! 3! 4!
2.3. Bài tập vận dụng

12


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang


Bài 1. Xác định số cách chia 10 quả bong bóng giống nhau cho 4 đứa trẻ sao cho mỗi
đứa nhận được ít nhất hai quả.
Bài 2. Hỏi có bao nhiêu cách trao 25 phần thưởng giống nhau cho 4 học sinh sao cho
mỗi học sinh nhận được ít nhất 3 nhưng không quá 7 phần thưởng.
Bài 3 (Rumania – 2003). Cho tập A = {2,3,7,9} . Tìm số các số có n chữ số lập từ
A mà số đó chia hết cho 3.
Bài 4. Cho X = { 0,1, 2,..., 25} . Tìm số các tập con của X có 7 phân tử và tổng các
phần tử của nó chia hết cho 19.
Bài 5. Cho T là tập các số nguyên không âm.
a) Kí hiệu f (n, k , T ) là số các tập con sắp thứ tự của T gồm k phần tử mà có tổng là
n
n (các phần tử có thể trùng nhau). Xác định ∑ f (n, k , T ) x .
n

b) Kí hiệu g (n, k , T ) là số các tập con sắp thứ tự của T gồm k phần tử phân biệt mà
n
có tổng là n . Xác định ∑ g (n, k , T ) x .
n

Bài 6. Chứng minh rằng có duy nhất cách phân chia tập số tự nhiên thành hai tập hợp
A và B sao cho: Với mỗi số nguyên không âm n thì số cách phân tích n thành dạng
a1 + a2 với a1 ≠ a2 ≥ 1; a1 , a2 ∈ A bằng số cách phân tích n thành tổng
b1 + b2 ; b1 ≠ b2 ; b1 , b2 ∈ B .
Bài 7. Cho p là một số nguyên tố lẻ và số nguyên dương n nguyên tố cùng nhau với
p . Tìm số các bộ
x1 ,K , x p −1
gồm p − 1 số tự nhiên sao cho tổng
x1 + 2 x2 + K ( p − 1) x p −1 chia hết cho p , trong đó các số x1, x2 ,K , x p −1 đều không lớn hơn
n −1.

Bài 8. Cho hai số nguyên dương m, n trong đó n + 2 Mm . Tìm số các bộ ba số nguyên
dương ( x, y, z ) thỏa mãn điều kiện x + y + z Mm trong đó x, y, z ≤ n .

(

)

13


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang

KẾT LUẬN
Chuyên đề đã trình bày những vấn đề cơ bản nhất của hàm sinh trong mối liên hệ của
nó với các bài toán đếm. Với mỗi bài toán đưa ra, chúng tôi đã cố gắng mô tả mô hình
hàm sinh áp dụng cho bài toán đó cùng với những nhận xét, bình luận giúp người đọc
hiểu rõ hơn ý đồ của tác giả trong từng bài toán. Cụ thể, chuyên đề đã nêu được một số
nội dung chính sau:
Một là, đưa ra khái niệm hàm sinh dưới dạng các chuỗi lũy thừa hình thức và một số
tính chất hay dùng của hàm sinh khi vận dụng vào các bài toán đếm.
Hai là, trình bày hệ thống bài toán về vận dụng hàm sinh là đa thức trong những bài
toán đếm.
Ba là, trình bày một số bài toán về vận dụng hàm sinh là các hàm giải tích trong
những bài toán đếm.
Bốn là, đưa ra một số bài tập vận dụng để học sinh tự giải và tìm hiểu thêm về các
vấn đề trình bày trong chuyên đề.
Từ chuyên đề trên chúng ta có thể mở rộng, phát triển các nội dung ứng dụng khác
của hàm sinh như: Sử dụng hàm sinh để xác định số hạng tổng quát của dãy số, sử dụng

hàm sinh để chứng minh các hằng đẳng thức tổ hợp, sử dụng hàm sinh nhiều biến trong
giải các bài toán tổ hợp,... Ngoài ra, các giáo viên có thể tìm hiểu thêm về tính chất của
các chuỗi lũy thừa hình thức dựa trên lí thuyết vành, môđun và topo I -adic.
Cuối cùng, tác giả xin chân thành cảm ơn TS. Trần Nam Dũng và thầy giáo Trần
Quốc Luật, giáo viên trường THPT chuyên Hà Tĩnh, đã cung cấp cho tác giả những tư
liệu quan trọng về hàm sinh làm cơ sở cho chuyên đề này.

14


Lương Ngọc Huyên

THPT Chuyên Tuyên Quang

Tài liệu tham khảo
[1]. Nhiều tác giả, Tài liệu tập huấn phát triển chuyên môn giáo viên trường THPT
chuyên, Môn Toán – 2012, Dự án PTDG THPT.
[2]. Milan Novakovic, Generating functions. Olympiad training materials – 2012.
[3]. Srini Devadas and Eric Lehman, Generating Functions, Lectures Notes, April
2005.
[4]. Wikipedia. Các bài: Gererating Functions, Probability Generating Functions.
[5]. Một số tài liệu trên Internet khác.

15