ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC ---------------------------
NGUYỄN BÁ DƯƠNG
CHUỖI LŨY THỪA HÌNH THỨC
VÀ TIÊU CHUẨN BẤT KHẢ QUY
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2017
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC ---------------------------
NGUYỄN BÁ DƯƠNG
CHUỖI LŨY THỪA HÌNH THỨC
VÀ TIÊU CHUẨN BẤT KHẢ QUY
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 60 46 01 13
NGƯỜI HƯỚNG DẪN KHOA HỌC TS. TRẦN NGUYÊN AN
THÁI NGUYÊN - 2017
Mục lục
MỞ ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chương 1. Chuỗi lũy thừa hình thức . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Định nghĩa và một số tính chất cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Một số phép toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3. Phép truy toán trong C[[x]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4. Phương pháp đếm dùng hàm sinh thông thường . . . . . . . . . . . . . . 23
1.5. Phương pháp đếm bằng hàm sinh mũ . . . . . . . . . . . . . . . . . . . . . . . . . 34
Chương 2. Tính bất khả quy của chuỗi lũy thừa hình thức 40
2.1. Tính phân tích duy nhất của vành Z[[x]] . . . . . . . . . . . . . . . . . . . . . 40
2.2. Tiêu chuẩn về tính bất khả quy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
i
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
MỞ ĐẦU
Chuỗi lũy thừa hình thức là một sự mở rộng của đa thức mà số các
số hạng có thể là vô hạn. Chính vì vậy ta không thể thay biến bởi một
giá trị bất kỳ, điều mà ta có thể làm được với các đa thức. Ta cũng có thể
xem chuỗi lũy thừa hình thức là một dãy vô hạn sắp thứ tự các phần tử.
Khi đó lũy thừa của biến được dùng để chỉ thứ tự các hệ số. Trong tổ hợp,
chuỗi lũy thừa hình thức dùng để chỉ dãy số hay đa tập (Một sự tụ tập các
vật có bản chất tùy ý, trong đó có thể có những vật không phân biệt được
với nhau (và có thể coi như là sự lặp lại của cùng một vật)). Chẳng hạn
ta có thể dùng để định nghĩa đệ quy một dãy số, còn được gọi là phương
pháp hàm sinh. Phương pháp đếm dùng hàm sinh là các phương pháp đếm
hữu hiệu và đang được phát triển. Nhiều loại hàm sinh đã được định nghĩa
và được sử dụng trong các bài toán đếm khác nhau. Tuy nhiên hàm sinh
thông thường và hàm sinh mũ là hai loại hàm sinh đã được dùng rộng rãi
và hữu hiệu hơn cả. Mục đích chính thứ nhất của luận văn là tìm hiểu về
vành các chuỗi lũy thừa hình thức và ứng dụng trong bài toán đếm.
Cho R là một vành giao hoán, ta ký hiệu R[[x]] là tập các chuỗi lũy
thừa hình thức trên R. Cùng với phép cộng và phép nhân R[[x]] là một
vành giao hoán. Giống như vành đa thức R[x] thì R[[x]] là một miền nguyên
khi R là một miền nguyên. Tuy nhiên trong khi các phần tử khả nghịch
của R[x] là các phần tử khả nghịch của R thì các phần tử khả nghịch của
R[[x]] là các chuỗi lũy thừa hình thức mà số hạng tự do khả nghịch. Điều
này làm cho việc nghiên cứu tính chất số học của R[[x]] khi R là trường
"khá đơn giản", chẳng hạn các phần tử bất khả quy chỉ là x. Tuy nhiên nghiên cứu tính bất khả quy của các phần tử trong Z[[x]] đã là bài toán khó. Cho đến nay có rất ít tiêu chuẩn bất khả quy cho các phần tử trong Z[[x]]. Mục đích chính thứ hai của luận văn là tìm hiểu một số tiêu chuẩn bất khả quy của các chuỗi lũy thừa hình thức hệ số nguyên.
Tài liệu tham khảo chính cho mục đích thứ nhất là cuốn sách Ngô Đắc
1
Tân (2004), Lý thuyết tổ hợp và đồ thị, Nhà xuất bản Đại học Quốc Gia Hà
Nội và Qiaochu Yuan (2009), Topics in generating functions, Massachusetts
Institute of Technology, tài liệu cho mục đích thứ hai là bài báo của D.
Birmajer and J. B. Gil (2008), "Arithmetic in the ring of formal power
series with integer coefficients" American Mathematical Monthly, 115(6),
541-549.
Luận văn được chia làm hai chương. Chương 1 trình bày về chuỗi
lũy thừa hình thức và ứng dụng trong các bài toán đếm. Để đơn giản luận văn thống nhất tìm hiểu chuỗi lũy thừa hình thức trên C trong chương này. Chương 2 tìm hiểu một số tiêu chuẩn bất khả quy của chuỗi lũy thừa
hình thức với hệ số nguyên. Để việc tìm hiểu đó có ý nghĩa trước hết luận văn trình bày kết quả Z[[x]] là miền phân tích duy nhất. Lưu ý thêm rằng nếu R là miền phân tích duy nhất thì R[x] cũng là miền phân tích duy
nhất tuy nhiên điều tương tự đã được Samuel [6] chỉ ra là không đúng cho
R[[x]].
Trong suốt quá trình làm luận văn, tôi nhận được sự hướng dẫn và
giúp đỡ tận tình của TS. Trần Nguyên An. Tôi xin được bày tỏ lòng biết
ơn sâu sắc đến thầy.
Tôi xin gửi lời cảm ơn chân thành đến quý thầy cô giảng dạy lớp Cao
học toán khoá 9 đã truyền thụ đến cho tôi nhiều kiến thức và kinh nghiệm
nghiên cứu khoa học.
Thái Nguyên, tháng 5 năm 2017
Nguyễn Bá Dương
2
Tôi xin chân thành cảm ơn!
Chương 1
Chuỗi lũy thừa hình thức
Trong suốt chương này cho C là trường các số phức. Ta tìm hiểu chuỗi lũy thừa hình thức với hệ số phức. Chú ý rằng ta có thể định nghĩa
chuỗi lũy thừa hình thức với hệ số trên một vành giáo hoán bất kỳ.
1.1. Định nghĩa và một số tính chất cơ bản
∞ (cid:88)
∞ (cid:88)
∞ (cid:88)
Định nghĩa 1.1.1. Một chuỗi lũy thừa hình thức trên C là một biểu thức
j=0
j=0
j=0
có dạng a = a(x) = ajxj, sao cho giả sử a(x) = ajxj, b(x) = bjxj
∞ (cid:88)
∞ (cid:88)
là hai chuỗi lũy thừa hình thức thì a(x) = b(x) khi và chỉ khi aj = bj với mọi j. Tập các chuỗi lũy thừa hình thức trên C kí hiệu là C[[x]].
j=0
j=0
Giả sử a(x) = ajxj và b(x) = bjxj là hai chuỗi lũy thừa hình
∞ (cid:88)
∞ (cid:88)
∞ (cid:88)
thức bất kỳ. Ta định nghĩa phép toán cộng, phép toán nhân trong C[[x]] và phép nhân các phần tử của C[[x]] với một số z ∈ C như sau:
j=0
j=0
j=0
∞ (cid:88)
∞ (cid:88)
∞ (cid:88)
a(x) + b(x) = ajxj + bjxj = (aj + bj)xj,
j (cid:88) (
j=0
j=0
j=0
k=0
∞ (cid:88)
∞ (cid:88)
a(x)b(x) = ( ajxj)( bjxj) = akbj−k)xj,
j=0
j=0
za(x) = z( ajxj) = (zaj)xj.
3
Dễ kiểm tra thấy rằng C[[x]] lập thành một không gian véc tơ trên C đối với phép toán cộng trong C[[x]] và phép nhân các phần tử của C[[x]] với một số z ∈ C. Đối với phép nhân, C[[x]] có phần tử đơn vị là
∞ (cid:88)
j=0
1(x) = 1 + 0.xj mà ta sẽ đơn giản kí hiệu là 1. Ta cũng dễ kiểm tra
thấy rằng C[[x]] lập thành một vành giao hoán có đơn vị 1 đối với phép cộng và phép nhân trong C[[x]]. Phép toán nhân và phép nhân mỗi phần tử của C[[x]] với một số z ∈ C thỏa mãn hệ thức sau:
z[a(x)b(x)] = [za(x)]b(x) = a(x)[zb(x)].
Điều đó chứng tỏ rằng C[[x]] lập thành một đại số trên C.
j=0 đó của tập 0, 1, 2, ..., n − 1, thì số hạng aixi cũng không cần viết; còn nếu ai = 1 cho một i nào đó của tập {0, 1, 2, ..., n − 1} , thì aixi được đơn giản
n (cid:88)
Nếu với n ∈ N, chuỗi lũy thừa hình thức a(x) có an (cid:54)= 0 và aj = 0 cho mọi j > n, thì a(x) được gọi là đa thức bậc n và được đơn giản viết là n (cid:88) ajxj hay a0 + a1x + ... + anxn. Hơn thế nữa, nếu ai = 0 cho một i nào
j=0
viết là xi. Phần tử 0(x) = 0xj, mà ta đơn giản kí hiệu là 0, là phần tử
0 của C[[x]] và được định nghĩa là có bậc là −1. Ta kí hiệu Cn[x] là tập tất cả các đa thức bậc nhỏ hơn n. Khi đó Cn[x] là không gian con số chiều n. Dễ thấy rằng ϕ : C1[x] → C, a(x) → a0 là đẳng cấu đại số. Vì thế ta có thể đồng nhất a0 với a(x) ∈ C1[x] và coi C như là một đại số con của C[[x]]. Khi đó phép nhân một phần tử của C[[x]] với một số z ∈ C có thể xem như là một trường hợp riêng của phép toán nhân trong C[[x]].
∞ (cid:88)
Mệnh đề 1.1.2. Chuỗi a(x) ∈ C[[x]] là khả nghịch khi và chỉ khi a0 (cid:54)= 0 .
j=0
Chứng minh. Giả sử b(x) = bjxj. Khi đó a(x)b(x) = 1 khi và chỉ khi hệ
phương trình sau có nghiệm:
a0b0 = 1,
a0b1 + a1b0 = 0,
a0b2 + a1b1 + a2b0 = 0,
.................. ... ...........
a0nb + a1bn−1 + ... + anb0 = 0,
4
............................ ... ...........................,
ở đây b0, b1, .., bn là các ẩn số. Dễ thấy rằng hệ này có nghiệm khi và chỉ khi a0 (cid:54)= 0.
Chú ý 1.1.3. Chứng minh tương tự ta có g(x) ∈ R[[x]] với R là vành giao
hoán bất kỳ khả nghịch khi và chỉ khi a0 khả nghịch.
Nếu a(x) là phần tử khả nghịch của C[[x]] thì phần tử nghịch đảo hay a−1(x). Nếu a(x) và b(x) của nó sẽ được kí hiệu là (a(x))−1 hay 1 a(x)
là các đa thức với a0 (cid:54)= 0, thì phần tử b(x)a−1(x) cũng thường được viết là b(x) và được gọi là hàm số hữu tỷ. Với mọi a(x) ∈ C[[x]] ta định nghĩa a(x)
a0(x) = 1,
(cid:124)
(cid:123)(cid:122) n
an(x) = a(x)a(x)...a(x) (cid:125)
cho mọi số nguyên dương n. Nếu a(x) là phần tử khả nghịch và a−1(x) là
phần tử nghịch đảo của a(x), thì ta định nghĩa
(cid:124)
(cid:123)(cid:122) n
a−n(x) = a−1(x)a−1(x)...a−1(x) (cid:125)
cho mọi số nguyên dương n.
Với z ∈ C và 0 (cid:54)= n, k ∈ N, đa thức (1 − zxn)k là khả nghịch theo
Mệnh đề 1.1.2. Ta có một số tính chất sau của đa thức trên
∞ (cid:88)
Mệnh đề 1.1.4. Với mọi z ∈ C và 0 (cid:54)= n, k ∈ N, ta có
j=0
(cid:32)
(cid:33)
∞ (cid:88)
zjxnj, (1) 1 1 − zxn =
j=0
∞ (cid:88)
∞ (cid:88)
∞ (cid:88)
zjxnj. (2) 1 (1 − zxn)k = k + j − 1 j
j=0
j=0
j=0
Chứng minh. Ta có (1 − zxn)( zjxnj) = zjxnj − zj+1xn(j+1) = 1.
Vậy ta có đẳng thức (1).
Ta chứng minh đẳng thức (2) bằng quy nạp theo k. Với k = 1, đẳng
5
thức (2) chính là đẳng thức (1). Giả sử đẳng thức (2) đã được chứng minh
là đúng cho k = t ≥ 1 khi đó,
1 (1 − zxn)t+1 =
∞ (cid:88)
∞ (cid:88)
1 (1 − zxn)t . (cid:32) 1 1 − zxn (cid:33)
j=0
j=0
(cid:32)
(cid:33)
∞ (cid:88)
= zjxnj zjxnj t + j − 1 j
j (cid:88) (
j=0
i=0
(cid:32)
(cid:33)
∞ (cid:88)
= zizj−i)xnj t + i − 1 i
j (cid:88) (
j=0
i=0
= )zjxnj. t + i − 1 i
(cid:32)
(cid:33)
(cid:32)
(cid:33)
(cid:32)
(cid:33)
j (cid:88)
Áp dụng công thức tổng cho hệ số nhị thức ta có
i=0
= = t + i − 1 i (t − 1) + j + 1 j (t + 1) + j − 1 j
∞ (cid:88)
và do đó đẳng thức (2) cũng được chứng minh cho k = t + 1.
j=0
∞ (cid:88)
Hệ quả 1.1.5. (1) (1 − x)−1 = xj,
j=0 ∞ (cid:88)
(2) (1 + x)−1 = (−1)jxj,
(cid:32)
(cid:33)
j=0 ∞ (cid:88)
(3) (1 − x2)−1 = x2j,
j=0
∞ (cid:88)
(4) (1 − x)−3 = xj. j + 2 j
j=0
∞ (cid:88)
Mệnh đề 1.1.6. Giả sử a(x) = ajxj có a0 = 1. Khi đó với mọi số
j=0
nguyên dương n, chuỗi lũy thừa hình thức an(x) = c(x) = cjxj có
c0 = 1, c1 = na1, cj = naj + fn,j(a1, ..., aj−1) cho mọi j ≥ 2, ở đây fn,j là đa thức j − 1 biến.
Chứng minh. Ta chứng minh Mệnh đề 1.1.6 bằng quy nạp theo n. Với
6
n = 1, mệnh đề hiển nhiên là đúng. Giả sử mệnh đề đã được chứng minh
∞ (cid:88)
∞ (cid:88)
là đúng cho n = k. Khi đó theo giả thiết quy nạp ta có
1 + ka1x +
.
j=0
j=0
ak+1(x) = ak(x)a(x) = cjxj ajxj
∞ (cid:88)
Do đó, hệ số của x0 cho ak+1(x) bằng a0 = 1, hệ số của x1 cho ak+1(x) bằng 1.a1 + ka1a0 = (k + 1)a1, và hệ số của xj(j ≥ 2) cho ak+1(x) bằng
j=0
ciaj−i = 1.aj + ka1aj−1 + (ka2 + fk,2(a1))aj−2 + ... +
(kaj + fk,j(a1, ..., aj−1))a0
= (aj + kaj) + ka1aj−1 + (ka2 + fk,2(a1))aj−2 + ... +
(kaj−1 + fk,j−1(a1, ..., aj−2))a1 + fk,j(a1, ..., aj−1)
= (k + 1)aj + fk+1,j−1(a1, ..., aj−1),
∞ (cid:88)
ở đây fk+1,j−1(a1, ..., aj−1) = (ka1aj−1 + ... + fk,j(a1, ..., aj−1)).
j=0
∞ (cid:88)
Mệnh đề 1.1.7. Giả sử a(x) = ajxj với a0 = 1 và n là một số nguyên
j=0
dương bất kỳ. Khi đó tồn tại duy nhất một b(x) = bjxj với b0 = 1 sao
cho bn(x) = a(x). Chuỗi b(x) tồn tại duy nhất trong Mệnh đề 1.1.7 được kí hiệu là a1/n(x).
Chứng minh. Theo Mệnh đề 1.1.6, b0, b1, b2, .., bk, .. lần lượt được xác định duy nhất từ các phương trình:
b0 = 1,
nb1 = a1,
nb2 + fn,2(b1) = a2,
..................... ... .......
nbk + fn,k(b1, ..., bk−1) = ak,
∞ (cid:88)
.................... ... ............
j=0
Giả sử a(x) = ajxj với a0 = 1. Theo Mệnh đề 1.1.2, a(x) có phần tử
7
nghịch đảo là a−1(x).
∞ (cid:88)
j=0
Mệnh đề 1.1.8. Giả sử a(x) = ajxj với a0 = 1 và n là một số nguyên
dương bất kỳ. Khi đó (a−1(x))n = (an(x))−1 và do đó a−n(x) = (an(x))−1.
Chứng minh. Do C[[x]] là đại số giao hoán ta có
∞ (cid:88)
an(x)(a−1(x))n = (a(x))n(a−1(x))n = (a(x)a−1(x))n = 1n = 1.
j=0
Mệnh đề 1.1.9. Giả sử a(x) = ajxj với a0 = 1, m là một số nguyên
∞ (cid:88)
bất kỳ, còn n là một số nguyên dương. Khi đó tồn tại duy nhất một
j=0
b(x) = bjxj với b0 = 1 sao cho bn(x) = am(x).
Chuỗi b(x) tồn tại duy nhất trong Mệnh đề 1.1.9 được kí hiệu là
am/n(x).
Chứng minh. Nếu m = 0, thì theo định nghĩa a0(x) = 1 và do đó a0(x) có hệ số của x0 bằng 1 theo Mệnh đề 1.1.6. Từ chứng minh Mệnh đề 1.1.2 ta cũng thấy rằng a−1(x) có hệ số của x0 bằng 1. Nếu m là số nguyên âm, thì −m là số nguyên dương. Do đó, lại theo Mệnh đề 1.1.6, am(x) = (a−1(x))−m
cũng có hệ số của x0 bằng 1.
Như vậy, với m là số nguyên âm bất kì, am(x) có hệ số của x0 bằng 1. Vì n là một số nguyên dương, nên theo Mệnh đề 1.1.7 tồn tại duy nhất
∞ (cid:88)
một
j=0
b(x) = bjxj,
với b0 = 1 sao cho bn(x) = am(x).
∞ (cid:88)
Giả sử c1(x), c2(x), .., ck(x), ... là một dãy các phần tử của C[[x]] với
j=0 Khi đó dãy
ck(x) = cjkxj và c0k = 0, k = 1, 2, ....
1 + c1(x), 1 + c2(x), ..., 1 + ck(x), ...
8
được gọi là khả tích nếu với mọi j ≥ 0 tồn tại số nguyên dương N = N (j) sao cho với mọi n > N hệ số của xj trong (cid:81)∞ k=1(1 + ck(x)) đều bằng nhau.
∞ (cid:88)
Nếu c1(x), c2(x), .., ck(x), .., là một dãy khả tích, thì ta có thể định
k=1(1 + ck(x)) =
j=0
nghĩa tích (cid:81)∞ sjxj ∈ C[[x]], ở đây hệ số sj của xj trong
k=1(1 + ck(x)) với n > N.
tích này chính là hệ số của xj trong tích (cid:81)n
∞ (cid:88)
Dãy a1(x), a2(x), ..., ak(x), .. các phần tử
j=0
ak(x) = ajkxj, k = 1, 2, ..
trong C[[x]] được gọi là khả tổng nếu mọi số nguyên r ≥ 0 tồn tại số nguyên dương N = N (r) sao cho với mọi n > N ta có a0n = a1n = ... = arn = 0.
Nếu dãy a1(x), a2(x), ..., ak(x), ... là dãy khả tổng, thì đối với dãy này
∞ (cid:88)
∞ (cid:88)
ta có thể định nghĩa tổng
j=0
k=1
ak(x) = sjxj,
ở đây sj = aj1 + aj2 + ... + ajN .
∞ (cid:88)
∞ (cid:88)
Mệnh đề 1.1.10. (1) Giả sử a1(x), a2(x), ..., ak(x), ... là dãy khả tổng và b1(x), b2(x), ..., bk(x), ... là dãy sao cho tồn tại song ánh σ : N → N thỏa mãn bσ(k)(x) = ak(x) cho mọi k ≥ 1. Khi đó b1(x), b2(x), ..., bk(x), ... cũng
k=1
k=1
là dãy khả tổng và ak(x) = bk(x).
(2) Nếu c1(x), c2(x), .., ck(x), ... là dãy khả tổng với c0k = 0 cho mọi
∞ (cid:88)
∞ (cid:88)
k ≥ 1, thì dãy 1 + c1(x), 1 + c2(x), ..., 1 + ck(x), ... là khả tích.
j=0
j=0
C[[x]] là một phần tử bất kỳ thì a0b0(x), a1b(x), a2b2(x), ..., akbk(x), ... là dãy khả tổng.
(3) Nếu b(x) = bjxj ∈ C[[x]] với b0 = 0, còn a(x) = ajxj ∈
1.2. Một số phép toán
∞ (cid:88)
∞ (cid:88)
Định nghĩa 1.2.1. Ánh xạ
j=0
j=0
9
D : C[[x]] → C[[x]] : a(x) = ajxj (cid:55)→ D(a(x)) = b(x) = (j + 1)aj+1xj
được gọi là toán tử đạo hàm trong C[[x]]. Ta cũng định nghĩa
D0(a(x)) = a(x),
Dn(a(x)) = D(Dn−1(a(x))),
S(a(x)) = a0
cho mọi n nguyên dương.
C[[x]].
Ta chứng minh một số tính chất sau đây của toán tử đạo hàm trong
Mệnh đề 1.2.2. (1) D(a(x) + b(x)) = D(a(x)) + D(b(x)).
(2) D(a(x)b(x)) = D(a(x))b(x) + a(x)D(b(x)).
(3) D(an(x)) = nan−1(x)D(a(x)) cho mọi n nguyên dương.
(4) Nếu a(x) khả nghịch và a−1(x) là phần tử nghịch đảo của a(x), thì D(a−1(x)) = −a−2(x)D(a(x)), D(a−n(x)) = −na−n−1(x)D(a(x)) cho
mọi n nguyên dương.
(5) Với mọi số hữu tỷ s = m/n (m nguyên, n nguyên dương) và mọi
a(x) ∈ C[[x]] thỏa mãn S(a(x)) = 1 ta có
∞ (cid:88)
D(as(x)) = sas−1(x)D(a(x)).
j=0
∞ (cid:88)
(6) Với mọi n ∈ N, Dn(a(x)) = [(j + n)!/j!]aj+nxj.
j=0
. (7) Với mọi a(x) ∈ C[[x]], ta có a(x) = S(Dj(a(x))) xj j!
(cid:33)
(cid:32) ∞ (cid:88)
∞ (cid:88)
(8) Nếu a1(x), a2(x), ..., ak(x), ... là dãy khả tổng, thì
k=1
k=1
D = ak(x) D (ak(x)) .
Tính chất (7) có thể xem như phân tích MacLaurin cho a(x).
10
Chứng minh. (1) Hệ số của xj ở vế phải bằng (j + 1)(aj+1 + bj+1). Hệ số của xj ở vế trái cũng như vậy. Vì vậy ta có tính chất (1).
j (cid:88)
j (cid:88)
(2) Hệ số của xj trong vế phải bằng
l=0
k=0
(l + 1)al+1bj−l + (j − k + 1)akbj−k+1.
Trong tổng thứ nhất ở trên ta làm phép đổi chỉ số k = l + 1. Khi đó biểu
j+1 (cid:88)
j (cid:88)
j+1 (cid:88)
thức ở trên bằng
k=0
k=0
k=1
akbj−k+1. (j − k + 1)akbj−k+1 = (j + 1) kakbj−k+1 +
Giá trị này cũng chính là hệ số của xj trong vế trái và (2) được chứng
minh.
(3) Tính chất (3) được chứng mình bằng quy nạp theo n. Với n = 1
đẳng thức là hiển nhiên. Giả sử đẳng thức đã được chứng minh cho n = k.
Theo tính chất (2) ta có
D(ak+1(x)) = D(ak(x)a(x)) = D(ak(x))a(x) + ak(x)D(a(x)).
Nhưng D(ak(x)) = kak−1(x)D(a(x)) theo giả thiết quy nạp. Do đó, từ các
đẳng thức trên ta nhận được
D(ak+1(x)) = kak−1(x)D(a(x))a(x) + ak(x)D(a(x))
= kak(x)D(a(x)) + ak(x)D(a(x))
= (k + 1)a(k+1)−1(x)D(a(x)).
Tính chất (3) đã được chứng minh.
(4) Áp dụng toán tử đạo hàm vào hai vế của đẳng thức a(x)a−1(x) =
1 ta được
D(a(x)a−1(x)) = 0,
⇔ D(a(x))a−1(x) + a(x)D(a−1(x)) = 0,
⇔ a(x)D(a−1(x)) = −D(a(x))a−1(x),
⇔ D(a−1(x)) = −a−1(x)D(a(x))a−1(x) = −a−2(x)D(a(x)).
11
Đẳng thức thứ nhất của tính chất (4) được chứng minh. Áp dụng đẳng
thức này và tính chất (3), ta có
D(a−n(x)) = D((a−1(x))n) = n(a−1(x))n−1D(a−1(x))
= na−(n−1)(x)D(a−1(x))
= na−(n−1)(x)(−a−2(x)D(a(x)))
= −na−n−1(x)D(a(x))
và đẳng thức thứ hai của tính chất (4) cũng được chứng minh.
(5) Theo định nghĩa của as(x) (xem Mệnh đề 1.1.9), (as(x))n =
am(x). Do đó theo tính chất (3) và (4),
D((as(x))n) = D(am(x)) = mam−1(x)D(a(x)).
Nhưng cũng theo tính chất (3), D((as(x))n) = n(as(x))n−1D(as(x)). Suy
ra,
n(as(x))n−1D(as(x)) = mam−1(x)D(a(x)),
⇔ n(as(x))n(as(x))−1D(as(x)) = mam(x)a−1(x)D(a(x)),
⇔ nam(x)(as(x))−1D(as(x)) = mam(x)a−1(x)D(a(x)),
n −1(x) = as−1(x). Vậy D(as(x)) =
as(x)a−1(x)D(a(x)). ⇔ D(as(x)) = m n
Ta có (as(x)a−1(x))n = (as(x))n(a−1(x))n = am(x)a−n(x) = am−n(x). Suy ra as(x)a−1(x) = a(m−n)/m(x) = a m sas−1(x)D(a(x)) và tính chất (5) được chứng minh.
(6) Ta chứng minh tính chất này bằng quy nạp theo n. Với n = 0, tính chất này hiển nhiên đúng vì theo định nghĩa D0(a(x)) = a(x). Giả sử
∞ (cid:88)
tính chất (6) đã được chứng minh cho n = k. Khi đó,
j=0
∞ (cid:88)
Dk+1(a(x)) = D(Dk(a(x))) = D [(j + k)!/j!]aj+kxj
j=0 ∞ (cid:88)
= (j + 1)[(j + 1 + k)!/(j + 1)!]aj+1+kxj
j=0
= [(j + (k + 1))!/j!]aj+(k+1)xj.
12
Tính chất (6) được chứng minh.
(cid:33)
(cid:32) ∞ (cid:88)
(7) Theo tính chất (6) ta có
l=0 = [j!/0!]aj = j!aj.
S(Dj(a(x))) = S [(l + j)!/l!]al+jxl
Vì thế, hệ số của xj ở vế phải trong tính chất (7) là aj.
(8) Dễ dàng suy ra từ định nghĩa của dãy khả tổng và các tính chất
trước đây của toán tử đạo hàm D.
Mệnh đề 1.2.3. Giả sử a(x) ∈ C[[x]] và 2 ≤ n ∈ N. Khi đó tồn tại b(x) ∈ C[[x]] thỏa mãn bn(x) = a(x) khi và chỉ khi số k nhỏ nhất với ak (cid:54)= 0 là bội số nguyên của n.
Chứng minh. Giả sử tồn tại b(x) ∈ C[[x]] sao cho bn(x) = a(x). Ta cũng giả sử rằng t là số nguyên nhỏ nhất sao cho bt (cid:54)= 0. Từ bn(x) = a(x) ta suy ra rằng số nguyên k nhỏ nhất sao cho ak (cid:54)= 0 bằng nt, tức là k là bội số nguyên của n.
Ngược lại, giả sử số k nhỏ nhất với ak (cid:54)= 0 là bội số nguyên của n,
∞ (cid:88)
chẳng hạn k = nt. Khi đó
j=0
a(x) = xnt cjxj,
(cid:88)
ở đây cj = aj+nt. Ta có c0 = ant = ak (cid:54)= 0. Giả sử f0 là một giá trị của căn bậc n của c0. Vì c0 (cid:54)= 0, nên f0 (cid:54)= 0. Do đó ta có thể xác định các số f1, f1, ...., fj, ... theo công thức truy hồi sau đây:
i1 . cj − fi = fi1fi2...fin 1
nf n−1
0 (cid:88) Từ đẳng thức trên ta biểu diễn cj qua f0, f1, ... và nhận được i1 (cid:88) fi = cj − fi1fi2...fin, nf n−1
0 0 (cid:88) ⇔ cj = nf n−1 fi + fi1fi2...fin, i1 i1 13 ⇔ cj = ∞
(cid:88) ∞
(cid:88) j=0 j=0 Vì vậy, nếu f (x) = fjxj, thì f n(x) = cjxj. Đặt b(x) = xtf (x). Khi ∞
(cid:88) đó j=0 bn(x) = xntf n(x) = xnt cjxj = a(x). ∞
(cid:88) ∞
(cid:88) Định nghĩa 1.2.4. Ánh xạ j=0 j=0 D∗ : C[[x]] → C[[x]], a(x) = xj ajxj (cid:55)→ D∗(a(x)) = aj−1
j được gọi là toán tử tích phân trong C[[x]]. Ta có một số tính chất sau của toán tử tích phân (xem [1]). Mệnh đề 1.2.5. Nếu z1, z2 ∈ C, còn a(x), b(x) ∈ C[[x]] thỏa mãn S(a(x)) =
S(b(x)) = 0, thì (1) D∗(D(a(x))) = D(D∗(a(x))) = a(x); (2) D∗(z1a(x) + z2b(x)) = z1D∗(a(x)) + z2D∗(b(x)); ∞
(cid:88) (3) D∗(a(x)D(b(x))) = a(x)b(x) = D∗(D(a(x))b(x)). j=1 Định nghĩa 1.2.6. Giả sử b(x) = bjxj và a(x) = 1 + b(x). Khi đó ∞
(cid:88) logarit L(a(x)) của a(x) được xác định bằng đẳng thức k=1 bk(x). L(a(x)) = L(1 + b(x)) = (−1)k−1
k Từ Mệnh đề 1.1.10 (3) ta thấy ngay rằng L(a(x)) luôn được xác định. Ta có một số tính chất sau Mệnh đề 1.2.7. Giả sử a(x), c(x) ∈ C[[x]] thỏa mãn S(a(x)) = S(c(x)) =
1. Khi đó, (1) D(L(a(x))) = ; D(a(x))
a(x) 14 (2) L(a(x)c(x)) = L(a(x)) + L(c(x)); (3) Với mọi số hữu tỷ r, ta có L(ar(x)) = rL(a(x)); (4) Nếu L(a(x)) = L(b(x)), thì a(x) = b(x); (5) Nếu b(x) ∈ C[[x]] thỏa mãn S(b(x)) = 0, thì với mọi số hữu tỷ r (cid:33) ∞
(cid:88) ta có (cid:32)
r
j j=1 (1 + b(x))r = 1 + bj(x), (cid:1) = ∞
(cid:88) = . ở đây (cid:0)r
j (r)j
j! r(r − 1)...(r − j + 1)
j! j=1 Định nghĩa 1.2.8. Giả sử b(x) = bjxj. Khi đó mũ E(b(x)) của b(x) ∞
(cid:88) được xác định bằng đẳng thức j=1 E(b(x)) = bj(x), 1
j! ở đây b0(x) = 1. Từ Mệnh đề 1.1.10 (3) ta thấy ngay rằng E(b(x)) luôn xác định. Ta có một số tính chất sau Mệnh đề 1.2.9. Giả sử b(x), c(x) ∈ C[[x]] thỏa mãn S(b(x)) = S(c(x)) =
0. Khi đó (1) D(E(b(x))) = E(b(x))D(b(x)); (2) Nếu E(b(x)) = E(c(x)) thì b(x) = c(x); (3) L(E(b(x))) = b(x), E(L(1 + b(x))) = 1 + b(x); (4) E(b(x) + c(x)) = E(b(x))E(c(x)). 15 Định nghĩa 1.2.10. Giả sử a(x) ∈ C[[x]] với S(a(x)) = 0 tức là a(x) = ∞
(cid:88) j=1 ∞
(cid:88) ajxj. Khi đó ta định nghĩa j=0
∞
(cid:88) sin(a(x)) = [E(ia(x)) − E(−ia(x))] = , 1
2i (−1)j a2j+1(x)
(2j + 1)! j=0 cos(a(x)) = [E(ia(x)) + E(−ia(x))] = , 1
2 a2k(x)
(2k)! tan(a(x)) = (sin(a(x)))(cos(a(x)))−1, sec(a(x)) = (cos(a(x)))−1, ở đây i là đơn vị ảo, tức là i2 = −1 và a0(x) = 1. Ta có một số tính chất sau Mệnh đề 1.2.11. (1) sin2(a(x)) + cos2(a(x)) = 1; (2) sec2(a(x)) = 1 + tan2(a(x)); (3) D(sin(a(x))) = (cos(a(x))D(a(x)); (4) D(cos(a(x))) = (−sin(a(x)))D(a(x)); (5) D(tan(a(x))) = (sec2(a(x)))D(a(x)); (6) D(sec(a(x))) = (sec(a(x)))(tan(a(x)))D(a(x)). ∞
(cid:88) 1.3. Phép truy toán trong C[[x]] j=0 ∞
(cid:88) Một phép truy toán cho C[[x]] được định nghĩa như là một ánh xạ
f : N × C[[x]] → C. Để trực quan ta coi f như là một hàm của vô hạn các
biến là n, a0, a1, a2, ... với n nhận giá trị trong N, còn a0, a1, a2, ... nhận giá
trị trong C và ajxj = a(x) ∈ C[[x]]. j=0 Giả sử k ∈ N và a(x) = ajxj ∈ C[[x]]. 16 Ta nói rằng a(x) hay dãy số a0, a1, a2, ... thỏa mãn phép truy toán f với
bậc truy toán k nếu f (n, a0, a1, a2, ..., an, 0, 0, ..) = 0 với mọi n ≥ k. Khi đó, a(x) được gọi là một lời giải của phép truy toán này. Nói chung, nếu phép truy toán có lời giải với bậc truy toán k, thì lời giải đó không nhất thiết phải là duy nhất. Người ta phân các phép truy toán cho C[[x]] ra các loại chính như ở Hình 1.1: Các loại truy toán. ∞
(cid:88) Hình 1.1 j=0 Định nghĩa 1.3.1. Ta nói rằng a(x) = ajxj ∈ C[[x]] hay dãy số k
(cid:88) a0, a1, a2, ... thỏa mãn một phép truy toán tuyến tính thuần nhất bậc k nếu
tồn tại các hằng số c0, c1, ..., ck ∈ C sao cho với mọi n ≥ k ta có j=0 cjan−j = 0. k
(cid:88) Đẳng thức trong định nghĩa trên được gọi là hệ thức truy hồi. Vì biểu thức j=0
tính. Vì các số hạng trong biểu thức trên đều có dạng giống nhau nên phép cjan−j là tuyến tính đối với aj nên phép truy toán này được gọi là tuyến truy toán này được gọi là thuần nhất. Cuối cùng, từ hệ thức truy hồi trên ta thấy mỗi an với n ≥ k biểu diễn được qua k số aj trước đó. Vì thế, phép
truy toán được gọi là có bậc bằng k. 17 Ví dụ 1.3.2. Xét F (x) = F0 + F1x + F2x2 + F3x3 + ... với F0 = 0, F1 = 1
và Fn = Fn−1 + Fn−2 với mọi n ≥ 2. Khi đó F (x) thỏa mãn phép truy toán
tuyến tính thuần nhất bậc 2 với hệ thức truy hồi Fn − Fn−1 − Fn−2 = 0
cho mọi n ≥ 2. Số Fj trên được gọi là số Fibonacci thứ j . k
(cid:88) j=0 Định nghĩa 1.3.3. Ta nói rằng a(x) = ajxj ∈ C[[x]] hay dãy số k
(cid:88) a0, a1, a2, .. thỏa mãn một phép truy toán tuyến tính không thuần nhất bậc
k nếu tồn tại các hằng số c0, c1, ..., ck ∈ C và hàm g : N → C sao cho với
mọi n (cid:54)= k ta có j=0 cjan−j + g(n) = 0. Đẳng thức trong định nghĩa trên cũng được gọi là hệ thức truy hồi ∞
(cid:88) j
(cid:88) cho phép truy toán tuyến tính không thuần nhất. j=0 k=0 k2 cho mọi j ∈ N. Khi Ví dụ 1.3.4. Xét a(x) = ajxj, ở đây aj = đó a(x) thỏa mãn phép truy toán tuyến tính không thuần nhất bậc 1 với
hệ thức truy hồi an − an−1 − n2 = 0 cho mọi n ≥ 1(k = 1, c0 = 1, c1 =
−1, g(n) = −n2). Định nghĩa 1.3.5. Phép truy toán mà không là tuyến tính thuần nhất ∞
(cid:88) và cũng không là tuyến tính không thuần nhất được gọi là phép truy toán j=0 không tuyến tính. Nếu a(x) = ajxj hay dãy số a0, a1, a2, .. thỏa mãn phép truy toán không tuyến tính f bậc k, tức là f (n, a0, a1, ..., an, 0, 0, ...) = 0 cho mọi n ≥ k, thì đẳng thức này cũng được gọi là hệ thức truy hồi cho f . Ví dụ 1.3.6. Ta định nghĩa số Catalan thứ n, kí hiệu là cn, là số cách chèn
n cặp ngoặc tròn vào tích x1x2...xn của n + 1 số sao cho mỗi lần nhân chỉ
có đúng hai thừa số. Chẳng hạn, ta có các cách chèn các cặp ngoặc tròn sau đây vào tích x1x2x3x4 : (x1(x2(x3x4))), ((x1x2)(x3x4)), (((x1x2)x3)x4), ((x1(x2x3))x4), (x1((x2x3)x4)). 18 Như vậy c3 = 5. Dễ thấy rằng, c1 = 1, c2 = 2. Để cho tiện sử dụng, ta định
nghĩa c0 = 1. Ta nhận xét rằng mỗi cách chèn n cặp ngoặc tròn vào tích x1x2...xn+1,
ở đây k có thể là 0, 1, .., n − 1. Số cách chèn các cặp ngoặc tròn vào tích x1x2..xk+1 là ck, còn số cách chèn các cặp ngoặc tròn vào tích xk+2xk+3...xn+1
là cn−k−1. Vì vậy ta nhận được cn = c0cn−1 + c1cn−2 + c2cn−3 + .. + cn−1c0. Đây là hệ thức truy hồi không tuyến tính. Các kết quả dưới đây cho phép ta tìm lời giải của một số phép truy toán tuyến tính thuần nhất. Định lý 1.3.7. Giả sử c1, c2, ..ck ∈ C là các số sao cho phương trình j=0 xk − c1xk−1 − c2xk−2 − ... − ck = 0
∞
(cid:88) có k nghiệm phân biệt r1, r2, ..., rk. Khi đó a(x) = ajxj là một lời giải của phép truy toán tuyến tính thuần nhất bậc k với hệ thức truy hồi an − c1an−1 − c2an−2 − ... − ckan−k = 0 cho mọi n ≥ k khi và chỉ khi 1 + α2rn 2 + ... + αkrn
k an = α1rn cho mọi n = 0, 1, 2, ... ở đây α1, α2, ..., αk là nghiệm của hệ phương trình
tuyến tính = a0
= a1 2 x2 + ... + rk−1 k xk x1 + x2 + ... + xk
r1x1 + r2x2 + ... + rkxk
.................................................... = ......
1 x1 + rk−1
rk−1
= ak−1. Nhận xét 1.3.8. Hệ phương trình tuyến tính trên có định thức . D = 1
rk
r2
k (cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12) (cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12) 1
r1
r2
1
...
rk−1
1 1
r2
r2
2
...
rk−1
2 ...
...
...
....
... rk−1
k (cid:89) Định thức này là định thức Vandermonde và được tính theo công thức i>j 19 D = (ri − rj). Vì r1, r2, ..., rk là các số đôi một khác nhau, nên D (cid:54)= 0. Do đó hệ phương
trình tuyến tính là hệ Cramer. Vì thế nó luôn có duy nhất một nghiệm 2 + ... + αkrn 1 + α2rn α1, α2, ..., αk. Chứng minh. Giả sử an = α1rn
k cho mọi n = 0, 1, 2, ..., ở
đây α1, α2, ..., αk là nghiệm của phương trình tuyến tính nói trên. Khi đó,
với n ≥ k, ta có 1 + α2rn k ) − c1(α1rn−1 1 + α2rn−1 2 + ... + αkrn−1 k 1 + α2rn−k k ) − ... an − c1an−1 − ... − ckan−k
2 + ... + αkrn 1 − c1α1rn−1 2 + ... + αkrn−k
1 − ... − ckα1rn−k k − ... − ckαkrn−k k ) 1 − c1rk−1 k − c1αkrn−1
k − c1rk−1 1
1 − ... − ck) + ... + αkrn−k 1 k k − ... − ck) )
) + ... + (αkrn
(rk (rk = (α1rn
− ck(α1rn−k
= (α1rn
= α1rn−k = 0 vì r1, r2, ..., rk là nghiệm của phương trình xk − c1xk−1 − ... − ck = 0. ∞
(cid:88) Vậy a(x) là lời giải của phép truy toán nói trên. j=0 Ngược lại, giả sử a(x) = ajxj là lời giải của phép truy toán tuyến tính thuần nhất bậc k với hệ thức truy hồi an − c1an−1 − c2an−2 − ... − ckan−k = 0 cho mọi n ≥ k ta chứng minh rằng 1 + α2rn 2 + ... + αkrn
k an = α1rn cho mọi n = 0, 1, 2, ... bằng quy nạp theo n. Nếu n = 0, 1, ..., k − 1, thì đẳng thức trên là hiển nhiên đúng do α1, ..., αk là nghiệm của hệ phương
trình tuyến tính nói tới trong định lý 1.1.15. Giả sử đẳng thức trên đã được chứng minh cho mọi 0 ≤ n ≤ t với t ≥ k − 1. Khi đó, do a(x) là lời giải của phép truy toán tuyến tính nói trên, nên 20 at+1 − c1at − c2at−1 − ... − ckat+1−k = 0. Suy ra at+1 = c1at + c2at−1 + ... + ckat+1−k k) + ... + ck(α1rt+1−k 1 ) 1 + ... + αkrt
1 + c2rt−1 1 + ... + ckrt+1−k
1
k + c2rt−1 k + ... + ckrt+1−k k ) + α2(c1rt + ... + αkrt+1−k
k
2 + c2rt−1
2 + ... 2 2 + c2rk−2 2 + ... + ck) + ... )
(c1rk−1 2 k rk
k 2 + ... + αkrt+1 k . = c1(α1rt
= α1(c1rt
+ ckrt+1−k
) + ... + αk(c1rt
2
= α1rt+1−k
1 + ... + ck) + α2rt+1−k
1 + c2rk−2
(c1rk−1
1
+ αkrt+1−k
k + c2rk−2
(c1rk−1
k + ... + ck)
k
= α1rt+1−k
rk
2 + ... + αkrt+1−k
rk
1 + α2rt+1−k
1
1 + α2rt+1
= α1rt+1 Từ Định lý 1.3.7 ta có hệ quả sau đây. ∞
(cid:88) Hệ quả 1.3.9. Giả sử c1, c2 ∈ C là các số sao cho phương trình x2 − c1x − j=0 c2 = 0 có hai nghiệm phân biệt r1, r2. Khi đó a(x) = ajxj là lời giải của phép truy toán tuyến tính thuần nhất bậc 2 với hệ thức truy hồi an − c1an−1 − c2an−2 = 0 cho mọi n ≥ 2 khi và chỉ khi 1 + α2rn
2 an = α1rn . và α2 = cho mọi n = 0, 1, 2, ..., ở đây α1 = −(a1 − a0r1)
r1 − r2 (cid:40) a1 − a0r2
r1 − r2
Chứng minh. Hệ phương trình tuyến tính x1 + x2
= a0
r1x1 + r2x2 = a1. có nghiệm α1, α2 như trong Hệ quả 1.3.9. Do đó, theo Định lý 1.3.7 ta có
Hệ quả 1.3.9. ∞
(cid:88) Định lý 1.3.10. Giả sử c1, c2 ∈ C là các số sao cho phương trình x2 − j=0 c1x − c2 = 0 có nghiệm kép r0 (cid:54)= 0. Khi đó a(x) = ajxj là lời giải của phép truy toán tuyến tính thuần nhất bậc 2 với hệ thức truy hồi 21 an − c1an−1 − c2an−2 = 0 cho mọi n ≥ 2 khi và chỉ khi an = α1rn 0 + α2(n − 1)rn
0
a1
r0 0 cho mọi n = 0, 1, 2, ..., ở đây 0 + α2(n − 1)rn
. Khi đó với n ≥ 2 ta có . và α2 = cho mọi n = 0, 1, 2, ..., ở đây α1 = a1 − a0r0
r0 0 + α2(n − 1)rn o ) − Chứng minh. Giả sử an = α1rn
α1 = và α2 = a1 − a0r0
r0 a1
r0 0 + α2(n − 2)rn−1 0 0 0 ) an − c1an−1 − c2an−2 = (α1rn
c1(α1rn−1 ) − c2(α1rn−2 ) + (α2(n − 3)rn−2 0 − c1α1rn−1 0 = (α1rn 0 ) (α2(n − 1)rn 0 − 0 = α1rn−2 0 − c1r0 − c2) − 0 0 − c2α1rn−2
) +
0 − c2α2(n − 3)rn−2
0 − c1α2(n − 2)rn−1
0 − c1α2nrn−1
0 − c1r0 − c2) + (α2nrn
) − (α2rn
0 − 3c2α2rn−2
0 − 2c1α2rn−1
)
0 − c1r0 − c2) + α2nrn−2
0 − 2c1r0 − 3c2)
(r2 (r2 (r2
0
c2α2nrn−2
0
(r2 0 − 2c1r0 − 3c2) 0 = α1rn−2
0
(r2
α2rn−2
0
= −α2rn−2 (do r0 là nghiệm của phương trình x2 − c1x − c2 = 0 ).
Vì r0 là nghiệm kép của phương trình x2 − c1x − c2 = 0 nên theo định lý
0 = −c2. Do đó c1 = 2r0 và c2 = −r2
Viét, r0 + r0 = 2r0 = c1 và r0r0 = r2
0.
Suy ra 0 − 2c1r0 − 3c2) = r2 0 − 2(2r0) − 3(−r2 0) = r2 0 − 4r2 0 + 3r2 0 = 0. (r2 Vì vậy, 0 − 2c1r0 − 3c2) = 0. 0 (r2 an − c1an−1 − c2an−2 = −α2rn−2 ∞
(cid:88) Vậy a(x) là lời giải của phép truy toán nói trên. j=0 Ngược lại, giả sử a(x) = ajxj là lời giải của phép truy toán tuyến tính thuần nhất bậc 2 với hệ thức truy hồi an − c1an−1 + α2an−2 = 0 cho mọi n ≥ 2. Ta chứng minh rằng 0 + α2(n − 1)rn
0 22 an = α1rn và α2 = a1
r0 . cho mọi n = 0, 1, 2, .... bằng quy nạp theo n, ở đây α1 =
a1 − a0r0
r0 0 + α2(0 − 1)r0 0 = α1 − α2 = − = a1
r0 a1 − a0r0
r0 + − = a0 và khẳng định đúng cho n = 0. Với n = 1, ta có Với n = 0, ta có α1r0
a1
r0 a0r0
r0 0 + α2(1 − 1)r1 0 = α1r0 = r0 = a1. Vậy khẳng định cũng đúng cho a1
r0 a1
r0
α1r1
n = 1. Giả sử đẳng thức đã được chứng minh là đúng cho mọi n ≤ t với t ≥ 1. Khi đó, do a(x) là lời giải của phép truy toán nói trên, nên at+1 − c1at − c2at−1 = 0. Suy ra 0) + c2(α1rt−1
) + (c1α2(t − 1)rt 0 + α2(t − 2)r0tt−1)
0 + c2α2(t − 2)rt−1 0 ) 0 + c2α2trt−1 0 0 ) 0 + α2(t − 1)rt
0 + c2α1rt−1
0
(c1r0 + c2) + (c1α2trt
0 + 2c2α2rt−1
0
(c1r0 + c2) + α2trt−1 ) 0 0 0 (c1r0 + c2) − α2rt−1 (c1r0 + 2c2). at+1 = c1at + c2at−1
= c1(α1rt
= (c1α1rt
= α1rt−1
− (c1α2rt
= α1rt−1 Do r0 là nghiệm của phương trình x2 − c1x − c2 = 0, nên c1r0 + c2 = r2
0.
Do đó, 0 + α2trt+1 0 − α2rt−1 0 0 = −c2. Suy ra, c1 = 2r0 và c2 = −r2
0. at+1 = α1rt+1 (c1r0 + 2c2). Vì r0 là nghiệm của phương trình x2 − c1x − c2 = 0, nên theo định lý Viét,
r0 + r0 = 2r0 = c1 và r0r0 = r2
Do đó, 0 − 2r2 0) = 2r2 c1r0 + 2c2 = (2r0)r0 + 2(−r2 0 = 0.
(c1r0 + 2c2) = α1rt+1 0 + α2trt+1 0 − α2rt−1 0 0 + α2trt+1 0 . Vì vậy, at+1 = α1rt+1 1.4. Phương pháp đếm dùng hàm sinh thông thường C[[x]] sao cho ϕ(a(x)) = b(x), ở đây a(x) = j=0 23 Giả sử aj, j = 0, 1, 2, ..., là các số phức. Ta nói rằng phần tử b(x) ∈
C[[x]] là hàm sinh cho dãy số a0, a1, a2, ..., aj, ... mà ta sẽ thường đơn giản
ký hiệu là (aj)∞
0 , nếu tồn tại một tự đẳng cấu ϕ của không gian véctơ
∞
(cid:88) ajxj. 0 , có nhiều hàm sinh khác nhau cho
nó, tuy nhiên, ta chú ý tới hàm sinh thường dùng hiện nay là hàm sinh Hiển nhiên là với mỗi dãy (aj)∞ thông thường và hàm sinh mũ. ∞
(cid:88) Định nghĩa 1.4.1. Nếu ϕ là tự đẳng cấu đồng nhất của không gian véctơ
C[[x]], tức là ϕ(c(x)) = c(x) cho mọi c(x) ∈ C[[x]], thì ϕ(a(x)) được gọi là
hàm sinh thông thường cho dãy (aj)∞
j=0. Như vậy, hàm sinh thông thường j=0 là chuỗi hình thức a(x) = j=0 cho dãy (aj)∞ ajxj. (cid:32) (cid:33) n
(cid:88) Ví dụ 1.4.2. Theo công thức nhị thức ta có j=0 (cid:32) (cid:33) (1 + x)n = (x + 1)n = xj. n
j (cid:32) (cid:33) Vì = 0 nếu j > n, nên ta có (1 + x)n chính là chuỗi lũy thừa hình (cid:32) (cid:32) (cid:33) (cid:32) (cid:33) (cid:33)
, n
j
∞
(cid:88) thức xj. Vậy hàm sinh thông thường cho dãy các hệ số nhị thức j=0
(cid:32)
n
1 n
j
(cid:33)
, , ..., chính là phần tử (1 + x)n của C[[x]]. n
j n
0 n
2 ∞
(cid:88) Ví dụ 1.4.3. Nếu z ∈ C, thì theo Mệnh đề 1.1.4 ta có j=0 (1 − zx)−1 = zjxj. là phần tử Vì vậy hàm sinh thông thường cho dãy z0, z1, z2, ..., zj, ..
(1 − zx)−1 của C[[x]]. Ý tưởng sử dụng hàm sinh để giải quyết bài toán đếm có thể tóm tắt như sau. Giả sử phép đếm phụ thuộc vào số tự nhiên j. Ta kí hiệu số 24 các phép đếm này bằng aj và muốn tính được aj bằng một biểu thức dễ
thực hiện chỉ phụ thuộc vào j ở dạng hiển. Để làm điều đó, ta xét hàm
sinh b(x) cho dãy (aj)∞
0 , ở đây b(x) = ϕ(a(x)) với ϕ là một tự đẳng cấu
của C[[x]]. Khi đó, do tính chất của dãy (aj)∞
0 , b(x), cần thỏa mãn các hệ
thức nhất định. Giải các hệ thức này ta tìm được biểu thức fb(x) của hàm
sinh b(x) cho dãy (aj)∞
0 . Biểu thức tìm được này thường là một biểu thức
với các phép toán trong C[[x]] như phép cộng, phép nhân, phép lấy phần ∞
(cid:88) tử đối, phép lấy phần tử nghịch đảo, phép lũy thừa,...của các hàm đã biết
trong C[[x]]. Nói chung biểu thức này chưa ở dạng chuỗi lũy thừa. Vì vậy
sau khi tìm được biểu thức fb(x) ta tìm cách khai triển nó thành dạng j=0 chuỗi lũy thừa, tức là biểu diễn fb(x) thành dạng fb(x) = bjxj bằng 0 , ta có
∞
(cid:88) ∞
(cid:88) một cách nào đó, ở đây bj là một biểu thức phụ thuộc vào j ở dạng hiển.
Do b(x) = fb(x) là hàm sinh cho dãy (aj)∞
. j=0 j=0 ∞
(cid:88) ∞
(cid:88) bjxj = fb(x) = ϕ(a(x)) = ϕ ajxj
. Từ đó ta tìm được công thức cho aj j=0 j=0 Suy ra ajxj = ϕ−1 bjxj qua j ở dạng hiển và giải quyết được bài toán đã đặt ra. Ví dụ 1.4.4 (Số Fibonacci). Ta định nghĩa F0 = 0, F1 = 1, còn với j ≥ 2
ta định nghĩa Fj là số các tập con của tập X = {1, 2, ..., j − 2} thỏa mãn
điều kiện là mỗi tập con đó đều không chứa hai số liên tiếp nào của tập X. Khi đó các số Fj, j = 0, 1, 2, ... được gọi là các số Fibonacci. Cụ thể hơn,
số Fj được gọi là số Fibonacci thứ j. Bài toán: Hãy tìm công thức tính Fj qua j. Giải. Trước hết ta chứng minh rằng với mọi j ≥ 2, Fj = Fj−1 + Fj−2 Ta có F2 = 1, F3 = 2. Do đó, đẳng thức trên đúng với j = 2, 3. Giả sử
j ≥ 4, X = {1, ..., j − 2} và P là tập tất cả các tập con của X thỏa mãn điều kiện là mỗi tập con đó đều không chứa hai số liên tiếp nào của X. Kí hiệu
P1 = {A ∈ P |A ⊇ j − 2} và P2 = {A ∈ P |A (cid:43) j − 2} . Khi đó P1 ∩ P2 = φ
và P = P1 ∪ P2. Theo quy tắc cộng, Fj = |P | = |P1| + |P2|. Mỗi A ∈ P1 đều
không thể chứa j − 3. Do đó mỗi A ∈ P1 tương ứng với đúng một tập con
của X\ {j − 3, j − 2} = {1, 2, ..., j − 4} thỏa mãn điều kiện là nó không 25 chứa hai số liên tiếp nào của tập X\ {j − 3, j − 2}. Suy ra |P1| = Fj−2. Mỗi
tập con A ∈ P2 cũng là một tập con của X\ {j − 2} = {1, 2, ..., j − 3} . Vì
vậy, |P2| = Fj−1. Suy ra, Fj = Fj−1 + Fj−2. Ta muốn tìm biểu thức tính Fj qua j bằng cách sử dụng hàm sinh
0 . Khi thông thường. Giả sử f (x) là hàm sinh thông thường cho dãy (Fj)∞
đó, f (x) = F0 + F1(x) + F2x2 + F3x3 + ...,
xf (x) = F0x + F1x2 + F2x3 + F3x4 + ...,
x2f (x) = F0x2 + F1x3 + F2x4 + ... Do đó, f (x) − xf (x) − x2f (x) = F0 + (F1 − F0)x + (F2 − F1 − F0)x2 + ... +(Fj − Fj−1 + Fj−2)xj + ... = x vì F0 = 0, F1 = 1 và Fj = Fj−1 + Fj−2 cho mọi j ≥ 2. Suy ra, (1 − x − x2)f (x) = x ⇔ f (x) = x Như vậy là ta đã tìm được hàm sinh cho dãy (Fj)∞
học của các hàm hữu tỷ, cụ thể là, f (x) = x trước tiên ta phân tích x
1 − x − x2 .
0 dưới dạng biểu thức số
1 − x − x2 . Tiếp theo, ta muốn
biểu diễn f (x) dưới dạng chuỗi lũy thừa hình thức. Để làm được điều đó,
1 − x − x2 thành tổng của các phân thức đơn giản bằng phương pháp hệ số bất định. Xét tam thức bậc hai 1 − x − x2. Tam thức này có hai nghiệm phân √ √ 1 + 5 5 1 − biệt là a = và b = . −2 −2 Suy ra, = + x
1 − x − x2 = A
x − a B
x − b = . = −x
(x − a)(x − b)
Ax − Ab − Bx − Ba
(x − a)(x − b) (A + B)x − (Ab − Ba)
(x − a)(x − b) (cid:40) Vì vậy ta nhận được hệ phương trình sau đây để xác định A và B: Ab + Ba = 0
A + B = −1. Giả hệ phương trình này ta tìm được A = và B = , tức là a
b − a −b
b − a 26 − . x
1 − x − x2 = a
(b − a)(x − a) b
(b − a)(x − b) Theo Mệnh đề 1.1.4 ta có ∞
(cid:88) j=0 1 = . = a
(b − a)(x − a) 1
a − b 1
a − b xj
aj , 1 − x
a ∞
(cid:88) j=0 1 = = . b
(b − a)(x − b) 1
a − b 1
a − b xj
bj . 1 − x
b √ Vì a − b = 5 nên từ hai đẳng thức trên ta nhận được ∞
(cid:88) ∞
(cid:88) x j=0 j=0
(cid:19)(cid:21) ∞
(cid:88) 1 − x − x2 = − xj
bj 1
√
5 j=0 xj. = xj
aj +
(cid:18) 1
bj − 1
aj 1
√
5
(cid:20) 1
√
5 Lại có 1
bj − 1
aj = aj − bj
(ab)j = (cid:32) (cid:32) ∞
(cid:88) xj. j=0 √ √ aj − bj
(−1)j = (−a)j − (−b)j. Do đó,
(cid:33)j
(cid:33)j 5 5 − 1 +
2 1 −
2 1
1 − x − x2 = 1
√
5 (cid:32) (cid:33)j (cid:32) (cid:33)j xj, Suy ra, √ √ 5 5 − Fj = 1 +
2 1 −
2 1
√
5 cho mọi j = 0, 1, 2, ... (cid:50) Nhận xét 1.4.5. Ta thấy rằng F (x) thỏa mãn phép truy toán tuyến tính √ √ thuần nhất bậc 2 với hệ thức truy hồi Fj − Fj−1 − Fj−2 = 0 cho mọi j ≥ 2.
Vì vậy ta có thể áp dụng Hệ quả 1.3.9 để tính Fj như sau. Phương trình
5 5 . x2 − x − 1 có hai nghiệm phân biệt là r1 = 1 −
2 1 +
2
= − . Theo Hệ quả = , α2 = F1 − F0r2
r1 − r2 −(F1 − F0r1)
r1 − r2 và r2 =
1
√
5 1
√
5 Do đó, α1 =
1.3.9, (cid:32) (cid:33)j (cid:32) (cid:33)j
. 1 + α2rj 2 = √ √ 5 5 − Fj = α1rj 1 +
2 1 −
2 1
√
5 Ví dụ 1.4.6. Bài toán: Có j hình vuông rời nhau kích thước tương ứng là 1 × 1, 2 × 2, ..., j × j cần được lát bằng các viên gạch kích thước 1 × 1. 27 Tính số viên gạch cần thiết để lát đủ j hình vuông đó (bằng công thức phụ thuộc vào j) j
(cid:88) Giải. Gọi aj là số viên gạch cần thiết để lát đủ j hình vuông đã cho. Khi
đó dễ thấy rằng k=0 j−1
(cid:88) j
(cid:88) k2. aj = k=0 k=0 k2 = j2 cho mọi j ≥ 1, tức là k2 − Do đó, a0 = 0 và aj − aj−1 = các số a0, a1, a2, ..., aj, .. thỏa mãn hệ thức truy hồi tuyến tính bậc 1 không
thuần nhất aj − aj−1 − j2 = 0. Ta sử dụng hàm sinh thông thường để tính aj. Giả sử a(x) là hàm 0 . Khi đó sinh thông thường cho dãy (aj)∞ a(x) = a0 + a1x + a2x2 + a3x3 + ...,
xa(x) = a0x + a1x2 + a2x3 + a3x4 + ... Do đó, ∞
(cid:88) (x) − xa(x) = a0 + (a1 − a0)x + (a2 − a1)x2 + (a3 − a2)x3 + ... j=0 ∞
(cid:88) = j2xj. j=0 Suy ra, (1 − x)a(x) = j2xj. Ta muốn nhận được biểu thức số học của các hàm hữu tỷ cho chuỗi ở bên phải trong đẳng thức trên. Để làm được điều đó, ta xuất phát từ (cid:32) (cid:33) ∞
(cid:88) ∞
(cid:88) đẳng thức sau đây mà đã được chứng minh ở Mệnh đề 1.1.4 (2): j=0 j=0 ∞
(cid:88) xj ⇔ (j + 1)xj. 1
(1 − x)2 = 2 + j − 1
j 1
(1 − x)2 = j=0 (j + 1)xj+1. Áp dụng toán tử đạo hàm D vào cả hai Suy ra x
(1 − x)2 = ∞
(cid:88) ∞
(cid:88) vế của đẳng thức này, ta được
= j=0 j=0 28 D(x(1 − x)−2) = D (j + 1)xj+1 (j + 1)2xj. Đẳng thức cuối cùng ta có được từ định nghĩa toán tử D. Mặt khác, theo mệnh đề 1.2.2 (2) (4) ta có D(x(1 − x)−2) = D(x)(1 − x)−2 + xD((1 − x)−2) = (1 − x)−2 + x(−2(1 − x)−3D(1 − x)) = (1 − x)−2 + 2x(1 − x)−3 ∞
(cid:88) = (1 + x)(1 − x)−3. j=0 ∞
(cid:88) ∞
(cid:88) (j + 1)2xj. Suy ra, Do đó 1 + x
(1 − x)3 = j=0 j=0 ∞
(cid:88) (j + 1)2xj+1 = j2xj. x + x2
(1 − x)3 = j=0 Nhưng như ta đã chứng minh ở trên rằng (1 − x)a(x) = j2xj. Vì vậy, (1 − x)a(x) = x + x2
(1 − x)3 , tức là a(x) = x + x2
(1 − x)4 . Như vậy là ta đã tìm được hàm sinh a(x) cho dãy số cần tìm dưới tìm cách khai triển hàm a(x) = dạng hàm hữu tỷ. Tiếp tục, để nhận được biểu thức cho aj qua j, ta phải
x + x2
(1 − x)4 thành chuỗi lũy thừa. Để làm
điều đó ta phân tích phân thức này thành tổng của các phân thức đơn giản bằng phương pháp hệ số bất định. Ta có + x + x2
(1 − x)4 = B
(1 − x)2 + C
(1 − x)3 + = D
A
(1 − x)4
1 − x
A(1 − x)3 + B(1 − x)2 + C(1 − x) + D
(1 − x)4 = A(1 − 3x + 3x2 − x3) + B(1 − 2x + x2) + C(1 − x) + D
(1 − x)4 = −Ax3 + (3A + B)x2 + (−3A − 2B − C)x
(1 − x)4 29 + . (A + B + C + D)
(1 − x)4 Suy ra
= 0
−A
3A + B
= 1
−3A − 2B − C = 1 A + B + C + D = 0 Giải hệ phương trình này ta tìm được A = 0, B = 1, C = −3, D = 2, tức là a(x) = x + x2
(1 − x)4 = 1
(1 − x)2 − 3
(1 − x)3 + 2
(1 − x)4 . Áp dụng Mệnh đề 1.1.4 (2) ta được (cid:32) (cid:32) (cid:33) 1 a(x) = ∞
(cid:88) j=0 (cid:34)(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) j=0
(cid:33)(cid:35) j=0
∞
(cid:88) 2
(1 − x)2 − 3(1 − x)3 +
(1 − x)4
(cid:33)
(cid:32)
(cid:33)
∞
∞
(cid:88)
(cid:88) xj − 3 xj + 2 xj = j + 2
j j + 1
j j + 3
j j=0
∞
(cid:88) = − 3 + 2 xj j + 1
j j + 2
j j + 3
j j=0 j
(cid:88) = xj. j(j + 1)(2j + 1)
6 k=0 k2 = . Suy ra aj = j(j + 1)(2j + 1)
6 Ví dụ 1.4.7. Ở Ví dụ 1.3.6 ta đã định nghĩa số Catalan thứ j, ký hiệu là Cj, là số cách chèn j cặp ngoặc tròn vào tích x1x2...xj+1 của j + 1 số sao
cho mỗi lần nhân chỉ có đúng hai thừa số. Khi đó c1 = 1, c2 = 2. Ta cũng
định nghĩa c0 = 1 và đã chứng minh được rằng cj = c0cj−1 + c1cj−2 + c2cj−3 + ... + cj−1c0 cho mọi j ≥ 1. 30 Bây giờ ta đi tìm công thức tính cj qua j. 0 . Khi đó, Giả sử c(x) là hàm sinh thông thường cho dãy (cj)∞ c(x) = c0 + c1(x) + c2x2 + c3x3 + c4x4 + ...., 0 + (c0c1 + c1c0)x + (c0c2 + c1c1 + c2c0)x2 + ... (c(x))2 = c2 + (c0cj−1c1cj−2 + ... + cj−1c0)xj−1 + ...
= c1 + c2x + c3x2 + c4x3 + ... Vì thế x2(c(x))2 = x[c1x + c2x2 + c3x3 + ...] = x[c(x) − 1] = xc(x) − x, tức
là (xc(x))2 − xc(x) + x = 0. Giải phương trình bậc hai trên đối với xc(x) √ √ 1 − ta tìm được
1 + hoặc xc(x) = . 1 − 4x
2 1 − 4x
2 xc(x) =
Vì S(−4x) = 0, nên theo Mệnh đề 1.2.11 (4) ta có hệ số của (−4x)j trong
√ 1 − 4x bằng ( − 1)( − 2)...( − j + 1) 1
2 1
2 1
2 1
2 , j! √ tức là hệ số của xj trong khai triển thành chuỗi lũy thừa của 1 − 4x bằng (−4)j( )( − 1)( − 2)...( − j + 1) 1
2 1
2 1
2 1
2
j! (−1)j22j( )(− )(− )...(− ) 3
2 1
2 1
2 2j − 3
2 = j! . = = (−1)j22j 1.3.5...(2j − 3)
j!(−1)j−12j
−2j(1.3.5...(2j − 3))
j! 31 √ Vì vậy chúng là các số nguyên âm cho mọi j ≥ 1. Điều đó chứng tỏ
1 + không thể bằng xc(x) vì các hệ số của xj trong xc(x) là rằng 1 − 4x
2 các số nguyên dương. Vậy √ 1 − xc(x) = 1 − 4x
2 (cid:21)
xj + ... = x + x2 + x3 + ... + 22
2! 1
2 23.1.3
3! 2j.1.3...(2j − 3)
j! (cid:20) 2
1!
2
2! = x + x2 + x3 + ... + xj + ... 22.1.3
3! 2j−1.1.3...(2j − 3)
j! Suy ra c(x) = 1 + x + x2 + ... + xj−1 + ... 2
2! 22.1.3
3! 2j−1.1.3...(2j − 3)
j! Do đó, cj = 2j.1.3...(2j − 1)
(j + 1)! = = (cid:33) Vì vậy, ta nhận được cj = 2j.1.2.3.4...(2j − 1)(2j)
(j + 1)!2.4...(2j)
2j(2j)!
(j + 1)!j!2j .
(cid:33)
(cid:32)
2j
1
.
j
(j + 1) (cid:32)
6
3 = 5. Từ công thức trên, chẳng hạn ta có c3 = 1
4 Ví dụ 1.4.8. Hợp thành và phân hoạch của số nguyên dương. Một biểu thức của số nguyên dương n dưới dạng tổng có thứ tự của k số nguyên dương được gọi là một hợp thành của n thành k phần. Một hợp thành của n chính là một hợp thành của n thành k phần với k nguyên dương nào đó. Chẳng hạn, số 4 có 8 hợp thành là 4, 3 + 1, 2 + 2, 2 + 1 + 1, 3 + 1, 1 + 2 + 1, 1 + 2 + 1, 1 + 1 + 1. Cụ thể hơn, số 4 có một hợp thành thành một phần là 4, có ba hợp thành thành hai phần là 3 + 1, 2 + 2, 1 + 3, có ba hợp thành thành ba phần là 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2 và có một hợp thành thành bốn phần là 1 + 1 + 1 + 1. Người ta cũng thường đồng nhất hợp thành của n thành k phần với lời giải nguyên dương của phương trình 32 x1 + x2 + ... + xk = n Ký hiệu số hợp thành của n thành k phần là C(n, k), còn tất cả các hợp thành của n là C(n). Mỗi một hợp thành a1 + a2 + ... + ak ta tương ứng
với một tập con lực lượng k − 1 của tập [n − 1] = {1, 2, ..., n − 1} như sau: (cid:32) a1 + a2 + ... + ak (cid:55)→ a1, a1 + a2, ..., a1 + a2 + ... + ak−1. Ngược lại, tập con
{s1, s2, ..., sk−1} lực lượng k − 1 với s1 < s2 < ... < sk−1 của [n − 1] xác định
một hợp thành a1 + a2 + ... + ak của n thành k phần tương ứng với nó như
sau: a1 = s1, a2 = s2 − s1, ..., ai = si − si−1(2 ≤ i ≤ k − 1), ...ak = n − sk−1.
Dễ chứng minh được rằng tương ứng trên là tương ứng một - một. Do đó, (cid:33)
, C(n, k) = n − 1
k − 1 (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) C(n) = C(n, 1) + C(n, 2) + ... + C(n, n) + + ... + = n − 1
1 n − 1
n − 1 n − 1
0
= 2n−1. Phân hoạch của một số nguyên n ≥ 0 là một dãy có thứ tự λ = (λ1, λ2, ...λk) các số nguyên dương λ1, λ2, ...λk sao cho λ1 ≥ λ2 ≥ ... ≥ λk
và λ1 + λ2 + ... + λk = n. Nếu λ = (λ1, λ2, ...λk) là phân hoạch của n thì ta
kí hiệu là λ (cid:96) n và gọi λ1, λ2, ...λk là các phần của nó. Như vậy, một phân hoạch của một số nguyên dương chính là một hợp thành của số đó, trong đó ta không quan tâm tới thứ tự của các số hạng. Một phân hoạch λ của n được xác định một cách duy nhất bởi số bội của các phần có thể là 1, 2, ..., n. Nếu i xuất hiên với bội ai ≥ 0, thì ta
viết λ = 1a12a2...nan. Nếu a1 + a2 + ... + an = k và λ = 1a12a2...nan là một
phân hoạch của n thành k phần, thì n = 1.a1 + 2.a2 + 3.a3 + ... + n.an. Sự xuất hiện của số i với các bội số có thể được biểu diễn bằng chuỗi ai(x) = 1 + (xi)1 + (xi)2 + (xi)3 + ... ∞
(cid:89) Dễ thấy rằng dãy các chuỗi lũy thừa hình thức a1(x), a2(x), a3(x), ..., ai(x), ... i=1 là khả tích, tức là ta có thể xác định phần tử ai(x) trong C[[x]]. Hơn ∞
(cid:89) thế nữa, phân hoạch λ = 1a12a2...nan tương ứng với duy nhất một số hạng i=1 33 (x1)a1(x2)a2...(xn)an của tích ai(x). Do đó, hệ số của xn trong tích trên chính là tổng số các phân hoạch của n, tức là hàm sinh cho dãy số các ∞
(cid:89) ∞
(cid:89) phân hoạch của các số nguyên không âm là i=0 i=0 p(x) = (1 + (xi)1 + (xi)2 + (xi)3 + (xi)4 + ...) = . 1
(1 − xi) Với lập luận tương tự ta có thể nhận được hàm sinh cho các phân hoạch của số nguyên n ≥ 0 với các ràng buộc khác nhau. Chẳng hạn, ∞
(cid:89) - Hàm sinh pd(x) cho số các phân hoạch của n ≥ 0 thành các phần khác
nhau là i=1 (1 + xi) pd(x) = (1 + x)(1 + x2)(1 + x3)... = vì chỉ có các bội cho phép là 0 hoặc 1. ∞
(cid:89) - Hàm sinh p0(x) cho số các phân hoạch của n ≥ 0 thành các phần là số lẻ
là i=0 p0(x) = 1
1 − x2i+1 vì các phần cho phép đều phải là số lẻ. ∞
(cid:88) ∞
(cid:88) 1.5. Phương pháp đếm bằng hàm sinh mũ j=0 j=0 ∞
(cid:88) xj cho mọi Định nghĩa 1.5.1. Nếu ϕ : C[[x]] → C[[x]] : cjxj (cid:55)→ cj
j! j=0
ϕ(a(x)) được gọi là hàm sinh mũ cho dãy (aj)∞ ∞
(cid:88) cjxj ∈ C[[x]], thì dễ thấy rằng ϕ là một tự đẳng cấu của C[[x]]. Khi đó 0 . Như vậy, hàm sinh mũ
aj
j! j=0 là chuỗi lũy thừa hình thức b(x) = bjxj, ở đây bj = cho dãy (aj)∞
0 cho mọi j = 0, 1, 2, ... Hàm sinh mũ đóng vai trò nền tảng trong việc nghiên cứu các loại tổ hợp (combinatorial species). Trong mục này ta chỉ đề cập tới phương pháp sử dụng hàm sinh mũ để giải quyết một số bài toán đếm như thế nào. Giả sử với mỗi tập hữu hạn N ta có một tập S(N ) các vật mà ta muốn đếm. (Như vậy, tập các vật cần đếm S(N ) phụ thuộc vào tập N .) Các vật của S(N ) có thể xem như là "được gắn nhãn" hay "được đỡ" bởi 34 tập N . Vì vậy, tập N có thể xem như là tập giá hay nói ngắn gọn gọi là giá của S(N ). Do đó, nếu M và N là các tập hữu hạn khác nhau, tức là M (cid:54)= N , thì ta luôn giả thiết rằng S(N ) ∩ S(M ) = φ. Hơn thế nữa nếu |N | = |M |, thì ta cũng luôn giả thiết rằng |S(N )| = |S(M )|. Khi đó hàm sinh mũ cho dãy các tập S([0]), S([1]), S([2]), ... hay ngắn gọn (S([n]))∞ 0 , được định nghĩa là hàm sinh mũ cho dãy số |S([0])|, |S([1])|, |S([2])|, ...
0 là một dãy các tập các vật khác. Ta định nghĩa tập
ST ([j]) là tập bao gồm tất cả các cặp (σ, τ ), ở đây σ là một phần tử của Giả sử (T ([j]))∞ (cid:33) j
(cid:88) tập S(K) với K là một tập con bất kỳ của [j], còn τ là một phân tử của
tập T ( ¯K) với ¯K = [j] K. Khi đó,
(cid:32) k=0 |ST (j)| = |S([k])||T ([j − k])|. j
k 0 , (T ([j]))∞ 0 và (ST ([j]))∞
0 Ký hiệu hàm sinh mũ cho dãy (S([j]))∞ tương ứng bằng s(x), t(x) và st(x). Khi đó, từ định nghĩa của ST ([j]) ở trên ta dễ thấy rằng st(x) = s(x)t(x). Mệnh đề 1.5.2. Với mỗi z ∈ C, ta ký hiệu chuỗi lũy thừa hình thức E(zx)
bằng ezx. Khi đó ezx = 1 + x + x2 + x3 + ... z
1! z2
2! z3
3! Như vậy, ezx chính là hàm sinh mũ cho dãy số z0, z1, z2, ..., zj, ...(cid:50) Ý tưởng sử dụng hàm sinh mũ để giải quyết bài toán đếm cho các cấu hình tổ hợp đã được nói tới trong mục trước. Bây giờ ta xét một số ví dụ cụ thể, ở đó hàm sinh mũ đã được áp dụng một cách thành công để giải quyết bài toán đếm. Ví dụ 1.5.3. Số mất thứ tự Giả sử X là một tập hữu hạn và X = {x1, x2, ..., xn} . Ta sẽ đồng
nhất hoán vị (a1, a2, ..., an) của các phần tử của X với song ánh ϕ : X →
X, xi (cid:55)→ ai. Khi đó phần tử xi ∈ X được gọi là điểm bất động của hoán vị
ϕ trên X nếu ϕ(xi) = xi. Hoán vị ϕ của X, mà không có điểm bất động
nào, được gọi là một mất thứ tự của X. Số tất cả các mất thứ tự của tập 35 hữu hạn X lực lượng n được kí hiệu là Dn. Bài toán: Hãy tính Dn theo n. Giải: Giả sử P ([n]) là tập tất cả các hoán vị của tập [n] và p(x) là hàm sinh mũ cho dãy P ([0]), P ([1]), ..., P ([n]), .... Mỗi hoán vị của [n] có thể phân tích thành tích của các chu trình độc lập, tức là nó có dạng (∗ ∗ ...∗)(∗ ∗ ...∗)...(∗ ∗ ...∗)(∗)(∗)...(∗), ở đây các chu trình (∗) tương ứng với các điểm bất động của hoán vị đó. Vì vậy mỗi hoán vị ϕ của [n] có thể xem như là cặp (σ, τ ), ở đây σ là một hoán vị không có điểm bất động trên K ⊆ [n] (một mất thứ tự) và τ là một hoán
vị đồng nhất trên ¯K = [n]\K. Chẳng hạn, hoán vị (19573)(46)(2)(8)(10)
trên {1, 2, ..., 10} có thể xem là cặp (σ, τ ) với σ = (19573)(46) là một thứ tự trên {1, 3, 4, 5, 6, 7, 9}, còn τ = (2)(8)(10) là hoán vị đồng nhất trên {2, 8, 10} . Kí hiệu I[n] là tập các hoán vị đồng nhất trên [n], còn D([n]) là tập 0 và (D([n]))∞ các mất thứ tự trên [n]. Khi đó |I([n])| = 1 và |D([n])| = Dn cho mọi
n = 0, 1, 2, .... Do đó, hàm sinh mũ cho dãy (I([n]))∞
0 tương ứng là x + x2 + x3 + ... = E(x), i(x) = 1 + 1
1! 1
2! 1
3! x + x2 + x3 + .... d(x) = D0 + D1
1! D2
2! D3
3! là Vì |P ([n])| = n!, nên hàm sinh mũ cho dãy (P ([n]))∞
0 p(x) = 1 + x2 + x + x3 + ... 1!
1! 2!
2! 3!
3!
= 1 + x + x2 + x3 + ... Mặt khác, như đã lập luận ở trên, ta có P ([n]) = DI([n]). Vì vậy p(x) =
di(x) = d(x)i(x), ở đây di(x) là hàm sinh mũ cho dãy (DI([n]))∞
0 . Suy ra, = (1 + x + x2 + x3 + ...)(1 − x3 + ...) x + = 1 + ... + (1 − + − d(x) = p(x)(i(x))−1 = p(x)(E(x))−1 = p(x)E(−x)
1
1
1
x2 −
3!
1!
2!
+ ... + (−1)n 1
)xn + ...
n! 36 ). + − Vì vậy, Dn = n!(1 − 1
1!
1
3! 1
1
2!
3!
+ ... + (−1)n 1
n! 1
1! 1
2! Xét hàm sinh mũ của dãy các tập (S([j]))∞
0 : s(x) = |S(φ)| + x + x2 + x3 + ... |S([1])|
1! |S([2])|
2! |S([3])|
3! Khi đó, nếu kí hiệu D(s(x)) bằng s(cid:48)(x) và tập các vật được đếm bởi s(cid:48)(x)
với giá [j] bằng S(cid:48)([j]), thì s(cid:48)(x) = |S([1])| + x + x2 + x3 + ... |S([2])|
1! |S([3])|
2! |S([4])|
3! Đẳng thức trên chứng tỏ rằng S(cid:48)([j]) = S([j + 1]) cho mọi j ≥ 0. Phần
tử "thừa" j + 1 cho tập S(cid:48)([j]) có nhiều ưu việt mà ta có thể sử dụng để thiết lập các hệ thức mà s(x) cần phải thỏa mãn. Ta minh họa điều này và phương pháp sử dụng hàm sinh mũ cho bài toán đếm ở hai ví dụ dưới đây. Ví dụ 1.5.4. Sắp xếp thành vòng tròn. Có j vị trí trên một vòng tròn. Mỗi cách sắp xếp j số của tập [j] = {1, 2, ..., j} vào j vị trí đó được gọi là sắp xếp thành vòng tròn của tập [j]. Hai sắp xếp thành vòng tròn của tập [j] được coi là như nhau nếu cùng xuất phát từ vị trí chứa số 1 và đi theo chiều quay của kim đồng hồ ta lần lượt gặp các số tương ứng bằng nhau trong hai sắp xếp đó. Bài toán: Tính số sắp xếp thành vòng tròn của tập [j] theo j. C([j]). Giả sử c(x) là hàm sinh mũ cho dãy (C([j]))∞ Giải: Ký hiệu tập các cách sắp xếp thành vòng tròn của tập [j] bằng
0 và c(cid:48)(x) = D(c(x)).
Khi đó, như ta đã có nhận xét ở trên đối với đạo hàm của hàm sinh mũ,
các sắp xếp thành vòng tròn của tập [j + 1] được đếm bởi c(cid:48)(x) với giá [j]. Mặt khác mỗi sắp xếp thành vòng tròn của tập [j + 1] cũng có thể đồng nhất với một sắp xếp thành hàng ngang của tập [j] bằng cách "cắt" vị trí chứa số j + 1 ra khỏi vòng tròn và "căng" các vị trí còn lại của sắp xếp ra "thành hàng ngang" với số đầu tiên là số sau j + 1 trên vòng tròn theo chiều kim đồng hồ. Ví dụ, sắp xếp thành vòng tròn 32154 của tập [5] được đồng nhất với sắp xếp thành hàng ngang 4321 của tập [4]. Vì vậy, nên ta 37 kí hiệu P ([j]) là tập các sắp xếp thành hàng ngang của tập [j] và p(x) là 0 , thì hàm sinh mũ cho dãy (P ([j]))∞ c(cid:48)(x) = p(x) với S(c(x)) = 1 (vì |C(φ)| = 1 ). Hiển nhiên là P ([j]) chính là tập các hoán vị của [j] và vì thế ∞
(cid:88) ∞
(cid:88) |P ([j])| = j!. Do đó, j=0 j=0 p(x) = xj = xj = . j!
j! 1
1 − x Đẳng thức cuối cùng có được nhờ Mệnh đề 1.1.4. Vậy c(cid:48)(x) = , S(c(x)) = 1. 1
1 − x Sử dụng mệnh đề 1.2.7(1) ta suy ra c(x) = −L(1 − x) + c0 ∞
(cid:88) với c0 là một hằng số. Từ S(c(x)) = 1 và S(L(1 − x)) = 0 suy ra c0 = 1 và
ta nhận được j=1
∞
(cid:88) ∞
(cid:88) c(x) = 1 − L(1 − x) = 1 − (−x)j (−1)j−1
j j=1 j=1 xj = 1 + xj. = 1 + 1
j (j − 1)!
j! Vậy |C([j])| = (j − 1)!. Ví dụ 1.5.5. Tìm số hạng tổng quát của dãy số a0 = 1, ana0 + an−1a1 + ... + a0an = 1. Giải: Xét hàm sinh A(x) = a0 + a1x + a2x2 + ... + anxn + ...
Biểu thức truy hồi gợi ta liên tưởng đến hệ số của hai đa thức 0 + (a0a1 + a1a0)x + ... + (ana0 + an−1a1 + ... + a0an)xn + ... A(x).A(x) = a2 = 1 + x + x2 + ... + xn = (1 − x)−1. Từ đó suy ra A(x) = (1 − x)−1/2 38 )x + ( )( ) + ... + ( )( )...( ) + ... = 1 + ( 1
2 3
2 n − 1
2 xn
n! 1
2 1
2 3
2 x2
2 Và như vậy = an = (2n − 1)!
2n.n! C n
2n
22n . Ví dụ 1.5.6. (Bài toán chia kẹo của Euler) Cho k, n là các số nguyên dương. Tìm số nghiệm nguyên không âm của phương trình x1 + x2 + ... + xn = k(∗) Gọi cn(k) là số nghiệm của (*). Xét tích của các tổng vô hạn
(1 + x + x2 + ...)(1 + x + x2 + ...)...(1 + x + x2 + ...) = (1 + x + x2 + ...)n Ta nhận xét rằng nếu khai triển tích trên thành chuỗi lũy thừa của x (1 + x + x2 + ...)n = c0 + c1x + ... + ckxk + ... thì ck = cn(k). Nhưng (1 + x + x2 + ...)n = (1 − x)−n = 1 + nx + ... + n(n + 1)...(n + k − 1) + ... xk
k! Suy ra n+k−1. 39 = C k cn(k) = n(n + 1)...(n + k − 1)
k! Trong chương này ta tìm hiểu tính bất khả quy của chuỗi lũy thừa hình thức với hệ số nguyên 2.1. Tính phân tích duy nhất của vành Z[[x]] Trong các phần còn lại của mục này ta sẽ chứng minh rằng Z[[x]] là
một miền phân tích duy nhất. Kết quả quan trọng của phần này là Định lý 2.1.10. Trước hết ta đưa ra hai mệnh đề sau: Mệnh đề 2.1.1. Nếu p số nguyên tố thì p cũng là phần tử nguyên tố trong
Z[[x]]. m
(cid:88) Chứng minh. Giả sử c(x) = a(x)b(x), với a(x), b(x) ∈ Z[[x]], p(x) | c(x)
nhưng p(x) (cid:45) b(x). Giả sử m là lũy thừa nhỏ nhất của x sao cho p (cid:45) bm. Vì j=1 cm = a0bm + ajbm−j, m
(cid:88) mà j=1 p | cm, p | ajbm−j. m+k
(cid:88) nên ta suy ra p | a0. Bằng quy nạp, giả sử p | aj với mọi j < k. Hệ số j=0 cm+k = ajbm+k−j 40 có thể được sắp xếp lại là: (cid:88) (cid:88) i+j=m+k
i i+j=m+k
j cm+k = akbm + aibj + aibj Theo giả thiết: p | cm+k, p | ai, ∀i < k và p | bj, ∀j < m nên p | akbm và
p | ak. Từ đó suy ra p | a(x). Mệnh đề 2.1.2. Giả sử a(x) ∈ Z[[x]]. Nếu a0 là số nguyên tố, thì a(x) là
bất khả quy. ∞
(cid:88) ∞
(cid:88) ∞
(cid:88) Chứng minh. Giả sử a(x) = p(x)q(x)(*) với p(x), q(x) ∈ Z[[x]], trong đó: j=0 j=0 j=0 a(x) = ajxj, p(x) = pjxj, q(x) = qjxj j=0 ajxj = (cid:80)∞ j=0 pjxj.(cid:80)∞ j=0 qjxj nên ta có : Từ (*) suy ra: (cid:80)∞ k+l=i a0 = p0q0
(cid:88) ai = pkql, ∀i Mà a0 là số nguyên tố nên p0 hoặc q0 là các phần tử khả nghịch trong Z.
Theo Mệnh đề 1.1.2 suy ra p(x) hoặc q(x) là khả nghịch trong Z[[x]]. Ví dụ 2.1.3. 2 + 7x + 3x2 bất khả quy trong Z[[x]]. Lưu ý đa thức trên
không bất khả quy trong Z[x]. n=0 pnxn và q(x) = Mệnh đề 2.1.4. Giả sử a(x) ∈ Z[[x]] là phần tử không khả nghịch. Nếu
a0 không là lũy thừa của một số nguyên tố, thì a(x) là khả quy. n=0 qnxn trong Z[[x]] sao cho: Chứng minh. Chúng ta sẽ tìm chuỗi lũy thừa p(x) = (cid:80)∞
(cid:80)∞ a(x) = p(x)q(x).(∗) Vì a0 không là lũy thừa của một số nguyên tố nên nó có thể viết thành tích hai số nguyên không khả nghịch: a0 = mn, với (m, n) = 1. 41 Vì (m, n) = 1 nên tồn tại α, β ∈ Z sao cho 1 = mα+nβ. Khi đó, a(x)
và b(x) được xác định bằng phương pháp quy nạp như sau. Đặt p0 = m và
q0 = n. Từ (*) ta có: a1 = mαa1 + nβa1. Đặt p1 = βa1 và q1 = αa1 thì a1 = p0q1 + p1q0. Như vậy p0, q0, p1 và q1 đã được xác định. Ta tìm p2, q2
thỏa mãn: a2 = p0q2 + p1q1 + p2q0, hay tương đương: a2 − p1q1 = p0q2 + p2q0 = mq2 + np2
⇔ a2(mα + nβ) − p1q1(mα + nβ) = mq2 + np2
⇔ mα(a2 − p1q1) + nβ(a2 − p1q1) = mq2 + np2. Vì 1 = nα + nβ ta có: p2 = β(a2 − p1q1) và q2 = α(a2 − p1q1). Với j = 3,4,5..., bằng quy nạp ta có: j−1
(cid:80)
k=1 j−1
(cid:80)
k=1 pj = β(aj − pkqj=k) và qj = α(aj − pkqj=k). Từ đó, ta thu được a(x) = p(x)q(x). Ví dụ 2.1.5. 6 + x + x2 khả quy trong Z[[x]]. Tuy nhiên đa thức trên bất
khả quy trong Z[x]. Mệnh đề 2.1.6. Nếu mọi phần tử khác không, không khả nghịch của một miền nguyên R có thể viết được thành tích hữu hạn các phần tử nguyên tố thì R là miền phân tích duy nhất. Chứng minh. Giả sử m ∈ R khác không và không khả nghịch, m = t1...tk
với ti nguyên tố. Vì mỗi phần tử nguyên tố đều là bất khả quy nên chúng
ta chỉ cần chứng minh sự phân tích của m là duy nhất. Giả sử m = s1...sj
cũng là sự phân tích của m thành các phần tử bất khả quy. Vì t1 là số
nguyên tố, mà t1 | s1 nên t1 liên kết với s1. Lại vì R là miền nguyên nên
ta có t2...tj và s2...sj là liên kết. Từ đó theo quy nạp ta có k = j và s2...sj
sau khi hoán vị liên kết với t2...tj. Như vậy ta suy ra tính duy nhất. Định nghĩa 2.1.7. Giả sử R là một vành giao hoán.Tập S ⊆ R được gọi 42 là một tập đóng nhân nếu 1 ∈ S và với mọi a, b ∈ S thì ab ∈ S. Ví dụ 2.1.8. (i) Giả sử a ∈ R. Khi đó tập S = {1, a, a2, ...} là tập đóng nhân. (ii) Giả sử P là iđêan nguyên tố của R. Khi đó R\P là một tập đóng nhân. Đặc biệt, nếu R là một miền nguyên thì R\{0} là một tập đóng i=1 Pi là tập đóng nhân. nhân. Tổng quát, giả sử P1, P2, ..., Pn là các iđêan nguyên tố của R. Khi
đó S = R\ ∪n Mệnh đề 2.1.9. [Krull] Giả sử S là tập đóng nhân không chứa phần tử
0 trong vành R. Đặt Ω ={J | J là iđêan của R, J ∩ S = ∅ }. Giả sử I là
phần tử tối đại của Ω. Khi đó, I là iđêan nguyên tố. Chứng minh. Vì 1 ∈ S nên 1 /∈ I ta suy ra I (cid:54)= R. Giả sử, I không là iđêan nguyên tố. Khi đó, tồn tại a, b ∈ R sao cho a (cid:54)∈ I và b (cid:54)∈ I, nhưng ab ∈ I.
Vì (I, a) (cid:33) I nên (I, a) ∩ S (cid:54)= ∅. Do đó tồn tại s ∈ S sao cho s = m + xa,
với m ∈ I và x ∈ R. Tương tự, tồn tại t ∈ S sao cho t = n + yb, với n ∈ I và y ∈ R. Khi đó, st = mn + mya + nxa + abxy ∈ I, Vì I ∩ S = ∅ nên st /∈ S . Điều này kéo theo S không đóng kín với phép
nhân. Điều này vô lý chứng tỏ I là iđêan nguyên tố. Định lý 2.1.10. Miền nguyên R là miền phân tích duy nhất nếu và chỉ nếu mỗi iđêan nguyên tố P khác không trong R chứa một phần tử nguyên tố. Chứng minh. Giả sử R là miền phân tích duy nhất và P là iđêan nguyên tố, P (cid:54)= 0 . Khi đó, P chứa phần tử a (cid:54)= 0 và a không khả nghịch. Ta có a được phân tích thành tích của các phần tử nguyên tố a = p1...pt. Vì a ∈ P
nên một trong các nhân tử pi phải thuộc P . Giả sử mỗi iđêan nguyên tố khác không của R đều chứa một phần tử nguyên tố, S là tập hợp bao gồm tất cả các tích của các phần tử nguyên tố và các phần tử khả nghịch. Rõ ràng, S đóng nhân và S không chứa phần tử 0. Hơn nữa, nếu ab ∈ S thì a ∈ S và b ∈ S. Theo Mệnh đề 2.1.6 ta suy 43 ra S chứa tất cả phần tử khác không của R. Giả sử 0 (cid:54)= c ∈ R và c /∈ S
suy ra (cid:104)c(cid:105) ∩ S = ∅, ta chỉ cần chứng minh iđêan sinh bởi (cid:104)c(cid:105) có tính chất (cid:104)c(cid:105) ∩ S = ∅. Theo bổ đề Zorn’s, c chứa trong iđêan tối đại I với tính chất
I ∩ S = ∅. Theo Mệnh đề 2.1.9, I là iđêan nguyên tố và và theo giả thiết
I chứa phần tử nguyên tố. Điều này kéo theo I ∩ S (cid:54)= ∅, vô lý với giả thiết
về S. Như vậy, c ∈ S và R là một miền phân tích duy nhất. Định lý 2.1.11. Vành Z[[x]] là một miền phân tích duy nhất. Chứng minh. Trong Z[[x]], ta sẽ chứng minh mọi iđêan nguyên tố khác
không trong Z[[x]] thì sinh ra bởi x, hoặc p, với p là phần tử nguyên tố,
hoặc a(x) với a(x) nguyên tố. Điều này kéo theo mỗi iđêan nguyên tố khác
không trong Z[[x]] đều chứa phần tử nguyên tố. Do đó Định lý 2.1.11 được
suy ra từ Định lý 2.1.10 với R = Z[[x]]. Giả sử P là iđêan nguyên tố khác không trong Z[[x]] . Ta xét hai
trường hợp: x ∈ P và x (cid:54)∈ P . Giả sử x ∈ P . Nếu P = (cid:104)x(cid:105) chúng ta có điều cần chứng minh. Nếu ∃a(x) ∈ P với a0 (cid:54)= 0 thì a0 = a(x) − x(a1 + a2x + a3x2 + ...) ∈ P. Vì P là iđêan thực sự nên a0 không khả nghịch trong Z. Do đó a0 phân tích
thành tích các phần tử nguyên tố, với ít nhất một phần tử trong tích đó nằm trong P . Gọi số nguyên tố đó là p. Khi đó, (cid:104)p, x(cid:105) ⊆ P . Mặt khác, nếu b(x) ∈ P và b0 (cid:54)= 0 thì b0 ∈ P . Nếu p không chia hết cho b0 thì UCLN(b0,
p) = 1 ∈ P , mâu thuẫn. Như vậy p | b0 và P = (cid:104)p, x(cid:105). Trường hợp còn lại: x (cid:54)∈ P . Nếu a(x) là phần tử khác không trong P , ta có a(x) = xm(b0 + b1x + b2x2 + ...), với b0 (cid:54)= 0. Vì P là nguyên tố và x (cid:54)∈ P nên (b0 + b1x + b2x2 + ...) ∈ P. Ta có: f : Z[[x]] −→ Z a(x) (cid:55)−→ a0 44 là một đồng cấu vành. Khi đó, ảnh P ∗ của P qua đồng cấu vành f là
một iđêan khác không trong Z. Giả sử P ∗ = (cid:104)q(cid:105), ta chọn q(x) ∈ P với q0 = q. Trước hết ta chứng minh q là lũy thừa của một số nguyên tố.
Bằng phản chứng, giả sử trên là sai. Khi đó q = st với s và t không khả nghịch và UCLN(s, t) = 1. Tương tự như chứng minh Mệnh đề 2.1.4, ta có q(x) = s(x)t(x) với s0 = s và t0 = t. Vì P nguyên tố và s(x)t(x) ∈ P nên
một trong 2 phần tử s(x) hoặc q(x) phải nằm trong P . Giả sử s(x) ∈ P do đó q | s0 = s, điều này vô lí với (*) . Như vậy q phải là lũy thừa của số
nguyên tố. Chúng ta chứng minh P = (cid:104)q(x)(cid:105). Rõ ràng q(x) ⊆ P . Giả sử b1(x) ∈ P . Vì (b1)0 ∈ P ∗ = (cid:104)q(cid:105) nếu (b1)0 = kq, k ∈ Z. Ta có b1(x) − k1q(x) = xb2(x) ∈ P, với k1 ∈ Z. Vì x (cid:54)∈ P nên b2(x) ∈ P . Tương tự, ∃k2 ∈ Z sao cho b2(x) − k2q(x) = xb3(x) ∈ P. Tiếp tục quá trình trên ta thu được: b1(x) = k1q(x) + xb2(x) = k1q(x) + x(k2q(x) + xb3(x)) = ... = q(x)(k1 + k2x + k3x2 + ....) ∈ (cid:104)q(x)(cid:105) Do P là iđêan nguyên tố nên q(x) là phần tử nguyên tố. Vì vậy P chứa
một phần tử nguyên tố. Vậy theo Định lí 2.1.10 ta có Z[[x]] là là một miền
phân tích duy nhất. 2.2. Tiêu chuẩn về tính bất khả quy Ở phần này, đưa ra một số tiêu chuẩn về tính bất khả quy bên cạnh những tiêu chuẩn đã được trình bày ở phần trước. Chúng ta đều biết rằng
Mệnh đề 2.1.2 nếu a0 là số nguyên tố trong Z, thì a(x) = (cid:80)∞
j=0 ajxj là bất
khả quy trong Z[[x]]. Hơn nữa, nếu a0 = pq với (p, q) = 1, p và p đều khác
1 thì a(x) là khả quy. Như vậy ta chỉ cần xét những chuỗi lũy thừa hình
thức có a0 = pµ, với p là số nguyên tố và số nguyên dương µ > 1. Để trình
bày ngắn gọn, ta chỉ xét trường hợp khi a0 = p2. Trường hợp tổng quát
được chứng minh tương tự. 45 Giả sử, a(x) = (cid:80) anxn là một phần tử của Z[[x]] với a0 = p2, trong (cid:88) (cid:88) đó p là nguyên tố. Nếu a(x) = ( bjxj)( cjxj), với | b0 |(cid:54)= 1 và | c0 |(cid:54)= 1 thì b0 = c0 = ±p và a1 = ±p(b1 + c1). Nói cách
khác, Nếu p không chia hết a1, thì a(x)là bất khả quy Xét đa thức dạng đơn giản a(x) = p2 + a1x. Nếu p (cid:45) a1 thì theo trên a(x)
bất khả quy. Ngược lại, giả sử p | a1 thì suy ra a(x) = p(p + a1
p x) nên a(x)
không bất khả quy. Vậy với a(x) = p2 + a1x thì a(x) là bất khả quy nếu
và chỉ nếu p (cid:45) a1. Tuy nhiên, các đa thức bậc cao hơn thì điều kiện trên là
điều kiện đủ, chưa là điều kiện cần. (cid:19)(cid:18) (cid:18) (cid:80) bjxj (cid:80) cjxj Ví dụ, dễ dàng kiểm tra được rằng a(x) = 4 + 2x + 3x2 là bất khả
(cid:19) . quy. Thật vậy, giả sử a(x) khả quy ta suy ra a(x) = Từ đó ta có: b0c0 = 4
b1c0 + b0c1 = 2
b2c0 + b1c1 + b0c2 = 3
|b0| (cid:54)= 1, |c0| (cid:54)= 1
Điều này kéo theo b0 = c0 = ±2
2 = ±2(b1 + c1)
±2(b2c2) + b1c1 = 3 Từ trên suy ra b1c1 ...2, đó là điều vô lý. Vậy a(x) là bất khả quy.
Lưu ý: Tiêu chuẩn tương tự cho các đa thức có dạng p2 + a1x + a2x2
với p | a1 và p (cid:45) a2 là không đúng. Ví dụ 4 − x2 và 4 + 4x + x2 khả quy
trong khi 4 + 4x + 3x2 là bất khả quy. Tuy nhiên, với đa thức bậc hai ta có tiêu chuẩn sau: 2
(cid:80)
n=1 Bổ đề 2.2.1. Giả sử a(x) = ajxj với a0 = p2, với p là số nguyên tố 46 và giả sử p | a1. Nếu a2 (cid:54)≡ αβ ( mod p), với mọi α, β ∈ Z/pZ thỏa mãn
a1/p ≡ α + β ( mod p), thì a(x) là bất khả quy. Chứng minh. Giả sử a(x) không bất khả quy. Khi đó a(x) = ((cid:80) bnxn)((cid:80) cnxn)
với | b0 |(cid:54)= 1 và | c0 |(cid:54)= 1. Từ đó ta có a1 = ±p(b1 + c1). Cho α ≡ ±b1(
mod p) và β ≡ ±c1( mod p). Vì vậy, a1/p ≡ α + β ( mod p) và a2 ≡ αβ(
mod p). Xét trường hợp đặc biệt p = 2, tức là a(x) = 4 + a1x + a2x2 với 2 | a1
và 2 (cid:45) a2. Giả sử tồn tại α, β ∈ Z/pZ sao cho a1/2 ≡ α + β ≡ 1 ( mod 2),
thì α và β có tính chẵn lẻ khác nhau. Do đó αβ ≡ 0 ( mod 2). Điều này kéo theo αβ (cid:54)≡ a2 (cid:54)≡ 0 ( mod 2). Từ Bổ đề 2.2.1 ta có a(x) là bất khả quy.
Với số nguyên tố p là lẻ, ta cũng có tiêu chuẩn tương tự. Giả sử
a(x) = (cid:80) ajxj với a0 = p2 khả quy. Từ Bổ đề 2.2.1, tồn tại α, β ∈ Z/pZ
với a1/p ≡ α + β ( mod p) và a2 ≡ αβ( mod p). Từ đó: (a1/p)2 − 4a2 ≡ (α + β)2 − 4αβ ≡ (α − β)2( mod p). Vì vậy (a1/p)2 − 4a2 là một thặng dư bậc hai ( mod p). Như vậy: Nếu (a1/p)2 − 4a2 không là một thặng dư bậc hai ( mod p) , thì
a(x) là bất khả quy Từ trên ta có, đa thức a(x) = p2 + a1x + a2x2 với p | a1 bất khả quy trong
các trường hợp sau: a1/p
p
a2
3
0 ( mod p)
1 ( mod p)
3 ±1( mod p)
2 ( mod p)
0 ( mod p)
5
2 hoặc 3 ( mod p)
5 ±1( mod p)
1 hoặc 2 ( mod p)
5 ±2( mod p)
3 hoặc 4 ( mod p)
1 hoặc 2 hoặc 4 ( mod p)
0 ( mod p)
7
7 ±1( mod p) 3 hoặc 4 hoặc 6 ( mod p)
7 ±2( mod p) 2 hoặc 3 hoặc 5 ( mod p)
7 ±3( mod p) 1 hoặc 5 hoặc 6 ( mod p) Bổ đề sau cho ta một tiêu chuẩn về tính bất khả quy trong Z[[x]] 47 của các đa thức bậc 3 và bậc 4 với a0 = p2.
Bổ đề 2.2.2. Giả sử a(x) = (cid:80) anxn với a0 = p2, trong đó p nguyên tố,
p2 | a1 và p | a2. Nếu p (cid:45) a3, thì a(x) là bất khả quy. Hơn nữa, nếu p | a3,
a4 (cid:54)≡ αβ( mod p), với mọi α, β ∈ Z/pZ, sao cho a2/p ≡ α + β ( mod p),
thì a(x) là bất khả quy. Chứng minh. Nếu a(x) = ((cid:80) bnxn)((cid:80) cnxn) với | b0 |(cid:54)= 1 và | c0 |(cid:54)= 1, thì
b0 = c0 = ±p, a1 = ± p(b1 + c1), a2 = ± p(b2 + c2) + b1c1, a3 = ± p(b3 + c3) + b1c2 + b2c1. Vì p | a2 nên p | b1c1 kéo theo p | b1 hoặc p | c1. Mà p2 | a1 nên p | (b1 + c1).
Như vậy, p chia hết cả b1 và c1. Điều này kéo theo p | a3. Do đó, a(x) là
bất khả quy nếu p (cid:45) a3. Để chứng minh mệnh đề thứ hai, cần lưu ý rằng b1c1 ≡ 0( mod p2),
có a2/p ≡ ±(b2 + c2)( mod p). Cho α ≡ ±b2( mod p) và β ≡ ±c2(
mod p). Vì a4 = ±p(b4 +c4)+b1c3 +b2c2 +b3c1 theo bảng , và vì b1 = c1 = 0(
mod p) nên ta có a4 ≡ αβ( mod p). Chú ý: Điều kiện p2 | a1 không suy ra p | a1 theo bảng. Đa thức
bậc ba p2 + px + px2 + x3 có thể phân tích thành (p + x)(p + x2), đa thức
9 + 3x + 3x3 + x4 phân tích thành (3 + x)(3 + x2) mặc dù điều kiện của hệ số thứ 3 và thứ 4 trong Bổ đề 2.2.2 được thỏa mãn. Bổ đề trên có thể tổng quát được như sau. Đây cũng là kết quả chính của mục. Định lý 2.2.3. Giả sử a(x) = (cid:80) ajxj ∈ Z[[x]] với a0 = p2, trong đó p là
số nguyên tố. Giả sử với mỗi m ta có p2 | aj với j = 1, ..., m và p | aj
với mọi số chẵn j ∈ {m + 1, ..., 2m}. Nếu p (cid:45) a2m+1, hoặc nếu p | a2m+1
nhưng a2m+1 (cid:54)≡ αβ( mod p), ∀α, β ∈ Z/pZ với am+1/p ≡ α + β( mod p),
thì a(x) là bất khả quy. j
(cid:88) j−1
(cid:88) Chứng minh. Giả sử a(x) = ((cid:80) bnxn)((cid:80) cnxn) với | b0 |(cid:54)= 1 và | c0 |(cid:54)= 1.
Như vậy, b0 = c0 = ±p, và mỗi hệ số của a(x) có dạng: k=0 k=1 aj = bkcj−k = ±p(bj + cj) + bkcj−k. Ta sẽ chứng minh rằng : 48 p | bj và p | cj với j = 1, ..., m.(1) Điều này kéo theo p | a2m+1 vì: a2m+1 = ±p(b2m+1 + c2m+1) + b1c2m + ... + bmcm+1 + bm+1cm + ... + b2mc1. m
(cid:88) Như vậy, nếu p (cid:45) a2m+1 thì a(x) là bất khả quy là điều cần chứng minh.
Hơn nữa, nếu (1) đúng, thì k=1 bkcm+1−k ≡ 0( mod p2). Vì vậy, am+1/p ≡ ±(bm+1 + cm+1)( mod p). Lấy α, β ∈ Z/pZ sao cho
α ≡ ±bm+1( mod p) và β ≡ ±cm+1( mod p). Ta có am+1/p ≡ α + β(
mod p). Vì a2m+2 = ±p(b2m+2 + c2m+2) + b1c2m+1 + ... + bm+1cm+1 + ... + b2m+1c1. Từ (1) suy ra a2m+2 ≡ αβ ( mod p). Như vậy, nếu a2m+2 (cid:54)≡ αβ( mod p), ∀α, β ∈
Z/pZ sao cho am+1/p ≡ α + β( mod p), thì a(x) là bất khả quy. Tiếp theo, ta chứng minh (1). Giả sử (1) sai, lấy k ≤ m là chỉ số nhỏ
nhất sao cho p (cid:45) bk hoặc p (cid:45) ck. Như vậy, p | bj và p | cj với j = 1, ..., k − 1.
Vì ak = ±p(bk + ck) + b1ck1 + ... + bk−1c1 và p2 | ak nên p | bk + ck. Mặt khác vì a2k = ±p(b2k + c2k) + b1c2k−1 + ... + bkck + ... + b2k−1c1 49 và p | a2k nên p | bkck. Điều này kéo theo p | bk và p | ck, mâu thuẫn với
giả thiết. Vậy (1) đúng. Luận văn đạt được một số kết quả như sau: - Hệ thống một số kiến thức cơ bản về chuỗi lũy thừa hình thức: Định nghĩa chuỗi lũy thừa hình thức; các phép toán, các toán tử và phép
truy toán cho chuỗi lũy thừa hình thức C[[x]]. - Ứng dụng của chuỗi lũy thừa hình thức trong một số bài toán đếm thông qua hai phương pháp đếm dùng hàm sinh. - Tìm hiểu tính phân tích duy nhất của Z[[x]].
- Tìm hiểu một số tiêu chuẩn bất khả quy của chuỗi lũy thừa hình thức với hệ số nguyên. Tiếng Việt [1] Ngô Đắc Tân (2004), Lý thuyết tổ hợp và đồ thị, Nhà xuất bản Đại học Quốc gia Hà Nội. Tiếng Anh [2] D. Birmajer and J. B. Gil (2008), "Arithmetic in the ring of for-
mal power series with integer coefficients" American Mathematical
Monthly, 115(6), 541-549. [3] J. Brewer (1981), Power Series Over Commutative Rings, Lecture
Notes in Pure and Applied Mathematics, vol. 64, Marcel Dekker, New
York. [4] D. Dummit and R. Foote (1991), Abstract Algebra, Prentice-Hall, En- glewood Cliffs, NJ. [5] M.A. Lerma (2016), Putnam training generating functions, Northwest- ern University Mathematics Department. [6] P. Samuel (1961), "On unique factorization domains", Illinois J. Math., 5, 1-17. [7] Q. Yuan (2009), Topics in generating functions, Massachusetts Insti- tute of Technology.Chương 2
Tính bất khả quy của chuỗi lũy thừa
hình thức
KẾT LUẬN
Tài liệu tham khảo
