Bài giảng Hàm sinh - Toán rời rạc thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

Hàm sinh là một trong những sáng tạo thần tình, bất ngờ, nhiều ứng dụng của toán rời rạc. Nói một cách nôm na, hàm sinh chuyển những bài toán về dãy số thành những bài toán về hàm số. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

Hàm sinh
Trần Vĩnh Đức
HUST
Ngày 26 tháng 4 năm 2016
1 / 51
Nội dung
Đếm đa thức
Định nghĩa hàm sinh
Các phép toán trên hàm sinh
Một bài toán đếm
hiệu hình thức
2 quả táo, 3 quả mận, 4 quả đào.
Ta hiệu
T := “lấy một quả táo”
M := “lấy một quả mận”
D := “lấy một quả đào”.
Lấy 1 quả táo, 2 quả mận, 3 quả đào:
TMMDDD = TM
2
D
3
.
Lấy 1 quả táo, 1 quả mận, 1 quả đào hoặc lấy 1 quả táo, 1
quả đào, 2 quả mận”:
TMD + TMD
2
.
3 / 51
Câu hỏi
Xâu sau đây biểu diễn những lựa chọn gì?
TMD + TMD
2
+ TM
2
D + T
2
MD + TM
2
D
2
+ · · · + T
2
M
3
D
4
= (T + T
2
)(M + M
2
+ M
3
)(D + D
2
+ D
3
+ D
4
).
Lời giải
Đây như một chuỗi hình thức tả mọi khả năng chọn trong số 2
quả táo, 3 quả mận, 4 quả đào, mỗi loại ít nhất một quả.
4 / 51
Bài tập
bao nhiêu cách chọn 6 quả trong số 2 quả táo, 3 quả mận, 4
quả đào, mỗi loại ít nhất một quả?
Lời giải
Ta chỉ cần thay thế mỗi T, M, D bằng biến hình thức x trong
chuỗi
(T + T
2
)(M + M
2
+ M
3
)(D + D
2
+ D
3
+ D
4
).
Vy mọi số hạng số 6 ứng với số lần x
6
xuất hiện.
Hệ số của x
6
chính số cách chọn 6 quả.
5 / 51
Đa thức đếm
Khi thay thế T, M, D bằng x thì hệ số của x
k
chính số cách
chọn đúng k quả.
Ta
(x + x
2
)(x + x
2
+ x
3
)(x + x
2
+ x
3
+ x
4
)
= x
3
(1 + x)(1 + x + x
2
)(1 + x + x
2
+ x
3
)
= x
3
(1 + 2x + 2x
2
+ x
3
)(1 + x + x
2
+ x
3
)
= x
3
+ 3x
4
+ 5x
5
+ 6x
6
+ 5x
7
+ 3x
8
+ x
9
.
Vy 6 cách lựa chọn 6 quả, 5 cách chọn 7 quả . . . .
6 / 51
Câu hỏi
Giả sử một quả mận 20 calo, một quả đào 40 calo,
một quả táo 60 calo.
Nếu ta thay thế
T x
60
, M x
40
D x
20
trong chuỗi hình thức
(T + T
2
)(M + M
2
+ M
3
)(D + D
2
+ D
3
+ D
4
).
thì hệ số của x
n
gì?
7 / 51
Lời giải
Ta thay thế
T x
60
, M x
40
D x
20
Vy thì hệ số của x
n
của đa thức số cách chọn quả để n
calo.
khi chọn T
i
M
j
D
k
ta được 60i + 40j + 20k calo.
8 / 51
dụ
Từ đa thức
(x
60
+ x
120
)(x
40
+ x
80
+ x
120
)(x
20
+ x
40
+ x
60
+ x
80
)
= x
120
(1 + x
20
+ 2x
40
+ 3x
60
+ 3x
80
+ 4x
100
+ 3x
120
+ 3x
140
+ 2x
160
+ x
180
+ x
200
)
= x
120
+ x
140
+ 2x
160
+ 3x
180
+ 3x
200
+ 4x
220
+ 3x
240
+ 3x
260
+ 2x
280
+ x
300
+ x
320
Ta thấy 3 cách chọn quả để 200 calo.
9 / 51
Bài tập
Biết rằng quả táo giá 60 đồng, quả mận giá 40 đồng, đào
giá 20 đồng.
bao nhiêu cách chọn các quả giá 200 đồng, thể loại
quả không được chọn?
10 / 51
Bài tập
y tìm đa thức hệ số x
k
số nghiệm nguyên không âm của
phương trình
x
1
+ x
2
+ x
3
= k.
11 / 51
Câu hỏi
Ta thể dùng kỹ thuật tả phần trước để lựa chọn các quả
táo, đào mận nhưng không hạn chế bao nhiêu quả cần lấy.
T
0
M
0
D
0
+ TM
0
D
0
+ · · · + TMD + TMD
2
+ · · · + T
i
M
j
D
k
+ · · ·
12 / 51
Tính toán hình thức
Việc chọn không, một,. . . tới một số bất kỳ táo (mận, đào )
thể biểu diễn một cách hình thức
T
0
+ T
1
+ T
2
+ · · · + T
i
+ · · ·
M
0
+ M
1
+ M
2
+ · · · + M
j
+ · · ·
D
0
+ D
1
+ D
2
+ · · · + D
k
+ · · ·
Việc chọn táo, đào, mận với số lượng tùy ý thể viết dưới
dạng tích
(
T
0
+ T
1
+ · · ·
)(
M
0
+ M
1
+ · · ·
)(
D
0
+ D
1
+ · · ·
)
.
13 / 51
dụ
Nếu thay thế T, M, D bởi x thì hệ số của x
n
trong tích của ba
chuỗi hạn sau chính số cách chọn đúng n quả.
(1 + x + x
2
+ · · · + x
i
+ · · · )
3
.
14 / 51
Nội dung
Đếm đa thức
Định nghĩa hàm sinh
Các phép toán trên hàm sinh
Một bài toán đếm
Định nghĩa
Hàm sinh của dãy số g
0
, g
1
, g
2
, · · · chuỗi hạn
G(x) = g
0
+ g
1
x + g
2
x
2
+ · · · .
Ta sử dụng hiệu mũi tên hai phía để chỉ tương ứng giữa một
y số hàm sinh của như sau:
g
0
, g
1
, g
2
, · · · g
0
+ g
1
x + g
2
x
2
+ · · · .
16 / 51
Định nghĩa
Ta hiệu [x
n
]G(x) hệ số của x
n
trong hàm sinh
G(x) = g
0
+ g
1
x + g
2
x
2
+ · · · .
nghĩa rằng [x
n
]G(x) = g
n
.
17 / 51
dụ
Dưới đây một vài y số hàm sinh của chúng:
0, 0, 0, 0, · · · 0 + 0x + 0x
2
+ 0x
3
+ · · · = 0
1, 0, 0, 0, · · · 1 + 0x + 0x
2
+ 0x
3
+ · · · = 1
3, 2, 1, 0, · · · 3 + 2x + 1x
2
+ 0x
3
+ · · · = 3 + 2x + x
2
18 / 51
dụ
Hàm sinh cho y hạn 1, 1, 1, · · · chuỗi hình học
G(x) := 1 + x + x
2
+ x
3
+ · · ·
Ta
G(x) = 1 + x + x
2
+ x
3
+ · · · + x
n
+ · · ·
xG(x) = 1 x x
2
x
3
· · · x
n
· · ·
G(x) xG(x) = 1
Vy hàm sinh của y 1, 1, . . .
1
1 x
= G(x) :=
n=0
x
n
.
19 / 51
Bài tập
y tìm công thức đóng cho hàm sinh của các dãy sau:
1. 0, 0, 0, 0, 6, 6, 6, 6, 6, 6, · · ·
2. 1, 0, 1, 0, 1, 0, · · ·
3. 1, 1, 0, 1, 1, 0, 1, 1, 0, · · ·
20 / 51
| 1/51

Preview text:

Hàm sinh Trần Vĩnh Đức HUST Ngày 26 tháng 4 năm 2016 1 / 51 Nội dung Đếm và đa thức Định nghĩa hàm sinh
Các phép toán trên hàm sinh Một bài toán đếm Ký hiệu hình thức
▶ Có 2 quả táo, 3 quả mận, và 4 quả đào. ▶ Ta ký hiệu
T := “lấy một quả táo”
M := “lấy một quả mận”
D := “lấy một quả đào”.
▶ Lấy 1 quả táo, 2 quả mận, và 3 quả đào:
TMMDDD = TM2D3.
▶ Lấy 1 quả táo, 1 quả mận, và 1 quả đào hoặc lấy 1 quả táo, 1
quả đào, và 2 quả mận”:
TMD + TMD2. 3 / 51 Câu hỏi
Xâu sau đây biểu diễn những lựa chọn gì?
TMD + TMD2 + TM2D + T2MD + TM2D2 + · · · + T2M3D4
= (T + T2)(M + M2 + M3)(D + D2 + D3 + D4). Lời giải
Đây như một chuỗi hình thức mô tả mọi khả năng chọn trong số 2
quả táo, 3 quả mận, và 4 quả đào, mỗi loại ít nhất một quả. 4 / 51 Bài tập
Có bao nhiêu cách chọn 6 quả trong số 2 quả táo, 3 quả mận, và 4
quả đào, mỗi loại ít nhất một quả? Lời giải
▶ Ta chỉ cần thay thế mỗi T, M, D bằng biến hình thức x trong chuỗi
(T + T2)(M + M2 + M3)(D + D2 + D3 + D4).
▶ Vậy mọi số hạng có số mũ 6 ứng với số lần x6 xuất hiện.
▶ Hệ số của x6 chính là số cách chọn 6 quả. 5 / 51 Đa thức và đếm
▶ Khi thay thế T, M, D bằng x thì hệ số của xk chính là số cách chọn đúng k quả. ▶ Ta có
(x + x2)(x + x2 + x3)(x + x2 + x3 + x4)
= x3(1 + x)(1 + x + x2)(1 + x + x2 + x3)
= x3(1 + 2x + 2x2 + x3)(1 + x + x2 + x3)
= x3 + 3x4 + 5x5 + 6x6 + 5x7 + 3x8 + x9.
▶ Vậy có 6 cách lựa chọn 6 quả, 5 cách chọn 7 quả . . . . 6 / 51 Câu hỏi
▶ Giả sử một quả mận có 20 calo, một quả đào có 40 calo, và một quả táo có 60 calo. ▶ Nếu ta thay thế T → x60, M → x40 D → x20 trong chuỗi hình thức
(T + T2)(M + M2 + M3)(D + D2 + D3 + D4).
thì hệ số của xn là gì? 7 / 51 Lời giải ▶ Ta thay thế T → x60, M → x40 D → x20
▶ Vậy thì hệ số của xn của đa thức là số cách chọn quả để có n calo.
▶ Vì khi chọn TiMjDk ta được 60i + 40j + 20k calo. 8 / 51 Ví dụ ▶ Từ đa thức
(x60 + x120)(x40 + x80 + x120)(x20 + x40 + x60 + x80)
= x120(1 + x20 + 2x40 + 3x60 + 3x80 + 4x100 + 3x120
+ 3x140 + 2x160 + x180 + x200)
= x120 + x140 + 2x160 + 3x180 + 3x200 + 4x220 + 3x240
+ 3x260 + 2x280 + x300 + x320
▶ Ta thấy có 3 cách chọn quả để có 200 calo. 9 / 51 Bài tập
▶ Biết rằng quả táo giá 60 đồng, quả mận giá 40 đồng, và đào giá 20 đồng.
▶ Có bao nhiêu cách chọn các quả giá 200 đồng, có thể có loại quả không được chọn? 10 / 51 Bài tập
Hãy tìm đa thức có hệ số xk là số nghiệm nguyên không âm của phương trình
x1 + x2 + x3 = k. 11 / 51 Câu hỏi
Ta có thể dùng kỹ thuật mô tả ở phần trước để lựa chọn các quả
táo, đào và mận nhưng không hạn chế bao nhiêu quả cần lấy.
T0M0D0 + TM0D0 + · · · + TMD + TMD2 + · · · + TiMjDk + · · · 12 / 51 Tính toán hình thức
▶ Việc chọn không, một,. . . tới một số bất kỳ táo (mận, đào )
có thể biểu diễn một cách hình thức là
T0 + T1 + T2 + · · · + Ti + · · ·
M
0 + M1 + M2 + · · · + Mj + · · ·
D
0 + D1 + D2 + · · · + Dk + · · ·
▶ Việc chọn táo, đào, mận với số lượng tùy ý có thể viết dưới dạng tích ( ) ( ) ( )
T0 + T1 + · · ·
M0 + M1 + · · ·
D0 + D1 + · · · . 13 / 51 Ví dụ
Nếu thay thế T, M, D bởi x thì hệ số của xn trong tích của ba
chuỗi vô hạn sau chính là số cách chọn đúng n quả.
(1 + x + x2 + · · · + xi + · · · )3. 14 / 51 Nội dung Đếm và đa thức Định nghĩa hàm sinh
Các phép toán trên hàm sinh Một bài toán đếm Định nghĩa
Hàm sinh của dãy số ⟨g0, g1, g2, · · · ⟩ là chuỗi vô hạn
G(x) = g0 + g1x + g2x2 + · · · .
Ta sử dụng ký hiệu mũi tên hai phía để chỉ tương ứng giữa một
dãy số và hàm sinh của nó như sau:
⟨g0, g1, g2, · · · ⟩ ←→ g0 + g1x + g2x2 + · · · . 16 / 51 Định nghĩa
Ta ký hiệu [xn]G(x) là hệ số của xn trong hàm sinh
G(x) = g0 + g1x + g2x2 + · · · .
Có nghĩa rằng [xn]G(x) = gn. 17 / 51 Ví dụ
Dưới đây là một vài dãy số và hàm sinh của chúng:
0, 0, 0, 0, · · · ⟩ ←→ 0 + 0x + 0x2 + 0x3 + · · · = 0
1, 0, 0, 0, · · · ⟩ ←→ 1 + 0x + 0x2 + 0x3 + · · · = 1
3, 2, 1, 0, · · · ⟩ ←→ 3 + 2x + 1x2 + 0x3 + · · · = 3 + 2x + x2 18 / 51 Ví dụ
▶ Hàm sinh cho dãy vô hạn 1, 1, 1, · · · ⟩ là chuỗi hình học
G(x) := 1 + x + x2 + x3 + · · · Ta có G(x) =
1 + x + x2 + x3 + · · · + xn + · · ·
−xG(x) = 1 − x − x2 − x3 − · · · − xn − · · ·
G(x) − xG(x) = 1
▶ Vậy hàm sinh của dãy 1, 1, . . . 1 ∑ = G(x) := xn. 1 − x n=0 19 / 51 Bài tập
Hãy tìm công thức đóng cho hàm sinh của các dãy sau:
1. 0, 0, 0, 0, −6, 6, −6, 6, −6, 6, · · · ⟩
2. 1, 0, 1, 0, 1, 0, · · · ⟩
3. 1, 1, 0, 1, 1, 0, 1, 1, 0, · · · ⟩ 20 / 51