PHƯƠNG PHÁP TẬP HỢP VÀ ÁNH XẠ
GIẢI TOÁN TỔ HỢP
SET AND MAPPING METHOD SOLVING COMBINATORICAL PROBLEMS TRẦN QUỐC CHIẾN
Trường Đại học Sư phạm, Đại học Đà Nẵng
NGUYỄN VĂN THÔNG
HV Cao học khoá 2004-2007 TÓM TẮT
Các bài toán tổ hợp ngày càng chiếm một vị trí quan trọng trong các kỳ thi olympic, vô địch
toán Toán tổ hợp là một dạng toán khó, đòi hỏi tư duy lôgic, tư duy thuật toán cao, tính hình
tượng tốt, phù hợp với mục đích tuyển chọn học sinh có khả năng và năng khiếu toán học.
Hơn nữa, nội dung các bài toán kiểu này ngày càng gần với thực tế, và điều này hoàn toàn
phù hợp với xu hướng của toán học hiện đại.
Bài báo đề xuất phương pháp tập hợp và ánh xạ để giải một số lớp bài toán tổ hợp quan
trọng.
ABSTRACT
Combinatorics Problems play an important role in Olympic Contests. Combinatorics is a
difficult branch of Mathematics, requiring logical and high algorithmic thinking and smart
imagination, suitable for selecting students with mathematical and informatic capacities. In
addition, problems of such type are close to practice and this fact approaches the tendency of
Modern Mathematics. The article suggests a method using sets and mappings solving some
classes of Combinatorics. MỞ ĐẦU
Các bài toán tổ hợp được phân thành bốn dạng sau: Bài toán tồn tại, bài toán đếm, bài toán liệt
kê và bài toán tối ưu, trong đó bài toán đếm đóng vai trò quan trọng. Công cụ chính để giải bài toán



Dễ dàng chứng minh h là song ánh. Từ đó, theo quy tắc tương đương ta có
AB= m + n = A+ B
Bằng qui nạp, có thể mở rộng mệnh đề 1 cho n tập hợp đôi một rời nhau.
Nếu x  A
Nếu x  B
 Mệnh đề 2. Nếu A
1
, A
2
, A
n
là các tập hữu hạn đôi một rời nhau, tức là
i j
A A
  
, i,j {1,
2, , n}, i  j, thì
A
1
 A
2
  A
n
 = A
1
+ A
2
+ + A

; b
j
),
1 ,1
i m j k
   
, có thể viết thành một bảng chữ nhật có m dòng k
cột như sau.







     
1 1 1 2 1
1 2
; , ; , , ;
.
; , ; , , ;
k
m m m k
a b a b a b
a b a b a b
K K K K K K K K K

Đặt



    1 2
. .
m
A B A A A mk A B
       
W

Bằng qui nạp, có thể mở rộng mệnh đề 3 cho n tập hợp.
 Mệnh đề 4. Nếu A
1
, A
2
, , A
n
là các tập hợp hữu hạn bất kỳ và A
1


A
2


,

A
n
là tích Đề các

x x
1
x
2
x
i
x
k

f(x) f(x
1
) f(x
2
) f(x
i
) f(x
k
)
Dòng thứ hai (f(x
1
) f(x
2
) f(x
k
)) là một dãy k phần tử của Y. Nó là một phần tử của
tích Đề các Y YY Y = Y
k
.
Đảo lại, mọi dãy k phần tử của Y là


cách phân phối k đồ vật vào m ngăn kéo.
2.2. Bài toán 2 (Vô địch Trung Quốc - 1997)
Trong các xâu nhị phân có độ dài n, gọi a
n
là số các xâu không chứa 3 số liên tiếp 0, 1, 0 và b
n

là số các xâu không chứa 4 số liên tiếp 0,0,1,1 hoặc 1,1,0,0. Chứng minh rằng b
n+1
= 2a
n
.
Lời giải
Ta gọi một xâu thuộc loại A nếu nó không chứa 3 số liên tiếp 0, 1, 0 và gọi một xâu thuộc loại
B nếu nó không chứa 4 số hạng liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0,0. Với mỗi xâu X = (x
1
, x
2
, , x
n
), ta xây
dựng f(X) = (y
1
, y
2
, , y
n+1
) như sau:
1 k 1 2 k 1
y 0,y x x x (mod2)

có hai chữ số, sau đó các chữ số 3 ở n chữ số đầu và các chữ số 4 ở n chữ số sau được đổi thành chữ số
1, các chữ số 3 ở n chữ số sau và các chữ số 4 ở n chữ số đầu được đổi thành chữ số 2. Ví dụ:
12341421234142123414212121221221112.
Như thế, ta thu được một số có đúng n chữ số 1 và n chữ số 2. Rõ ràng đây là một đơn ánh từ
tập các số n chữ số sang tập các số 2n chữ số. Để chứng minh đây là một song ánh, ta xây dựng ánh xạ
ngược như sau: với mỗi số có n chữ số 1 và n chữ số 2, ta cắt n chữ số đầu và n chữ số cuối rồi cộng
chúng theo cột với quy tắc: 1+1=1, 2+2=2, 1+2=3, 2+1=4, và ta thu được một số có n chữ số gồm các
chữ số 1, 2, 3, 4 với số chữ số 1 bằng số các số 2.
Ví dụ 12121221221112 
1234142
1221112
1212122
 1234142.
Như thế song ánh giữa hai tập hợp đã được thiết lập và ta có M=N.
2.4. Bài toán 4 (IMO - 2005)
Cho các số nguyên dương n, k với n  k.
Xét phép toán f đối với bộ sắp thứ tự X = [x
1
, , x
n
] như sau: mỗi lần chọn k số liên tiếp tuỳ ý
trong X và đổi dấu của chúng.
Tìm số các bộ thứ tự X =[x
1
, , x
n
] thoả mãn các điều kiện:
(i) Mọi phần tử của X đều thuộc tập {-1,1}.
(ii) Có thể thực hiện hữu hạn lần phép toán f để từ X nhận được bộ [1,1, ,1].
Lời giải

aa
k
aaa
k
aaaaaa
xxxxxx
knknknkkk 111221211
)1(,)1(, ,)1(,)1(, ,)1(,)1(
11

21







Từ đó, dễ thấy mỗi bộ A xác định duy nhất một bộ X thoả điều kiện bài toán nên đáp số bài
toán chính là số các bộ A, tức là
n k 1
2
 
.

2.5. Bài toán 5 (VMO - 1995 - Bảng B)
Từ các số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số có 10 chữ số thoả mãn đồng thời các điều
kiện sau:
1) Trong mỗi số, mỗi chữ số có mặt đúng hai lần;
2) Trong mỗi số, hai chữ số giống nhau không đứng cạnh nhau.

1i
i
A
+



51
21
21
ii
ii
AA





51
321
321
iii
iii
AAA
+



51
4321

Gọi T là tập gồm tất cả các số có (10k) chữ số, lập được từ các chữ số 1, 2, 3, 4, 5 thỏa mãn: mỗi chữ
số i
j
, j=1,2, ,k, có mặt đúng một lần, còn các chữ số khác, mỗi chữ số có mặt đúng hai lần. Đặt tương
ứng mỗi số a 
k
iii
AAA 
21
, với số nhận được từ a bằng cách bỏ đồng thời ở a một chữ số i
1
,
một chữ số i
2
, , một chữ số i
k
.
Rõ ràng là phép tương ứng trên xác lập một song ánh từ
1 2

k
i i i
A A A
  
đến T. Điều
này cho ta
k
iii
AAA 
21

2
!7
C 
1
4
5
2
!6
C 
0
2
!5


2.6. Bài toán 6 (VMO - 1995)
Cho số nguyên
2
n

và cho một đa giác đều 2n đỉnh. Người ta tô tất cả các đỉnh của đa giác
đều đó bởi n màu sao cho các điều kiện sau được đồng thời thoả mãn
1) Mỗi đỉnh được tô bởi một màu;
2) Mỗi màu được dùng để tô cho đúng hai đỉnh không kề nhau.
Hai cách tô màu, thoả mãn các điều kiện trên, được gọi là tương đương nếu cách tô màu này
có thể nhận được từ cách tô màu kia nhờ một phép quay quanh tâm của đa giác đều đã cho.
Hỏi có tất cả bao nhiêu cách tô màu đôi một không tương đương?
Lời giải
Xuất phát từ một đỉnh nào đó, lần lượt theo chiều kim đồng hồ, ký hiệu các đỉnh của đa giác
bởi
1 2 2

i i
m m
có thứ tự; mỗi m
i
,
1,
i n

, có mặt đúng hai lần
trong bộ;
1
, 1,2
j j
i i
m m j n

  
(Quy ước
2 1 1
:
n
i i
m m


).
Xét tập
 



Đặt




g n B n

. Ta có







. 1
f n g n n g n
  
. (4)
Thật vây, ký hiệu C(n) là tập tất cả các bộ


1 2
, ,
n
i i
m m

trong B(n) thỏa
1

1
\
n
i
i
B n T T


U
. Theo nguyên lý bù trừ ta có
g(n) = B(n)  = T  

n
i
i
T
1
= T  


n
i
i
T
1
+



nii

+ + (1)
n


n
i
i
T
1
(5)
Trước tiên ta có
T 
n
n
2
!2
(6)
Xét k bất kỳ thuộc tập


1,2, ,
n
và xét bộ


1 2
, , ,
k
i i i
bất kỳ thỏa mãn

tương ứng nói trên xác lập cho ta một song ánh từ tập
1
j
k
i
j
T

I
đến tập V gồm tất cả các bộ có thứ tự


1 2
, ,
n k
i i
m m

thỏa mãn mỗi
, 1,
j
i
m j k
 , có mặt đúng một lần, còn mỗi


1
\ , ,
k
i i i

2 2
n
k
k
n
n n k
k
n n k
g n C



  

(7)
Áp dụng cho g(n1) ta có
g(n

1) =
1
2
)!22(


n
n





n
kn
k
C
kn
1
1
1
2
)!12(
)1(
(8)

Thay (7) và (8) vào (4) ta được

f(n) =
n
n
2
)!2(






n
k
k
n


=
n
n
2
)!2(
















n
k
k
n
kn
k
n
kn


n
k
k
n
k
n
kn
k
nCCkn
kn
1
1
1
.).2(
2
)!12(
)1(

=
n
n
2
)!2(

 





n
n k
k
n k
f n n C


 
 


Tiếp theo ta nhận xét rằng mỗi cách tô màu mà tồn tại


1,2, ,
k n
 sao cho
k
A
và
k n
A


khác màu, đều có đúng 2n cách tô màu tương đương với nó; còn mỗi cách tô màu mà
k
A
và
k n
A

n!






n
k
k
n
kn
k
C
kn
1
2
)!12(
)1(
+
2
)!1(

n3. ỨNG DỤNG TÍNH BIỂU THỨC TỔ HỢP
Ý tưởng áp dụng bài toán đếm để tính biểu thức tổ hợp là biểu diễn biểu thức tổ hợp bằng số
cách xây dựng một cấu hình tổ hợp thích hợp mà số cấu hình tổ hợp này dễ dàng tính được thông qua
các công thức tổ hợp cơ bản.



cách
chọn và ta chọn được tổng cộng n số, trong đó k chạy từ 0 tới n. Lập luận đó cho ta điều phải chứng
minh.

3.2. Bài toán 8 (VMO - 2004)
Cho trước các số nguyên dương m, n. Tính
k k
m n
n k m k
n k m k
k 0 k 0
C C
T
2 2
 
 
 
 
 

Lời giải
Ta chứng minh tổng cần tính bằng 2, tức là:
m n
k m k k n k m n 1
n k m k
k 0 k 0
C 2 C 2 2
   

và a
n+1
= n+k+1 với 0km (do có
n
n k
C

cách chọn n phần
tử (a
1
, a
2
, , a
n
) từ tập {1, 2, , n+k}, 1 cách chọn a
n+1
= n+k+1, và 2
m-k
cách chọn tập con của tập
{n+k+1, , n+m+1}). Như vậy
m
k m k
n k
k 0
C 2




là số tập con của S có nhiều hơn n phần tử.



là số tất cả các tập con của S, tức là 2
m+n+1
. Đó chính là
điều phải chứng minh.

3.3. Bài toán 9 (VMO - 2002)
Cho tập S gồm tất cả các số nguyên trong đoạn [1; 2002]. Gọi T là tập hợp tất cả các tập con
không rỗng của S. Với mỗi X thuộc T, kí hiệu m(X) là trung bình cộng các phần tử của X. Tính
m =
T
Xm
TX


)(

Lời giải
Ta xây dựng song ánh f: TT như sau:




f X 2003 x x X , X T
    
. Rõ ràng XT,
m(X) + m(f(X)) = 2003. Do đó
     
 

b 9 a
 

Do N+f(N) = 99 9 (2002 số 9) chia hết 9, nên f là song ánh. Từ đó suy ra
2

MN
N =





MN
NfN )( = M .99 9 (2002 số 9)
Cuối cùng ta nhận được trung bình cộng các số N là
{
2002
2002cs9
10 1
99 9
2


.

KẾT LUẬN
Bài toán tổ hợp là bài toán có nội dung thực tế, lý luận hấp dẫn và lý thú, những điều nghe như
là đơn giản nhưng giải được nó là một quá trình tư duy sâu sắc, ứng dụng tập hợp và ánh xạ sẽ làm rõ
hơn cách giải toán rời rạc cho học sinh giải toán ở trường Trung học phổ thông, chuyên Toán, Tin.