Trường Đại học Hoa Lư
KHÓA LUẬN TỐT NGHIỆP
"PHÂN DẠNG CÁC BÀI TOÁN ĐẠI SỐ
TỔ HỢP TRONG CHƯƠNG TRÌNH
TOÁN TRUNG HỌC PHỔ THÔNG’’
SVTH: Đinh Thị Ngát
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
LỜI MỞ ĐẦU
Toán tổ hợp là một lĩnh vực toán học được nghiên cứu từ khá sớm và
ngày càng được quan tâm nhờ vai trò quan trọng của nó trong nội bộ toán học
cũng như trong các nghành khoa học khác. Kết quả quan trọng của nó đánh dấu
bởi bài toán đếm số phân hoạch cuả Leonhard Euler. Trong toán học những kết
quả của nó đóng vai trò kiến thức nền tảng của giải tích, xác suất, thống kê, hình
học,…
Trong thực tiễn giáo dục thì việc dạy và học toán tổ hợp cũng rất quan
trọng bởi khi học tốt toán tổ hợp người học sẽ có năng lực sáng tạo và tư duy
nhạy bén để học tốt môn học khác cũng như các lĩnh vực khác trong cuộc sống.
Các bài toán đại số tổ hợp luôn là một nội dung quan trọng trong các đề thi đại
học và cao đẳng ở nước ta, mặc dù mức độ không khó nhưng các thí sinh thường
gặp khó khăn khi giải các bài toán này. Trong các kỳ thi học sinh giỏi quốc gia,
thi toán sinh viên giữa các trường đại học và cao đẳng, thi Olympic toán khu
vực và quốc tế các bài toán tổ hợp xuất hiện là một thử thách lớn cho các thí
sinh. Rất nhiều các bài toán hay và khó được giải một cách khá gọn và đẹp bằng
cách sử dụng các kiến thức về tổ hợp. Em là người rất yêu thích toán tổ hợp
nhưng mới chỉ bết sơ qua về nó khi còn ngồi trên ghế nhà trường phổ thông. Vì
vậy em lựa chọn đề tài: ’’PHÂN DẠNG CÁC BÀI TOÁN ĐẠI SỐ TỔ HỢP TRONG CHƯƠNG
TRÌNH TOÁN TRUNG HỌC PHỔ THÔNG’’ với mục đích nghiên cứu về lý thuyết tổ hợp
từ đó xây dựng một cách có hệ thống, có sáng tạo các bài toán đại số tổ hợp.
Trong khóa luận này em đã tổng kết và phân dạng các bài tập đại số tổ
Đinh Thị Ngát
Đinh Thị Ngát – D1 Toán Tin B
3
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
Chương I: Cơ sở lý thuyết về tổ hợp
Chương này sẽ nhắc lại một số lý thuyết về tập hợp và hệ thống lý thuyết cơ
bản của toán tổ hợp như: Hoán vị, chỉnh hợp, tổ hợp, nhị thức Newton, Các nội
dung này cũng được giảng dạy cho học sinh trung học phổ thông hệ cơ bản,
nâng cao và hệ chuyên nghành toán.
1.1. Nhắc lại về tập hợp
1. Tập hợp con
Định nghĩa: Cho tập hợp
A
. Tập hợp
B
gọi là tập con của tập
A
khi mọi
phần tử của tập
B
đều thuộc
A
.
B
⊂
A
↔
∀
,x x B∈
m
, sao cho với
những phần tử khác nhau ứng với những số khác nhau.
Khi đó bộ sắp thứ tự
m
phần tử là một dãy hữu hạn
m
phần tử và hai bộ
sắp thứ tự
( )
1 2
, , ,
m
a a a
và
( )
1 2
, , ,
m
b b b
bằng nhau khi mọi phần tử tương
ứng bằng nhau
( )
1 2
, , ,
m
a a a
=
( )
1 2
A
∪
B
│= │
A
│+│
B
│-│
A
∩
B
│.
│
A
∪
B
∪
C
│=│
A
│+│
B
│+│
C
│-│
A
∩
B
│-│
∪
n
A
│=
1
n
i
i
A
=
−
∑
1
n
i k
i k n
A A
≤ < ≤
∩ +
∑
+
1 n
n
i k l
i k l
A A A
≤ < < ≤
∩ ∩
∑
+…+
tương ứng bằng
1 2
, , ,
m
n n n
cách và giả sử không có hai việc nào có thể làm
đồng thời. Khi đó số cách làm một trong việc đó là:
1 2
m
n n n+ + +
.
Biểu diễn dưới dạng tập hợp:
1. Nếu
, X Y
là hai tập hợp hữu hạn, không giao nhau thì:
X Y X Y+ = +
Nếu
1 2
, , ,
n
X X X
là
n
tập hữu hạn, từng đôi một không giao nhau thì:
1 2
n
cách,
2
H
có thể làm bằng
2
n
cách, sau khi đã hoàn thành công việc
1
H
.
Khi đó để thực hiện công việc
H
sẽ có
1 2
.n n
cách.
Quy tắc nhân dạng tổng quát:
Giả sử để hoàn thành một nhiệm vụ
H
cần thực hiện
k
công việc nhỏ là
1
H
,
2
H
,…,
k
.
Khi đó để thực hiện công việc
H
sẽ có
1 2
.
k
n n n
cách.
Biểu diễn dưới dạng tập hợp:
Nếu
1 2
, , ,
n
A A A
là
n
tập hợp hữu hạn
( )
1n >
, khi đó số phần tử của tích đề
các các tập hợp này bằng tích của số các phần tử mọi tập thành phần.
Để liên hệ với quy tắc nhân hãy nhớ là việc chọn một phần tử của tích đề các
1 2
n
A A A× × ×
được tiến hành bằng cách chọn lần lượt một phần tử của
1
A
số tự nhiên liên tiếp từ 1
đến
n
.
( ) ( )
! 1.2.3 . 1 . n n n= … −
,
n∈¥
,
n
>1.
Quy ước : 0!= 1.
1!= 1.
2. Hoán vị
Định nghĩa: cho tập hợp
A
, gồm
n
phần tử
( 1)n ≥
. Một cách sắp thứ tự
n
phần tử của tập hợp
A
được gọi là một hoán vị của
n
phần tử đó.
Kí hiệu:
n
A
là số các chỉnh hợp chập
k
của
n
phần tử.
Công thức:
k
n
A
=
!
( )!
n
n k−
=
( ) ( )
. 1 1 n n n k− … − +
(với 1
k≤ ≤
n
).
Chú ý: Một chỉnh hợp
n
chập
n
được gọi là một hoán vị của
n
phần tử.
(1
k≤ ≤
n
) là số các tổ hợp chập
k
của
n
phần tử.
Công thức:
k
n
C
=
!
!( )!
n
k n k−
Đinh Thị Ngát – D1 Toán Tin B
7
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
Chú ý:
0
n
C
= 0.
k n k
n n
C C
−
. Một chỉnh hợp chập
p
có lặp lại gọi
tắt là chỉnh hợp lặp của
n
vật đó là một dãy thứ tự gồm
p
phần tử trong đó mỗi
phần tử có thể lặp lại nhiều lần.
Chú ý:
• Số các chỉnh hợp lặp chập
p
của
n
phần tử là
p
n
.
• Như vậy chỉnh hợp có lặp lại là khi giữa các phần tử yếu tố thứ tự là cốt
lõi, còn yếu tố khác biệt không quan trọng.
1.6.2.Hoán vị lặp
Cho một tập hợp gồm
n
vật, trong đó có
a
vật loại
A
giống nhau,
b
vật loại
Kí hiệu:
p
n
C
là số tổ hợp có lặp chập
n
của
p
phần tử.
Chú ý:
• Số tổ hợp có lặp lại
n
chập
p
là
p
n
C
=
1
p
n p
C
+ −
=
1
1
n
n p
C
(1 ) ( 1)
n n
n n
n n n n
x
x
C C C x C x
= ± + ± +
± −
.
Chú ý:
- Số các số hạng của sự khai triển
( 1)
n
a+
là
1n +
.
- Tổng các số mũ của
a
và
b
trong mỗi số hạng của sự khai triển bằng số mũ
n
.
- Số hạng tổng quát
1k
T
+
của khai triển là
2n =
1 2 1
3n =
1 3 3 1
4n =
1 4 6 4 1
Đinh Thị Ngát – D1 Toán Tin B
9
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
5n =
1 5 10 10 5 1
… …
Như vậy
k
n
C
+
1k
n
C
+
=
1
1
k
n
C
+
+
÷
, với
n∀ ∈¢
,
n
>2.
Giải:
Ta có
2
(1.2 )n
=
( ) ( ) ( ) ( )
1. 2 1 1 .1n n k n k n− … − + …
.
Mà
( )
1 k n k n− + ≥
, với
, , 0n k n k∀ ∈ ≥ >¢
.
Áp dụng cho
1, 2, , k n= …
, ta có:
1. ,
k n k n
=
+ − + +
÷
.
Áp dụng cho
1, 2, , k n= …
ta có:
2
1. ,
1
2
n
n
<
+
÷
2
2.( 1) ,
1
2
n
n
− … − + … <
+
÷
. (2)
Từ (1), (2)
→
2
2
1
(1.2 )
2
n
n
n
n
n
< <
+
÷
, với
n∀ ∈¢
,
2n >
.
÷
(với
k ∈¥
).
Ta chứng minh bất đẳng thức đúng với
1n k= +
.
( ) ( ) ( )
1 ! 1 ! 1
k
k k k k
k
e
+ = + > +
÷
=
1
1
k
k
e
+
+
÷
÷
+
)
Vậy
n
!>
n
n
e
÷
với
n
∈¥
.
W
Bài 3: Chứng minh
2
2 2 2
( )
n n n
n k n k n
C C C
+ −
≤
(với 0
k n≤ ≤
;
⇔
2 2
n n
n i n i
C C
+ −
≤
2 1 2 1
n n
n i n i
C C
+ − − +
⇔
( ) ( ) ( ) ( )
2 1 2 1n i n i n i n i+ − + < − + +
⇔
( )
2 1 .i n−
≥
0 (đúng)
1 0
k k
u u u
=
−
≤
÷
÷
−
∏
(1)
Giải:
Đinh Thị Ngát – D1 Toán Tin B
12
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
Với
2n =
thì bất đẳng thức có dạng:
1
2
0 1
2 2
2 2
2 1
C C
−
≤
÷
÷
−
−
=
−
−
=
−
⇒ ⇔ ≤
÷
÷
−
−
⇔ ≤
−
∏
∏
Áp dụng bất đẳng thức Cosi ta có :
n
i
n
1 2 n 1 n
n 1
i
i 0
n n n
n 1
n
i 1
≤
÷
÷
−
∏
(
*
2 n≤ ∈¥
).
W
Dấu ‘=’ xảy ra
1 2 n 1
n n n
C C C
−
⇔ = = =
n 2
n 3
=
⇔
=
Bài tập tự giải
Bài 1: CMR :
2 2 2 5
1 3 5 5
. !
.
Bài 4: (Đề thi tuyển sinh ĐH-CĐ khối B, 2008)
CMR:
*
1
1 1
1 1 1 1
( , , )
2
k k k
n n n
n
n k k n
n
C C C
+
+ +
+
+ = ∈ ≤
÷
÷
+
¥
.
Đinh Thị Ngát – D1 Toán Tin B
13
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
Bài 5: CMR:
n n 2
CT3: k.C n.C , (CT3.1)
k(k-1)C n(n 1).C , (CT3.2)
−
−
−
−
=
= −
….
Tổng quát:
m m
k (m 1)
k
n
n (m 1)
i o i o
(k i)C (n i)C
− +
− +
= =
− = −
∏ ∏
(với
0 m k 1≤ ≤ −
).
CT4:
k k 1
n n 1
1 1
(với
1 m≤ ∈¥
).
Bài 1: Tính
2012
1110
o i
i 1110
S C
=
=
∑
. Tổng quát: Tính
n
m
i
i m
S C
=
=
∑
.
Giải:
Đinh Thị Ngát – D1 Toán Tin B
14
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
Theo CT1 ta có:
2012
i 1110 0 1 2 902
= =
= =
∑ ∑
0 1 n m
m m 1 n
0 1 n m
m 1 m 1 n
C C C
C C C
−
+
−
+ +
= + +
= + +
1 2 n m
m 2 m 2 n
C C C
−
+ +
= + +=
n m m 1
n 1 n 1
C C
=
=
∑
.
Giải:
Theo CT3.1 ta có:
2012
1110 1110 1110 1110
i 1110 1111 2012
i 1110
iC 1110C 1111C 2012C
=
= + + +
∑
1110 1110 1110
1110 1111 2012
(1111 1)C (1112 1)C (2013 1)C= − + − + + −
Đinh Thị Ngát – D1 Toán Tin B
15
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
1110 1110 1110 1110
1110 2012 1110 2012
(1111C 2013C ) (C C )= + + − + +
0 1 902 0 902
1111 1111 2013 1111 2012
1111(C C C ) (C C )= + + + − + +
=
∑
.
m m m
m m 1 n
S mC (m 1)C nC
+
= + + + +
m m m
m m 1 n
(m 1 1)C (m 2 1)C (n 1 1)C
+
= + − + + − + + −
( )
m 1 m 1 m 1 0 n m
m 1 m 2 n 1 m n
m 1 C (m 1)C (m 1)C (C C )
+ + + −
+ + +
= + + + + + − + +
0 1 n m 0 1 n m
m 1 m 2 n 1 m 1 m 1 n
0 1 n m n m
÷
+ − +
m 1
n 1
m.n m n
C
m 2
+
+
+ +
=
+
.
Bài 3: Tính
2012
1110
i
i 1110
S i(i 1)C
=
= +
∑
. Tổng quát tính
n
m
i
i m
S i(i 1)C
i 2 i 1
i 1110 i 1110
1111.1112.C 2 1111.C
+ +
= =
= −
∑ ∑
2014 2013
1112 1111
i i
i 1112 i 1111
1111.1112.C 2 1111.C
= =
= −
∑ ∑
2014 2013
i 1112 i 1111
i i
i 1112 i 1111
1113 1112
2015 2014
1111.1112 C 2.1111 C
1111.1112.C 2.1111.C
− −
= =
= −
= −
∑ ∑
= + = + − +
= + + − +
∑ ∑
∑ ∑
n n
m 2 m 1
i 2 i 1
i m i m
(m 2)(m 1)C 2 (m 1)C
+ +
+ +
= =
= + + − +
∑ ∑
n n
m 2 m 1
i 2 i 1
i m i m
(m 2)(m 1) C 2(m 1) C
+ +
+ +
= =
= + + − +
∑ ∑
n 2 n 1
m 2 m 1
i i
k
n
m
i
i m
j 0
S (i j)C
=
=
= +
∑
∏
.
Giải:
[ ]
k
n
m
i
i m
j 1
S i (k 1) (k 1) (i j)C
=
=
= + + − + +
∑
∏
k k
= =
= =
= + − + +
= + − + +
∑ ∑
∏ ∏
∑ ∑
∏ ∏
k 1 k
n n
m k 1 m k
i k 1 i k
i m i m
j 1 j 1
(m j) C (k 1) (m j) C
+
+ + +
+ + +
= =
= =
= + − + +
∑ ∑
∏ ∏
k 1 k
n k 1 n k
m k 1 m k
i i
i m k 1 i m k
+ + − + + −
∏ ∏
∏ ∏
k 1 k
j 1 j 1
n k 2 (n k 1)!
(m j) (k 1) (m j)
m k 2 (m k 1)!(n m)!
+
= =
+ + + +
÷
= + − + +
÷
+ + + + −
∏ ∏
Đinh Thị Ngát – D1 Toán Tin B
18
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
k 1 k
m k 1
n k 1
j 1 j 1
n k 2
(m j) (k 1) (m j) C
m k 2
m
k 0
i 1
C
S
(k i)
=
=
= ×
+
∑
∏
Giải:
Áp dụng CT4 ta có:
k
n n
k 1
n
0 n 1
k 0 k 0
C
1
S C
k 1 n 1
+
+
= =
= =
+ +
+
Tổng quát:
k
n n
k m
n
n m
m m
k 0 k 0
i 1 i 1
C
1
S C
(k i) (n i)
+
+
= =
= =
= =
+ +
∑ ∑
∏ ∏
n m m 1
k k
n m n m
m m
k 0 k 0
i 1 i 1
+ −
=
= −
+
∏
.
Đinh Thị Ngát – D1 Toán Tin B
19
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
Bài tập tự giải
Bài 1: Tính tổng
1 2
1 1
( 1) à ( 1)( 2)
n n
i i
S i i v S i i i
= =
= + = + +
∑ ∑
.
Bài 2: Tính tổng
2011
2011
2012 2012
0
k k
k
k
S C C
n
x− =
( )
0
1
n
k
k k
n
k
C x
=
−
∑
( )
1
n
x+ =
0
n
k k
C x
n
k
∑
=
( )
n
m k n N m
∈ =
.
Giải:
Ta có
( )
1
1
n
n
k k
x C x
n
k
+ =
∑
=
.
Chọn
x i=
, ta có:
Đinh Thị Ngát – D1 Toán Tin B
20
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
( ) ( )
1
Theo định lý Moivre ta có:
( )
1
1 3 5
2
2 cos sin 1
4 4
p
n
p
n n n n
n n
i S i C C C C
π π
−
+ = + − + − + −
÷
÷
÷
.
Đồng nhất 2 vế
2 cos
4
n
n
i
S C
=
=
∑
và
( )
1
2
2 1
2 2
0
n
i
n
i
S C
−
+
=
=
∑
.
Giải:
( )
( )
( ) ( )
2
2
k k
+ =
=
+ =
=
+ + =
∑ ∑
÷
÷
÷
= =
∑
∑
Từ (1) thấy hệ số của
2n
x
là
2
4
n
n
C
.
Từ (2) ta thấy hệ số của
2n
x
2
2
2
2 4
0
n
k n
n n
k
C C
=
⇒ =
∑
(*)
( ) ( )
2
2
1 1
2
0
n
n k
k k
x C x
n
k
− = −
∑
=
k
k k
x C x
n
k
+ = −
∑
=
(4).
Ở (4) hệ số của
2n
x
là
( )
4
1
n
n
n
C−
.
Ở (3) hệ số của
2n
x
là
( ) ( )
2
2
1
2
2 4
0
n
k n
k n
C C
n n
k
⇒ − = −
∑
=
(**).
Lấy (*) + (**) ta có :
(
)
( )
( )
2
2 2
2 1
2 4 4
0
2
1
4 4
1
2
n
n
2 2
1 1
4 4 4 4
2
2 2
n
n
i n n
C C C
n n n
i
n n
n n n n
C C C C
n n n n
S
−
+
= − −
∑
=
+
− − + −
⇒ = =
Bài 3: Tính
4
0
m
k
S C
=
(1).
Với
( )
2 2 1i n i≤ < +
( )
1
0
n
n
k k
x C x
n
k
+ =
∑
=
.
Cho
1 2 (*)
0
n
k n
x C
n
k
= → =
∑
=
2 2 1j n j≤ < +
) và
2 1 1
2
0
j
i n
C
n
i
+ −
=
∑
=
(3)
(với
2 1 2 3j n j+ ≤ < +
).
(1) + (2) ta có :
( )
1
2
4 2
2 2 os
4
0
m
n
n
k n
j
i n
C
n
i
+ −
=
∑
=
(4).
Theo bài 1 ta có :
( )
2 1
1 2 sin
4
0
n
i
j
n
i
C
n
i
π
+
− =
∑
=
(5).
2
4024
1
i
i
S C
=
=
∑
.
Đinh Thị Ngát – D1 Toán Tin B
23
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
Bài 3: Tính
0
( 1) ( , ,1 )
k
i i k i
n n i
i
S C C n k k n
− +
−
=
= − ∈ ≤ ≤
∑
¢
.
Bài 4: Tính
2
n
k
1 n
k 1
S k.C
=
=
∑
.
Giải:
Ta có
( )
0
1 (1)
n
n
k k
n
k
x C x
=
+ =
∑
Lấy đạo hàm hai vế của (1) ta có :
n
n 1 k k 1
n
k 1
n.(1 x) k.C .x
−
−
=
=
= −
∑
∏
.
Giải:
Đinh Thị Ngát – D1 Toán Tin B
24
Khóa luận tốt nghiệp Trường Đại học Hoa Lư
Lấy đạo hàm hai vế (1) ta có:
n
n 1 k k 1
n
k 1
n(1 x) kC x
− −
=
+ =
∑
(2).
Lấy đạo hàm hai vế của (2) ta có:
n
n 2 k k 2
n
k 2
n
k m
i 0 i 0
S (k i)C a (n i)(1 a)
− −
− −
=
= =
→ = − = − +
∑
∏ ∏
.
Bài 2: Tính
n
k 2
n
k 1
S k.(C )
=
=
∑
.
Giải:
Theo bài 1 ta có:
n
n k k
n
k 0
(1 x) x C
x x
x
−
=
⇔ + =
÷
∑
(3).
Đinh Thị Ngát – D1 Toán Tin B
25
Copyright: Tài liệu đại học ©