anh_phuong_22393
New Member
Download miễn phí Ebook Tuyển tập các chuyên đề tổ hợp
MỤC LỤC
Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Sử dụng phép đếm để chứng minh các đẳng thức tổ hợp
Nguyễn Tất Thu . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Phương pháp đếm bằng hai cách
Phan Đức Minh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Phương pháp xây dựng mô hình trong giải toán tổ hợp
Lê Phúc Lữ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Phương pháp hàm sinh
Hoàng Minh Quân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Phương pháp hàm sinh
Lê Hữu Phước, Trần Nguyễn Quốc Cường . . . . . . . . . . . . . . . . . . . . 69
Giải toán tổ hợp bằng đại lượng bất biến
Trần Gia Huy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Một số bài toán tô màu
Lê Tuấn Linh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Cực trị và bất đẳng thức rời rạc
Nguyễn Hiền Trang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Một số bài toán tổ hợp điển hình về bàn cờ
Nguyễn Việt Dũng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Số Stirling loại hai
Hoàng Minh Quân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ho Bn = {0}.4. Lời giải
Bài tập 1. Cho số tự nhiên n. Tính tổng:
∞∑
i=0
(
n
i
)(
n− i
i
)
2n−2i
85
Lời giải. Ta có:
an =
∞∑
i=0
(
n
i
)(
n− i
i
)
2n−2i
là hệ số tự do trong khai triển:
∞∑
i=0
(
n
i
)
2n−2i(1 + x)n−i
xi
=
∞∑
i=0
(
n
i
)
(2 + 2x)n−i
(2x)i
=
(
2x+ 2 +
1
2x
)n
=
(2x+ 1)2n
(2x)n
Do đó suy ra:
an =
(
2n
n
)
r
Bài tập 2. Cho số tự nhiên n. Tính tổng:
n∑
i=0
(
n
i
)(
n− i⌊
n−i
2
⌋)
Lời giải. Ta có
( n−i
⌊n−i2 ⌋
)
là hệ số tự do trong khai triển của (x+ 1)
(
x+ 1
x
)n−i.
Do đó: ∞∑
k=0
(
n
k
)(
n− k⌊
n−k
2
⌋)2k
là hệ số tự do trong khai triển:
∞∑
k=0
(
n
k
)
(1 + x)
(
x+
1
x
)n−k
2k = (1 + x)
(
x+
1
x
+ 2
)n
=
(1 + x)2n+1
xn
Suy ra:
∞∑
k=0
(
n
k
)(
n− k⌊
n−k
2
⌋)2k = (2n+ 1
n
)
r
Bài tập 3. Cho m,n là hai số tự nhiên. Tính tổng:
∞∑
k=0
(
n
k
)(
n− k⌊
m−k
2
⌋)
Lời giải. Chú ý rằng
( n−k
⌊m−k2 ⌋
)
là hệ số tự do trong khai triển của:
yn−m(1 + y)
(
y +
1
y
)n−k
86
Do đó: ∞∑
k=0
(
n
k
)(
n− k
⌊m−k
2
⌋
)
xk
là hệ số tự do trong khai triển theo y của:
∞∑
k=0
(
n
k
)
yn−m(1 + y)
(
y +
1
y
)n−k
xk = (1 + y)yn−m
∞∑
k=0
(
n
k
)(
y +
1
y
)n−k
xk
= (1 + y)yn−m
(
x+ y +
1
y
)n
=
(1 + y)(xy + y2 + 1)n
ym
Từ đó ta có được cách tính tổng đã cho. r
Bài tập 4. Cho số tự nhiên n. Tính tổng
n∑
k=0
(
2n
2k
)(
2k
k
)
22n−2k
Lời giải. (i) Cách 1. Ta có
2n
2k
)(
2k
k
)
=
(2n)!
(2k)!(2n− 2k)! ·
(2k)!
(k!)2
=
(2n)!
(2n− k)!k! ·
(2n− k)!
(2n− 2k)!k!
=
(
2n
k
)(
2n− k
k
)
Do đó:
n∑
k=0
(
2n
2k
)(
2k
k
)
22n−2k
là hệ số tự do trong khai triển:
2n∑
k=0
(
2n
k
)
22n−2k(x+ 1)2n−k
xk
= (2x+ 2)2n
2n∑
k=0
(
2n
k
)
1
(4x2 + 4x)k
= (2x+ 2)2n
(
1 +
1
4x2 + 4x
)2n
=
(2x+ 1)4n
(2x)2n
Tức là:
n∑
k=0
(
2n
2k
)(
2k
k
)
22n−2k =
(
4n
2n
)
(ii) Cách 2. Ta có
(
2k
k
)
là hệ số tự do trong khai triển (x+1)
2k
xk
. Như vậy ta có:
n∑
k=0
(
2n
2k
)(
2k
k
)
22n−2k
87
là hệ số tự do trong khai triển của
n∑
k=0
(
2n
2k
)
(1 + x)2k
xk
22n−2k
tức là hệ số tự do trong khai triển:
22n−1
((
1 +
1 + x
2
√
x
)2n
+
(
1− 1 + x
2
√
x
)2n)
=
(1 +
√
x)4n + (1−√x)4n
2xn
Ta có đáp số là
(
4n
2n
)
.
(iii) Cách 3. Xét hàm sau:
F (x) =
∞∑
n=0
xn
n∑
k=0
(
2n
2k
)(
2k
k
)
22n−2k
=
∞∑
k=0
1
22k
(
2k
k
) ∞∑
n=k
(
2n
2k
)
(2
√
x)2n
Ta có: (
2n
2k
)
(2
√
x)2n =
1
2
(2
√
x)2k
(
1
(1− 2√x)2k+1 +
1
(1 + 2
√
x)2k+1
)
Như vậy:
F (x) =
1
2(1− 2√x)
∞∑
k=0
(
2k
k
)(
x
(1− 2√x)2
)k
+
1
2(1 + 2
√
x)
∞∑
k=0
(
2k
k
)(
x
(1 + 2
√
x)2
)k
=
1
2(1− 2√x)
1√
1− 4x
(1−2√x)2
+
1
2(1 + 2
√
x)
1√
1− 4x
(1+2
√
x)2
=
1
2
√
1− 4√x +
1
2
√
1 + 4
√
x
=
1
2
∞∑
n=0
(
2n
n
)√
x
n
+
1
2
∞∑
n=0
(
2n
n
)
(−√x)n
=
∞∑
n=0
(
4n
2n
)
xn
Ta thu được điều cần chứng minh. r
Bài tập 5. Cho m,n là hai số nguyên dương. Chứng minh rằng:
m∑
k=0
(
2m− k
m+ n
)
2k = 4m −
n∑
j=1
(
2m+ 1
m+ j
)
Lời giải. Ta có:
22m+1 =
2m+1∑
i=0
(
2m+ 1
i
)
= 2
2m+1∑
i=m+1
(
2m+ 1
i
)
88
Suy ra:
4m =
2m+1∑
i=m+1
(
2m+ 1
i
)
Như vậy ta được:
4m −
n∑
j=1
(
2m+ 1
m+ j
)
=
2m+1∑
j=m+n+1
(
2m+ 1
j
)
Ta đặt:
at =
2m+1∑
j=t+1
(
2m+ 1
j
)
Xét hàm sinh:
F (x) =
∞∑
t=0
atx
t
Vậy:
F (x) =
∞∑
t=0
2m+1∑
j=t+1
(
2m+ 1
j
)
xt
=
2m+1∑
j=1
j−1∑
t=0
(
2m+ 1
j
)
xt
=
2m+1∑
j=1
(
2m+ 1
j
)
xj − 1
x− 1
=
1
x− 1
(
2m+1∑
j=0
(
2m+ 1
j
)
xj −
2m+1∑
j=0
(
2m+ 1
j
))
=
1
x− 1
(
(1 + x)2m+1 − 22m+1)
= (1 + x)2m + 2(1 + x)2m−1 + · · ·+ 22m
Từ đó ta được hệ số của xt trong khai triển của F là:
at =
2m∑
j=0
(
j
t
)
22m−j
Suy ra đẳng thức cần chứng minh. r
Bài tập 6. Tìm công thức tổng quát của dãy số (an,k) xác định như sau: an,0 = 2n+1, a0,k = 1,
với n > 0 và k > 1, ta có:
an+1,k = an,k + an,k−1 + · · ·+ an,0
Lời giải. Ta có:
an+1,k+1 = an,k+1 + an,k + · · ·+ an,0
= an,k+1 + an+1,k
89
Xét hàm sinh:
F (x, y) =
∞∑
n=0
∞∑
k=0
an,kx
nyk
=
∞∑
n=0
an,0x
n +
∞∑
k=0
a0,ky
k − 1 +
∞∑
n=1
∞∑
k=1
an,kx
nyk
=
∞∑
n=0
an,0x
n +
∞∑
k=0
a0,ky
k − 1 +
∞∑
n=1
∞∑
k=1
(an−1,k + an,k−1)xnyk
=
∞∑
n=0
an,0x
n +
∞∑
k=0
a0,ky
k − 1 + y
∞∑
n=1
∞∑
k=0
an,kx
nyk + x
∞∑
n=0
∞∑
k=1
an,kx
nyk
Ngoài ra ta có:
∞∑
n=0
an,0x
n =
∞∑
n=0
(2n+ 1)xn
= 2
∞∑
n=0
(n+ 1)xn −
∞∑
n=0
xn
=
2
(1− x)2 −
1
1− x
∞∑
k=0
a0,ky
k =
∞∑
k=0
yk
=
1
1− y
y
∞∑
n=1
∞∑
k=0
an,kx
nyk = y
(
F (x, y)−
∞∑
k=0
a0,ky
k
)
= yF (x, y)− y
1− y
x
∞∑
n=0
∞∑
k=1
an,kx
nyk = x
(
F (x, y)−
∞∑
n=0
an,0x
n
)
= xF (x, y)− x
2 + x
(1− x)2
Như vậy ta suy ra:
F (x, y) =
1 + x
(1− x)(1− x− y)
=
1 + x
1− x
∞∑
t=0
(x+ y)t
=
1 + x
1− x
∞∑
k=0
yk
∞∑
t=k
(
t
k
)
xt−k
=
1 + x
1− x
∞∑
k=0
yk
(1− x)k+1
Vậy an,k bằng hệ số của xn trong khai triển của 1+x(1−x)k+2 tức là:
an,k =
(
n+ k + 1
k + 1
)
+
(
n+ k
k + 1
)
90
r
Bài tập 7. Cho số tự nhiên n. Biết rằng các phương trình ix + (i + 1)y = n + 1 − i có đúng
Ri nghiệm (x, y) ∈ N2 với mọi 1 6 i 6 n+ 1. Chứng minh rằng:
n+1∑
k=1
Ri = n+ 1
Lời giải. Ta có Ri là hệ số tự do trong khai triển của:
1
xn+1−i(1− xi)(1− xi+1)
=
(1− xi+1)− (1− xi)
(1− x)xn+1(1− xi)(1− xi+1)
=
1
xn+1(1− x)
(
1
1− xi −
1
1− xi+1
)
Như vậy:
n+1∑
k=1
Ri
là hệ số tự do trong khai triển:
1
xn+1(1− x)
(
1
1− x −
1
1− xn+2
)
=
1
xn+1
∞∑
k=0
xk
( ∞∑
k=0
xk −
∞∑
k=0
xk(n+2)
)
tức là hệ số tự do trong khai triển:
1
xn
(1 + x+ x2 + · · ·+ xn)2
Từ đó ta có:
n+1∑
k=1
Ri = n+ 1
r
Bài tập 8. Cho dãy (an) xác định bởi a1 = 0, a2 = 1, và với mọi n > 3:
an =
nan−1
2
+
n(n− 1)an−2
2
+
(−1)n−1n
2
+ (−1)n
Tính tổng
an + 2
(
n
1
)
an−1 + · · ·+ n
(
n
n− 1
)
a1
Lời giải. Bổ sung thêm a0 = 1.
Đặt bn = ann! . Khi đó:
bn =
bn−1
2
+
bn−2
2
+
(−1)n
n!
+
(−1)n−1
2(n− 1)!
91
Khi đó, xét:
F (x) =
∞∑
k=0
bkx
k
Ta có:
F (x) = 1 +
x2
2
+
∞∑
k=3
bkx
k
= 1 +
x2
2
+
∞∑
k=3
(
bk−1
2
+
bk−2
2
+
(−1)k
k!
+
(−1)k−1
2(k − 1)!
)
xk
= 1 +
x2
2
+
x
2
(F (x)− 1) + x
2
2
(F (x)− 1) + e−x − 1 + x− x
2
2
+
x
2
(e−x − 1 + x)
Suy ra:
F (x) =
e−x
1− x
Ta tính tổng:
an + 2
(
n
1
)
an−1 + · · ·+ n
(
n
n− 1
)
a1 + (n+ 1)
(
n
n
)
a0
=n!
n∑
i=0
(i+ 1)bn−i
i!
Dễ thấy:
n∑
i=0
(i+ 1)bn−i
i!
là hệ số của xn trong khai triển của:
∞∑
k=0
bkx
k
∞∑
k=0
k + 1
k!
xk
=
e−x
1− x(xe
x + ex)
=1 +
2x
1− x
=1 + 2x+ 2x2 + · · ·
Vậy ta có kết quả:
an + 2
(
n
1
)
an−1 + · · ·+ n
(
n
n− 1
)
a1 = 2n!− n− 1
r
Bài tập 9. Đếm số đường đi với k bước đi để đi từ (0, 0) đến (m,n) sao cho mỗi bước đi là đi
từ (i, j) đến đúng một trong bốn vị trí (i− 1, j), (i+ 1, j), (i, j − 1), (i, j + 1).
Lời giải. Điều kiện tồn tại đường đi là k +m+ n chẵn và k > m+ n.
Xét hàm:
f(x, y) =
(
x+ y +
1
x
+
1
y
)k
92
Hệ số của xmyn trong f chính là số đường đi cần tìm.
Ta có:
f(x, y) = (x+ y)k
(
1 +
1
xy
)k
= (x+ y)k
k∑
t=0
1
(xy)t
(
k
t
)
Như vậy ta cần tìm hệ số của xrys trong (x + y)k với r, s thỏa mãn r − s = m− n, r + s = k.
Tức là:
r =
k +m− n
2
s =
k −m+ n
2
Từ đó suy ra hệ số của xmyn trong f là
k
k+m−n
2
)(
k
k−m−n
2
)
Ta có kết quả cần tìm. r
Bài tập 10. Cho 2n số thực phân biệt a1, a2, . . . , an và b1, ...