TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
KHOA TOÁN
-------------------------------

NGUYỄN THỊ THÚY

NGUYÊN LÝ ĐẾM

H

LU N T T NGHIỆP ĐẠI HỌC
C

nn

n

Đại số

N ƣời ƣớng dẫn khoa học
T .S DƢƠNG THỊ LUYẾN

HÀ NỘI - 2014


GVHD:Th.S Dương Thị Luyến

Khóa luận tốt nghiệp

LỜI CẢM ƠN
Trong thời gian nghiên cứu và hoàn thành khóa luận, em đã nhận

(đã nêu trong mục tài liệu tham khảo).
Em xin cam đoan những kết quả trong khóa luận này là kết quả
nghiên cứu của bản thân, không trùng với kết quả của tác giả khác. Nếu
sai em xin hoàn toàn chịu trách nhiệm.
Hà Nội, tháng 5 năm 2014
Sinh viên

Nguyễn Thị Thúy


Khóa luận tốt nghiệp

GVHD:Th.S Dương Thị Luyến
MỤC LỤC

MỞ ĐẦU .................................................................................................. 1
NỘI DUNG............................................................................................... 3
CHƢƠNG 1. CƠ SỞ LÝ THUYẾT ......................................................... 3
1.1. Những kiến thức cơ bản về lý thuyết tổ hợp .................................... ..3
1.1.1. Các khái niệm và định nghĩa ..................................................... 3
1.1.2. Các phép toán trên tập hợp ...................................................... 4
1.2. Hai nguyên lý đếm cơ bản ................................................................ 6
1.2.1. Nguyên lý cộng ........................................................................ 6
1.2.2. Nguyên lý nhân ........................................................................ 8
1.3. Hoán vị, chỉnh hợp, tổ hợp ............................................................... 11
1.3.1. Hoán vị .................................................................................... 11
a. Hoán vị không lặp ..................................................................... 11
b. Hoán vị có lặp ........................................................................... 13
c. Hoán vị vòng tròn ...................................................................... 15
1.3.2. Chỉnh hợp ................................................................................ 16


Khóa luận tốt nghiệp

MỞ ĐẦU
Toán tổ hợp là một lĩnh vự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 ngành khoa học khác. 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 các 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 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 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. Đặc biệt, các bài toán đếm đƣợc nghiên cứu từ
thế kỉ 17, khi những câu hỏi về tổ hợp đƣợc đƣa ra trong những công
trình nghiên cứu các trò chơi may rủi. Liệt kê, đếm các đối tƣợng có tính
chất nào đó là phần quan trọng của lý thuyết tổ hợp. chúng ta cần phải
đếm các đối tƣợng để giải nhiều bài toán khác nhau. Em là ngƣời rất yêu
thích toán tổ hợp vì vậy em lựa chọn đề tài: “NGUYÊN LÝ ĐẾM” 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 đếm.
Trong khóa luận này em đã hệ thống hóa,phân tích, diễn giải đƣợc
một số khái niệm về hai nguyên lý đếm cơ bản cũng nhƣ một số khái



Khóa luận tốt nghiệp

NỘI DUNG
CHƢƠNG 1. CƠ SỞ LÝ THUYẾT
1.1 Những kiến thức cơ bản về lý thuyết tập hợp
1.1.1 Các khái niệm v địn n
Địn n

ĩa

ĩa 1. Tập các đối tƣợng trong một tập hợp đƣợc gọi là các phần

tử của tập hợp. Các tập hợp thƣờng đƣợc kí hiệu bởi những chữ cái in
hoa nhƣ A, B, X, Y…, các phần tử thuộc tập hợp hay đƣợc kí hiệu bởi
các chữ cái in thƣờng nhƣ a, b, c, u, v… Để chỉ a là phần tử của tập A ta
viết a  A, trái lại nếu a không thuộc A ta viết a  A.
Tập hợp không chứa bất kì phần tử nào đƣợc gọi là tập rỗng (kí hiệu
là ϕ)
Tập hợp A đƣợc gọi là bằng tập hợp B khi và chỉ khi chúng có
chung các phần tử và đƣợc kí hiệu là A=B. Ví dụ tập A={ 1, 3, 5} sẽ
bằng tập B={ 3, 5, 1}.
Địn n

ĩa 2. Tập A đƣợc gọi là một tập con của tập hợp B và kí hiệu là

A  B khi và chỉ khi mọi phần tử của tập hợp A đều là phần tử của tập
hợp B.
Từ định nghĩa trên chúng ta rút ra một số hệ quả sau:
-


tƣơng đƣơng với bất kì tập con thực sự nào của A. Một tập không phải là
tập hữu hạn thì đƣợc gọi là tập vô hạn.
Nhận xét. Khi tập hợp A là hữu hạn thì bản số của nó chính là số lƣợng
các phần tử. Kí hiệu là |A| hoặc card A.
Địn n

ĩa 4. Cho tập hữu hạn X = {a1, a2, a3,…, an} và một số tự nhiên

k, kn. Khi đó
(i) Bộ k phần tử (ai1, ai2, ai3,…, aik), aij  X đƣợc gọi là bộ có thứ
tự nếu đổi vị trí các phần tử ta đƣợc một bộ mới. Ngƣợc lại ta
đƣợc bộ (ai1, ai2, ai3,…, aik), aij  X là bộ không có tính thứ tự.
(ii) Bộ k phần tử (ai1, ai2, ai3,…, aik), aij  X đƣợc gọi là bộ không
lặp nếu aij  ail,  i, l  {1, 2,…, k}, j  l. Ngƣợc lại ta có bộ k
phần tử (ai1, ai2, ai3,…, aik), aij  X là bộ có lặp.
Địn n

ĩa 5. Cho A và B là hai tập hợp. Tích đề các của A và B đƣợc

ký hiệu là A  B, là tập hợp gồm tất cả các cặp (a, b) với aA, bB.
Hay có thể biểu diễn bằng biểu thức
A  B = { (a, b) | aA và bB}.
Tích đề các của các tập A1, A2, …, An đƣợc kí hiệu là A1  A2  … An
là tập hợp gồm các dãy sắp thứ tự (a1, a2, a3,…, an) trong đó ai  Ai với
i= 1, 2,…, n. Nói cách khác:
A1  A2  … An = { (a1, a2, a3,…, an) | ai  Ai với i= 1, 2,…, n}.
1.1.2 Các phép toán trên tập hợp
Các tập hợp có thể đƣợc tổ hợp với nhau theo nhiều cách khác nhau
thông qua các phép toán trên tập hợp. Các phép toán trên tập hợp bao

Địn n

ĩa 4. Cho A và B là hai tập hợp. Hiệu của A cho B là tập hợp
B

đƣợc kí hiệu là A\B hoặc C A , có các phần tử thuộc tập hợp A nhƣng
không thuộc tập hợp B. Hiệu của A và B còn đƣợc gọi là phần bù của B
đối với A. Nói cách khác:
A\B = { x | x A và xB}.
Địn n

ĩa 5. Cho tập hợp A  B. Ta gọi

là phần bù của A trong B là

một tập hợp bao gồm những phần tử không thuộc A hay
Địn n

= { x | xA}

ĩa 6. Hợp của các tập hợp A1, A2, …, An là tập hợp gồm tất cả

các phần tử thuộc ít nhất một trong các tập hợp Ai (i= 1,2, …, n). Kí hiệu
n
i 1

Địn n

A i  A1  A2  ...  A n .


n

| A1  A 2    A n |   A i 
i 1



n



1 i  k  l  n

n



1 i  k  n

Ai  A k 

A i  A k  A l  ...  (1)n 1 A1  A 2  ...  A n

1.2 Hai nguyên lý đếm cơ bản
1.2.1 Nguyên lý cộng (tổng)
Giả sử có hai sự kiện T1, T2 rời nhau (loại trừ nhau: Nếu T1 xảy ra thì
T2 không xảy ra)
Nếu T1 xảy ra n cách.
Nếu T2 xảy ra m cách.
Thì sự kiện xảy ra hoặc T1 hoặc T2 là n + m cách.

i 1

i 1

X i và

n

n
i 1

X i là

Xi =

X
i 1

i

(1.1)

Chứng minh. Ta chứng minh quy nạp theo n với n  2.
Nếu n = 2 thì |X1  X2| = |X1| + |X2| - |X1  X2| = |X1| + |X2|
(do |X1  X2| = ϕ)
Giả sử (1.1) đúng với n = k, (k  2). Ta sẽ chứng minh (1.1) đúng
với n = k+1, nghĩa là
k 1
i 1



=

X
i 1

i

Suy ra (1.2) đƣợc chứng minh.
Theo nguyên lý quy nạp toán học, quy tắc cộng là đúng với mọi n
 , n 2.
Ví dụ 1. Từ các chữ số 1, 2, 3 có thể lập đƣợc bao nhiêu số khác nhau có
những chữ số khác nhau.
Giải
Từ các chữ số 1, 2, 3 có thể lập đƣợc:
- Ba số khác nhau có một chữ số là: 1, 2, 3. Trong trƣờng hợp này
có 3 cách lập.
- Sáu số khác nhau, mỗi số có hai chữ số là: 12, 13, 21, 23, 31, 32.
Trong trƣờng hợp này có 6 cách lập.
- Sáu số khác nhau, mỗi số có ba chữ số là: 123, 132, 213, 231, 312,
321. Trong trƣờng hợp này có 6 cách lập.
Các cách lập trên đôi một không trùng nhau. Vậy theo quy tắc cộng
có 3 + 6 + 6 = 15 cách lập những số khác nhau có những chữ số khác
nhau từ các chữ số 1, 2, 3.
1.2.2 Nguyên lý nhân (tích)
Giả sử ta có một công việc A tách ra làm hai công đoạn A1, A2.
A1

A2
A

Biểu diễn dưới dạng tập hợp
Nếu A1, A2, …, An là n tập hợp hữu hạn (n  1), 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 cần chú ý là việc chọn một phần tử của
tích đề các A1 A2 … An đƣợc tiến hành bằng cách chọn lần lƣợt 1
phần tử của A1, một phần tử của A2, …, một phần tử của An. Theo quy
tắc nhân ta nhận đƣợc đẳng thức: |A1 A2 …An| = |A1|. A2|. …. |An|
Định lý 2. Giả sử có n tập hữu hạn Xi, (i = 1, n ) với |Xi| = mi. Chọn một
bộ gồm n phần tử (a1, a2, … , an) với ai  Xi. Khi đó, số cách chọn khác
nhau là |X1  X2  …Xn | và
n

|X1  X2  …Xn | =

Nguyễn Thị Thúy - K36A - Toán

m
i 1

i

(1.3)

9


GVHD:Th.S Dương Thị Luyến

Khóa luận tốt nghiệp

...

a

...

1

m2

2

m2

m1

, b m2



Đặt Ei = { (ai, b1), (ai, b2),…, (ai, b m2 ) : 1  i  m1 }  |Ei| = m2.
Ta có X1  X2 = E1  E2 … E m1 với Ei  Ej = ϕ, i  j. Theo quy
tắc cộng ta đƣợc |X1  X2| = |E1  E2 … E m1 | =

m1

E
i 1

i

Vậy |X1  X2  …Xk Xk+1| = m1.m2….mk.mk+1.
Theo nguyên lý quy nạp toán học, công thức (1.3) đúng với mọi n
 , n 2.
Ví dụ 2. Có bao nhiêu số gồm ba chữ số khác nhau có thể lập từ các chữ
số 0, 2, 4, 6, 8.
Giải
Số cần lập có dạng a1a 2 a 3 . Ta có 4 cách chọn a1, vì a1  0. Ứng với
mỗi cách chọn a1 có 4 cách chọn a2. Ứng với mỗi cách chọn a1, a2 có 3
cách chọn a3. Theo quy tắc nhân ta có 4.4.3 = 48 số cần lập.
1.3

Hoán vị, chỉnh hợp, tổ hợp

1.3.1. Hoán vị
a. Hoán vị không lặp
 Định nghĩa
Cho tập hợp A gồm n phần tử. Mỗi cách sắp xếp n phần tử này
thành một dãy theo thứ tự xác định gọi là một hoán vị của tập hợp A.
Ta có thể phát biểu:
Số các hoán vị của tập n phần tử bằng số các đơn ánh (đồng thời
cũng là song ánh) từ tập n phần tử vào tập n phần tử và bằng n!
Thông thƣờng ngƣời ta còn gọi mọi song ánh từ A lên A là một
phép thế trên A vì thế ta còn có thể phát biểu:

Nguyễn Thị Thúy - K36A - Toán

11


GVHD:Th.S Dương Thị Luyến


c a
 ;
b c

b
b

c

a

b
a

c  a
 ;
c b

b
c

c

a

 Công thức tính
Kí hiệu Pn là số các hoán vị của n phần tử ta có Pn = n.(n-1)…2.1= n!
Chứng minh.
Ta chứng minh công thức này dựa trên nguyên lý nhân. Xét công

8, 9 sao cho thỏa mãn 2 điều kiện sau:
1. Mỗi chữ số đều có mặt 1 lần trong các số đƣợc lập.
2. Chữ số 0 không đứng ở vị trí thứ nhất bên trái.
Giải
Theo 1. Ta lập đƣợc 10! số, nếu số đầu tiên bằng 0 ta có 9! số
Do vậy để thỏa mãn cả hai điều kiện 1, 2 ta có
10! - 9! = 9!9 = 3265920 số.
b. Hoán vị có lặp
 Định nghĩa
Có n vật (n  1) đƣợc sắp vào n vị trí trong đó:
Có n1 vật loại 1
Có n2 vật loại 2
…
Có nk vật loại k
Ở đây n1 + n2 + …+ nk = n
Mỗi cách sắp thứ tự n vật nhƣ trên vào n vị trí gọi là hoán vị có lặp
của n phần tử đó.
 Công thức tính
Kí hiệu Cn(n1,n2,…,nk) là số các hoán vị lặp của n phần tử
Cn(n1,n2,…,nk) =

n!
n1 !n 2 !...n k !

Chứng minh.
Đầu tiên, nếu xem nhƣ n phần tử là khác nhau, ta có n! hoán vị. Tuy
nhiên do có n1 phần tử loại 1 giống nhau, nên ứng với một hoán vị ban

Nguyễn Thị Thúy - K36A - Toán


P1EP2P3ER; P1EP3P2ER; P2EP1P3ER; P2EP3P1ER
P3EP1P2ER; P3EP2P1ER
Cả 6 cách sắp xếp này trùng với cách sắp xếp PEPPER nếu ta bỏ đi
việc đánh chỉ số cho các mẫu tự P. Tiếp theo mỗi cách sắp xếp dãy 6
mẫu tự trong đó các mẫu tự P đã đƣợc đánh chỉ số ta sẽ có 2 cách sắp
xếpkhác nhau nếu các mẫu tự E đƣợc phân biệt bằng cách đánh chỉ số
cho chúng. Chẳng hạn, nếu phân biệt 2 mẫu tự e thì sự sắp xếp
P1EP2P3ER

có 2 cách sắp xếp tƣơng ứng là P1E1P2P3E2R và

P1E2P2P3E1R. Từ đó chúng ta có:
3!  2!  (Số cách sắp xếp các mẫu tự trong từ PEPPER)
= Số hoán vị của 6 phần tử P1, E1, P2, P3, E2, R
= 6!

Nguyễn Thị Thúy - K36A - Toán

14


GVHD:Th.S Dương Thị Luyến

Khóa luận tốt nghiệp

Ví dụ 7. Có bao nhiêu cách phân phối 7 chuyên gia trẻ vào 3 ban, theo
thứ tự cần 1, 2, 4 chuyên gia?
Giải
Số cách phân phối là C 7 1, 2, 4  


phần tử: P5 = 5! = 120

Nguyễn Thị Thúy - K36A - Toán

15


Khóa luận tốt nghiệp

GVHD:Th.S Dương Thị Luyến

b. Tƣơng tự trên, ta có P5 hoán vị tuy nhiên mỗi hoán vị này đƣợc
lặp lại 2 lần do cách gọi tên của một đa giác chiều xuôi và chiều ngƣợc
lại là nhƣ nhau. (VD: đa giác ABCDEF chính là đa giác AFEDCB). Nhƣ
vậy số đa giác nhận 6 điểm A, B, C, D, E, F làm đỉnh là

P5 5!
  60 đa
2 2

giác.
1.3.2. Chỉnh hợp
a. Chỉnh hợp không lặp
 Định nghĩa
Cho tập A gồm m phần tử x1, x2,…, xm và số nguyên dương n với 1 
n  m. Ta thiết lập bộ (a1, a2, …, an) | ai  A  i= 1, n , ai khác nhau từng
đôi một được gọi là một chỉnh hợp không lặp chập n của m phần tử đã
cho.
Nhận xét. (Nhìn theo quan điểm ánh xạ) Mỗi chỉnh hợp chập n của m
phần tử có thể xác định một đơn ánh từ tập {1, 2, 3, …, n} đến tập m

Kí hiệu A m hoặc (m)n là số các chỉnh hợp chập n của m phần tử.

A mn  m.(m  1)....(m  n  1) 

m!
(m  n)!

Chứng minh.
Cách 1. Để tạo ra một chỉnh hợp không lặp chập n của m phần tử ta
làm nhƣ sau: Chọn một phần tử bất kỳ của A để xếp vào thành phần thứ
nhất mà ta gọi là a1, sẽ có m cách chọn. Sau đó chọn một phần tử bất kỳ
trong các phần tử còn lại để xếp vào thành phần thứ hai mà ta kí hiệu là
a2, sẽ có m – 1 cách chọn. Nhƣ thế ta có m.(m – 1) cách chọn hai phần tử
khác nhau từ A để xếp vào hai thành phần đầu. Tiếp tục quá trình trên, ta
sẽ có m – (n – 1) cách chọn một phần tử còn lại của A để xếp vào thành
phần thứ n. Nhƣ vậy có m.(m – 1).( m – 2)…(m – n + 1) cách lập bộ (a1,
a2, …, an) theo yêu cầu trên.
n
Do đó ta có A m  m.(m  1)...(m  n  1) 

m!
(m  n)!

Cách 2. (Theo quan điểm ánh xạ)
Ta kí hiệu số các đơn ánh từ {1, 2, 3, …, n} đến tập A gồm m phần
n
tử là A m ;
1
Chẳng hạn A m là số các đơn ánh từ {1} đến A (chứa m phần tử)



2

*

Tập (n-1) phần tử ảnh
của 1,2, .., n-1 qua đơn
ánh

*
*

,..
*

n-1 *
n

*

*

*
*

Tập m - (n-1) phần tử
của A không là ảnh
của 1,2, .., n-1

A


GVHD:Th.S Dương Thị Luyến

Giải
+ Số có 5 chữ số: Có 5! Cách lập số có 5 chữ số từ 5 số trên, trong
đó có 4! cách lập số có 5 chữ số mà bắt đầu bằng số 0. Do vậy, có
5! - 4! = 96 số.
4
+ Số có 4 chữ số: Có thể lập đc A 5 số từ những chữ số trên. Trong

3
đó có A 4 số có 4 chữ số mà bắt đầu bởi chữ số 0. Do vậy, có

A 54 - A 34 = 96 số.
3
+ Số có 3 chữ số: Có thể lập đc A 5 số từ những chữ số trên. Trong
2
đó có A 4 số có 3 chữ số mà bắt đầu bởi chữ số 0. Do vậy, có

A 35 - A 24 = 48 số.
2
1
+ Tƣơng tự, có A 5 - A 4 = 16 cách chọn số có 2 chữ số và 5 cách

chọn số có 1 chữ số
Suy ra theo nguyên lý cộng ta có 96 + 96 + 48 + 16 + 5 = 261 số
thỏa mãn yêu cầu bài toán.
b. Chỉnh hợp có lặp
 Định nghĩa
Cho X là một tập n phần tử. Chỉnh hợp có lặp chập k của n phần tử

Số chỉnh hợp lặp chập k của n phần tử của X bằng số các ánh xạ từ
từ tập k phần tử đến tập n phần tử.
 Công thức tính
k

k

Kí hiệu A n là số chỉnh hợp lặp chập k của n phần tử. Ta có A n = nk
Chứng minh
Cách 1.
Phần tử đầu tiên của chỉnh hợp lặp có n cách chọn, vì tập có n phần
tử.
Phần tử thứ hai của chỉnh hợp lặp cũng có n cách chọn, vì phần tử
có thể lấy lặp lại.
Tƣơng tự nhƣ vậy ta có n cách chọn phần tử thứ 3, …., có n cách
chọn phần tử thứ k.
k

Suy ra theo nguyên lý nhân A n = nk.
Cách 2. (Theo quan điểm ánh xạ)
Ta kí hiệu số ánh xạ từ tập tập {1, 2, … , k} đến tập X (có n phần
k

1

tử) là A n ; Chẳng hạn A n là số ánh xạ từ {1} đến X;
2

A n là số ánh xạ từ {1, 2} đến X;
…