ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
1
Hàm sinh
Kim Đình Sơn, 12A1,THPT Chuyên Vĩnh Phúc
1 Giới thiệu
Xét dãy số(
)
và hàm số
(
)
=
+
+
+ ⋯+
+ ⋯
Khi đó
(
)
−
−
)
+
(
(
)
−
)
+
(
)
= 0
Hay
(
)
=
+
)
(
1 −
)(
1−
)
=
(
1 −
)
+
(
1 −
)
= (
∞
+
, ∀≥
1.
Giải Xét
(
)
=
∑
,
∝
khi đó
(
)
=
+(
∞
(1 −)
=
1
−
1 −
−
1 −
=
−
−
∞
ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
2
Do đó
=
∞
Xét hàm sinh
(
)
=
∑
,
∝
khi đó
(
)
=
∞
−
=
∞
và
= 0 =
,
= 1 =
.
.Suy ra
=
,∀ .Ta có điều cần chứng minh.
VÍ DỤ 3.(ℎ )
Chứng minh rằng
2
−
−
2
∞
= (). Ta có pháp nhân.
Tiếp theo, giả sử hai dãy
{
}
à
{
}
có hai hàm sinh lần lượt là A(x) và B(x). Khi đó
dãy
{
+
}
có hàm sinh là
∑ (
+
,
bằng số 0 thì ta có hàm sinh co dãy 0,0,…,0,
,
,… chính
là
∑
∞
=
(), ta có phép nhân.
ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
3
Bây giờ ta xét hàm
(
)
=
(
)
∙
chính là hàm G(x). Ta gọi quy tắc này là “phép xoắn” hay quy tắc
“xoắn”(ta có hai dãy
{
}
à
{
}
ghép cặp từng số hạng như kiểu
)
=
∞
= 1 +
∞
Khi đó
(
)
−1 =
∑
∞
=
∑ ∑
√
1 −4= (1 −4)
=
−
1
2
∞
(−4)
=
1
2
∙
1
2
−1
1
2
−2…
1
2
−+ 1.
!
∞
Vậy ta có điều phải chứng minh
ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
4
VÍ DỤ 5. Chứng minh đẳng thức sau đúng với mọi số nguyên dương ,,
+
=
−
(Công thức )
VÍ DỤ 6. Cho dãy
{
}
xác định bởi
)
. Ở đây thông tin là sự xuất hiện của phần tử trong dãy.
VÍ DỤ 7
(
2003
)
Có bao nhiêu số có chữ số từ tập hợp
{
2,3,7,9
}
và chia hết cho
3?
Giải Ta có một số chia hết cho 3 nếu và chỉ nếu tổng các chữ số của nó chia hết cho 3. Như vậy
yêu cầu bài toán tương đương với việc tìm số các số có chữ số mà tổng các chữ số của nó chia
hết cho 3. Ta có mỗi chữ số của số thỏa mãn có giả trị là một trong các số 2,3,7 ℎặ 9. Do đó
hàm sinh cho mỗi chữ số sẽ là
+
+
+
. Xét hàm sinh
1
ℱ
(
)
}
mà có tổng các chữ số là .
Xác định =
/
là nghiệm nguyên thủy bậc ba của Unity ( phương trình
= 1), ta có
≠1 à 1 + +
= (
−1)/(−1) = 0. Khi đó
ℱ
(
1
)
=
+
+
+
+
+ ⋯
ℱ
(
+ ⋯
Khi đó
ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
5
ℱ
(
1
)
+ ℱ
(
)
+ ℱ
(
)
= 3
+
(
1 + +
)
+ ℱ
(
)
+ ℱ
(
)
=
1
3
((
1 + 1 + 1 + 1
)
+
(
+ 1 + + 1
)
+
(
+ 1+
+ 1
)
+ ⋯
Trong đó dãy
(
)
∈
là dãy hữu hạn hoặc vô hạn
VÍ DỤ 8. Cho các số nguyên dương phân biệt
,
,…,
,
,
,…,
, với ≥2 thỏa mãn
+
|1 ≤< ≤
)
=
+
+
+ ⋯+
Suy ra
(
)
=
∑
+ 2
∑
)
−(
) =
(
)
−
(
)
Hay
(
)
−
(
)
=
(
)
)
, (1) ≠0
Dođó
(
−1
)
(
)
(
)
+
(
)
=
(
−1
)
(
6
Với =1, ta có 2= 2
hay = 2
. Vậy là một lũy thừa của 2
Ngoài ra, việc xây dựng hàm sinh không chỉ dựa trên một biến (vì một biến chỉ cho ta một
thông tin duy nhất!). Đối với những bài toán đòi hỏi nhiều thông tin ta cần xét hàm sinh với
nhiều biến hơn. Nhưng trước khi đến với các ví dụ đo ta hãy xét bốn định lý cơ bản sau
4 Định lý
Trong ví dụ 7, ta đã thấy một phương pháp giải các bài toán dạng này có sự kết hợp với số phức
để tính (như một bài báo của thầy Đặng Hùng Thắng trên tạp chí Toán học & Tuổi trẻ: “dùng cái
ảo đếm cái thực”).
ĐỊNH LÝ 1 Xác định =
/
với là một số nguyên dương. Khi đó mọi đa thức
ℱ
(
)
=
+
+
+ ⋯
= 1 +
+ ⋯+
(
)
.Nếu chia hết
, khi đó
= 1 nên
= . Trong trường hợp khác ta có
≠1 và
=
(
)
= 0. Ta có
ℱ
(
1
)
+ ℱ
(
}
thỏa mãn
(i) có đúng phần tử và
(ii) Tổng tất cả các phần tử của chia hết cho
Giải Bài toán trên có hai thông tin cần biết: số các phần tử của tập hợp và tổng các phần tử của
tập hợp. Đến đây ta có hai hướng giải như sau
Hướng 1 Rõ ràng với mỗi ,1 ≤≤2 ta không thể góp vào nó với hàm
+
= 1 +
vì
tích
1 +
Không thể hiện được tập có đúng p phần tử. Vì thế ta phải xét hàm sinh
ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
7
(
,
)
= 2− và (ii) () = .
Vì vậy ta cần tính =
∑
,|
. Đặt =
/
là nghiệm nguyên thủy của Unity và
=
{
,
,…,
,
= 1
}
Ta sẽ tính tổng
∑ ∑
(
,
)
∈∈
theo hai cách
Đầu tiên ta có
∑
,1
)
=
(
+1
)
. Mặt khác với mọi ≢0 ta có
{
1,2,…,
}
=
{
1 ⋅,2 ⋅,…,∙
}
.
Do đó
+
=
+
−
)
…
(
−
)
=
−1, ta có
(
−
)
=
(
−1
)
(
+
)(
+
)
…
(
+
∈∈
=
[(
+ 1
)
+ (−1)
(
+ 1
)
]
∈
=
(
+ 1
)
∈
+
(
−1
)
(
+ 1
∈,,
+ 4
(
−1
)
= 2 +
2
+ 4
(
−1
)
=
2
+ 4−2
(
†
)
Bây giờ ta tính
∑ ∑
(
,
)
∈∈
theo cách khác. Để ý rằng
ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
,
∙
,
|
∈
= ∙
,
∈
,
|
= ∙
,
∙
,
|
=
∙
(
+ 2
)
(
ℎô íℎ ườ ℎợ = 0 à = 0
)
,
Trong đó
,
là số các tập con k phần tử của
{
1,2,…,2
}
với tổng các phần tử là n. Khi đó ta
cần tính =
,
+
.
+ ⋯ Để tìm dạng tổng quát cho
(
,
)
ta cần xác định mỗi tập con
gồm k phần tử và có tổng các phần tử là n. Với mỗi 1 ≤≤2 ta có m được chọn thì m cũng
sẽ thuộc vào một tập con, ngược lại m không được chọn thì m cũng không thuộc vào tập con đó
.Do đó hàm sinh cho m là
+
,
,
|
=
1
[
(
1,
)
+
(
,
)
+ ⋯+
(
,
)]
(⋆)
Ta tính
(
,
)
,
)
=
(
1 +
)(
1 +
)(
1 +
)
…
(
1 +
)
=
(
1 +
)(
1 +
)
=
(
1 +
)
Vậy
,
,
|
=
1
((
1 +
)
+
(
−1
)(
)
=
1
2
+ 2
(
−1
)
Đó là đáp số cần tính
VÍ DỤ 10 Cho là một số nguyên tố lẻ và số nguyên dương không chia hết cho . Tìm số các
bộ
,
,…,
gồm −1 số tự nhiên không lớn hơn −1 sao cho tổng
+ 2
+ ⋯+
(
−1
|
.
Trước khi đến với ví dụ 12 ta xét định lý sau
ĐỊNH LÝ 2 Đạo hàm của hàm số ℋ
(
)
=
∏
(
)
( trong đó
(
)
là các hàm khả vi với
biến ) là
ℋ
(
)
)
là sso các số 1 xuất hiện trong và () xác
định là số các số nguyên dương phân biệt xuất hiện trong (ví dụ = 13 và là phân hoạch
1 + 1 +2+ 2 + 2 + 5, khi đó () = 2 và () = 3 ).
Chứng minh rằng với mỗi cố định , ta có
(
)
à â ạ ủ
=
(
)
à â ạ ủ
Giải
Đặt
∑
(
)
à â ạ ủ
=
và
∑
(
= ℬ
(
)
, từ đó suy ra
=
,∀.
Với ≥2 hàm sinh cho là 1 +
+
+ ⋯ Với = 1, nếu 1 được chọn lần thì ứng
với ta có
, tuy nhiên để biết thêm về số lần 1 xuất hiện trong ta gán thêm biến , nếu 1
được chọn lần thì cũng xuất hiện lần trong , do đó hàm sinh cho = 1 là 1 + +
+
⋯ Xét
ℱ
(
,
)
=
,
,
lần số 1 xuất hiện trong các phân hoạch của . Do đó
=
,
+
,
+
,
+ ⋯=
,
Do đó
(
)
=
=
,
)
Mà
ℱ
(
,
)
=
1
(
1 −
)(
1 −
)(
1 −
)
…
Do đó
(
)
=
1 −
1
+⋯
)(
1 +
+
+⋯
)
…
= 1+
1 −
Trong đó
,
là số các phân hoạch của với phần tử phân biệt . Biến biểu diễn cho tổng
các phần tử trong phân hoạch và biến là số lần xuất hiện của phần tử nào đó trong phân hoạch.
Tương tự ta suy ra
ℬ
(
)
=
)
= 1 +
,⟶
(
)
=
vậy ta có
()
()
=
Suy ra
Từ
(
⋆
)
à (⋆⋆) suy ra
(
)
= ℬ
(
)
, do đó
=
,∀.
CHÚ Ý Bài toán có thể giải bằng cách sử dụng nguyên lý và ta có một lời giải khá gọn!
ĐỊNH LÝ 3 Giả sử , là các số nguyên dương , > 1. Khi đó
=
−1 ế |
+ 2
+ 4
với
,, không nhất thiết phân biệt.
Bài toán 2( 1996) Xác định ( kèm chứng minh) tập con của tập các sô nguyên với
tính chất sau: mọi số nguyên có đúng một nghiệm của phương trình + 2= với ,∈
Bài toán 3 Cho là số nguyên dương, đặt
ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
13
(
)
=
(
1 +
)
(
1 −
Bài toán 5 Chứng minh rằng
(
−1
)
2−2
−1
= 0
Bài toán 6 ( đồng nhất thức Euler). Đặt
(
)
=
(
1 −
4 = 1 + 1+2 = 1 + 2 + 1 = 2 + 1 +1 = 2 + 2 = 1 + 1 + 1 +1
( ta có
(
4
)
= 5). Gọi () là số các cách biểu diễn thành tổng các số nguyên lớn hơn 1. Ví
dụ 6 = 4 + 2 = 2 +4 = 3+ 3= 2 + 2 + 2 ta có
(
6
)
= 5. Chứng minh rằng
(
)
=
(
+2
)
.
Bài toán 9( ℎ 2007) Tìm tất cả các số nguyên dương sao cho tập S=
{1,2,…,} có thể tô màu đỏ và xanh thỏa mãn tính chất sau: tập
chứa đúng 2007 bộ có thứ tự
(,,) sao cho
(i) ,, cùng màu
(ii) ++ chia hết cho
ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
14
|
∈
}
,
=
⋃
−
⋂
, với mọi số nguyên dương . Xác định tất cả các sô
nguyên dương để
=
{
0
}
.
( đáp số : là lũy thừa của 2, đẻ chứng minh bài này trước hết ta hay giải quyết hai bổ đề sau
BỔ ĐỀ 1 Nghiệm của dãy hàm
() thỏa mãn phương trình
(
−1 −
BỔ ĐỀ 2 Số tự nhiên là lũy thừa của 2 nếu và chỉ nếu
à ộ ℎẵ,∀0< <
2
ớ
(
)
= ,ℎ = 2
.)
ℳừng xuân Canh Dần 2010 Hàm sinh ⋇franciscokison⋇
16
Tài Liệu Tham Khảo
[1] A path to Combinatirics for Undergraduates, Counting Strategies,
Andreescu,T.; Feng. Z. , Bikhauser, 2004
[2] Chuyên đề chọn lọc,Tổ hợp và toán rời rạc, NXBGD 2008
[3] Hàm sinh, Trần Nam Dũng, nguồn http://forum.mathscope.org
[4] Hàm sinh và áp dụng ( topic), Biến phức và áp dụng, Nguyễn Văn Mậu (Chủ
biên)
[5] Multivariate Generating Function and Other Tidbits, Zachary R Abel,
Mathematical Reflections, vol 2, 2006
[6] Shortlisted IMO 2007/ IMO Group, www://imomath.com
[7] Putnam and Beyond, Andreescu,T
[8] 102 Problems in Algebrafrom the Trainingof the USA IMO Team,
Andreescu,T.; Feng. Z. , Bikhauser, 2002
Copyright: Tài liệu đại học ©