
A.LÝ DO CHỌN CHUYÊN ĐỀ
Toán học tổ hợp (hay giải tích tổ hợp, đại số tổ hợp, lý thuyết tổ hợp) là một
ngành toán học rời rạc, nghiên cứu về các cấu hình kết hợp các phần tử của một tập
hữu hạn phần tử. Các cấu hình đó là các , các phần tử
của một Môn toán này có liên quan đến nhiều lĩnh vực khác của toán học,
như đại số, lý thuyết xác suất, lý thuyết ergod (ergodic theory) và hình học, cũng
như đến các ngành ứng dụng như khoa học máy tính và vật lí thống kê nên có
nhều vấn đề rất sâu phải có trình độ cao. Tuy nhiên, với trình độ phổ thông cơ sở
vẫn có thể tiếp cận và ứng dụng giải nhiều bài toán rất hay gặp trong thực tế cũng
như các đề thi ( Thi HSG, thi tuyển sinh ).
Đối với bộ môn tin học trong khi lập trình chúng ta thường xuyên phải làm các
thao tác sắp xếp, phân hoạch, lấp tập con thành tập hợp lớn hơn … trên một tập hợp
các phần tử hữu hạn và rời rạc nghĩa là thường xuyên đụng chạm đến khái niệm
của giải tích và tổ hợp đó là :



B.PHẠM VI MỤC ĐÍCH CHUYÊN ĐỀ
  !"#$%&
-Do đặc thù của học sinh THCS còn hạn chế về kiến thức toán học và kỹ thuật
lập trình và khả năng bản thân còn có nhiều hạn chế, nên chuyên đề chỉ nêu
được một số thuật giải mẫu và các ví dụ minh hoạ về “ tổ hợp, chỉnh hợp, hoán
vị ”mà qua quá trình học tập giảng dạy tôi đã sưu tầm và tích lũy được .
' (%)*+"#$%&
-Giúp học sinh hiểu được các khái niệm về tổ hoán vị, chỉnh hợp ,tổ hợp và các
1
thuật toán, cách cài đặt chương trình .
-Giúp học sinh chủ động lĩnh hội kiến thức hơn, phát huy vai trò tích cực trong
học tập của học sinh. Khắc sâu những kiến thức cơ bản, học sinh biết áp dụng ,
tìm tòi, khám phá không ngừng năng cao chất lượng bồi dưỡng HSG và học

thì tập hợp này có tất cả 6 Hoán vị .
Cho tập hợp có phần tử ( ). Mỗi thay đổi vị trí sắp xếp phần tử này theo
một thứ tự nhất định, ta được một  các phần tử của tập .
'DE
>) Số các Hoán vị của một tập hợp có phần tử là:

6F! !G+
Một đoàn khách du lịch dự định đến tham quan điểm du lịch và
ở Hà Nội. Họ đi tham quan theo thứ tự nào đó, chẳng hạn :
. Như vậy mỗi cách họ chọn thứ tự tham quan là
một Hoán vị của tập . Do vậy đoàn khách có tất cả
cách chọn.
( Như bài này rõ ràng cách liệt kê thô sơ khõ lòng giải quyết được)
3
Một hoán vị của n phần tử là một bộ gồm n phần tử để được sắp theo một trật
tự nhất định, mỗi phần tử có mặt đúng một lần

+1!!2 &
3)4( :
Trong trận chung kết bóng đá phải phân định thắng thua bằng đá luân lưu .
Huấn luyện viên của mỗi đội cần trình với trọng tài một danh sách sắp thứ tự cầu
thủ trong số cầu thủ của đội để tham gia đá. Hỏi mỗi đội bóng có bao nhiêu
phương án chọn ?
.!7! Ta có thể chọn trong cầu thủ để đá quả đầu tiên.
Tiếp theo có cách chọn cầu thủ đá quả thứ hai,
rồi cách chọn cầu thủ đá quả thứ ba,
cách chọn cầu thủ đá quả thứ tư và cuối cùng có cách chọn cầu thủ đá quả thứ
năm. Theo quy tắc nhân, mỗi đội sẽ có: cách chọn.
Mỗi danh sách có xếp thứ tự cầu thủ được gọi là một chỉnh hợp chập của
cầu thủ

n
A =
, do đó công thức (1) đúng với mọi số nguyên thỏa mãn :
0 k n
≤ ≤
QAMột  của một tập phần tử chính là một  chập của
phần tử đó .
Do đó :
!
n
n n
A p n
= =

:1!!2 :Cho tập A có n phần tử và số nguyên với . Mỗi tập con
của có phần tử gọi là một Tổ hợp chập của phần tử của ( gọi tắt là Tổ
hợp chập của )
Như vậy, lập một Tổ hợp chập của chính là lấy ra phần tử của mà không
quan tâm đến thứ tự.
* DE
>) Số các Tổ hợp chập của một tập hợp có phần tử ( ) là:
!
(2)
! !( )!
k
n
k
n
A n
C

C C
−
=
)S' Cho các số nguyên n, k thỏa mãn .
Khi đó:
1
1
k k k
n n n
C C C
−
+
= +
86F!VF
6F!: Có bao nhiêu cách xếp chỗ ngồi cho 10 bạn vào ngồi quanh 2 bàn tròn sao
cho bàn thứ nhất có 6 bạn, bàn thứ hai có 4 bạn? Chú ý rằng 2 cách xếp n người cụ
thể vào ngồi quanh một bàn tròn được coi là như nhau nếu người ngồi bên trái mỗi
người trong 2 cách xếp là giống nhau.
W@H4RH!7!
6
Chia là ba bước.
Bước 1: chọn nhóm 6 người (hoặc 4 người). Có cách.
Bước 2: Xếp người vào bàn tròn vị trí. cách.
Bước 3: Xếp người vào bàn tròn có vị trí. cách.
Áp dụng quy tắc nhân, tính kết quả.
6F!' Một người dùng ổ khóa số gồm 3 vòng số, mỗi vòng có 10 chữ số từ 0 đên
9. Hỏi người đó có bao nhiêu cách đặt mật mã ( số để khóa chỉ người đó biết ) cho
ổ khóa ?
VD2: Hoán vị của 3 phần tử : 1 2 3
Hoán vị thứ nhất : 1 2 3

Begin
For J:=1 to n do
If b[i] then
Begin
A[i]:=j;
B[j]:=false;
Find(i+1);
B[j]:= true;
End;
End;
End;
…………………………………………………….
8
Ví dụ: n =3
F(1)
1 2 3
F(2) F(2) F(2)
2 3 1 3 1 2

F(3) F(3) F(3) F(3) F(3) F(3)
3 2 3 1 2 1
P(1 2 3) P(1 3 2) P(2 1 3) P(2 3 1) P(312 ) P(3 2 1)
Program HoanVi;
uses crt;
const n=5;
var A,S:array[1 100]of integer;
B:array[1 100]of boolean;
i,dem:integer; g:text;
procedure Print;
var i:longint;

10
Một số được gọi là “ số gần nguyên tố “nếu nó không phải là só nguyên tố nhưng
tồn tại một
cách sắp xếp lại các chữ số của nó (bỏ đi các chữ số 0 vô nghĩa ở đầu số sau khi sắp
xếp các chữ số nếu có ) sao cho số sau khi sắp xếp trở thành một số nguyên tố . Yêu
cầu: Nhập từ bàn phím mọt số nguyên dương N không quá 1000000, sau đó thông
báo ra màn hình “số gần nguyên tố ”lớn nhất có giá trị không vượt quá N. Nếu
không tìm được “số gần nguyên tố “nào không vượt quá N thì đưa ra dòng thông
báo: KHONG CO . Dữ liệu nhập vào coi như là chuẩn, không cần kiểm tra.
Ví dụ :
+Nhập N=19 , thì đưa ra dòng thông báo :SO CAN TIM LA 16
+Nhập N=20 , thì đưa ra dòng thông báo :SO CAN TIM LA 20
:"
+ một vòng lặp từ lớn đến nhỏ, với mỗi số nếu không phải là nt thì đổi ra
xâu
+ Đưa xâu st vào hoán vị ,
+ Với mỗi hoán vị, ta chuyển lại thành số
+ KT tính NT của hoán vị đó
+ Nếu thỏa mãn thì kết thúc vòng lặp tìm kiếm.

F!%d
program gan_nguyen_to;
uses crt;
var A:array[1 20]of char;
B:array[1 20]of boolean;
i,j,n,n1,k:longint; kq,st:string; kt:boolean;
f,g:text;
function nt(k:longint):boolean;
var i:longint;
11

end;
BEGIN
assign(f,'gnt.inp');reset(f);
assign(g,'gnt.out'); REWRITE(G);
readln(f,n1);
i:=n1; kt:=false;
repeat
if not(nt(i)) then
begin
str(i,st);n:=length(st) ;
for j:=1 to n do B[j]:=true;
Find(1);
end;
dec(i);
until kt;
close(f);
close(g);
END.
*Hãy lập trình giải các bài toán sau đây
6F! Xếp lại dãy số
Cho dãy số nguyên dương đôi một khác nhau: a
1
, a
2
, , an. Một hoán vị của
dãy số là một cách sắp xếp khác các số hạng của dãy. Hãy liệt kê tất cả các hoán vị
của dãy đã cho thoả mãn: giữa hai phần tử bất kỳ M và N trong hoán vị đó, không
tồn tại phần tử P nào của hoán vị để:2P = M + N.
13
Ví dụ: Với dãy: 11, 22, 33, 44 thì

10
Bài 2: Vòng tròn nguyên tố
Một vòng tròn chứa 2n vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ
được đánh số từ 1 đến 2n theo chiều kim đồng hồ. Cần điền một số tự nhiên từ 1
14
đến 2n vào mỗi vòng tròn nhỏ (mỗi số chỉ được phép điền một lần) sao cho tổng
của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ
1 luôn là số 1.
1
2
4
6
3
5
-e>!2"F Đọc từ file văn bản CIRCLE.INP gồm chỉ một dòng chứa số
nguyên dương n (1 < n < 10).
-e>!2"C+ Ghi ra file văn bản CIRCLE.OUT có cấu trúc như sau:
• k dòng đầu, mỗi dòng ghi các số trong các vòng tròn nhỏ bắt đầu từ vòng
tròn nhỏ 1 đọc theo thứ tự của các vòng tròn nhỏ, mỗi số cách nhau một
dấu cách.
• Dòng cuối cùng ghi số lượng các cách điền số tìm được (k).
3)4(
CIRCLE.INP CIRCLE.OUT CIRCLE.INP CIRCLE.OUT
3 1 4 3 2 5 6
1 6 5 2 3 4
2
4 1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

16
for h:=i+1 to n do
if 2*a[i]=a[k]+a[h] then Kt :=false;
inc(i);
until not(kt)or(i=n);
if kt then begin inc(d);
for i:=1 to n do write(g,a[i],' ');
writeln(g);
end;
end;
procedure Find(i:longint);
var j,k:longint;
begin
if i>n then print
else
begin
for j:=1 to n do
if B[j] then
begin
A[i]:=c[j];
B[j]:=false;
find(i+1);
B[ j]:=true;
end;
end;
end;
BEGIN
17
assign(f,'sort.inp');reset(f);
assign(g,'sort.out'); REWRITE(G);

end;
procedure Print;
var i,h,k:longint; kt:boolean;
begin
IF a[1]=1 then
begin
inc(n);a[n]:=a[1]; kt:=true;
for i:=1 to n-1 do
if not(nt(a[i]+a[i+1])) then Kt :=false;
if kt then begin inc(d);
for i:=1 to n-1 do write(g,a[i],' ');
writeln(g);
end;
dec(n);
end;
end;
procedure Find(i:longint);
var j,k:longint;
begin
if i>n then print
else
begin
19
for j:=1 to n do
if B[j] then
begin
A[i]:=j;
B[j]:=false;
find(i+1);
B[j]:=true;

B[j]:=1;
end;
end;
F!%d
program chinh_hop;
uses crt;
const n=9;
var A:array[1 n]of byte;
B:array[1 n]of 0 1;
i,dem,r:integer;
procedure Print;
var i:longint;
begin
inc(dem);Write('Chinh hop thu ',dem,' : ');
for i:=1 to r do write(A[i]);writeln;
21
readln;
end;
procedure Find(i:longint);
var j:longint;
begin
if i>r then print else
begin
for j:=1 to n do
if B[j]=1 then
begin
A[i]:=j;
B[j]:=0;
find(i+1);
B[j]:=1;

end;
end;
F!%d
program to_hop1;
uses crt;
const n=5;
var A:array[1 n]of byte;
B:array[1 n]of 0 1;
i,dem,r:integer;
procedure Print;
var i:longint;
23
begin
inc(dem);Write('To hop thu ',dem,' : ');
for i:=1 to r do write(A[i]);writeln;
readln;
end;
procedure Find(i:byte);
var j:byte;
begin
if i>r then print else
begin
for j:=1 to n do
if (B[j]=1)and(j>a[i-1]) then
begin
A[i]:=j;
B[j]:=0;
find(i+1);
B[j]:=1;
end;

i i ik
A A A M
+ + + =

6F!P Vé xe hạnh phúc:
- Một vé xe buýt bất kỳ có mã số là một dãy gồm 6 số tự nhiên, được gọi là vé xe
hạnh phúc nếu tổng của 3 chữ số đầu bằng tổng của 3 chữ số cuối. Tính xem có
tất cả bao nhiêu vé xe hạnh phúc.
6F!8
- Cho tập A={0,1,2,5,7,8} . Có bao nhiêu số tự nhiên chia hết cho 6, có đúng 5 chữ
số, được chọn từ tập A
6F!g
- Cho tập A={0,1,2,4,7,8,9} . Có bao nhiêu số tự nhiên nhỏ hơn 80000 mà chia hết
cho 3, có các chữ số được chọn từ tập A
6F!N
- Cho tập A={0,1,2} . Có bao nhiêu số tự nhiên có đúng 6 chữ số được tạo thành
từ A , sao cho số đó có ít nhất một cặp số 0,2 đứng cạnh nhau.
1h?i
Cùng với sự phát triển vũ bão của công nghệ thông tin, yêu cầu giảng dạy bộ
môn tin học trong nhà trường ngày một cao hơn các bài tập toán tin cũng ngày ngày
một khó thêm với những yêu cầu nhanh hơn dữ liệu lớn hơn, thuật toán khó hơn …
25