CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT

CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP
QUI TẮC ĐẾM
QUI TẮC CỘNG ( The Addition Priciples- AP) :
Nếu có
1
n
đối tượng khác nhau trong tập hợp thứ nhất ,
2
n
đối tượng khác nhau
trong tập hợp thứ hai ,……
m
n
đối tượng khác nhau trong tập hợp thứ m, Thế thì
số cách để chọn 1 đối tượng từ 1 trong m tập hợp là
1 2

m
n n n
+ + +
.
Cách phát biểu khác:
Cho
1 2
; ;
m
A A A
là m tập hợp hữu hạn , k≥1.Nếu các tập hợp này đôi một rời
nhau , nghĩa là

kết hợp lại là phân biệt Thế thì số kết quả kết hợp lại của toàn bộ quá trình là
1 2
.
m
n n n
.
Cách phát biểu khác :
Cho
( )
{ }
1 2 1 2
1
; ; ; / ; 1;2 ;
m
i m m i i
i
A A A A a a a a A i m
=
= × × × = ∈ =
∏
là tích Decarste của
các tập hợp hữu hạn
1 2
; ;
m
A A A
. Khi đó , ta có
1 2
1 1


1
1
500
500 500a q q
a
≤ ⇒ ≤ ≤
Cho nên :
1
3
500
2 7 1 aq
q
 
≤ ≤ ≤ ≤
 
 
.Điều đó có nghĩa là số cấp số nhân với
công bội q là
3
500
q
 
 
 
. Theo qui tắc cộng , số cấp số nhân thỏa điều kiện là :
7
3
2
500
62 18 7 4 2 1 94

Với mỗi i=0 ;1 ;2 ;3 ;4 ;5 ta đặt
( )
{ }
2 2
; / ; ;
i
S x y x y Z x y i
= ∈ + =
.
Dễ kiểm tra :
2
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
0 1 2 3 4 5
1; 4; 4; 0; 4; 8;S S S S S S= = = = = =
Vậy
5
0
21
i
i
S
=
=
∑
.

4. Tìm số ước số dương của 600 , bao gồm cả 1 và 600
GIẢI :
Trước hết ta chú ý rằng 600=
3 1 2

. Thế thì số các ước số dương của n là
( )
1
1
m
i
i
k
=
+
∏
.
5. (AIME 1988)Tính xác suất để chọn được ngẩu nhiên 1 ước số
nguyên dương của
99
10
là một bội số của
88
10
.
GIẢI :
Ước số của
99
10
có dạng
2 .5 0 a;b 99;a,b Z
a b
≤ ≤ ∈
.Có 100 cách chọn a , 100
cách chọn b, nên có 100×100 ước số của

=


=


Vì
3 7 13
2 .5 .11
là BCNN của a,b nên max{x ;s}=3 ; max{y ;t}=7 ; max
{z ;u}=13.
Bằng cách liệt kê ta có 7 cách chọn cặp (x ;s) ; 15 cách chọn (y ;t) ; 27
cách chọn (z ;u). Theo qui tắc nhân , ta được 7×15×27=2835 cặp số (a ;b)
thỏa điều kiện .
3
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
MỞ RỘNG :
Nếu n là số nguyên dương và
1 2
1 2
. .
k
k
n p p p
α
α α
=
là phân tích thành thừa số
nguyên tố của n.Thì sẽ có
( ) ( ) ( )

Ta nói rằng 4 điểm n×n quartet ( nhóm 4 ) nếu chúng là các đỉnh của hình
vuông n×n mà các cạnh của nó song song với đường biên của lưới. Ta
cũng nói rằng 1 hình vuông với các đỉnh của 1 quartet là một quartet
square.
Ta có 81=
2
9
quartet 1×1.
Ta có : 8 quartet 2×2 trong lưới 3×10 và có 8 lưới 3×10 trong lưới 10×10
.
Vậy , có
2
8
quartet 2×2 trong lưới 10×10.
Tương tự ta có :
2
7
quartet 3×3 trong lưới đó .
Nghĩa là , khi k∈{1 ;2 ;… ;9} có
( )
2
10 k
−
quartet k×k .
Nhưng phần khó khăn là các hình vuông có cạnh không song song với
đường biên của lưới .Mỗi hình vuông này sẽ nội tiếp bên trong 1 quartet.
Cho nên ta chỉ cần đếm tất cả các quartet và các hình vuông nội tiếp nó.
Không khó khăn gì ta được trong 1 k×k quartet có k hình vuông nội tiếp ,
4
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT

tam giác tức là x+y>z. Ta sắp xếp các tam giác không cân theo độ dài
cạnh lớn nhất của nó. Với 1≤k≤n , ta đặt
( )
{ }
; ; / ; ; ;1
k
A x y z x y z N x y z k x y z= ∈ ≤ < < = ∧ + >
Do đó theo qui tắc cộng , ta cần tính :
1 2

n
A A A+ + +
.
Ta có :
1 2
0A A
= =
. Nếu z=3 thì x=1 và y=2 , do đó không tồn tại tam
giác.Vậy
3
0A
=
. Bây giờ ta giả sử rằng
4k
≥
.
Ta xét 2 trường hợp :
Trường hợp 1 : Trong trường hợp này , ta giả sử rằng k chẳn, tức là
k=2m ; m∈Z ; m≥2. Bởi vì x<y nên x+y>2x . Chú ý rằng x+y> z . Ta xét
2x≤z và 2x> z nghĩa là 1≤x≤m ; và m <x .

− − −
= + = −
Chú ý rằng công thức này vẫn đúng khi m=1 nghĩa là khi k=2.
Trường hợp 2 : Trong trường hợp này ta giả sử k lẻ , nghĩa là k=2m+1
với k là số nguyên , m≥2.
Khi 1≤x≤m , ta cũng cần có y> z-x = k-x. Lúc này , k=2m+1>2x
như thế k-x >x . Như trước đó , y có thể lấy các giá trị nguyên nằm giữa
k-x+1 và k-1 , như thế sẽ có (k-1)- (k-x+1) + 1= x-1 giá trị mà y có thể
nhận .
Khi m < x . Như thế sẽ có (k-1)- (x-1)+ 1= k-x-1= 2m-x giá trị mà
y có thể nhận được . Bởi vậy , cho nên khi k= 2m+1
( ) ( ) ( )
( ) ( )
( )
2 1
1 1 1 0
1 1
1 2 1 1
2 2
m m m m
k
x x m x i
m m m m
A x m x x i m m
−
= = + = =
− −
= − + − = − + = + = −
∑ ∑ ∑ ∑
.

=
∑ ∑ ∑ ∑
Nếu n chẳn : n=2p với p là số nguyên dương . Thì ta có :
6
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
( ) ( )
( ) ( )
( ) ( )
1 2
1 3 2 1 2 4 2
1 1 1
2
2
0 1 1 01 1 2
1 4 5
6
n
p p
p p p p
m m m m
A A A
A A A A A A
m m m m m
p p p
−
− − −
= = = =

= + + + −
− +
= − −
− −
=
10. Trước khi Rick mở một tủ đựng đồ thể thao của mính , thì Rick
phải nhớ mật mã khóa của tủ , Hai trong các bộ 3 cặp số của mật mã là 17
và 24 , nhưng anh ta không nhớ được cặp số thứ ba. Và không nhớ được
thứ tự của 3 cặp số . Có 40 khả năng của cặp số thứ ba. Trong 10 giây ,
thì có thể nhớ được tất cả các khả năng xảy không ?
GIẢI :
Ta xét 6 tập con của các khả năng của mã khóa .
( )
{ }
( )
{ }
( )
{ }
( )
{ }
( )
{ }
( )
{ }
1
2
3
4
5
6

S
là tập hợp các bằng lái không có số 0.

2
S
là tập hợp các bằng lái không có chữ o.

3
S
là tập hợp các bằng lái không có số 0và không có chữ o.
Ta có :
3 3 3 3 3 3
1 2 3
26 .9 25 .10 25 .9 17047279.S S S+ − = + − =
12. Xác định số số nguyên dương nhỏ hơn 1000 chứa ít nhất một chữ
số 1 trong cách viết thập phân.
GIẢI :
CÁCH 1 :
Gọi S là tập hợp các số nguyên dương nhỏ hơn 1000.
999.S =
Gọi
1 2 3
; ;S S S
là tập hợp các số nguyên dương có 1 , 2, 3 chữ số.
Với i=1 ;2 ;3 đặt
i i
A S
⊂
chứa đúng các chữ số đó và có ít nhất 1 chữ số 1.
Ta chỉ cần tinh

1 2 3
A A A+ +
=271.
CÁCH 2:
Ta có thể phân chia tập hợp như sau : Gọi S’ là tập hợp những số nguyên
không âm nhỏ hơn 1000. Gọi
1
B
là tập hợp các số nguyên không âm nhỏ
hơn 1000 chứa ít nhất 1 chữ số 1, và Gọi
2
B
là tập hợp các số nguyên
không âm nhỏ hơn 1000 không chứa chữ số 1. Nghĩa là
1 2
' 1000.B B S+ = =
Ta có
2
9.9.9 729B
= =
Nên
1
1000 729 271B
= − =
.
13. Có 15 lỗ thông hơi máy lạnh trong 1 rạp hát . Để giữ cho nhiệt độ
mát mẻ , phải có ít nhất 1 lỗ thông hơi làm việc suốt thời gian. Hỏi có bao
8
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
nhiêu cách thực hiện.

∈
có
ảnh khác nhau thì f được gọi là đơn ánh ( injective- one to one) . Nếu f
vừa là đơn ánh vừa là toàn ánh thì f là song ánh( bijective– one-to-one
correspondence)
HOÁN VỊ : ( PERMUTATION)( khái niệm mở rộng):tương đương với
khái niệm chỉnh hợp của sgk)
Một cách sắp xếp thứ tự m phần tử phân biệt của n phần tử phân biệt cho
trước ( m≤n) được gọi là 1 hoán vị lấy m phần tử của n phần tử . Vì các
phần tử là không lặp lại nên nên hoán vị cùng là không lặp và số hoán vị
lấy m phần tử của n phần tử phân biệt được ký hiệu là
( )
m m
n n
P A
.Khi đó ta
có :
( ) ( ) ( )
( )
!
1 2 1
!
m
n
n
A n n n n m
n m
= − − − + =
−
.( m≤n).

chữ số không lặp lại.
GIẢI:
Gọi abcde là số cần tìm , Chữ số a có thể chọn từ {2;3;4;5;6} và chữ số e
có thể chọn từ {0;2;4;6;8} . Vì {2;3;4;5;6}
I
{0;2;4;6;8}={2;4;6} nên ta
chia thành 2 trường hợp rời nhau:
Trường hợp 1: a∈{2;4;6} : a có 3 cách chọn , e có 5-1=4 cách chọn , và
bcd có
3 3
10 2 8
A A
−
=
cách chọn .Vậy có
3
8
3 4 4032A
× × =
số chẳn.
Trường hợp 2: a∈{3;5} a có 2 cách chọn , e có 5 cách chọn và còn lại
bcd có
3
8
A
cách chọn . Vậy có
3
8
2 5 3360A
× × =

= = + + + = + + + =
∑
.
b/ Gọi
1
α
xác định tổng của các chữ số hàng đơn vị của các số trong S,
2
α
xác định tổng của các chữ số hàng chục của các số trong S;
3
α
xác định tổng của các chữ số hàng trăm của các số trong S
4
α
xác định tổng của các chữ số hàng ngàn của. các số trong S.
Do đó ;
1 2 3 4
10 100 1000
α α α α α
= + + +
Trước hết , ta xác định
1
α
; Rỏ ràng , tổng của các chữ số hàng đơn vị
trong
1
S
là 1+3+5+7 =16. Trong
2

+ + + =
.
Trong
4
S
có
3
3
A
số mà các chữ số đơn vị tương ứng là 1,3,5,7 nên tổng
các chữ số hàng đơn vị của các số trong
4
S
, là
3
3
(1 3 5 7) 96A
+ + + =
.
Cho nên :
1
16 48 96 96 256
α
= + + + =
Tương tự , ta có :
( ) ( ) ( )
( )
1 2 3
2 3 3 3
2 3

có thể chia thành cặp {13;75};{15;73};{17;71};{35;53}…
và tổng của 2 số trong mỗi cặp này là 88.
Tương tự ; 24 số trong
3
S
có thể chia thành cặp và tổng của 2 số trong
mỗi cặp này là 888.
24 số trong
4
S
có thể chia thành cặp và tổng của 2 số trong mỗi cặp này
11
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
là 8888.
Như vậy :
4 12 24 24
8 88 888 8888 117856.
2 2 2 2
α
= × + × + × + × =
TỔ HỢP ( COMBINATION)
Một lựa chon m phần tử phân biệt không sắp xếp thứ tự của n phần tử
phân biệt được gọi là tổ hợp m phần tử của n phần tử. Vì các phần tử
không lặp lại nên tổ hợp này còn gọi là tổ hợp không lặp. Số tổ hợp
không lặp lại của m phần tử từ n phần tử là
( )
!
! !
m
n

C
−
−
. ( chỉ cần lấy thêm r-1 phần tử)
Số cách lấy không có phần tử “1” là
1
r
n
C
−
.
Từ đó suy ra đpcm.
Một dãy các số
1 2
; ;
n
a a a
được gọi là xâu k-aray , với n,k ∈
*
N
, nếu
{ }
0;1;2; ; 1
i
a k
∈ −
với mỗi i=1 ;2 ;…… ;n. Độ dài của xâu là n , chính là
số số hạng trong xâu .Đôi khi một xâu như thế có thể viết là
( )
1 2

12
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
Trước hết ta xếp 3 số 0 vào 3 trong 7 vị trí của chuỗi .
Sau đó xếp 4 số 1 vào 4 vị trí còn lại.
Vậy có
3 4
7 4
.C C
chuỗi thỏa điều kiện .
20. Có bao nhiêu cách lập ra 1 Ủy Ban gồm 5 người từ 11 người bao
gồm 4 thầy giáo và 7 học sinh, nếu :
a/ Không có yêu cầu về cách lựa chọn .
b/Ủy ban phải bao gồm đúng 2 thầy giáo .
c/ Ủy ban phải bao gồm ít nhất 3 thầy giáo.
d/ Đặc biệt 1 thầy giáo và 1 học sinh không thể cùng nằm trong ủy ban.
GIẢI:
a/
5
11
462C
=
b/
2 3
4 7
. 210C C
=
.
c/
3 2 4 1
4 7 4 7

13
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
A\{x;y} . Số cách để chọn người cùng cặp với z là 2n-3. Tiếp tục quá
trình đó .Số cách cần tìm là :
(2n-1)(2n-3)… 5.3.1.
Cách 2:
Trước hết ta tạo ra 1 tập con có 2 phần tử của A và đặt vào vị trí (1) như
hình vẽ .Có
2
2n
C
cách là như thế .
{ { { {
(1) (2) (3) ( )
{ } { } { } { }
n

Kế tiếp , lại tạo ra 1 tập con có 2 phần tử từ phần còn lại của A và đặt
chúng vào vị trí (2) . Có
2
2 2n
C
−
cách làm như thế . Và cứ tiếp tục như vậy.
Do đó số cách cần tìm là :
2 2 2 2
2 2 2 4 2
. .
!
n n

nó là phân biệt và lấy từ các chữ số {1;2;3;4;5}
GIẢI:
Cách 1:
Ta chia thành các loại:
- Số các có 5 chữ số mà chữ số hàng chục nghìn có thể là 1 trong các số
3,4,5:
là
1
3 4
.A P
.
14
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
- Số các có 5 chữ số mà chữ số hàng chục nghìn có thể là số 2 và chũ số
hàng nghìn là 1 trong các số 3,4,5 là
1
3 3
.A P
.
-Số các có 5 chữ số mà chữ số hàng chục nghìn có thể là 2 và chữ số hàng
nghìn là 1 là
3
P
.
Vậy tổng số các số là
1 1
3 4 3 3 3
. . 96A P A P P
+ + =
.

n
C
cạnh . Kế tiếp , mỗi điểm P của S
theo điều kiện (ii) có thể vẽ được 1 đường tròn tâm P(C(P)) sao cho
đường tròn đó chứa ít nhất k điểm của S. Rõ ràng rằng mỗi điểm của S
nằm trên (C(P)) xác định ít nhất
2
k
C
cạnh . Do đó với n điểm P trong tập
hợp S thì tổng số cạnh ít nhất là n
2
k
C
( có đếm lặp lại). Bây giờ ta thấy
rằng , các cạnh được đếm nhiều hơn 1 lần. 1 cạnh được đếm nhiều hơn 1
lần khi và chỉ khi cạnh đó là dây cung chung của ít nhất 2 đường tròn. Vì
2 đường tròn có nhiều nhất 1 dây cung chung cho nên n đường tròn , số
dây cung chung được đếm lặp lại nhiều nhất
2
n
C
. Cho nên :
( )
( )
2 2 2 2 2 2 2
2
2
2 2 1 0
1 1 8 1

Xác định n phần tử phân biệt là 1,2,3…n. Thế thì một tổ hợp lặp có
dạng :
( ) ( )
1 2 1 2
; ; ; 1
m m
i i i i i i n≤ ≤ ≤ ≤ ≤
Đặt
1 1
2 2
1 2
1
1 1

1
m
m m
j i
j i
j j j n m
j i m
=


= +

⇒ ≤ < < < ≤ + −




lặp lại tương ứng là
1 2 1 2
; ; :
m m
n n n n n n n
+ + + =
, tất cả các hoán vị của n
phần tử được gọi là tất cả các hoán vị của các đối tượng phân biệt không
đầy đủ , ta có số hoán vị loại đó là
1 2
; ; ;
1 2
!
!. ! !
k
n n n
n
k
n
A
n n n
=
.
Chứng minh :
Gọi f là số hoán vị thỏa mãn bài toán .Nếu ta trao đổi các phần tử trong
cùng một loại và sắp xếp lẩn nhau từng nhóm thì ta sẽ có
1 2
!. ! !
k
n n n

chỉ ra ở trên có thể biểu diễn dưới dạng
2 1 3 1
b b b b
. Đó là hoán vị của bộ
{ }
1 2 3
2 ; ;b b b×
.
Cách thứ hai biểu diễn bởi
1 3 3
b b b
. Đó là hoán vị của
{ }
3 1
2 ;b b
×
.
Chú ý rằng tổng của các chỉ số trong mỗi bộ đều bằng 7.
GIẢI:
Từ minh họa trên , ta thấy số cách yêu cầu bằng với số hoán vị của một
vài số
i
b
sao cho tổng của các chỉ số của
i
b
là 7. Ta có 8 trường hợp bao
gồm các khả năng sau đây:
( ) { } ( ) { }
( ) { } ( ) { }

2! 3!
3! 3!
( ) 3 (viii) =3
2! 2!
i
iii
v
vii
=
= =
= =
=
Như vậy sẽ có : 44 cách lát .
27. Chứng minh rằng (4n)! là bội số của
3
2 .3
n n
với mỗi số tự nhiên n.
GIẢI:
Xét tập hợp
{ }
1 2
4 ;4 ; ;4
n
M a a a
= × × ×
.
Ta có :
( )
( )

Cho M=
{ }
1 2
. ; . ; ; . ;
n
a a a∞ ∞ ∞
là 1 multi-set với n ∈N.
Một multi-set của dạng
{ }
1 1 2 2
. ; . ; ; .
n n
m a m a m a
với
i
m
là các số nguyên
không âm, được gọi là một
( )
1 2

n
m m m
+ + +
-phần tử của multi-subset cua
M. Với số nguyên không âm r , goi
r
n
H
xác định số r-phần tử của multi-

tự khác nhau dẫn đến chuỗi nhị phân khác nhau. Ta thấy có 1 song ánh
giữa tập hợp các cách sắp xếp với tập hợp chuỗi nhị phân như trên. Cho
nên ta có ,
3 2
6 8
H C
=
.
Xét trường hợp tổng quát:
1
a
2
a
3
a
n
a
S
1
oo o
r
14 2 43
1
oo o
r
14 2 43
3
oo o
r
14 2 43

1 2
. ; . ; ; . ;
n
a a a∞ ∞ ∞
là 1 tập con với n ∈N.Số r-phần tử của M là
1
r r
n n r
H C
+ −
=
.
NHÂN TỔ HỢP:
Sắp xếp n phần tử phân biệt vào k loại phân biệt ( k≤n) sao cho có
i
n

phần tử trong nhóm thứ i , ( i=1;2….;k;
1 2

k
n n n n
+ + + =
) Thế thì số cách
19
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
sắp xếp là :
1 2
; ; ;
1 2

n n
C
−
…………………………….
Số cách lấy
k
n
từ n
1 2 1

k
n n n
−
− − − −
phần tử là
1 2 1

k
k
n
n n n n
C
−
− − − −
Sử dụng qui tắc nhân ta được số cách thành lập là :
( ) ( ) ( )
1 2
1 1 2 1
1 2 1
1

=
29. Giả sử có 3 cờ đỏ , 4 cờ xanh và 2 cờ vàng để đặt vào vị trí của 9
cột cờ đã đánh số . Hỏi có bao nhiêu ký hiệu phân biệt từ các cây cờ đó.
GIẢI:
Số ký hiệu phân biệt là :
9!
1260
3!2!4!
=
.
30. Có bao nhiêu cách chọn ra 3 cặp đôi từ n người ( n≥6).
GIẢI:
Cách 1:
Số cách lấy 6 người từ n người :
6
n
C
.
6 người này phân chia thành 3 nhóm , mỗi nhóm có đúng 2 người , số
cách chia là :
2,2,2
6
C
nhưng 3 nhóm này không cần thứ tự nên số cách chọn
theo yêu cầu là:
( )
6 2,2,2
6
.
!

6 4 2
. . .
!
3! 48( 6)!
n
C C C C
n
n
=
−
20
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
HOÁN VỊ VÒNG TRÒN CỦA CÁC PHẦN TỬ PHÂN BIỆT:
Nếu ta sắp xếp n phần tử phân biệt trên 1 đường tròn thì hoán vị được gọi
là hoán vị vòng tròn của n phần tử, Số hoán vị vòng tròn của n phần tử
là :
( )
1 !
n
P
n
n
= −
.
CHỨNG MINH :
Vì n hoán vị đường thẳng cho ta 1 hoán vị đường tròn mà ta lại có n!
hoán vị đường thẳng nên suy ra đpcm.
Các hoán vị nhận được từ nhau qua 1 phép quay quanh tâm , được xem là
một.
Gọi A là một tập hợp gồm n phần tử phân biệt . Với 0≤r≤n , số hoán vị

Vậy số cách xếp thỏa mãn bài toán là : 7!- 1440=3600.
c/ Trước hết ta xếp 5 nam vào bàn , có (5-1)! Cách xếp.
Lần lượt có 5 cách để xếp G1; 4 cách để xếp G2; và 3 cách để xếp G3.
Vậy có tất cả 4!×5×4×3=1440 cách xếp.
32. Tìm số cách xếp chỗ ngồi cho n cặp vợ chồng xung quanh 1 bàn
21
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
tròn sao cho :
a/ Nam và nữ ngồi luân phiên.
b/ Mỗi Nữ ngồi kề với chồng của mình .
GIẢI:
a/ Xếp n người nam có (n-1)! cách xếp.
n người nữ có thể ngồi vào n khoảng trong giữa 2 người nam , nên có n!
cách xếp . Vậy có n!.(n-1)! Cách xếp.
b/ Mỗi cặp vợ chồng xem như 1 phần tử .
Số cách xếp n phần tử này là (n-1)! . Vì mỗi cặp vợ chồng có 2 cách xếp ,
nên số cách xêp tổng cộng là :
( )
1 !.2
n
n −
.
CHÚ Ý : Một bài toán khó hơn và nổi tiếng liên hệ với bài tập trên là:
Có bao nhiêu cách xếp chỗ ngồi cho n cặp vợ chồng (n≥3) quanh 1 bàn
tròn sao chon nam và nữ ngồi xen kẽ nhau nhưng vợ không ngồi cạnh
chồng ?
Bài toán này lần đầu tiên được giới thiệu bởi nhà toán học Pháp Francis
Edward Anatole Lucas (1842-1891)
33. Nếu phải xếp ít nhất 1 người trên một bàn thì có bao nhiêu cách
xếp 6 người ngồi:

Trường hợp 3: Ta chú ý trường hợp này . Số cách để chia 6 thành 2 nhóm
22
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
3 và 3 là
3
6
1
2
C
. Vậy số cách xếp là
3
6
1
2! 2! 40
2
C
× × =
.
Cho nên theo qui tắc cộng là : 144+90+40=274.
b/ Với 3 bàn ta có 3 trường hợp : (1)4+1+1 (2)3+2+1 (3) 2+2+2.
Số cách sắp xếp trong mỗi trường hợp là:
( )
( )
4 1
6 2
3 2
6 3
2 2
6 4
1

Để đơn giản , ta gọi r phần tử phân biệt là 1,2,….r. Xét phần tử “1” , với
bất kỳ cách sắp xếp các phần tử , hoặc là :
(i) 1 chỉ là 1 phân tử trong 1 đường tròn .
(ii) 1 trộn với các phần tử khác trong 1 đường tròn.
Trong trường hợp thứ nhất có s(r-1;n-1) cách xếp .
Trong trường hợp thứ hai có s(r-1;n) cách xếp các phần tử 2;3;…r vào n
đường tròn , khi đó 1 có thể đặt vào 1 trong r-1 khoảng trống phân biệt
đến “ immediate right “ của r-1 phần tử tương ứng. Theo qui tắc nhân ,
trường hợp này có (r-1).s(r-1;n) cách sắp xếp.
Suy ra đpcm.
Sử dụng các giá trị ban đầu: s(0;0)=1 ; s(r;0)=0 ; s(r;1)= (r-1)! Với r≥1ta
23
CÁC KIẾN THỨC CƠ BẢN VỀ TỔ HỢP GIÁO VIÊN : TRẦN TIẾN ĐẠT
có thể tìm được các giá trị s(r;n) với r,n khá nhỏ.
SỐ XÂU CHUỖI HẠT:
Giả sử 1 xâu chuỗi hạt bao gồm n hột được sắp xếp trên 1 đường tròn thế
thì số xâu phân biệt là 1 ( nếu n=1 ;2) hay
( )
1
1 !( 3)
2
n n
− ≥
.
CHỨNG MINH :
Nếu n=1 hay n=2 thì số xâu chuỗi là 1.
Giả sử n ≥3, bởi vì 1 xâu chuỗi có thể quay hay lật ngược lại mà không làm
thay đổi gì , nên số xâu chuỗi bằng ½ số hoán vị vòng tròn.
35. Có bao nhiêu cách sắp xếp 6 nữ và 15 nam để nhảy múa theo vòng
tròn sao cho có ít nhất 2 người nam đứng giữa bất kỳ 2 người nữ .

m n
n m n m
C C
−
+ − + −
=
.
CHỨNG MINH :
Ta xét mỗi nghiệm không âm của phương trình là
( )
1 2
; ; ;
m
x x x
tương ứng
với 1 hoán vị của n đường tròn “ O” và m-1 cạnh “/ “ :
1 2
OO / OO / / OO
m
x x x
O O O
14 2 43 14 2 43 142 43
.
Ở đây
1
x
là số đường tròn “O” ở bên trái dấu / thứ nhất,
1i
x
+

m
x x x n m n N n m
+ + + = ∈ ≥
(1)
bằng
1
1
m
n
C
−
−
.
CHỨNG MINH :
Đặt
1( 1;2 ; )
i i
y x i m
= − =
Khi đó ta có :
1 2
(1)
m
y y y n m
⇔ + + + = −
.(2)
Số nghiệm dương của (1) bằng số nghiệm không âm của phương trình (2)
do đó sẽ bằng
( )
1 1

(2)
Thế thì số nghiệm nguyên của (1) bằng số nghiệm nguyên không âm của
(2) tức là
6 1 5 3
3 6 1 8 8
C C C
−
+ −
= =
.Như vậy 15 nam được chia thành 6 nhóm sao
cho trong mỗi nhóm có ít nhất 2 nam thì có
3
8
C
cách. Ta sắp xếp 6 nhóm
đó trong vòng tròn thì có (6-1)!=5! cách. Người lảnh đạo của mỗi nhóm
là 1 nữ và vị trí của nó được xác định . 15 nam ngồi trên đường tròn có
15! cách . Theo qui tắc nhân ta có số hoán vị thỏa mãn yêu cầu bài toán là
3
8
8!.15!
.5!.15!
3!
C =
.
36. Có bao nhiêu số nguyên có 3 chữ số sao cho tổng các chữ số của
mỗi số nguyên là 11.
GIẢI:
Ta xác định chữ số hàng trăm , hàng chục và hàng đơn vị là
1 2 3 1 2 3