BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN

NGUYỄN THỊ NGỌC LINH

ĐẲNG THỨC TỔ HỢP
VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN

LUẬN VĂN THẠC SĨ TỐN HỌC

Bình Định - 2021


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN

NGUYỄN THỊ NGỌC LINH

ĐẲNG THỨC TỔ HỢP
VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 8.46.01.13

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn: TS. NGUYỄN HỮU TRỌN


Lời cam đoan
Tơi xin cam đoan nội dung trình bày trong luận văn này là trung thực và không

trùng khớp với đề tài khác. Tôi cũng xin cam đoan rằng các kết quả trong luận văn,
tài liệu tham khảo và nội dung trích dẫn đảm bảo tính trung thực, chính xác.
Quy Nhơn, tháng 8 năm 2021
Học viên

NGUYỄN THỊ NGỌC LINH


Lời cảm ơn
Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của thầy Nguyễn Hữu
Trọn. Tơi xin bày tỏ lòng biết ơn sâu sắc đến thầy, người đã giúp đỡ và chỉ bảo tơi một
cách tận tình trong suốt quá trình thực hiện luận văn. Xin cảm ơn các thầy cơ trong
khoa Tốn và Thống kê - Đại học Quy Nhơn đã ân cần dạy tôi trong suốt q trình
học tập tại đây.
Đặc biệt tơi xin gửi lời cảm ơn chân thành và biết ơn vô tận đối với gia đình tơi,
những người đã ln sát cánh và tạo động lực để tơi hồn thành luận văn này.
Cuối cùng, vì kiến thức bản thân cịn hạn chế nên dù rất cố gắng nhưng chắc chắn
luận văn còn nhiều thiếu sót. Kính mong q thầy cơ cùng các bạn đồng nghiệp đóng
góp ý kiến để luận văn có thể hoàn chỉnh hơn.
Quy Nhơn, tháng 8 năm 2021
Học viên

Nguyễn Thị Ngọc Linh


Mục lục
Lời cam đoan

1


Lời cảm ơn
1 KIẾN THỨC CHUẨN BỊ
1.1

3

Một số kiến thức về lý thuyết tổ hợp . . . . . . . . . . . . . . . . . . .

3

1.1.1

Quy tắc cộng . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.2

Quy tắc nhân . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.3

Hoán vị và tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.4


Hoán vị và tổ hợp suy rộng . . . . . . . . . . . . . . . . . . . .

7

1.2

Một số kiến thức về số nguyên và phép chia . . . . . . . . . . . . . . .

9

1.3

Một số kiến thức về số phức . . . . . . . . . . . . . . . . . . . . . . . .

13

2 ĐẲNG THỨC TỔ HỢP
2.1

2.2

15

Hệ số nhị thức, định lý nhị thức . . . . . . . . . . . . . . . . . . . . . .

15

2.1.1

Hệ số nhị thức


. . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.1.2

Định lý nhị thức . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.1.3

Lũy thừa giảm, lũy thừa tăng . . . . . . . . . . . . . . . . . . .

17

2.1.4

Khai triển nhị thức suy rộng với số mũ thực . . . . . . . . . . .

18

Các đẳng thức tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3 MỘT SỐ VẤN ĐỀ LIÊN QUAN
3.1


25

Ứng dụng đẳng thức tổ hợp trong số học . . . . . . . . . . . . . . . . .

25

3.1.1

25

Định lý . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


3.2

3.1.2

Một số hệ thức cơ bản . . . . . . . . . . . . . . . . . . . . . . .

27

3.1.3

Các bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

Chứng minh đẳng thức tổ hợp bằng hai cách . . . . . . . . . . . . . . .

32


3.2.1

Phương pháp cân bằng hệ số chứng minh đẳng thức tổ hợp . . .

33

3.2.2

Kỹ thuật đếm bằng hai cách chứng minh đẳng thức Tổ hợp . .

51

Kết luận

60

Tài liệu tham khảo

61


Một số kí hiệu
• N: Tập số tự nhiên
• Z: Tập số nguyên
• R: Tập số thực
• C: Tập số phức
• |Ai |: Số phần tử của tập Ai
• Pnk : Số chỉnh hợp chập k của một tập hợp n phần tử
• Cnk : Số tổ hợp chập k của một tập hợp n phần tử

• Pnn : Hốn vị của n phần tử
• xn : Lũy thừa giảm n của x
• (x)n : Lũy thừa tăng n của x
•

 

•

 

n
k

s
k

: Số tổ hợp n chập k (cịn gọi là hệ số nhị thức)

: Hệ số nhị thức mở rộng

• n!: Hàm n giai thừa
• < xm > f (x): Hệ số của xm trong khai triển f (x)
• |z| : Module của số phức z
• (p, k): Ước số chung lớn nhất của p và k
• Re(z): Phần thực của số phức z
• Im(z): Phần ảo của số phức z


1


Lời nói đầu
Tố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ợp có
hữu hạn phần tử. Các cấu hình đó là các hoán vị, chỉnh hợp, tổ hợp,... các phần tử
của một tập hợp.
Nó 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 ergodic 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ê.
Tốn học tổ hợp liên quan đến cả khía cạnh giải quyết vấn đề lẫn xây dựng cơ sở lý
thuyết, mặc dù nhiều phương pháp lý thuyết vững mạnh đã được xây dựng, tập trung
vào cuối thế kỷ XX. Một trong những mảng lâu đời nhất của toán học tổ hợp là lý
thuyết đồ thị, mà bản thân lý thuyết này lại có nhiều kết nối tự nhiên đến các lĩnh
vực khác.
Toán học tổ hợp được dùng nhiều trong khoa học máy tính để có được cơng thức
và ước lượng trong phân tích thuật tốn.
Đại số tổ hợp ngày nay đã trở thành một môn học không thể thiếu trong chương
trình trung học phổ thơng. Khi nói về các bài tốn Tổ hợp, chúng ta khơng thể khơng
nhắc tới một dạng tốn rất hay và quen thuộc đó là Đẳng thức tổ hợp.
Đẳng thức tổ hợp là những đẳng thức có chứa các hệ số nhị thức thường được phát
biểu dưới dạng tính tổng, thiết lập mối liên hệ giữa các cấu hình tổ hợp. Có thể nói
Đẳng thức tổ hợp là một trong những đề tài khó nhưng thú vị của Đại số tổ hợp.
Trong những năm gần đây, Đẳng thức tổ hợp xuất hiện thường xuyên trong các kỳ thi
Đại học, học sinh giỏi các cấp trong nước và quốc tế, đã cho thấy vai trò của vấn đề


2
này trong toán học cũng như trong việc giảng dạy của giáo viên, học tập của học sinh
các cấp. Việc nghiên cứu về vấn đề này áp dụng vào việc giải quyết các bài toán đang
thu hút và nhận được sự quan tâm của nhiều nhà toán học hiện nay. Để tìm hiểu vấn

đề này một cách hệ thống, dựa trên các tài liệu tham khảo [1]-[6], trong luận văn này
chúng tơi tìm hiểu về các đẳng thức tổ hợp, chứng minh các đẳng thức tổ hợp bằng
nhiều cách, ứng dụng của đẳng thức tổ hợp vào các bài toán tổ hợp thường gặp.
Luận văn tập trung nghiên cứu các đẳng thức tổ hợp, chứng minh các đẳng thức tổ
hợp bằng những công cụ khác nhau, và ứng dụng của đẳng thức tổ hợp trong việc giải
quyết các bài toán tổ hợp thường gặp. Ngoài mục lục, danh mục các ký hiệu, phần mở
đầu và phần kết luận, nội dung của luận văn được chúng tơi trình bày trong 3 chương.
Chuơng 1. Trong chương này, chúng tơi trình bày một số kiến thức cơ sở để chuẩn
bị cho các chương sau của luận văn.
Chương 2. Nội dung chính của chương này là giới thiệu và trình bày các đẳng
thức tổ hợp.
Chương 3. Trình bày một số vấn đề liên quan như ứng dụng của đẳng thức tổ hợp
và chứng minh đẳng thức tổ hợp bằng hai cách.
Mặc dù bản thân đã đầu tư nhiều thời gian, cố gắng thực hiện luận văn một cách
nghiêm túc, tuy nhiên luận văn sẽ khơng tránh khỏi những thiếu sót. Vì vậy rất mong
q thầy cơ, các bạn đồng nghiệp góp ý để luận văn được hồn thiện hơn. Tơi xin chân
thành cảm ơn.
Quy Nhơn, tháng 8 năm 2021
Học viên

Nguyễn Thị Ngọc Linh


3

Chương 1
KIẾN THỨC CHUẨN BỊ
Chương này dành cho việc trình bày các kiến thức cơ sở cần thiết phục vụ cho các
chương sau liên quan đến các bài toán về đẳng thức tổ hợp như một số kiến thức về
lý thuyết tổ hợp (các tuy tắc đếm, hoán vị và tổ hợp), số nguyên và phép chia trong

số học, số phức. Các kết quả trong chương này được tham khảo từ các tài liệu [1], [2],
[3], [5].

1.1.

Một số kiến thức về lý thuyết tổ hợp

1.1.1

Quy tắc cộng

Quy tắc cộng 1.1. Giả sử có hai cơng việc. Cơng việc thứ nhất có thể làm bằng n1
cách, cơng việc thứ hai có thể làm bằng n2 cách và nếu hai việc này khơng thể làm đồng
thời, khi đó sẽ có n1 + n2 cách làm một trong hai việc đó.
Ví dụ 1.1. Giả sử cần chọn hoặc là một cán bộ của khoa toán hoặc là một sinh viên
toán làm đại biểu trong hội đồng của một trường đại học. Hỏi có bao nhiêu cách chọn
vị đại biểu này nếu khoa toán có 37 cán bộ và 83 sinh viên?
Ta gọi việc thứ nhất là việc chọn một cán bộ của khoa tốn. Nó có thể làm bằng
37 cách. Việc thứ hai, chọn một sinh viên tốn, có thể làm bằng 83 cách. Theo quy tắc
cộng có 37 + 83 = 120 cách chọn vị đại diện này.


4
Mở rộng Quy tắc cộng cho trường hợp có nhiều hơn hai công việc.
Quy tắc cộng 1.2 (Quy tắc cộng tổng quát). Giả sử các việc T1 , T2 , . . . , Tm có thể
làm tương ứng bằng n1 , n2 , . . . , nm cách và giả sử khơng có hai việc nào có thể làm đồng
thời. Khi đó, số cách làm một trong m việc đó là n1 + n2 + . . . + nm .
Ví dụ 1.2. Một sinh viên có thể chọn bài thực hành máy tính từ một trong ba danh
sách tương ứng có 23, 15, 19 bài. Có bao nhiêu cách chọn bài thực hành?
Có 23 cách chọn bài thực hành từ danh sách thứ nhất, 15 cách từ danh sách thứ

hai và 19 cách từ danh sách thứ ba. Vì vậy có 23 + 15 + 19 = 57 cách chọn bài thực
hành.
Phát biểu Quy tắc cộng dưới dạng của ngôn ngữ tập hợp như sau.
Quy tắc cộng 1.3 (Quy tắc cộng cho tập hợp). Cho A1 , A2 , . . . , Am là các tập hợp hữu
hạn (số phần tử của chúng hữu hạn), khác rỗng và đôi một rời nhau, tức là Ai ∩ Aj 6= ∅
với mọi i, j = 1, 2, ..., n và i 6= j. Khi đó
|A1 ∪ A2 ∪ . . . ∪ Am | = |A1 | + |A2 | + . . . + |Am |,
trong đó kí hiệu |A| chỉ số phần tử của tập hợp A và |∅| = 0.

1.1.2

Quy tắc nhân

Quy tắc nhân 1.1. Giả sử một nhiệm vụ nào đó được tách ra làm hai việc. Việc thứ
nhất có thể làm bằng n1 cách, việc thứ hai có thể làm bằng n2 cách sau khi việc thứ
nhất đã hồn thành. Khi đó, ta sẽ có n1 n2 cách thực hiện nhiệm vụ này.
Ví dụ 1.3. Người ta có thể ghi nhãn cho những chiếc ghế trong một giảng đường bằng
một chữ cái và một số nguyên dương không vượt quá 100. Bằng cách như vậy, nhiều
nhất có bao nhiêu chiếc ghế có thể được ghi nhãn khác nhau?
Thủ tục ghi nhãn cho một chiếc ghế gồm hai việc, gán một trong 26 chữ cái và sau đó
gán thêm một trong 100 số nguyên dương. Quy tắc nhân chỉ ra rằng có 26.100 = 2600


5
cách khác nhau để gán nhãn cho một chiếc ghế. Như vậy nhiều nhất ta có thể gán
nhãn cho 2600 chiếc ghế.
Người ta thường sử dụng Quy tắc nhân mở rộng như sau.
Quy tắc nhân 1.2 (Quy tắc nhân tổng quát). Giả sử rằng một nhiệm vụ nào đó được
thi hành bằng cách thực hiện các việc T1 , T2 , . . . , Tm . Nếu việc Ti có thể làm bằng ni
cách sau khi các việc T1 , T2 , . . . , Ti−1 đã hoàn thành. Khi đó, có n1 n2 . . . nm cách thực

hiện nhiệm vụ đã cho.
Ví dụ 1.4. Có nhiều nhất bao nhiêu biển đăng kí xe ơ tơ nếu mỗi biển chứa một dãy
ba chữ cái tiếp sau là ba chữ số (không bỏ dãy chữ nào ngay cả khi nó có ý nghĩa khơng
đẹp)?
Có tất cả 26 cách chọn cho mỗi một trong ba chữ cái và 10 cách chọn cho mỗi chữ
số. Vì thế theo quy tắc nhân, nhiều nhất có 26.26.26.10.10.10 = 17576000 biển đăng
kí xe.
Quy tắc nhân có thể được phát biểu dưới dạng ngơn ngữ của tập hợp như sau.
Quy tắc nhân 1.3. Cho A1 , A2 , . . . , Am là các tập hợp hữu hạn khác rỗng. Khi đó
số phần tử của tích Đề-các của các tập này bằng tích của số các phần tử của các tập
thành phần, tức là
|A1 × A2 × . . . × Am | = |A1 |.|A2 | . . . |Am |.

1.1.3

Hoán vị và tổ hợp

Định nghĩa 1.1 (Hoán vị). Hoán vị của một tập các đối tượng khác nhau là một cách
sắp xếp có thứ tự các đối tượng này.
Ví dụ 1.5. Cho S = {1, 2, 3}. Cách sắp xếp 3, 2, 1 là một hốn vị của S, cịn cách sắp
xếp 3, 2 là một chỉnh hợp chập 2 của S.
Chúng ta cũng quan tâm tới việc sắp xếp có thứ tự một số phần tử của một tập
hợp.


6
Định nghĩa 1.2 (Chỉnh hợp). Một cách sắp xếp có thứ tự k phần tử của một tập n
phần tử được gọi là một chỉnh hợp chập k của tập n phần tử. Số chỉnh hợp chập k của
tập S có n phần tử được biểu thị bởi Pnk .
Theo Quy tắc nhân ta có.

Định lý 1.1. Số chỉnh hợp chập k của tập S có n phần tử là
Pnk = n(n − 1)(n − 2) . . . (n − k + 1).
Từ Định lý 1.1, suy ra
Pnk = n(n − 1)(n − 2) . . . (n − k + 1) =

n!
.
(n − k)!

Trường hợp đặc biệt ta có Pnn = n! = 1.2.3 . . . (n − 1).n là hốn vị của n phần tử.
Ví dụ 1.6.
a) Có bao nhiêu cách chọn 4 cầu thủ khác nhau trong 10 cầu thủ của đội bóng quần
vợt để chơi 4 trận đấu đơn, các trận đấu là có thứ tự?
b) Giả sử rằng một thương nhân định đi bán hàng tại tám thành phố. Chị ta bắt đầu
cuộc hành trình của mình tại một thành phố nào đó, nhưng có thể đến bảy thành phố
kia theo bất kì thứ tự nào mà chị ta muốn. Hỏi chị ta có thể đi qua tất cả các thành
phố này theo bao nhiêu lộ trình khác nhau?
a) Mỗi cách chọn có thứ tự 4 cầu thủ của đội bóng là một chỉnh hợp chập bốn của
4
mười phần tử. Khi đó P10
= 10.9.8.7 = 5040.

b) Số lộ trình có thể giữa các thành phố bằng số hoán vị của bảy phần tử, vì thành
phố đầu tiên đã được xác định, nhưng bảy thành phố cịn lại có thể có thứ tự tùy ý.
Do đó có 7! = 5040 cách để người bán hàng chọn hành trình của mình. Nếu muốn tìm
lộ trình ngắn nhất thì chị ta phải tính tổng khoảng cách cho mỗi hành trình có thể,
tức là tổng cộng phải tính cho 5040 hành trình.
Định nghĩa 1.3 (Tổ hợp). Một tổ hợp chập k của một tập hợp gồm n phần tử là một
cách chọn khơng có thứ tự k phần tử của tập đã cho. Như vậy, một tổ hợp chập k chính



7
là một tập con k phần tử của tập ban đầu. Số tổ hợp chập k của tập có n phần tử được
biểu thị bởi Cnk .
Ví dụ 1.7. Cho S là tập {1, 2, 3, 4}. Khi đó {1, 3, 4} là một tổ hợp chập 3 của S.
Chúng ta có thể xác định số tổ hợp chập k của tập có n phần tử nhờ cơng thức
tính chỉnh hợp chập k của n phần tử. Để làm được điều đó chú ý rằng các chỉnh hợp
chập k của một tập hợp có thể nhận được bằng cách trước hết lập các tổ hợp chập k
rồi sắp thứ tự cho các phần tử thuộc các tổ hợp đó. Từ đó ta có
Cnk =

n!
Pnk
=
.
k!
k!(n − k)!

Hệ quả 1.1. Cho n và k là các số nguyên không âm sao cho k 6 n. Khi đó
Cnk = Cnn−k .
Ví dụ 1.8. Có bao nhiêu cách tuyển 5 trong số 10 cầu thủ của một đội bóng quần vợt
để đi thi đấu tại một trường khác?
5
=
Đó chính là số tổ hợp chập 5 của 10 phần tử. Khi đó C10

1.1.4

10!
= 252.

5!5!

Hốn vị và tổ hợp suy rộng

Trong nhiều bài toán đếm, các phần tử có thể được sử dụng lặp lại. Ví dụ các chữ
cái hoặc các chữ số được dùng nhiều lần trong một biển đăng kí xe. Cũng như vậy,
một số bài tốn đếm có chứa các phần tử giống nhau.
Định nghĩa 1.4. Một cách sắp xếp có thứ tự k phần tử của một tập n phần tử, trong
đó mỗi phần tử có thể lặp lại nhiều lần được gọi là một chỉnh hợp lặp chập k của n
phần tử.
Định lý 1.2. Số các chỉnh hợp lặp chập k từ tập n phần tử bằng nk .
Ví dụ 1.9.
a) Từ bảng chữ cái tiếng Anh có thể tạo ra bao nhiêu xâu có độ dài n?


8
b) Có bao nhiêu cách có thể lấy được liên tiếp 3 quả bóng đỏ ra khỏi bình kín chứa 5
quả đỏ và 7 quả xanh, nếu sau mỗi lần lấy một quả bóng ra lại bỏ nó trở lại bình?
a) Theo quy tắc nhân, vì có 26 chữ cái và vì mỗi chữ cái có thể dùng lại nên chúng
ta có 26n xâu với độ dài n.
b) Theo quy tắc nhân, số các kết cục có lợi - tức là số cách lấy được 3 quả bóng đỏ
là 53 = 125, vì mỗi lần lấy ta có 5 quả đỏ ở trong bình.
Định nghĩa 1.5. Một cách chọn ra k phần tử từ tập có n phần tử (trong đó mỗi phần
tử có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp chập k của n.
k
Định lý 1.3. Số tổ hợp lặp chập k từ tập n phần tử bằng Cn+k−1
.

Ví dụ 1.10.
a) Giả sử trong một đĩa quả có táo, cam, lê mỗi loại có ít nhất 4 quả. Tính số cách lấy

4 quả từ đĩa này, nếu giả sử rằng thứ tự các quả được chọn không quan trọng, và các
quả thuộc cùng một loại là không phân biệt?
b) Một cửa hàng bánh quy có 4 loại bánh khác nhau. Có bao nhiêu cách chọn 6 hộp
bánh?(Giả sử là chỉ quan tâm tới loại bánh mà không quan tâm tới hộp bánh cụ thể
nào và thứ tự chọn chúng).
a) Ta liệt kê tất cả 15 cách chọn 4 quả như sau.
· 4 táo, 4 cam, 4 lê.
· 3 táo 1 cam, 3 táo 1 lê, 3 cam 1 táo, 3 cam 1 lê, 3 lê 1 táo, 3 lê 1 cam.
· 2 táo 2 cam, 2 táo 2 lê, 2 cam 2 lê.
· 2 táo 1 cam 1 lê, 2 cam 1 táo 1 lê, 2 lê 1 táo 1 cam.
Lời giải chính là số các tổ hợp lặp chập 4 từ tập 3 phần tử {táo, cam, lê}.
4
Ta có C3+4−1
= C64 = 15 cách chọn theo yêu cầu bài toán.

b) Số cách chọn 6 hộp bánh bằng số tổ hợp lặp chập 6 của 4 phần tử. Khi đó số
6
cách chọn là C4+6−1
= C96 = 84.

Định lý 1.4 (Hoán vị của tập hợp có các phần tử giống nhau). Số hốn vị của n phần
tử trong đó có n1 phần tử như nhau thuộc loại 1, n2 phần tử như nhau thuộc loại 2,. . .,


9

và nk phần tử như nhau thuộc loại k, bằng

n!
.

n1 !n2 ! . . . nk !

Ví dụ 1.11. Có thể nhận được bao nhiêu xâu khác nhau bằng cách sắp xếp lại các chữ
cái của từ SUCCESS?
Vì một số chữ cái của từ SUCCESS là như nhau nên câu trả lời khơng thể là số
hốn vị của 7 chữ cái được. Từ này chứa 3 chữ S, 2 chữ C, 1 chữ U và 1 chữ E. Khi đó
7!
= 420.
số xâu có thể hình thành là
3!2!1!1!
Nhận xét 1.5 (So sánh giữa tổ hợp và chỉnh hợp có lặp hay không lặp).
Loại

Chỉnh hợp chập k

Tổ hợp chập k

Chỉnh hợp chập k

Tổ hợp chập k

Có lặp khơng

Cơng thức

Khơng

Pnk =

Khơng


Cnk =

n!
k!(n − k)!

Có

Có

n!
(n − k)!

nk

k
Cn+k−1
=

(n + k − 1)!
k!(n − 1)!

Bảng 1.1: Bảng so sánh

1.2.

Một số kiến thức về số nguyên và phép chia

Khi một số nguyên được chia cho một số ngun thứ hai khác khơng, thương số có
12

11
thể là một số ngun hoặc khơng. Ví dụ,
= 4 là một số nguyên, trong khi
= 2, 75
3
4
lại không là một số nguyên. Điều này dẫn tới định nghĩa.


10
Định nghĩa 1.6. Nếu a và b là hai số nguyên với a 6= 0, ta nói b chia hết cho a nếu
có một số nguyên c sao cho b = a.c. Khi b chia hết cho a, ta cũng nói a là một ước số
của b và b là bội của a. Ký hiệu a|b là chỉ b chia hết cho a và a - b để chỉ b khơng chia
hết cho a.
Ví dụ 1.12. Xác định xem 3|7 và 3|12 có đúng khơng?
Ta có: 3 - 7 vì

12
7
khơng phải là một số nguyên. Trái lại 3|12 vì
= 4 là một số
3
3

nguyên.
Ví dụ 1.13. Cho n và d là hai số nguyên dương. Có bao nhiêu số nguyên dương không
vượt quá n chia hết cho d?
Các số nguyên dương chia hết cho d là tất cả các số nguyên dương có dạng d.k,
với k cũng là một số nguyên dương. Do đó, số các số nguyên dương chia hết cho d và
n

không vượt quá n sẽ bằng số các số nguyên k với 0 < k.d 6 n hay 0 < k 6 . Vì vậy
d
 
n
có
số ngun dương không vượt quá n chia hết cho d.
d
Định nghĩa 1.7. Số nguyên dương p lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ có
các ước số dương là 1 và p. Các số nguyên dương lớn hơn 1 và không phải là số nguyên
tố được gọi là hợp số.
Ví dụ 1.14. Số 7 là số nguyên tố vì nó chỉ có các ước số dương là 1 và 7, trong khi 9
là một hợp số vì nó chia hết cho 3.
Định lý 1.6 (Định lý cơ bản của Số học). Mọi số nguyên dương đều có thể được viết
duy nhất dưới dạng tích của các số nguyên tố. Trong đó các số nguyên tố được viết
theo thứ tự tăng dần.
Ví dụ 1.15. Sự phân tích 100, 641, 999, 1024 ra thừa số nguyên tố như sau
100 = 2.2.5.5 = 22 52 ,

641 = 641,

999 = 3.3.3.37 = 33 .37,

1024 = 210 .

Định lý 1.7 (Thuật toán chia). Cho a là một số nguyên và d là một số nguyên dương.
Khi đó tồn tại các số q và r duy nhất, với 0 6 r < d, sao cho a = dq + r.
Trong đẳng thức được cho trong thuật toán chia, d được gọi là số chia, a là số bị chia,
q được gọi là thương số và r được gọi là số dư.



11
Ví dụ 1.16. Xác định thương số và số dư khi chia 101 cho 11. Khi đó 101 = 11.9 + 2.
Vậy thương của phép chia là 9 và số dư là 2.
Ước số chung lớn nhất, bội số chung nhỏ nhất
Định nghĩa 1.8. Cho a và b là hai số nguyên khác không, số nguyên d lớn nhất sao
cho d|a và d|b được gọi là ước số chung lớn nhất của a và b. Ước số chung lớn nhất của
a và b được kí hiệu là ƯCLN(a, b).
Ví dụ 1.17.
1) Tìm ước số chung lớn nhất của 24 và 36. Khi đó các ước số chung dương của 24 và
36 là 1, 2, 3, 4, 6, 12. Vậy ƯCLN(24, 36) = 12.
2) Tìm ước số chung lớn nhất của 17 và 22. Khi đó các ước số chung của 17 và 22
khơng có một ước số chung dương nào ngoài 1. Vậy ƯCLN(17, 22) = 1.
Định nghĩa 1.9. Các số nguyên a và b được gọi là nguyên tố cùng nhau nếu ước số
chung lớn nhất của chúng bằng 1.
Từ ví dụ 1.17 ở trên, ta suy ra 17 và 22 là nguyên tố cùng nhau.
Định nghĩa 1.10. Bội số chung nhỏ nhất của hai số nguyên a và b là số nguyên dương
nhỏ nhất chia hết cho cả a và b. Bội số chung nhỏ nhất của hai số nguyên a và b kí
hiệu là BCNN(a, b).
Ví dụ 1.18. Xác định bội số chung nhỏ nhất của 23 .35 .72 và 24 .33 .
Khi đó
BCN N (23 .35 .72 , 24 .33 ) = 2max{3;4} .3max{5;3} .7max{2;0} = 24 .35 .72 .
Đồng dư
Định nghĩa 1.11. Cho a là một số nguyên và m là một số nguyên dương. Khi đó ta
kí hiệu a mod m là số dư khi chia a cho m.
Từ định nghĩa của số dư, ta suy ra rằng a mod m là số nguyên r sao cho a = qm+r
và 0 6 r < m.


12
Ví dụ 1.19. Ta thấy 17 mod 5 = 2, −133 mod 9 = 2, 2001 mod 101 = 82.

Định nghĩa 1.12. Nếu a và b là hai số nguyên và m là một số nguyên dương, thì a
được gọi là đồng dư với b theo mođun m nếu a − b chia hết cho m. Chúng ta sẽ kí hiệu
a ≡ b (mod m) để chỉ rằng a đồng dư với b theo mođun m. Nếu a và b không đồng dư
theo mođun m, ta viết a 6≡ b (mod m).
Chú ý rằng a ≡ b (mod m) nếu và chỉ nếu a mod m = b mod m.
Ví dụ 1.20. Xác định 17 có đồng dư với 5 theo mođun 6 không? Tương tự vậy với 24
và 14?
Khi đó 17 − 5 = 12 chia hết cho 6 nên 17 ≡ 5 (mod 6). Tuy nhiên, vì 24 − 14 = 10
không chia hết cho 6 nên 24 6≡ 14 (mod 6).
Định lý 1.8. Cho m là một số nguyên dương. Các số nguyên a và b đồng dư theo
mođun m nếu và chỉ nếu tồn tại một số nguyên k sao cho a = b + km.
Thuật tốn Euclid. Thuật tốn này dùng để tìm ước số chung lớn nhất.
Mô tả: Chúng ta sẽ dùng các phép chia liên tiếp để qui bài tốn tìm ước số chung lớn
nhất của hai số nguyên dương về chính bài tốn đó nhưng với hai số ngun nhỏ hơn,
cho tới khi một trong hai số nguyên là 0.
Thuật toán Euclid dựa trên kết quả sau về các ước số chung lớn nhất và thuật toán
chia.
Bổ đề 1.1. Cho a = bq + r, trong đó a, b, q, r là các số ngun. Khi đó
ƯCLN(a, b) = ƯCLN(b, r).
Thuật tốn. Giả sử rằng a và b là hai số nguyên dương với a ≥ b. Giả sử r0 = a
và r1 = b. Bằng cách áp dụng liên tiếp thuật tốn chia, ta tìm được
r0 = r1 q1 + r2 ,

0 6 r2 < r1 .

r1 = r2 q2 + r3 ,

0 6 r3 < r2 .



13
....
....
rn−2 = rn−1 qn−1 + rn , 0 6 rn < rn−1 .
rn−1 = rn qn .
Cuối cùng số dư 0 sẽ xuất hiện trong dãy các phép chia liên tiếp, vì dãy các số dư
a = r0 > r1 > r2 > . . . ≥ 0 không thể chứa quá a số hạng được. Hơn nữa từ Bổ đề
1 suy ra ƯCLN(a, b) = ƯCLN (r0 , r1 ) = ƯCLN(r1 , r2 ) = . . . = ƯCLN (rn−2 , rn−1 ) =
ƯCLN (rn−1 , rn ) = ƯCLN (rn , 0) = rn .
Do đó, ước số chung lớn nhất là số dư khác không cuối cùng trong dãy các phép chia.
Ví dụ 1.21. Dùng thuật tốn Euclid tìm ƯCLN(414, 662)?
Khi đó dùng liên tiếp thuật toán chia, ta được
662 = 414.1 + 248.
414 = 248.1 + 166.
248 = 166.1 + 82.
166 = 82.2 + 2.
82 = 2.41.
Do đó, ƯCLN(414, 662) = 2 vì 2 là số dư khác không cuối cùng.

1.3.

Một số kiến thức về số phức

Định nghĩa 1.13. Số phức (dạng đại số) sẽ có dạng z = a + bi, trong đó a, b là các
số nguyên, a được gọi là phần thực, b được gọi là phần ảo và i được xem là đơn vị ảo,
qui ước i2 = −1.
Tập hợp số phức được kí hiệu là C.
Kí hiệu: Re(z) = a và Im(z) = b.



14
Chú ý: Nếu z là số thực thì phần ảo b = 0, ngược lại, nếu z là số thuần ảo thì phần
thực của z là a = 0.
Xét hai số phức z1 = a1 + b1 i và z2 = a2 + b2 i. Điều kiện để 2 số phức bằng nhau
z1 = z2 khi và chỉ khi a1 = a2 , b1 = b2 .
z1 = z2 ⇔





Re(z1 ) = Re(z2 )




Im(z1 ) = Im(z2 )

.

Phép tính trong số phức. Xét hai số phức z1 = a1 + b1 i và z2 = a2 + b2 i. Khi đó
· z1 + z2 = (a1 + a2 ) + (b1 + b2 )i.
· z1 − z2 = (a1 − a2 ) + (b1 − b2 )i.
· −z1 = −a1 − b1 i.
· z1 .z2 = (a1 a2 − b1 b2 ) + (a1 b2 + a2 b1 )i.
· kz1 = ka1 + kb1 i, k ∈ Z.
Số phức liên hợp. Số phức liên hợp của z = a + bi kí hiệu là z, và z = a − bi.
√
Môđun của số phức. Môđun của số phức z = a + bi kí hiệu là |z| và |z| = a2 + b2 .
√

a
b
Dạng lượng giác của số phức. Đặt r = a2 + b2 , cos ϕ = , sin ϕ = thì số phức
r
r
z = a + bi được biểu diễn thành z = r(cos ϕ + i sin ϕ).
Trong đó ϕ là acgumen của số phức z và z n = rn (cos nϕ + i sin nϕ).


15

Chương 2
ĐẲNG THỨC TỔ HỢP
Trong chương này chúng tơi trình bày hệ thống một số khái niệm về hệ số nhị thức,
định lý nhị thức và các đẳng thức tổ hợp (một số tính chất cơ bản của hệ số nhị thức).
Các kết quả trong chương này được tham khảo từ các tài liệu [1], [2], [3], [4], [6].

2.1.

Hệ số nhị thức, định lý nhị thức

Trong mục này, chúng tôi trình bày khái niệm về hệ số nhị thức và định lý nhị thức.

2.1.1

Hệ số nhị thức

Định nghĩa 2.1. Hệ số nhị thức kí hiệu

 

n
k

là hệ số của xk trong khai triển của nhị

thức
n

(1 + x) =

n
X
k=0

 
n
k

!

n k
x .
k

đọc là số tổ hợp n chập k.

Lưu ý rằng, một số quốc gia Châu Á (trong đó có Việt Nam) thường kí hiệu Cnk .
Trong tồn bộ luận văn này chúng ta sử dụng ký hiệu quốc tế
Tính chất 2.1. Quy ước


 
n
k

 
n
k

.

= 0 nếu k > n ≥ 0 hoặc k < 0 6 n.

Định lý 2.2 (Công thức giai thừa). Với mọi số nguyên không âm n và k, ta có
!

n
n!
=
.
k! (n − k)!
k


16
Với n! = 1.2...n, trong đó quy ước 0! = 1.

2.1.2

Định lý nhị thức


Định lý 2.3 (Định lý nhị thức). Với x, a là các số thực và n là số nguyên dương, khi
đó
n

(x + a) =

n
X
k=0

!

n n−k k
x a
k

!

!

(2.1)
!

!

!

n n
n n−1
n

n n−k k
n n
=
x +
x a+
)xn−2 a2 + . . . +
x a + ... +
a
0
1
2
k
n
!
!
!
n n−1
n
n n−k k
n
n−2 2
=x +
x a+
)x a + . . . +
x a + . . . + an .
1
2
k
Quy ước x0 = a0 = 1.
Công thức trên được gọi là định lý nhị thức. Kết quả của định lý này là việc khai triển

một nhị thức bậc n thành một đa thức có n + 1 số hạng.
Trong biểu thức ở vế phải của cơng thức (2.1) ta có
(i) Số các hạng tử là n + 1;
(ii) Các hạng tử có số mũ của x giảm dần từ n đến 0, số mũ của a tăng dần từ 0 đến
n, nhưng tổng các số mũ của x và a trong mỗi hạng tử luôn bằng n;
(iii) Các hệ số của mỗi hạng tử cách đều 2 hạng tử đầu và cuối thì bằng nhau.
Chứng minh.
• Cách 1. Chứng minh bằng phương pháp tổ hợp. Thật vậy, các số hạng
trong khai triển của (x + a)n sẽ có dạng xn−k ak với k = 0, 1, . . . , n. Để nhận được số
hạng dạng xn−k ak ta chọn x từ n − k tổng (x + a) và có Cnn−k cách chọn như vậy. Khi
đó a được chọn từ k tổng cịn lại (chỉ có một cách duy nhất). Do đó hệ số của xn−k ak
là Cnn−k = Cnk . Đó chính là điều cần chứng minh.
• Cách 2. Chứng minh bằng phương pháp quy nạp. Công thức (2.1) hiển
nhiên đúng với n = 1. Giả sử (2.1) đúng với n ∈ Z+ . Ta sẽ chứng minh công thức (2.1)
đúng với n + 1. Thật vậy
n+1

(x + a)

n

= (x + a)(x + a) = (x + a)

n
X
k=0

!

n n−k k

x a
k


17
"

!

!

!

n n−1
n n−2 2
n n−k k
x a+
x a + ... +
x a + . . . + an
= (x + a) x +
1
2
k

#

n

!


=x

n+1

!

!

n n
n n−1 2
n
+
x a+
x a + ... +
x2 an−1 + xan
1
2
n−1
!

!

!

n n−1 2
n n−2 3
n
+x a +
x a +
x a + ... +

xan + an+1 .
1
2
n−1
n

Theo công thức Pascal
!

!

!

!

!

!

n
n
n+1
n
n
n+1
+
=
,
+
=

,...,
1
0
1
2
1
2
!

!

!

!

!

!

n
n
n+1
n
n
n+1
+
=
,
+
=

.
n−1
n−2
n−1
n
n−1
n
Do đó
!

n+1

(x + a)

=x

n+1

!

n+1 n
n + 1 n−1 2
+
x a+
x a + ...
1
2

!


!

n + 1 2 n−1
n+1
+
xa
+
xan + an+1 .
n−1
n
Vậy ta đã chứng minh công thức (2.1) đúng cho trường hợp n + 1. Theo nguyên lý quy
nạp, định lý nhị thức được chứng minh.

2.1.3

Lũy thừa giảm, lũy thừa tăng

Định nghĩa 2.2 (Lũy thừa giảm). Lũy thừa giảm n của x là
xn = x(x − 1) . . . (x − n + 1) .
|

{z

n nhân tử

}

Quy ước x0 = 1.
Định nghĩa 2.3 (Lũy thừa tăng). Lũy thừa tăng n của x là
(x)n = x(x + 1) . . . (x + n − 1) .

|

{z

n nhân tử

}

Quy ước (x)0 = 1.
Tính chất 2.4.
n
nk
(n − k + 1)k
(−1)k (−n)k
=
=
=
.
k
k!
k!
k!
!


18
Chứng minh.
!

n

n!
=
k
k! (n − k)!
n(n − 1)(n − 2) . . . [n − (k − 1)](n − k)!
n(n − 1)(n − 2) . . . (n − k + 1)
nk
=
=
(2.2)
k! (n − k)!
k!
k!
(n − k + 1)(n − k + 2) . . . (n − k + 1 + k − 2)(n − k + 1 + k − 1)
(n − k + 1)k
=
=
(2.3)
k!
k!
(−1)k (−n)(−n + 1) . . . (−n + k − 2)(−n + k − 1)
(−1)k (−n)k
=
=
(2.4).
k!
k!
=

Kết hợp (2.2), (2.3), (2.4), ta được kết luận mong muốn.


2.1.4

Khai triển nhị thức suy rộng với số mũ thực

Trong phần này, chúng ta mở rộng khai triển nhị thức với số mũ thực bất kỳ.
Định lý 2.5. Với mọi số thực x và s ta có
s

(1 + x) =

∞
X

s k
s1
s2 2
sk k
x = 1 + x + x + ... + x + . . .
k
1!
2!
k!
!

k=0

Chứng minh. Đặt f (x) = (1 + x)s , áp dụng khai triển Maclaurin cho f (x), ta có lần
lượt
f (x) = (1 + x)s |x=0 = s0 ,

f 0 (0) = s (1 + x)s−1 |x=0 = s1 ,
f 00 (0) = s2 (1 + x)s−2 |x=0 = s2 ,
... = ...,
f (k) (0) = sk .

Do đó

f (x) =

∞ sk
f (k) (0) k
P
.x =
xk .
k!
k=0 k!
k=0
∞
P

Vì lý do trên ta mở rộng hệ số nhị thức cho "cơ số" thực s bất kỳ như sau.
Định nghĩa 2.4. Với s ∈ R và k ∈ N,
s
sk
s(s − 1)...(s − k + 1)
=
=
.
k
k!

k!
!

 
s
k

được xác định như trên được gọi là hệ số nhị thức mở rộng.