TRƯỜNG ĐẠI HỌC HÙNG VƯƠNG
KHOA TOÁN TIN
-----------------------

NGUYỄN THỊ NGỌC HUYỀN

GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TỐN ĐẾM

KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC
Ngành: Sư phạm Toán

Phú Thọ, 2018


TRƯỜNG ĐẠI HỌC HÙNG VƯƠNG
KHOA TOÁN TIN

-----------------------

NGUYỄN THỊ NGỌC HUYỀN

GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TỐN ĐẾM

KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC
Ngành: Sư phạm Toán

NGƯỜI HƯỚNG DẪN: ThS. Nguyễn Huyền Trang

Phú Thọ, 2018

i

LỜI CẢM ƠN
Trong suốt thời gian thực hiện khóa luận tốt nghiệp, ngồi sự nỗ lực
của bản thân, tơi cịn nhận được sự giúp đỡ nhiệt tình của các thầy, cơ giáo
trong khoa Tốn – Tin Trường Đại học Hùng Vương.
Đặc biệt, tơi xin bày tỏ lịng viết ơn sâu sắc tới cô giáo Thạc sĩ Nguyễn
Huyền Trang – Giảng viên khoa Tốn – Tin. Cơ đã dành nhiều thời gian q
báu để tận tình hướng dẫn, chỉ đạo tơi trong suốt q trình thực hiện khóa
luận tốt nghiệp, đồng thời cơ giáo cịn là người giúp tơi lĩnh hội và nắm vững
được nhiều kiến thức chuyên môn cũng như rèn luyện cho tôi tác phong
nghiên cứu khoa học.
Mặc dù đã rất cố gắng xong khóa luận khơng khỏi có những thiếu xót.
Vì vậy, tơi rất mong được sự góp ý từ các thầy giáo, cô giáo và các bạn để
khóa luận được hồn thiện hơn.
Tơi xin chân thành cảm ơn!
Việt Trì, ngày…….tháng….. năm……
Sinh viên

Nguyễn Thị Ngọc Huyền


ii

MỤC LỤC
LỜI CẢM ƠN .................................................................................................... i
MỞ ĐẦU ........................................................................................................... 1
1. Lý do chọn đề tài khóa luận .......................................................................... 1
2. Mục tiêu khóa luận ........................................................................................ 2
3. Ý nghĩa khoa học và thực tiễn....................................................................... 3

CHƯƠNG 1: KIẾN THỨC CƠ SỞ .................................................................. 4
1.1. Sơ lược về các bước giải và khai thác một bài tốn................................... 4
1.1.1. Tìm hiểu sơ bộ đề tốn ............................................................................ 4
1.1.2. Khai thác đề tốn ..................................................................................... 4
1.1.3. Tìm tịi lời giải......................................................................................... 5
1.1.3b. Phân tích bài tốn để đưa về những bài toán đơn giản hơn. ................. 5
1.1.3c. Liên hệ và sử dụng các bài tốn đã giải ................................................ 5
1.1.3d. Mị mẫm, dự đốn ................................................................................. 6
1.1.3e. Bản gợi ý của Pơlya ............................................................................... 6
1.1.4. Trình bày lời giải ..................................................................................... 7
1.1.5. Khai thác một số bài toán ........................................................................ 7
1.2. Một số kiến thức về tập hợp ....................................................................... 8
1.3. Quy tắc cộng và quy tắc nhân .................................................................... 9
1.3.1. Quy tắc cộng ........................................................................................... 9
1.3.2. Quy tắc nhân ......................................................................................... 10
1.4. Giai thừa và hoán vị ................................................................................. 11
1.4.1. Giai thừa ................................................................................................ 11
1.4.2. Hoán vị .................................................................................................. 11
1.5. Chỉnh hợp, tổ hợp ..................................................................................... 11
1.5.1. Chỉnh hợp .............................................................................................. 11
1.5.2. Tổ hợp ................................................................................................... 12
1.6. Chỉnh hợp lặp, hoán vị lặp, tổ hợp lặp ..................................................... 12
1.6.1. Chỉnh hợp lặp ........................................................................................ 12
1.6.2. Hoán vị lặp ............................................................................................ 12
1.6.3. Tổ hợp lặp ............................................................................................. 13


iii

KẾT LUẬN CHƯƠNG 1................................................................................ 14

CHƯƠNG 2: GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN
......................................................................................................................... 15
2.1. Một số bài tốn đếm khơng lặp ................................................................ 15
2.1.1. Bài tốn lập số ....................................................................................... 15
2.1.2. Bài toán chọn vật, chọn người, sắp xếp ................................................ 32
2.2. Một số bài tốn đếm có lặp ...................................................................... 41
2.2.1. Bài toán lập số ....................................................................................... 41
2.2.2. Bài toán đếm sử dụng tổ hợp lặp .......................................................... 46
2.2.3. Bài toán đếm sử dụng chỉnh hợp lặp ..................................................... 47
2.2.4. Bài toán đếm sử dụng hoán vị lặp ......................................................... 48
2.3. Bài toán phân bổ các đồ vật vào trong hộp .............................................. 49
KẾT LUẬN CHƯƠNG 2................................................................................ 51
CHƯƠNG 3: GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TOÁN TỔ HỢP SỬ
DỤNG PHÉP ĐẾM NÂNG CAO .................................................................. 52
3.1. Một số bài toán sử dụng nguyên lý trừ bù ............................................... 52
3.1.1. Nguyên lý bù trừ ................................................................................... 52
3.1.2. Các bài toán giải bằng phương pháp bù trừ .......................................... 53
3.2. Một số bài toán giải bằng phương pháp song ánh ................................... 57
3.2.1. Phương pháp song ánh .......................................................................... 57
3.2.2. Các bài toán giải bằng phương pháp song ánh ..................................... 57
3.3. Một số bài toán giải bằng phương pháp hàm sinh ................................... 61
3.3.1. Bài toán chọn các phần tử riêng biệt ..................................................... 61
3.3.2. Bài tốn chọn các phần tử có lặp .......................................................... 62
3.4. Một số bài toán giải bằng phương pháp hệ thức truy hồi ........................ 64
3.4.1. Khái niệm mở đầu và mơ hình hóa bằng hệ thức truy hồi .................... 64
3.4.2. Các bài toán giải bằng hệ thức truy hồi ................................................ 64
KẾT LUẬN CHƯƠNG 3................................................................................ 70
KẾT LUẬN ..................................................................................................... 71
TÀI LIỆU THAM KHẢO ............................................................................... 72



1

MỞ ĐẦU
1. Lý do chọn đề tài khóa luận
Có thể nói tư duy về tổ hợp ra đời từ rất sớm. Vào thời nhà Chu, người
ta đã biết đến các hình vẽ có liên quan đến những hình vng thần bí. Thời Hi
Lạp, nhà triết học Kxenokrat sống ở thế kỷ IV trước cơng ngun đã biết tính
số các từ khác nhau từ một bảng chữ cái cho trước. Nhà tốn học Pitago và
các học trị của ơng đã tìm ra nhiều con số có tính chất đặc biệt. Việc tìm ra
được các số như vậy địi hỏi phải có một nghệ thuật tổ hợp nhất định. Lý
thuyết tổ hợp được hình thành cùng với hàng loạt các cơng trình nghiên cứu
nghiêm túc của các nhà toán học xuất sắc như: Pascal, Euler, Leibnitz,
Fermat,…Mặc dù vậy, trong suốt hơn hai thế kỷ, tổ hợp khơng có vai trị
nhiều trong việc nghiên cứu tự nhiên. Đến nay, với sự hỗ trợ đắc lực của máy
tính, tổ hợp đã chuyển sang lĩnh vực tốn ứng dụng với sự phát triển mạnh
mẽ, có nhiều kết quả hữu ích cho con người.
Mặc dù được nghiên cứu từ khá sớm và không được chú ý nhiều nhưng
toán tổ hợp ngày càng được quan tâm nhờ có vị trí đặc biệt cũng như vai trị
quan trọng của nó trong nội bộ tốn học, nó khơng chỉ là đối tượng để nghiên
cứu mà cịn là cơng cụ đắc lực của các mơ hình rời rạc của giải tích, đại
số,…và trong các ngành khoa học khác. Kết quả quan trọng của nó đánh dấu
bởi bài tốn đếm số phân hoạch của Leonhard Euler. 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,…
Một trong những vấn đề đầu tiên của việc nghiên cứu tổ hợp là đếm
xem có bao nhiêu cấu hình được tạo ra với các quy tắc đã nêu? Để đếm được
chính xác, ta phải phân biệt được các cấu hình dựa vào các quy luật xây dựng
chúng. Vì thế có thể xem bài toán đếm là những bài toán luyện tập đầu tiên để
con người làm quen với tư duy tổ hợp, điều này giải thích vì sao một số bài

tốn đếm đã được đưa vào phổ thông từ rất sớm.


2

Bài toán đếm rất phong phú và đa dạng. Độ khó của bài tốn đếm được
trải rất rộng: Từ những bài tốn dễ với các số liệu cụ thể, có thể kiểm chứng
bằng trực giác đến những bài tốn khó, với những dữ liệu đầu vào bằng chữ
mà kết quả của nó được biểu diễn bằng một cơng thức tốn học. Có những
cơng thức được tìm ra qua một vài suy luận đơn giản nhưng cũng có những
cơng thức mà việc tìm thấy chúng phải kéo dài đến hàng thế kỷ. Có những bài
tốn đếm nếu như giải bằng phương pháp trực tiếp sẽ gặp rất nhiều khó khăn,
bế tắc, trong khi giải bằng phương pháp gián tiếp lại trở nên rõ ràng và đơn
giản.
Để giải được các bài toán đếm cần đòi hỏi học sinh phải tư duy tốt, linh
hoạt, sáng tạo. Bài toán đếm giúp học sinh phát huy tốt năng lực tư duy sáng
tạo để học tốt 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 tốn tổ hợp nói chung và các bài tốn đếm nói riêng ln 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 các bài toán này.
Tuy nhiên các tài liệu về tổ hợp cũng như các bài toán đếm mới chỉ
dừng lại ở việc giải các bài tốn, mặc dù đã có sự phân loại các dạng tốn một
cách cụ thể và có hệ thống nhưng vẫn chưa chú trọng đến vấn đề khai thác.
Việc khai thác các bài tốn khơng chỉ giúp học sinh phát triển năng lực
sáng tạo, đào sâu kiến thức mà còn tạo ra một hệ thống các dạng toán và bài
tập toán phong phú và đa dạng. Nhưng trên thực tế, hầu hết các tài liệu chỉ
chú trọng vào việc giải tốn, cịn việc khai thác các bài tốn cịn hạn chế.
Với tất cả các lí do trên, để nâng cao khả năng giải toán và hứng thú
học tập cho học sinh. Với mong muốn đưa ra hệ thống tập trung, phân loại
kiến thức và khai thác một số dạng toán về tổ hợp đếm nhằm đem lại thuận

lợi cho người học có thể tìm hiểu sâu sắc hơn về bài tốn đếm. Vì vậy tơi
chọn và nghiên cứu khóa luận “Giải và khai thác một số bài tốn đếm ”.
2. Mục tiêu khóa luận
- Hệ thống nội dung lí thuyết tổ hợp, phân dạng các bài tốn đếm. Xây
dựng hệ thống ví dụ và bài tập minh họa.


3

- Giải và khai thác một số bài toán đếm cơ bản và nâng cao.
3. Ý nghĩa khoa học và thực tiễn
 Ý nghĩa khoa học
Khóa luận đã hệ thống các kiến thức cơ sở, các dạng toán liên quan đến
bài toán đếm, đồng thời đưa ra cách giải cho các dạng tốn đó.
 Ý nghĩa thực tiễn
Khóa luận góp thêm tài liệu tham khảo cho các sinh viên ngành sư
phạm Toán, cho giáo viên và cho các em học sinh THPT có nhu cầu tìm hiểu
về bài tốn đếm.


4

CHƯƠNG 1
KIẾN THỨC CƠ SỞ
1.1. Sơ lược về các bước giải và khai thác một bài tốn
Thơng thường để giải một bài tốn, cần qua nhiều cơng đoạn khác nhau
như: Tìm hiểu sơ bộ đề bài, khai thác đề bài, tìm tịi lời giải, trình bày lời giải,
đánh giá lời giải, khai thác lời giải, đề xuất các bài toán mới. Tất nhiên khơng
phải bài tốn nào cũng phải trải qua đủ các cơng đoạn đó, song chúng giúp ích
rất nhiều cho việc giải các bài toán, và đối với các bài tốn được chọn lọc điển

hình thì nên phân tích kỹ theo trình tự đó để rèn luyện các thao tác tư duy.
1.1.1. Tìm hiểu sơ bộ đề tốn
Khi chọn bài tốn, khơng nên chọn bài q khó, mà cũng khơng nên
chọn bài q dễ. Cần trình bày bài toán sao cho tự nhiên và gợi được hứng thú
cho người học.
Trước hết cần đọc kỹ bài toán để thấy được tồn cảnh của bài tốn,
càng sáng sủa, càng rõ ràng càng hay, không vội đi vào chi tiết nhất là chi tiết
rắc rối. Cần cố gắng khoanh vùng phạm vi của đề toán: Bài toán này thuộc
vùng kiến thức nào? Sẽ cần có những kiến thức, kỹ năng gì? Nếu giải quyết
được thì sẽ giải quyết vấn đề gì?
1.1.2. Khai thác đề tốn
Nếu là bài tốn về tìm tịi thì cần xác định rõ đâu là ẩn? Cần phải làm
gì? Đâu là các dữ kiện? Đã cho biết những gì? Mối tương quan giữa cái cần
tìm, cái chưa biết (Các điều kiện ràng buộc). Nếu là bài toán chứng minh thì
cần nêu rõ các giả thiết, kết luận.
Nếu bài tốn cần có hình vẽ thì phải vẽ hình. Nếu cần có thể sử dụng
nét đậm, nét nhạt, nét đứt hoặc dùng màu trong hình vẽ. Cảm nhận trực giác
trên hình vẽ có thể giúp chúng ta nắm bắt được dễ dàng hơn nội dung ghi
trong đề toán.


5

1.1.3. Tìm tịi lời giải
Đây là bước quan trọng trong việc giải bài tốn. Khơng có một thuật
tốn tổng qt nào để giải được mọi bài toán, mà chỉ đưa ra những lời
khuyên, những kinh nghiệm, chúng giúp cho việc tìm tịi lời giải được đúng
hướng hơn, nhanh hơn, thuận lợi hơn và có nhiều khả năng dẫn tới thành công
hơn. Tùy trường hợp cụ thể mà vận dụng các kinh nghiệm đó, càng linh hoạt
càng nhuần nhuyễn thì càng dễ tới thành cơng. Càng giải quyết được nhiều

bài tốn thì chúng càng trở thành của mình, thành những kinh nghiệm sống
chứ không phải là những chỉ dẫn khô khan.
1.1.3a. Nhận dạng và tập hợp kiến thức
Như đã nói trong bước tìm hiểu đề tốn, cần khoanh vùng bài tốn, và
vùng được khoanh càng hẹp càng tốt, giúp ta nhận dạng được bài toán thuộc
loại nào. Khi đã nhận dạng, đã phân loại được bài tốn thì trong óc phải
nhanh chóng huy động và tổ chức các kiến thức đã học, đã biết từ trước; phải
nhớ lại để chuẩn bị vận dụng một loạt yếu tố cần thiết để giải loại tốn này.
Q trình đó có thể là “Tự phát” nhất là khi đã quen với việc giải toán.
1.1.3b. Phân tích bài tốn để đưa về những bài tốn đơn giản hơn.
Một bài toán, nhất là bài toán tổng hợp, bài tốn khó được xây dựng từ
những bài tốn đơn giản hơn. Cần phải xem có thể phân tích bài tốn đang xét
thành những bài tốn đơn giản hơn khơng, rồi giải từng bài tốn nhỏ ấy, sau
đó kết hợp chúng lại để có lời giải bài tốn đã cho.
1.1.3c. Liên hệ và sử dụng các bài toán đã giải
Thật khó mà đặt ra một bài tốn hồn tồn mới, khơng giống bất kì bài
tốn nào, hoặc khơng liên quan gì với các bài tốn khác. Vì thế khi gặp một
bài toán, ta gắng nhớ lại xem đã gặp một bài toán tương tự hoặc gần giống với
bài toán cần giải chưa, và nhớ lại con đường đi đến lời giải của bài tốn đã
biết. Điều đó giúp ta rút ngắn việc tìm tịi lời giải của bài tốn mới này và tạo
thêm rất nhiều thuận lợi.


6

Việc nhớ được một hay một số bài toán tương tự bài tốn đang xét, có
thể về dạng, về phương pháp, về vấn đề đặt ra,…ta đã lợi dụng được những
điểm tương đồng về phương pháp giải, về kinh nghiệm, về kết quả,…
1.1.3d. Mị mẫm, dự đốn
Trong khi tìm tịi lời giải cho bài tốn, ta có thể thử nghiệm với một số

trường hợp đặc biệt, nhiều khi sẽ cho ta những gợi ý để giải quyết trong
trường hợp tổng quát. Việc này cũng là nội dung của phương pháp đặc biệt
hóa, nhưng ở đây được sử dụng để gợi ý, để tìm tịi lời giải và phương pháp đi
tới kết quả.
1.1.3e. Bản gợi ý của Pôlya
 Bạn đã gặp bài toán này lần nào chưa? Hay đã gặp bài tốn này ở dạng
tương tự.
 Bạn có biết một bài tốn nào liên quan khơng? Một định lý nào có thể
sử dụng ở đây được không?
 Xét kĩ cái chưa biết và thử nhớ lại một bài toán quen thuộc cùng ẩn hay
có ẩn tương tự.
 Đây là một bài tốn liên quan mà bạn đã có lần giải rồi, có thể sử dụng
nó khơng? Có thể sử dụng kết quả, phương pháp của nó khơng? Có cần phải
đưa thêm một số yếu tố phụ thì mới sử dụng được khơng?
 Có thể phát biểu bài tốn một cách khác khơng?
 Nếu bạn vẫn chưa giải được bài tốn đã cho thì hãy thử giải một bài
tốn liên quan mà dễ hơn khơng? Một bài tốn tổng qt hơn? Một trường
hợp đặc biệt? Một bài toán tương tự? Hoặc một phần của bài toán? Hãy giữ
lại một số điều kiện, bỏ qua các điều kiện khác. Khi đó ẩn được xác định đến
một chừng mực nào đó, nó biến đổi như thế nào? Bạn có thể từ các dữ kiện
rút ra được một số yếu tố có ích khơng? Có thể nghĩ ra các dữ kiện khác giúp
bạn xác định được ẩn khơng? Có thể thay đổi ẩn hoặc các dữ kiện sao cho các
ẩn mới và các dữ kiện mới gần nhau hơn không?
 Bạn đã sử dụng hết mọi dữ kiện chưa? Đã sử dụng hết các quan hệ


7

chưa? Đã để ý đến mọi khái niệm chủ yếu trong bài tốn chưa?
1.1.4. Trình bày lời giải

Khi đã tìm được lời giải rồi thì việc trình bày lời giải khơng cịn khó
khăn nữa, song tính chất hai cơng việc có khác nhau. Việc trình bày lời giải là
văn bản để đánh giá kết quả hoạt động tìm tịi lời giải bài tốn.
Khi đang tìm tịi lời giải, ta có thể mị mẫm, dự đốn hoặc có thể dùng
lập luận tạm thời, cảm tính. Nhưng khi trình bày lời giải thì chỉ được dùng
những lý luận chặt chẽ, phải kiểm nghiệm lại từng chi tiết. Phải chú ý đến
trình tự các chi tiết, đến tính chính xác của từng chi tiết, đến mối liên hệ giữa
các chi tiết trong từng đoạn của lời giải và trong toàn bộ lời giải. Khơng có
chi tiết nào bỗng dưng xuất hiện mà khơng căn cứ vào những kiến thức đã học
hoặc những chi tiết mà ta trình bày trước đó. Khi trình bày lời giải, để cho
ngắn gọn ta thường dùng những phương pháp tổng hợp.
Lời giải được trình bày gọn gàng, sáng sủa, dễ đọc.
1.1.5. Khai thác một số bài tốn
Cơng việc này rất cần thiết trong học toán nhưng thường hay bị bỏ qua.
Việc nhìn nhận lại tồn bộ cách giải một bài tốn có thể giúp chúng ta phát
hiện được cách giải khác tốt hơn, ngắn gọn hơn, hay hơn hoặc sâu sắc hơn.
Việc nhìn nhận lại tồn bộ lời giải sẽ gợi ý cho ta tìm được những bài toán
mới, mà bài toán vừa xét chỉ là một trường hợp đặc biệt. Công đoạn này được
gọi là khai thác bài tốn.
Có thể khai thác một bài tốn theo các hướng như sau:
a) Hướng 1: Phát biểu bài toán tương tự, bài tốn này có thể giải được khơng?
b) Hướng 2: Khái qt hóa, có thể phát biểu bài tốn tổng qt được khơng?
Bài tốn tổng qt có cịn đúng nữa khơng? Trái lại với khát qt hóa là đặc
biệt hóa ln ln đưa đến kết quả đúng, thậm chí có thể mạnh hơn.
c) Hướng 3: Thay đổi giả thiết để được một bài toán mới. Phương pháp để
giải một bài toán khác.
d) Hướng 4: Từ ý nghĩa bài toán đã giải dẫn đến phương pháp giải một bài
toán khác.



8

Ví dụ 1.1.1. Từ bài tốn “ Chứng minh rằng tồn tại số có dạng:
20032003…200300…0 chia hết cho 2002”, ta có thể khai thác thành các bài
tốn sau:
Bài tốn tương tự: Có hay khơng một số có dạng 19911991…199100…0 chia
hết cho 1990?.
Bài tốn tổng qt hóa: Có hay khơng một số có dạng:
(n+1)(n+1)…(n+1)000…000 chia hết cho n.
Ví dụ 1.1.2. Từ bài tốn “Bên trong một cái sân hình chữ nhật có chiều dài là
4m và chiều rộng là 3m có 6 con chim đang ăn. Chứng minh rằng phải có ít
nhất là 2 con chim mà khoảng cách giữa chúng nhỏ hơn 2”, ta có bài tốn
tương tự sau:
Bài tốn tương tự: “Trong hình trịn đường kính 5cm có 10 điểm. Chứng
minh rằng tồn tại ít nhất hai điểm mà khoảng cách giữa chúng nhỏ hơn hoặc
bằng 2”.
Ví dụ 1.1.3. Từ bài tốn “Chứng minh rằng tích hai số tự nhiên liên tiếp chia
hết cho 2”, ta có thể khai thác thành các bài toán như sau:
Bài toán tương tự 1: Chứng minh rằng tích 3 số tự nhiên liên tiếp chia hết cho
3.
Bài toán tương tự 2: Chứng minh rằng tích bốn số tự nhiên liên tiếp chia hết
cho 4.
Bài tốn đặc biệt hóa: Chứng minh rằng tích hai số chẵn liên tiếp chia hết cho
8.
Bài toán tổng quát hóa: Chứng minh rằng tích của n số tự nhiên liên tiếp chia
hết cho n.
1.2. Một số kiến thức về tập hợp
Tập hợp con
Định nghĩa 1.2.1: Cho tập hợp A , tập hợp B gọi là tập con của tập hợp A
khi mọi phần tử của tập hợp B đều thuộc A .

Tính chất: + Mọi tập hợp A đều có hai tập con là  và A .
+ Tập A có n phần tử thì số tập con của A là 2n .


9

Tập hợp sắp thứ tự
Một tập hợp hữu hạn có m phần tử được gọi là sắp thứ tự nếu với mỗi
phần tử của tập hợp đó ta cho tương ứng một số tự nhiên từ 1 đến m sao cho
với những phần tử khác nhau ứng với những số khác nhau.
Khi đó bộ sắp thứ tự m phần tử là một dãy hữu hạn m phần tử và hai
bộ sắp thứ tự  a1, a2 ,..., am  và  b1, b2 ,..., bm  bằng nhau khi và chỉ khi mọi phần
tử tương ứng bằng nhau, tức là:

 a1, a2 ,..., am   b1, b2 ,..., bm   ai  bi ,

i  1, m .

Số phần tử của một số tập hợp
Tập hợp A có hữu hạn phần tử thì số phần tử của A được kí hiệu là: A
hoặc n  A .
Cho A, B, C là ba tập hữu hạn, khi đó:
A B  A  B  A B .
A B C  A  B  C  B C  A B  C  A  A B C .

Tổng quát: Cho A1, A2 ,..., An là n tập hữu hạn  n  1 . Khi đó:
n

A1  A2  ...  An   Ai 
i 1


n





1i  k l  n

n



1i  k  n

Ai  Ak 

Ai  Ak  Al  ...   1

n 1

 A1  ...  An 

1.3. Quy tắc cộng và quy tắc nhân
1.3.1. Quy tắc cộng
Định nghĩa 1.3.1: Một cơng việc được hồn thành bởi một trong hai hành
động. Nếu hành động này có m cách thực hiện, hành động kia có n cách thực
hiện khơng trùng với bất kì cách nào của hành động thứ nhất thì cơng việc đó
có m  n cách thực hiện.
Quy tắc cộng dạng tổng qt:

Một cơng việc được hồn thành bởi một trong các hành động
T1,T2 ,...,Tn . Trong đó:


10

T1 có m1 cách thực hiện.

T2 có m2 cách thực hiện.
…
Tn có mn cách thực hiện.

Giả sử khơng có hai việc nào có thể làm đồng thời thì cơng việc đó có
m1  m2  ...  mn cách thực hiện.

Biểu diễn dưới dạng tập hợp
Nếu X ,Y là hai tập hợp hữu hạn, khơng giao nhau thì: X  Y  X  Y .
Nếu X1, X 2 ,..., X n là n tập hữu hạn, từng đôi một khơng giao nhau thì:
X1  X 2  ...  X n  X1  X 2  ...  X n

Nếu X ,Y hai tập hữu hạn và X  Y thì: X  Y \ X  Y  X .
1.3.2. Quy tắc nhân
Giả sử để hoàn thành một nhiệm vụ H cần thực hiện hai công việc nhỏ
là H1 và H 2 . Trong đó:
H1 có thể làm bằng n1 cách.

H 2 có thể làm bằng n2 cách, sau khi đã hồn thành cơng việc H1 .

Khi đó để thực hiện cơng việc H sẽ có n1.n2 cách.
Quy tắc nhân dạng tổng quát:

Giả sử để hoàn thành một nhiệm vụ H cần thực hiện k công việc nhỏ
là H1, H 2 ,..., H k , trong đó:
H1 có thể làm bằng n1 cách.

H 2 có thể làm bằng n2 cách, sau khi đã hồn thành cơng việc H1 .
…
H k có thể làm bằng nk cách, sau khi đã hồn thành cơng việc H k 1 .

Khi đó để thực hiện cơng việc H sẽ có n1.n2 .....nk cách.


11

Biểu diễn dưới dạng tập hợp
Nếu A1, A2 ,..., An là n tậ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 hãy nhớ 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 một 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 .
1.4. Giai thừa và hoán vị
1.4.1. Giai thừa
Định nghĩa 1.4.1: Giai thừa n , kí hiệu là n! là tích của n số tự nhiên liên
tiếp từ 1 đến n .
n!  1.2.3..... n  1.n, n  1

Quy ước:

0!  1 .
1!  1.


1.4.2. Hoán vị
Định nghĩa 1.4.2: Cho tập hợp A gồm n phần tử  n  1 . Một cách sắp thứ
tự n phần tử của tập hợp A được gọi là một hốn vị của n phần tử đó.
Kí hiệu: Pn là số các hoán vị của n phần tử.
Pn  n!  1.2..... n  1.n

1.5. Chỉnh hợp, tổ hợp
1.5.1. Chỉnh hợp
Định nghĩa 1.5.1: Cho tập hợp A gồm n phần tử  n  1 . Kết quả của việc
lấy k phần tử khác nhau từ n phần tử của tập hợp A và sắp xếp chúng theo
một thứ tự nào đó được gọi là một chỉnh hợp chập k của n phần tử.
Công thức: Ank 

n!
 n. n  1..... n  k  1
 n  k !

với 1  k  n .

Chú ý: Một chỉnh hợp n chập n được gọi là một hoán vị của n phần tử.
Ann  Pn  n!


12

1.5.2. Tổ hợp
Định nghĩa 1.5.2: Giả sử tập hợp A gồm n phần tử  n  1 . Mỗi tập con gồm
k phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho với
1 k  n.


Kí hiệu: Cnk , 1  k  n  là số tổ hợp chập k của n phần tử.
Công thức: Cnk 

n!
.
k ! n  k !

Chú ý:
Cn0  1.
Cnk  Cnnk ,  0  k  n  .
Cnk  Cnk 1  Cnk11 , 1  k  n  .

1.6. Chỉnh hợp lặp, hoán vị lặp, tổ hợp lặp
1.6.1. Chỉnh hợp lặp
Định nghĩa 1.6.1: Một cách sắp xếp có thứ tự r phần tử có thể lặp lại của một
tập n phần tử được gọi là một chỉnh hợp lặp chập r từ tập n phần tử. Nếu A là
tập gồm n phần tử đó thì mỗi chỉnh hợp như thế là một phần tử của tập A.
Ngoài ra, mỗi chỉnh hợp lặp chập r từ tập n phần tử là một hàm từ tập r phần
tử vào tập n phần tử. Vì vậy, số chỉnh hợp lặp chập r từ tập n phần tử là n k .
1.6.2. Hoán vị lặp
Trong bài tốn đếm, một số phần tử có thể giống nhau. Khi đó cần phải
cẩn thận, tránh đếm chúng hơn một lần.
Định lý 1.6.1: Số hoán vị của n phần tử trong đó có n1 phần tử như nhau
thuộc loại 1, có n2 phần tử như nhau thuộc loại 2,…và có nk phần tử như
nhau thuộc loại k bằng

n!
.
n1 !n 2!..nk !


Chứng minh
Để xác định số hoán vị trước tiên chúng ta nhận thấy có Cnn1 cách giữ

n1 số cho n1 phần tử loại 1, còn lại n  n1 chỗ trống.


13

Sau đó có Cnn2 n1 cách đặt n2 phần tử loại 2 vịa hốn vị, cịn lại
n  n1  n2 chỗ trống.

Tiếp tục đặt các phần tử loại 3, loại 4,…,loại k  1 vào chỗ trống trong
hoán vị. Cuối cùng có Cnnk n1 n2 ...n k 1 cách đặt nk phần tử loại k vào hoán vị.
Theo quy tắc nhân tất cả các hốn vị có thể là: Cnnk n1 n2 ...n k 1 

n!
.
n1 !n 2!..nk !

1.6.3. Tổ hợp lặp
Một tổ hợp lặp chập k của một tập hợp là một cách chọn khơng có thứ
tự k phần tử có thể lặp lại của tập đã cho. Như vậy một tổ hợp lặp kiểu này là
một dãy không kể thứ tự gồm k thành phần lấy từ tập n phần tử. Do đó có thể
là k  n .
Định lý 1.6.2: Số tổ hợp lặp chập k từ tập n phần tử bằng Cnkk 1 .
Chứng minh
Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một
dãy n  1 thanh đứng và k ngôi sao. Ta dùng n  1 thanh đứng để phân cách
các ngăn. Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần tử thứ i của

tập xuất hiện trong tổ hợp.
Mỗi dãy n  1 thanh và k ngôi sao ứng với một tổ hợp lặp chập k của n
phần tử. Do đó mỗi dãy ứng với một cách chọn k chỗ cho k ngôi sao từ
n  k  1 chỗ chứa n  1 thanh và k ngơi sao. Đó là điều cần chứng minh.

Chú ý:
+ Số tổ hợp có lặp chập p của n là Cnp  Cnp p1  Cnn1p1 .
+ Tổ hợp có lặp lại khi một phần tử có thể xuất hiện nhiều lần và thứ tự
của các phần tử không cần để ý.


14

KẾT LUẬN CHƯƠNG 1
Trong chương 1, khóa luận trình bày hệ thống lý thuyết về tổ hợp đếm
và các ví dụ về khai thác bài toán để làm cơ sở áp dụng vào làm bài tập của
chương 2 và chương 3.


15

CHƯƠNG 2
GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN
2.1. Một số bài tốn đếm khơng lặp
Trong các bài tốn về phép đếm khơng lặp, mỗi phần tử cần đếm chỉ
có thể xuất hiện tối đa một lần. Để giải các bài tốn đếm khơng lặp người ta
sử dụng hai quy tắc chính của phép đếm là quy tắc cộng và quy tắc nhân,
cũng như sử dụng hai phương pháp đếm trực tiếp hoặc đếm gián tiếp.
2.1.1. Bài tốn lập số
Thơng thường để lập được số n  a1a2 ...ar  a1  0  từ các số cho trước:

+) Ta dùng phép chỉnh hợp – hoán vị.
+) Nếu trong q trình sắp xếp, nếu có các chữ số hoặc các số có điều
kiện thì ta chọn trước và các chữ số có tính chất bình đẳng thì chọn sau.
+) Sau đó vận dụng quy tắc nhân – quy tắc cộng trong phép đếm để có
hiệu quả.
Bài tốn 2.1.1: Cho tập X  0,1,2,3,4,5,6 . Có thể lập được bao nhiêu số
gồm năm chữ số mà các chữ số khác nhau từng đơi một.
 Phân tích bài tốn
Theo u cầu bài tốn số cần tìm có các chữ số khác nhau nên ta sử
dụng kiến thức chỉnh hợp để giải bài toán này.
Giải
Gọi số thành lập là: n  a1a2a3a4a5 , ai  X .
 Cách 1
- Chọn a1  0 , có 6 cách chọn.
- Cịn a2 , a3 , a4 , a5 là một bộ phân biệt có thứ tự được chọn từ X do đó
nó là một chỉnh hợp chập 4 của 6 (Trừ đi số a1 đã chọn). Có A64 cách chọn.
Vậy số các số thỏa mãn yêu cầu bài toán là: 6. A64 =2160 số.
 Cách 2
- Chọn a1  0 , có 6 cách chọn.


16

- Chọn a2 , có 6 cách chọn.
- Chọn a3 , có 5 cách chọn.
- Chọn a4 , có 4 cách chọn.
- Chọn a5 , có 3 cách chọn.
Theo quy tắc nhân số các số nhận được là: 6.6.5.4.3=2160.
Vậy có 2160 số thỏa mãn yêu cầu bài toán.
Khai thác bài tốn

Bài tốn 2.1.1a (Bài tốn tương tự): Có thể lập được bao nhiêu số có ba chữ
số mà các chữ số khác nhau đôi một.
Giải
Gọi n  a1a2a3 .
- Chọn a1  0 , có 9 cách.
- Chọn a2 , có 9 cách.
- Chọn a3 , có 8 cách.
Theo quy tắc nhân số các số nhận được là: 9.9.8 = 648 số.
Vậy có 648 số thỏa mãn yêu cầu bài tốn.
Bài tốn 2.1.1b (Bài tốn đặc biệt hóa ): Cho tập hợp các chữ số 1, 2,…, 9.
Từ tập hợp X có thể lập được bao nhiêu số chẵn có 6 chữ số mà các chữ số
khác nhau từng đôi một.
Giải
Gọi X  1,2,...,9 và số cần lập là n  a1a2a3a4a5a6 , ai  X , i  1,6 .
Vì n là số chẵn nên a6 2; 4;6;8 có 4 cách chọn.
Còn a1, a2 , a3 , a4 , a5 là một bộ phân biệt có thứ tự được chọn từ X do
đó nó là một chỉnh hợp chập 5 của 8 (Trừ đi số a6 đã chọn). Có A85 cách
chọn.
Vậy có 4. A85  224 số thỏa mãn yêu cầu bài toán.


17

Bài tốn 2.1.1c (Bài tốn đặc biệt hóa ): Cho tập hợp X  0,1,2,...,7 . Từ
tập hợp X có thể lập được bao nhiêu số tự nhiên n gồm năm chữ số mà các
chữ số đôi một khác nhau nếu:
a) n là số chẵn.
b) n là số lẻ.
Giải
Gọi số cần lập là n  a1a2a3a4a5 , ai  X , i  1, 5, a1  0 .

a) Vì n là số chẵn nên a5 0;2; 4; 6 .
 Trường hợp 1: Nếu a5  0 thì a5 có 1 cách chọn.
Khi đó a1, a2 , a3 , a4 là một bộ phân biệt có thứ tự được chọn từ X \ 0 . Do
đó nó là một chỉnh hợp chập 4 của 7. Có A74 cách chọn.
Vậy có A74  840 số thỏa mãn bài toán.
 Trường hợp 2: Nếu a5 được chọn từ 2,4,6 thì a5 có 3 cách chọn.
a1 được chọn từ tập X \ 0, a5 nên a1 có 6 cách chọn. a2 , a3 , a4 là một bộ

phân biệt thứ tự được chọn từ X \ a1 , a5 , do đó nó là một chỉnh hợp 6 chập
3. Có A63 cách chọn.
Vậy có 3.6. A63  2160 số thỏa mãn bài tốn.
Vậy số các số chẵn gồm 5 chữ số phân biệt hình thành từ X là:
840  2160  3000 (số).

b) Do n là số lẻ nên:
- Chọn a5 từ các số: 1, 3, 5, 7. Có 4 cách chọn.
- Chọn a1 từ tập X \ a5 ,0 . Có 6 cách chọn.
- Chọn ba vị trí cịn lại từ tập X \ a1 , a5 . Có A63 cách chọn.
Các số lẻ nhận được là: 4.6. A63  4.6.

6!
 2880 .
3!

Vậy có 2880 số lẻ thỏa mãn yêu cầu bài toán.


18

Bài tốn 2.1.2: Có bao nhiêu số chẵn gồm sáu chữ số mà các chữ số khác

nhau đôi một trong đó chữ số đầu tiên là số lẻ.
Giải
Gọi A  0;1;2;3;4;5;6;7;8;9 và số thành lập là: n  a1a2a3a4a5a6 .
- Chọn a1 là số lẻ: Có 5 cách chọn.
- Chọn a6 là số chẵn: Có 5 cách chọn.
- Chọn bốn vị trí cịn lại từ A \ a1; a6  , số cách chọn là A84 .
Vậy các số nhận được thỏa mãn yêu cầu bài toán là:
5.5. A84  5.5.

8!
 42000 số.
4!

Khai thác bài toán
Bài toán 2.1.2a (Bài toán đặc biệt hóa): Cho tập hợp X  0;1;2;3;4;5;6;7 .
Từ tập hợp X có thể lập được bao nhiêu số tự nhiên gồm năm chữ số mà các
chữ số khác nhau từng đơi một và có chữ số đứng đầu là chữ số 2.
Giải
Gọi số thành lập là: n  a1a2a3a4a5 .
- Chọn a1  2 , có 1 cách chọn.
- Chọn a5 từ các chữ số 0,4,6 , có ba cách chọn.
- Chọn ba vị trí cịn lại từ tập X \ 2, a5 , có A63 cách chọn.
Vậy số các số thỏa mãn yêu cầu bài toán là: 3. A63  360 số.
Bài toán 2.1.2b (Bài toán tổng quát hóa): Có bao nhiêu số gồm sáu chữ số mà
các chữ số khác nhau đơi một trong đó có đúng ba chữ số lẻ và ba chữ số
chẵn.
Giải
Gọi A  0;1;2;3;4;5;6;7;8;9 và số thành lập là: n  a1a2a3a4a5a6 .
 Trước tiên ta tìm số gồm sáu chữ số đơi một khác nhau trong đó có
đúng ba chữ số lẻ và ba chữ số chẵn, kể cả số có a1  0 .



19

- Chọn ba số chẵn, có C53 cách chọn.
- Chọn ba số lẻ, có C53 cách chọn.
- Sắp thứ tự sáu số vừa chọn được, có 6! Cách chọn.
Vậy các số nhận được là: C53 . C53 .6!=72000 số.
 Trong 72000 số vừa tìm được, ta tìm các số có dạng: 0a2a3a4a5a6 .
- Chọn hai số chẵn cịn lại, có C42 cách chọn.
- Chọn ba số lẻ, có C53 cách chọn.
- Sắp thứ tự năm số vừa chọn được, có 5! cách chọn.
Vậy các số nhận được là: C42 . C53 .5!=7200 số.
Kết luận: Các số thỏa mãn yêu cầu bài toán là: 72000  7200  64800 số.
Bài toán 2.1.3: Cho các chữ số 0, 1, 2, 3, 4, 5. Từ các chữ số đã cho lập được
bao nhiêu số chia hết cho 5, có ba chữ số và ba chữ số đó khác nhau từng đơi
một.
 Phân tích bài tốn
Theo bài tốn các số cần tìm chia hết cho 5 nên chữ số tận cùng chỉ có thể
là 0 hoặc 5.
Giải
Gọi số thành lập là n  a1a2a3
 Trường hợp 1: Số có dạng a1a2 0 . Có A52 số.
 Trường hợp 2: Số có dạng a1a2 5
- Chọn a1  0 : Có 4 cách.
- Chọn a2  0 : Có 4 cách.
Vậy có 4.4=16 cách.
Kết luận: Có A52 +16=

5!

 16  20  16  36 số thỏa mãn yêu cầu bài toán.
3!


20

Khai thác bài toán
Bài toán 2.1.3a (Bài toán tương tự): Cho các chữ số 0, 1, 2, 3, 4, 5. Từ các
chữ số đã cho lập được bao nhiêu số chia hết cho 9, có ba chữ số và ba chữ số
đó khác nhau từng đơi một.
Giải
Gọi số thành lập là n  a1a2a3 với điều kiện là a1  a2  a3 chia hết cho 9.
Vậy a1 , a2 , a3 có thể là: 0;4;5,1;3;5,2;3;4 .
 Xét 0;4;5 thì các số lập được là 405; 450; 504; 540.
 Xét 1;3;5 có 3! số nhận được.
 Xét 2;3;4 có 3! số nhận được.
Bài toán 2.1.4: Cho các chữ số 0, 1, 2, 3, 4, 5, 6, 7. Có thể lập được bao nhiêu
số có bốn chữ số đơi một khác nhau và khơng chia hết cho 10.
 Phân tích bài tốn
Theo bài tốn số cần lập khơng chia hết cho 10 nên chữ số tận cùng
không thể là chữ số 0.
Giải
Gọi A  0, 1, 2, 3, 4, 5, 6, 7 và số thành lập là: n  a1a2a3a4 .
 Chọn a4 từ tập A \ 0 , có 7 cách chọn.
 Chọn a1 từ tập A \ 0, a4  , có 6 cách chọn.
 Chọn hai vị trí còn lại từ tập A \ a1 , a4  , có A62 cách chọn.
Vậy các số nhận được thỏa mãn yêu cầu bài toán là: 7.6. A62  1260 số.
Khai thác bài toán
Bài toán 2.1.4a (Bài toán tương tự): Cho tập A  0,1,2,3,4,5 . Hỏi có thể
lập bao nhiêu số có ba chữ số khác nhau và khơng chia hết cho 3.

Giải
Gọi số thành lập là: n  a1a2a3 .
 Trước tiên ta tìm các số có dạng a1a2 a3 được lập từ A.