MỞ RỘNG CÁC KHÁI NIỆM VỀ ĐẠI SỐ TỔ HỢP LÝ THỊ THÚY LAN
MỘT SỐ KHÁI NIỆM MỞ RỘNG VỀ ĐẠI SỐ TỔ HỢP
A. ĐẶT VẤN ĐỀ:
Bắt đầu từ năm 2009-2010 trường THPT Nguyễn Hữu Huân chính thức tuyển sinh các lớp chuyên
trong đó có lớp chuyên toán. Việc giảng dạy các lớp chuyên đòi hỏi người giáo viên phải tìm hiểu đi
sâu các vấn đề của toán học, trên cơ sở chương trình chuyên đã được áp dụng cho các trường chuyên
của thành phố Hồ Chí Minh. Mặc dù không được phân công trực tiếp dạy lớp chuyên nhưng trong tình
hình thiếu giáo viên ở một hai năm đầu, tôi được phân công hỗ trợ một chuyên đề cho lớp 11 Chuyên
Toán, chuyên đề ĐẠI SỐ TỔ HỢP.
Hạn chế của trường là mặc dù được mở lớp chuyên nhưng tài liệu chuyên của trường rất ít, hầu hết
giáo viên không được trang bị thêm kiến thức và kĩ năng giảng dạy chuyên, đa số tự tìm tòi đọc sách,
tra cứu qua mạng. Các nguồn tài liệu chuyên tuy nhiều nhưng không có hệ thống, và mức độ không
dành cho học sinh phổ thông nên việc tìm tài liệu đáp ứng cho một chuyên đề là không đơn giản.
Nhằm mục đích tự trang bị thêm cho mình và giúp tổ bộ môn một số tiết chuyên đề về đại số tổ
hợp cho lớp 11, tôi đã chọn lọc trong một số tài liệu, những khái niệm mở rộng, các ví dụ, bài tập cũng
như ứng dụng sao cho các khái niệm cơ bản của sách giáo khoa là trường hợp đặc biệt của các khái
niệm tổng quát hơn, xử lý được nhiều dạng bài hơn, đánh giá vấn đề bằng góc nhìn khác hơn, để viết
nên chuyên đề này.
Mặc dù hết sức cố gắng nhưng vì còn hạn chế về nhiều mặt nên chắc chắn bài viết này còn nhiều
sơ sót và chủ quan, tôi rất mong sự đóng góp từ phía các đồng nghiệp nhằm bổ sung, chỉnh sửa để bài
viết hoàn thiện hơn.
B. NỘI DUNG:
I) Các khái niệm nhắc lại
II) Mở rộng các phép toán trên tập hợp
III) Số phần tử của một tập hợp hữu hạn
IV) Hoán vị – Chỉnh hợp – Tổ hợp
V) Chỉnh hợp lặp
VI) Hoán vị lặp
VII) Tổ hợp lặp
VIII) Áp dụng vào khai triển đa thức
1

thì P(n) đúng,
*Nn∈∀
Lưu ý: đôi khi mệnh đề P(n) chỉ đúng từ n = p trở đi (với p hằng số)
4) Kí hiệu :
ni ,1=
để chỉ các số tự nhiên i chạy từ 1 đến n
T(A) để chỉ tập hợp gồm tất cả các tập con của A
II)Mở rộng phép toán trên tập hợp
1) Hợp của n tập hợp
{ }

n
i
ii
AxnixA
1
:,1/
=
∈=∃=
2) Giao của n tập hợp :
{ }

n
i
ii
AxnixA
1
:,1/
=
∈=∀=

( )
{ }
niAaaaaAAAA
in
n
n
,1,/, ,,
21
lan
=∀∈=×××=
  
Ví dụ: cho
{ } { }
baBA ;;3;2;1 ==
.
( ) ( ) ( ){ }
bababaBA ,3();,3;,2();,2;,1();,1=×
Hãy nêu các tập tích
32
;; BAAB×
và nhận xét về sự bằng nhau và khác nhau của 2 phần tử bất kỳ
của tập hợp.
Ví dụ: Có sự tương ứng 1–1 từ tập
( ){ }
RyxyxR ∈= ,/;
2
đến tập hợp các điểm trong mặt phẳng
tọa độ Oxy nên ta cũng gọi tập hợp này là
2
R

i
i
,1,
1
1
==
∑
=
=

trong đó
{ }
njiAA
ji
; ;2;1,, ∈∀=∩
φ
(thử chứng minh công thức trên)
• Với
XA ⊂
:
AXACA
X
−==
• Cho 2 tập hợp bất kỳ A, B. Số phần tử của
BA ∪
bằng tổng các số phần tử của A và B trừ
số phần tử của
BA ∩
BABABA
∩−+=∪

số các số chia hết cho 5 là
56
5
280
=






số các số chia hết cho 2 và 3 là
46
6
280
=






số các số chia hết cho 2 và 5 là
28
10
280
=




2) Số phần tử của tập tích Đềcác :
 Tích
BA×
với
nA =
,
kB =
:
Với mỗi
ni ,1=
,
i
a
được ghép với k phần tử trong B
Vậy với n phần tử trong A có
kn
×
cách ghép thành các phần tử trong
BA×
. Ta có:
BABA .
=×
 Tích
n
AAA ×××
21
với
ii
kA =
, bằng phép quy nạp ta có thể chứng minh

k
mBB ==
4) Bài toán về số tập con của một tập hợp hữu hạn :
Chứng minh rằng số tất cả các tập con của một tập hợp gồm n phần tử là
n
2
Giải: dùng quy nạp, gọi T(A) là tập chứa tất cả các tập con của A
với n = 1, A chỉ có 2 tập con là rỗng và chính nó,
2T(A) =
giả sử tập hợp A gốm k phần tử
k
aaa , ,,
21
có
k
2
tập con. Nếu ghép vào A một phần tử
1+k
a

nữa ta được tập A’ có k + 1 phần tử. T(A’) được chia thành 2 phần, một phần gồm tất cả tập
con có chứa
1+k
a
và phần kia gồm các tập con không chứa
1+k
a
. Kí hiệu A* là một tập con
nào đó của A’ chứa
1+k

sao cho nếu
Bx
∈
thì f(x) = 1, nếu
Bx
∉
thì f(x) = 0. Tương ứng từ T(A)
đến tập các ánh xạ như trên là 1–1 nên
)(AT
bằng số các ánh xạ từ A tới Y và bằng
k
2
5) Chứng minh quy tắc cộng và quy tắc nhân của phép đếm
Quy tắc cộng : Một bài toán chọn sao cho ít nhất một trong các khả năng
k
AAA , ,,
21
xảy ra
có thể chia thành k trường hợp
k
AAA , ,,
21
, mỗi trường hợp
kiA
i
,1, =
có
i
a
cách chọn, giả

i
A
, yêu cầu của bài toán là tìm số phần tử của

k
i
i
A
1=
, do
5
MỞ RỘNG CÁC KHÁI NIỆM VỀ ĐẠI SỐ TỔ HỢP LÝ THỊ THÚY LAN
đó số cách chọn là
∑
=
=
=
k
i
i
k
i
i
AA
1
1

Hệ quả: Số cách chọn của bài toán
A
trong X, (tức nếu thỏa A thì không chọn) là

21
, số
cách chọn theo yêu cầu bài toán là số phần tử của tập tích Đềcác tức là
k
aaa
21
IV) Hoán vị – chỉnh hợp – tổ hợp :
1) Hoán vị :
VD1: Tìm số song ánh có thể lập được từ tập A có n phần tử lên chính nó.
VD2: có bao nhiêu cách xếp thứ tự tập hợp
{ }
n2; ;2;1
sao cho các số chẵn đều ở vị trí chẵn.
2) Chỉnh hợp :
•Tìm số đơn ánh có thể lập từ tập A có k phần tử đến tập B có n phần tử, với
nk
≤≤
1
•Trong mặt phẳng cho n điểm trong đó không có ba điểm nào thẳng hàng. Hỏi có bao nhiêu
đường gấp khúc hở, bao nhiêu đường gấp khúc khép kín gồm k cạnh được tao thành
3) Tổ hợp :
Trong tập hợp A gồm n phần tử
{ }
n
aaa , ,
21
chứng minh rằng số tập con chứa phần tử
i
a


k
n
CCC =+
−
−
− 1
1
1
V) Chỉnh hợp lặp :
1) Định nghĩa
Cho tập hợp
{ }
n
aaaX , ,,
21
=
, từ X ta lấy ra 1 phần tử, sau đó bỏ phần tử đó trở lai X, tiếp
tục lấy phần tử thứ hai,… cứ như thế đến khi lấy được phần tử thứ k, ta được một bộ k–sắp
thứ tự gọi là một chỉnh hợp có lặp chập k của n phần tử (vì phần tử lấy ra lần sau có thể lặp
lại phần tử đã lấy ra trước đó)
Số chỉnh hợp lặp chập k của n phần tử:
kk
n
nA =
chứng minh: cách 1
7
MỞ RỘNG CÁC KHÁI NIỆM VỀ ĐẠI SỐ TỔ HỢP LÝ THỊ THÚY LAN
ta chia làm k giai đoạn: mỗi giai đoạn có n cách chọn phần tử để lấy nên có
k
n

b) các vật đó khác nhau đôi một.
HD: a) chọn p dòng cho mỗi cột là chỉnh hợp có lặp chập p của n phần tử. b) chọn cột cho n
vật khác nhau có n! cách, trong mỗi cột lại chọn trong p dòng, nên có …
VI) Hoán vị lặp :
1) Định nghĩa :
Hoán vị có lặp cấp n kiểu
m
kkk , ,,
21
là một chỉnh hợp có lặp chập n của m phần tử trong đó
quan tâm đến số lần lặp lại của phần tử thứ i là
i
k
. Như vậy
nkkk
m
=+++
21
Số hoán vị lặp cấp n kiểu
m
kkk , ,,
21
của m phần tử
!! !
!
), ,,(
21
21
m
mn

!
), ,,(
21
21
m
mn
kkk
n
kkkC =
3) Ví dụ:
• có bao nhiêu cách gieo một xúc xắc 21 lần với 1 lần xuất hiện số 1, 2 lần xuất hiện số 2,…, 6
lần xuất hiện số 6?
• có bao nhiêu cách gieo một đồng xu n lần trong đó có đúng k lần xuất hiện mặt sấp?
4) Nhận xét :
k
nn
C
knk
n
knkC
=
−
=−
)!(!
!
),(
5) Bài tập
1/ Có bao nhiêu cách đặt 2 đèn xanh và 4 đèn đỏ thành 1 hàng.
2/ Từ các chữ số 1, 2, 3, 4, 5 có thể lập bao nhiêu số có 8 chữ số biết chữ số 2 có mặt ba lần,
chữ số 1 có mặt hai lần, các chữ số khác có mặt đúng một lần.

là aa, ab, ac, bc, bb, cc
3) Số tổ hợp lặp chập k của n phần tử là
1
11
−
−+−+
==
n
kn
k
kn
k
n
CCC
Chứng minh:
Cách 1:Cho tập hợp X có n phần tử, mỗi tổ hợp lặp chập k của được xem như một đơn thức có
dạng
n
k
n
kk
aaa
21
21
trong đó
n
aaa ; ;;
21
là n phần tử của X,
n

M
sao cho
11
lAM =
,
221
lMM =
,…,
112 −−−
=
nnn
lMM
(khi đó đương nhiên
nn
lBM =
−1
). Số nghiệm nguyên dương của PT(1) cũng là số cách chọn n–1
điểm vạch cm trên thước (có n+k–1 vạch như thế) nên sẽ có
1
1
−
−+
n
kn
C
cách chọn
Cách 2: Ta lập một tương ứng mỗi tổ hợp lặp chập k của n phần tử với một dãy nhị phân được
sắp xếp như sau:
1
k

1) Nhị thức Newton
Xem
( ) ( ) ( ) ( )
  
lân

n
n
babababa +++=+
10
MỞ RỘNG CÁC KHÁI NIỆM VỀ ĐẠI SỐ TỔ HỢP LÝ THỊ THÚY LAN
Mỗi số hạng là tích của các phần tử của chỉnh hợp chập n của 2 phần tử a và b. Các số hạng đồng
dạng dạng
ik
ba
là số các hoán vị cấp n , kiểu (k, i) với k + i = n. Số hạng tổng quát của khai triển
là
ik
n
baikC ),(
và ta có công thức
( ) ( )
∑∑
=
−
=+
≤≤
==+
n
k

≤≤
=+++
nkkk
nk
k
m
kk
mn
n
m
m
i
m
aaakkkCaaa

0
212121
21
21
, ,,
Số số hạng là số tổ hợp lặp chập n của m phần tử,
suy ra có
1
1
−
−+
m
mn
C
số hạng.

3
!3!0!0
!3
!0!3!0
!3
!0!0!3
!3
cbacbacbacba
+++++
021120102012
!0!2!1
!3
!1!2!0
!3
!1!0!2
!3
!0!1!2
!3
cbacbacbacba
111210201
!1!1!1
!3
!2!1!0
!3
!2!0!1
!3
cbacbacba +++
abcbcaccbabcabacba 6333333
222222333
+++++++++=