Lý thuyết tổ hợp số và ứng dụng thực tế Tìm hiểu lý thuyết tổ hợp số và ứng dụng hay nhất

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (543.38 KB, 79 trang )

BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

NGUYỄN THỊ KIỀU

LÝ THUYẾT TỔ HỢP SỐ VÀ ỨNG DỤNG

Chuyên ngành : Phương pháp Toán sơ cấp
Mã số:

60.46.40

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

Người hướng dẫn khoa học: PGS.TSKH. TRẦN QUỐC CHIẾN

Đà Nẵng – Năm 2013

LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng
được ai công bố trong bất kỳ công trình nào khác.

Người cam đoan

Nguyễn Thị Kiều

MỤC LỤC
MỞ ĐẦU ………………………………………………………………………………………… 1

1. Lý do chọn đề tài ……………………………………………………………………. 1
2. Mục đích nghiên cứu ………………………………………………………………. 2
3. Đối tượng nghiên cứu và phạm vi nghiên cứu …………………………….. 2
4. Nhiệm vụ nghiên cứu ……………………………………………………………… 2
5. Phương pháp nghiên cứu …………………………………………………………. 2
6. Ý nghĩa khoa học và thực tiễn của đề tài…………………………………….. 2
7. Cấu trúc luận văn……………………………………………………………………. 3
CHƯƠNG 1. CƠ SỞ LÝ THUYẾT…………………………………………………… 4
1.1. TẬP HỢP VÀ CÁC PHÉP TOÁN TẬP HỢP …………………………………. 4
1.1.1. Khái niệm tập hợp………………………………………………………………. 4
1.1.3. Lực lượng tập hợp………………………………………………………………. 5
1.2. BÀI TOÁN TỔ HỢP …………………………………………………………………… 5
1.2.1. Cấu hình tổ hợp …………………………………………………………………. 5
1.2.2. Các dạng bài toán tổ hợp ……………………………………………………… 6
1.3. NGUYÊN LÝ CỘNG VÀ NGUYÊN LÝ NHÂN ……………………………. 6
1.2.1. Nguyên lý nhân………………………………………………………………….. 6
1.2.2. Nguyên lý cộng ………………………………………………………………….. 8
1.4. CÁC CẤU HÌNH TỔ HỢP CƠ BẢN …………………………………………… 10
1.4.1. Chỉnh hợp lặp ………………………………………………………………….. 10
1.4.2. Chỉnh hợp không lặp …………………………………………………………. 11
1.4.3. Hoán vị …………………………………………………………………………… 13
1.4.4. Tổ hợp ……………………………………………………………………………. 15

1.5. CÁC CẤU HÌNH TỔ HỢP NÂNG CAO ……………………………………… 17
1.5.1. Hoán vị lặp ……………………………………………………………………… 17
1.5.2. Tổ hợp lặp……………………………………………………………………….. 19
1.5.3. Phân hoạch thứ tự tổ hợp …………………………………………………… 21
1.5.4. Phân hoạch không thứ tự……………………………………………………. 23
1.6. NGUYÊN LÝ BÙ TRỪ …………………………………………………………….. 24

1.6.1. Công thức bao hàm và loại trừ ……………………………………………. 24
1.6.2. Công thức Sieve ……………………………………………………………….. 25
CHƯƠNG 2. LÝ THUYẾT TỔ HỢP SỐ ………………………………………… 28
2.1. SỐ SQUARE-FREE ………………………………………………………………….. 28
2.2. HÀM TÍNH NHÂN …………………………………………………………………… 28
2.3. HÀM EULER (n) …………………………………………………………………… 32
2.4. HÀM MÖBIUS (n) ………………………………………………………………… 35
2.5. HÀM RIEMANN ZETA  (s) …………………………………………………….. 41
CHƯƠNG 3. ỨNG DỤNG LÝ THUYẾT TỔ HỢP SỐ …………………….. 44
3.1. BÀI TOÁN TÌM CÁC SỐ NGUYÊN DƯƠNG KHÔNG CHIA HẾT
CHO TẬP SỐ NGUYÊN DƯƠNG ……………………………………………………. 44
3.2. BÀI TOÁN TÌM CÁC SỐ NGUYÊN TỐ NHỎ HƠN MỘT SỐ
NGUYÊN DƯƠNG NÀO ĐÓ ………………………………………………………….. 47
3.3. BÀI TOÁN TÌM CÁC SỐ NGUYÊN SQUARE-FREE KHÔNG
VƯỢT QUÁ SỐ NGUYÊN DƯƠNG N CHO TRƯỚC………………………… 53
3.4. BÀI TOÁN ĐẾM CÁC ƯỚC VÀ TÍNH TỔNG CÁC ƯỚC CỦA MỘT
SỐ NGUYÊN DƯƠNG CHO TRƯỚC ………………………………………………. 54
3.4.1. Đếm các ước nguyên dương của một số nguyên dương ………….. 54
3.4.2. Tính tổng các ước nguyên dương của một số nguyên dương ……. 56

3.5. BÀI TOÁN ĐẾM SỐ TỪ TRÒN CÓ ĐỘ DÀI N ĐƯỢC LẤY TỪ M
KÍ TỰ CHO TRƯỚC ………………………………………………………………………. 61
3.6. TÌM SỐ DƯ TRONG PHÉP CHIA MỘT LŨY THỪA CHO MỘT SỐ65
3.7. GIẢI PHƯƠNG TRÌNH ĐỒNG DƯ BẬC NHẤT MỘT ẨN

ax  b (mod m) ……………………………………………………………………………… 69
KẾT LUẬN …………………………………………………………………………………… 71
TÀI LIỆU THAM KHẢO………………………………………………………………. 72
QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN THẠC SĨ (BẢN SAO)

1

MỞ ĐẦU
1. Lý do chọn đề tài
Lý thuyết số là một ngành của toán học lý thuyết nghiên cứu về tính
chất của số nói chung và số nguyên nói riêng, cũng như những lớp rộng hơn
các bài toán mà phát triển từ những nghiên cứu của nó.
Toán học tổ hợp được hình thành vào đầu thế kỷ XVII và phát triển
mạnh cùng với sự bùng nổ của công nghệ thông tin, đặc biệt là các công trình
nghiên cứu của các nhà toán học nổi tiếng như Pascal, Fermat, Leibnitz,
Euler,…
Các vấn đề liên quan đến lý thuyết tổ hợp là một bộ phận quan trọng,
hấp dẫn và lí thú của Toán học nói chung và toán rời rạc nói riêng. Nó có nội
dung phong phú và được ứng dụng nhiều trong đời sống, đặc biệt là từ khi tin
học ra đời.
Lý thuyết tổ hợp số là một nội dung hay của lý thuyết tổ hợp, nó giải
quyết các bài toán về lý thuyết số mà có tư tưởng tổ hợp trong công thức hoặc
cách chứng minh.
Tổ hợp đã được đưa vào giảng dạy ở chương trình học phổ thông, đại
học, sau đại học và nó là một bộ môn tương đối khó đối với học sinh, sinh
viên vì khái niệm trừu tượng và nhiều dạng toán rất khó nhưng thời lượng
dành cho môn này còn hạn chế nhất là bậc trung học phổ thông.
Trong nhiều kì thi học sinh giỏi quốc gia, thi Olympic toán quốc tế, thi
Olympic sinh viên giữa các trường đại học, cao đẳng các bài toán liên quan
đến tổ hợp hay được đề cập và thường thuộc loại rất khó nên học sinh đa số
còn lúng túng khi giải quyết những bài toán loại này.
Chính vì các lý do nêu trên, tôi quyết định chọn đề tài “Lý thuyết tổ

2

hợp số và ứng dụng” để tìm hiểu, nghiên cứu nhằm phục vụ cho công tác
giảng dạy của tôi nói chung và luyện thi học sinh giỏi nói riêng sau này.
2. Mục đích nghiên cứu
Nghiên cứu về lý thuyết tổ hợp số và ứng dụng của lý thuyết tổ hợp số
để giải các bài toán về số tổ hợp.
3. Đối tượng nghiên cứu và phạm vi nghiên cứu
– Đối tượng nghiên cứu là lý thuyết tổ hợp số.
– Phạm vi nghiên cứu là số tổ hợp và ứng dụng của nó.
4. Nhiệm vụ nghiên cứu
– Tìm hiểu về lý thuyết tổ hợp, đặc biệt là lý thuyết tổ hợp số
– Tìm hiểu và xây dựng các ứng dụng của lý thuyết tổ hợp số
5. Phương pháp nghiên cứu
– Nghiên cứu lý thuyết thông qua việc siêu tầm các loại tài liệu như
sách, báo, tạp chí, mạng internet, thầy cô, bạn bè. Trình bày một cách có hệ
thống các nội dung lý thuyết đã nghiên cứu và tìm hiểu. Mỗi nội dung ta phải
chứng minh cụ thể, rõ ràng và lấy ví dụ minh họa xác thực, dễ hiểu.
– Phân loại và hệ thống các dạng toán. Tìm ra các phương pháp đặc
trưng để giải mỗi dạng toán cụ thể.
6. Ý nghĩa khoa học và thực tiễn của đề tài
– Đề tài góp phần nghiên cứu ứng dụng của lý thuyết tổ hợp số vào giải
toán tổ hợp phù hợp với chuyên ngành Phương pháp toán sơ cấp.
– Sau khi cho phép bảo vệ, được sự góp ý của các thầy cô trong hội
đồng, luận văn có thể dùng làm tài liệu tham khảo cho sinh viên, giáo viên,
học sinh phổ thông và những ai quan tâm đến lĩnh vực này.

3

– Thời gian nghiên cứu không nhiều nên có thể còn một số nội dung
hay mà luận văn chưa đề cập đến. Tôi sẽ tiếp tục nghiên cứu và bổ sung
thường xuyên để nội dung luận văn được phong phú, có thể dùng làm tài liệu
ôn thi học sinh giỏi ở bậc trung học phổ thông.
7. Cấu trúc luận văn
Luận văn được trình bày trong 3 chương
 Mở đầu
 Chương 1 – Cơ sở lý thuyết
 Chương 2 – Lý thuyết tổ hợp số
 Chương 3 – Ứng dụng của lý thuyết tổ hợp số
 Kết luận

4

CHƯƠNG 1
CƠ SỞ LÝ THUYẾT
1.1. TẬP HỢP VÀ CÁC PHÉP TOÁN TẬP HỢP
1.1.1. Khái niệm tập hợp
Định nghĩa 1.1.
Tập hợp được coi là xác định nếu ta có thể chỉ ra được tất cả các phần
tử của nó.
Tập hợp thường được kí hiệu bằng các chữ cái in hoa A, B, C,…
Các phần tử của tập hợp thường được kí hiệu bằng các chữ cái thường
a, b, c,…
Để chỉ x là phần tử của tập X ta viết
x  X ( đọc: x thuộc X)

Để chỉ x không phải là phần tử của tập X ta viết

x  X ( đọc: x không thuộc X)
Tập không có phần tử nào gọi là tập rỗng và kí hiệu là 
Mỗi phần tử của tập B đều thuộc tập A thì tập B được gọi là tập con
của tập A và được kí hiệu là B  A hoặc B  A .
Các phần tử của một tập hợp được chỉ ra bằng một trong hai cách sau
 Liệt kê chúng
 Chỉ ra tính chất đặc trưng của chúng
1.1.2. Các phép toán tập hợp
a. Phép hiệu: Hiệu của A và B, ký hiệu A \ B là tập

5

A \ B  x | x  A & x  B
b. Phần bù: Cho tập X và A  X. Phần bù của A trong X là tập

AX  X \ A
c. Phép hợp: Hợp của A và B, kí hiệu A  B là tập
A  B  x | x  A hoÆc x  B

d. Phép giao: Giao của A và B, ký hiệu A  B là tập

A  B  x | x  A & x  B
1.1.3. Lực lượng tập hợp
Số phần tử của tập A, ký hiệu là A hoặc card(A), gọi là lực lượng của
tập A. Nếu A  , ta nói A là tập hữu hạn. Nếu A  , ta nói A là tập vô
hạn.
1.2. BÀI TOÁN TỔ HỢP
Lý thuyết tổ hợp nghiên cứu việc phân bố, sắp xếp các phần tử của một

hoặc nhiều tập hợp, thỏa mãn một số điều kiện nào đó.
Mỗi cách phân bố, sắp xếp như thế gọi là một cấu hình tổ hợp.
1.2.1. Cấu hình tổ hợp
Cho các tập hợp A1,…, An. Giả sử S là sơ đồ sắp xếp các phần tử của
A1,…, An được mô tả bằng các qui tắc sắp xếp và R1,…, Rm là các điều kiện
ràng buộc lên mỗi sắp xếp theo sơ đồ S. Khi đó, mỗi sắp xếp các phần tử của
A1,…, An thỏa mãn điều kiện R1,…, Rm gọi là một cấu hình tổ hợp trên các
tập A1,…, An.

6

1.2.2. Các dạng bài toán tổ hợp
Có bốn dạng bài toán tổ hợp cơ bản: Bài toán tồn tại, bài toán đếm, bài
toán liệt kê và bài toán tối ưu.
1.3. NGUYÊN LÝ NHÂN VÀ NGUYÊN LÝ CỘNG
1.2.1. Nguyên lý nhân
Giả sử một cấu hình tổ hợp được xây dựng qua k bước, trong đó
bước 1 có thể thực hiện n1 cách,
bước 2 có thể thực hiện n2 cách,
…,
bước k có thể thực hiện nk cách.
Khi đó số cấu hình tổ hợp là
n1.n2…nk
Ví dụ 1.1. Từ A đến B có 4 đường đi, từ B đến C có 6 đường đi
i. Có bao nhiêu đường đi từ A đến C
ii. Có bao nhiêu đường đi từ A đến C và trở lại A
iii. Có bao nhiêu đường đi từ A đến C và trở lại A nhưng không đi
đường nào đó quá một lần.
Giải

i. Có bao nhiêu đường đi từ A đến C
Có 4 cách chọn đường đi từ A đến B
Có 6 cách chọn đường đi từ B đến C
Vậy theo nguyên lý nhân, số đường đi từ A đến C là

7

4  6  24 cách chọn.
ii. Có bao nhiêu đường đi từ A đến C và trở lại A
Có 4 cách chọn đường đi từ A đến B
Có 6 cách chọn đường đi từ B đến C
Có 6 cách chọn đường đi từ C trở lại B
Có 4 cách chọn đường đi từ B trở lại A
Vậy theo nguyên lý nhân, số đường đi từ A đến C là

4  6  6  4  576 cách chọn.
iii. Có bao nhiêu đường đi từ A đến C và trở lại A nhưng không đi đường nào
đó quá một lần
Có 4 cách chọn đường đi từ A đến B
Có 6 cách chọn đường đi từ B đến C
Có 5 cách chọn đường đi từ C trở lại B vì không đi lại đường cũ
Có 3 cách chọn đường đi từ B trở lại A vì không đi lại đường cũ
Vậy theo nguyên lý nhân, số đường đi từ A đến C là

4  6  5  3  360 cách chọn.
Ví dụ 1.2. Có bao nhiêu cách chọn trang phục cho ca sĩ Đàm Vĩnh Hưng gồm
áo, quần, giày và nịt trong đêm trình diễn biết rằng có 30 kiểu áo, 21 kiểu
quần, 15 kiểu giày và 8 kiểu nịt.
Giải

Có 30 cách chọn áo
Có 21 cách chọn quần

8

Có 15 cách chọn giày
Có 8 cách chọn nịt
Theo nguyên lí nhân, tổng số cách chọn trang phục cho ca sĩ trên là

30  21 15  8  75.600 cách chọn
1.2.2. Nguyên lý cộng
Giả sử X1 ,X 2 ,…,X n  là một phân hoạch của tập S. Khi đó:

S  X1  X 2  …  X n
Ví dụ 1.3. Từ các chữ số 0,1, 2,3, 4,5,6 có thể thành lập được bao nhiêu số tự
nhiên chẵn gồm 5 chữ số khác nhau.
Giải
Gọi số có 5 chữ số là a1a 2a 3a 4a 5
Số tự nhiên chẵn gồm 5 chữ số khác nhau nên a5 phải là 0, 2,4,6.
+ Nếu a5 = 0 thì còn lại 6 số 1, 2,3,4,5,6
Có 6 cách chọn a1
Có 5 cách chọn a2
Có 4 cách chọn a3
Có 3 cách chọn a4
Vậy theo nguyên lý nhân, tất cả các số tự nhiên gồm 5 chữ số khác nhau mà
tận cùng bằng 0 là

6  5  4  3  360 số
+ Nếu a 5  0 thì ta chọn a 5 trước, có 3 cách chọn a 5

9

có 5 cách chọn a1
có 5 cách chọn a2
có 4 cách chọn a3
có 3 cách chọn a4
Theo nguyên lý nhân, tất cả các số tự nhiên gồm 5 chữ số khác nhau mà tận
cùng bằng 2,4,6 là

5  5  4  3  3  900 số
Vậy theo nguyên lý cộng, tổng các số tự nhiên chẵn gồm 5 chữ số khác nhau
là

360  900  1260 số
Ví dụ 1.4. Có bao nhiêu số tự nhiên gồm bốn chữ số sao cho không có chữ số
nào lặp lại đúng ba lần.
Giải
Gọi số tự nhiên có bốn chữ số là a1a 2a 3a 4
Tổng các số có bốn chữ số được tạo thành (không cần chú ý đến điều
kiện)

a 1 có 9 cách chọn ( a1  0 )
a 2 có 10 cách chọn
a3 có 10 cách chọn
a 4 có 10 cách chọn
Theo nguyên lý nhân, ta có 9  10  10  10  9.000 số có bốn chữ số.
Số có bốn chữ số và có chữ số lặp lại đúng ba lần.

10

Trường hợp 1: a1  a 2  a 3

a1a 2a 3 được coi như một phần tử, có 9 cách chọn phần tử này (vì

a1  0 )
Có 9 cách chọn a 4 (vì a 4  a1 )
Vậy có 9  9  81 cách chọn.
Tương tự cho hai trường hợp a1  a 3  a 4 và a 2  a 3  a 4, mỗi trường
hợp có 81 cách chọn.
Các số có bốn chữ số trong ba trường hợp trên là khác nhau, nên có tất
cả 81  81  81  243 số có chữ số lặp lại đúng ba lần.
Vậy số tự nhiên gồm bốn chữ số mà không có chữ số nào lặp lại đúng
ba lần là 9000  243  8757 số.
1.4. CÁC CẤU HÌNH TỔ HỢP CƠ BẢN
1.4.1. Chỉnh hợp lặp
Định nghĩa 1.2. Một chỉnh hợp lặp chập k của n phần tử khác nhau là một bộ
có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các thành phần có thể
được lặp lại.
Định lí 1.1. Nếu gọi số các chỉnh hợp lặp chập k của n phần tử là AR(n,k) thì
AR(n,k) = nk
Chứng minh
Một chỉnh hợp lặp chập k của n phần tử khác nhau được xem như là
một phần tử của tích Đề-các Xk, với X là tập hợp n phần tử.
k

Mà X  n k

11

Nên AR(n,k) = nk
Ví dụ 1.5. Có bao nhiêu dãy gồm 4 chữ cái được lấy từ 26 chữ cái trong bảng
chữ cái.
Giải
Mỗi cách chọn 4 chữ cái là một chỉnh hợp lặp chập 4 của 26 phần tử.
Vậy có AR  26,4   264  456.976 dãy.
Ví dụ 1.6. Từ các chữ số 1, 2, 3, 5 có thể thành lập được bao nhiêu số chẵn
gồm bốn chữ số.
Giải
Trong bốn số 1, 2, 3, 5 chỉ có duy nhất số 2 là số chẵn. Do đó, gọi số có
bốn chữ số là a1a 2a 3a 4, số a1a 2a 3a 4 là số chẵn khi và chỉ khi a 4  2 .
Mặt khác, a1 ,a 2 ,a 3 có thể bằng nhau nên mỗi cách chọn a1 ,a 2 ,a 3 là một
chỉnh hợp lặp chập 3 của bốn phần tử 1, 2, 3, 5. Vậy có A(3, 4)  43  64
cách.
1.4.2. Chỉnh hợp không lặp
Định nghĩa 1.3. Một chỉnh hợp không lặp chập k của n phần tử khác nhau là
một bộ có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các thành phần
không được lặp lại.
Định lí 1.2. Nếu gọi số các chỉnh hợp không lặp chập k của n phần tử là
A(n,k) thì
A  n, k  

n!
(n  k)!

12

Chứng minh
Một chỉnh hợp không lặp chập k của n phần tử khác nhau là một bộ có
thứ tự gồm k thành phần không lặp a 1a 2 …a k được xây dựng qua k bước kế
tiếp như sau:
Chọn thành phần a1

: có n khả năng, còn lại n – 1 phần tử,

Chọn thành phần a2

: có n – 1 khả năng, còn lại n – 2 phần tử,

…
Chọn thành phần a2

: có n – k + 1 khả năng, còn lại n – k phần tử.

Theo nguyên lí nhân, số tất cả các chỉnh hợp không lặp chập k của n
phần tử khác nhau là:
A  n, k   n.(n  1)…(n  k  1) 

n!
(n  k)!

Ví dụ 1.7. Một cuộc khiêu vũ có 10 nam và 5 nữ. Hỏi có bao nhiêu cách chọn
3 nam và 3 nữ để ghép thành 3 cặp.
Giải
Mỗi cách chọn 3 nam trong 10 nam là một chỉnh hợp không lặp chập 3
của 10 phần tử. Vậy có A(10,3) 

10!
 10  9  8  720 cách.
(10  3)!

Mỗi cách chọn 3 nữ trong 5 nữ là một chỉnh hợp không lặp chập 3 của
5 phần tử. Vậy có A(5,3) 

5!
 5  4  3  60 cách.
(5  3)!

Theo nguyên lý nhân, tổng số cách chọn 3 cặp là:
A(10,3).A(5,3)  720  60  43.200 cách

Ví dụ 1.8. Với các chữ số 0,1, 2,3, 4,5,6 ta có thể lập được bao nhiêu số gồm

13

4 chữ số khác nhau và trong đó phải có mặt chữ số 5.
Giải
Gọi số có 4 chữ số là a 1a 2a 3a 4
Nếu a1  5 thì mỗi cách chọn 3 số còn lại là một chỉnh hợp không lặp
chập 3 của 6 phần tử. Vậy có A(6,3) 

6!
 120 số.
(6  3)!

Nếu a 2  5 thì mỗi cách chọn 3 số còn lại là một chỉnh hợp không lặp
chập 3 của 6 phần tử hay A(6,3), nhưng loại trừ các số mà có a1  0 .
Các số có 4 chữ số mà có a1  0, a 2  5 là một chỉnh hợp không lặp
chập 2 của 5 phần tử hay A(5,2) .
Vậy có A(6,3)  A(5,2)  120  20  100 số.
Tương tự cho các trường hợp a 3  5, a 4  5 .
Vậy số các số thỏa mãn điều kiện bài toán là

120  3  100  420 số.
1.4.3. Hoán vị
Định nghĩa 1.4. Một hoán vị của n phần tử khác nhau là một cách sắp xếp các
phần tử đó.
Định lí 1.3. Nếu gọi số tất cả các hoán vị của n phần tử là P(n) thì

P(n)  n!
Chứng minh
Một hoán vị của n phần tử có thể xem là một trường hợp riêng của
chỉnh hợp không lặp chập k của n phần tử với n = k.

14

Vậy số hoán vị của n phần tử khác nhau là:

P(n)  n.(n  1)…2.1  n!
Ví dụ 1.9. Mười học sinh cùng ngồi trên một hàng ghế, chơi trò đổi chỗ. Cho
rằng mỗi lần đổi chỗ mất hết 1 phút. Hỏi thời gian họ đổi chỗ hết cho nhau là
bao nhiêu?
Giải
Mỗi lần đổi chỗ là một hoán vị của 10 phần tử. Vậy tổng số lần đổi chỗ

là

P(10)  10!  3.628.800 lần.
Vậy thời gian các học sinh đổi chỗ cho nhau là 3.628.800 phút hay
2.520 giờ hay gần 7 năm.
Ví dụ 1.10. Một hội nghị bàn tròn có phái đoàn các nước: Việt Nam 6 người,
Lào 3 người, Campuchia 2 người, Thái Lan 3 người và Trung Quốc 4 người.
Có bao nhiêu cách xếp chỗ ngồi cho các phái đoàn sao cho người cùng quốc
tịch thì ngồi cùng nhau.
Giải
Có thể mời một phái đoàn nào đó ngồi vào chỗ trước, sau đó xếp bốn
phái đoàn còn lại cùng ngồi vào bàn. Vậy có, 4!  24 cách xếp các phái đoàn
ngồi theo cùng quốc gia của mình.
trong đó có

6! cách xếp chỗ ngồi cho người Việt Nam

3! cách xếp chỗ ngồi cho người Lào
2! cách xếp chỗ ngồi cho người Campuchia

15

3! cách xếp chỗ ngồi cho người Thái Lan
4! cách xếp chỗ ngồi cho người Trung Quốc
Vậy có 24.6!3!2!3!4!  29.859.840 .
1.4.4. Tổ hợp
Định nghĩa 1.5. Một tổ hợp chập k của n phần tử khác nhau là một bộ không
kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử đã cho. Hay một tổ
hợp chập k của n phần tử khác nhau là một tập con có k phần tử lấy từ n phần

tử đã cho.
Định lí 1.4. Nếu gọi số tổ hợp chập k của n phần tử là C(n,k) thì
C  n, k  

n!
k!(n  k)!

Chứng minh
Một tổ hợp chập k của n phần tử khác nhau là một tập con có k phần tử
từ n phần tử đã cho.
Do đó:
A(n;k)  C(n;k).k!

Suy ra C  n, k  

n!
k!(n  k)!

Ví dụ 1.11. Có bao nhiêu đường chéo trong đa giác lồi n cạnh.
Giải
Nối hai đỉnh không kề nhau của đa giác ta được đường chéo của đa
giác.
Nối hai đỉnh kề nhau ta được một cạnh của đa giác.

16

Mỗi cách nối bất kì hai đỉnh của đa giác là một tổ hợp chập 2 của n
phần tử. Vậy có
C(n, 2) 

n!
n  (n  1)

2! (n  2)!
2

Vậy số đường chéo trong đa giác lồi n cạnh là:
n  (n  1)
n  (n  3)
đường.
n
2
2

Ví dụ 1.12. Cho 10 câu hỏi trong đó có 4 câu lí thuyết và 6 câu bài tập. Người
ta cấu tạo đề thi từ các câu hỏi đó. Biết rằng mỗi đề thi gồm 3 câu, trong đó
nhất thiết phải có 1 câu lý thuyết và 1 câu bài tập. Hỏi có bao nhiêu khả năng
cấu tạo đề thi?
Giải
Trường hợp 1: Đề thi gồm 2 câu lý thuyết và 1 câu bài tập
Mỗi cách chọn 2 câu lí thuyết là một tổ hợp chập 2 của 4 phần tử hay
C(4,2)

Mỗi cách chọn 1 câu bài tập là một tổ hợp chập 1 của 6 phần tử hay
C(6,1)

Theo nguyên lý nhân, tổng số cách chọn là:
C(4,2)C(6,1)  36 đề

Trường hợp 2: Đề thi gồm 1 câu lí thuyết và 2 câu bài tập
Mỗi cách chọn 1 câu lí thuyết là một tổ hợp chập 1 của 4 phần tử hay

C(4,1)
Mỗi cách chọn 2 câu bài tập là một tổ hợp chập 2 của 6 phần tử hay

C(6,2)

17

Theo nguyên lý nhân, tổng số cách chọn là:
C(4,1)C(6,2)  60 đề

Mỗi cách cấu tạo đề thi trong hai trường hợp là khác nhau nên theo
nguyên lý cộng, tổng số đề thi được tạo ra là

36  60  96 đề.
1.5. CÁC CẤU HÌNH TỔ HỢP NÂNG CAO
1.5.1. Hoán vị lặp
Định nghĩa 1.6. Hoán vị lặp là hoán vị trong đó mỗi phần tử được ấn định lại
một số lần lặp lại cho trước
Định lí 1.5. Số hoán vị lặp của k phần tử khác nhau, trong đó phần tử thứ nhất
lặp n1 lần, phần tử thứ hai lặp n 2 lần, …, phần tử thứ k lặp lại n k lần là

P(n;n 1 ,n 2 ,…,n k ) 

n!
,
n1 !.n 2 !…n k !

trong đó

n  n1  n 2  …  n k .
Chứng minh
Cách xếp chỗ cho n1 phần tử thứ nhất là: C(n; n1), còn lại n  n1 chỗ,
Cách xếp chỗ cho n 2 phần tử thứ hai là: C( n  n1 ; n2), còn lại

n  n1  n 2 chỗ,
…
Cách xếp chỗ cho n k phần tử thứ k là :
còn lại n  n1  n 2  …  n k chỗ,

C( n  n1  n 2  …  n k 1 ;

nk),

18

Theo nguyên lý nhân, số tất cả các hoán vị lặp của k phần tử khác nhau
là

P(n;n1 ,n 2 ,…,n k )  C(n;n 1 )C(n  n1;n 2 )…C(n  n1  …  n k 1;n k )


n!
(n  n 1 )
(n  n1  …  n k 1 )
…

n1 !.(n  n 1 )! n 2 !.(n  n1  n 2 )!
n k !.0!



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

Ví dụ 1.13. Có 10 chiếc điện thoại giống nhau, trong đó có 4 chiếc điện thoại
màu đỏ, 3 chiếc điện thoại màu trắng và 3 chiếc điện thoại màu xanh được lắp
vào 12 phòng. Hãy đếm số phương án lắp các điện thoại.
Giải
10 chiếc điện thoại lắp vào 12 phòng, vậy có hai phòng không có điện
thoại. Do đó, khi lắp 10 chiếc điện thoại vào 10 phòng thì bao gồm 4 loại: 4
chiếc điện thoại màu đỏ, 3 chiếc điện thoại màu trắng, 3 chiếc điện thoại màu
xanh và 2 phòng không có điện thoại. Như vậy, mỗi phương án lắp điện thoại
là một hoán vị lặp của bốn phần tử, trong đó
phần tử thứ nhất lặp lại 4 lần
phần tử thứ hai lặp lại 3 lần
phần tử thứ ba lặp lại 3 lần
phần tử thứ bốn lặp lại 2 lần.
Vậy các phương án lắp điện thoại là

P(12;4,3,3,2) 

12!
 554.400 cách lắp.
4!3!3!2!

Ví dụ 1.14. Một lớp học có 20 sinh viên. Nhà trường chia các sinh viên trên

vào 4 kí túc xá khác nhau, trong đó 3 sinh viên vào kí túc xá đầu tiên, 5 sinh

19

viên vào kí túc xá thứ hai, 4 sinh viên vào kí túc xá thứ ba và các sinh viên
còn lại vào kí túc xá thứ tư. Có bao nhiêu phương án phân chia như vậy.
Giải
20 sinh viên chia vào 4 kí túc xá khác nhau, có 3 sinh viên vào kí túc xá
đầu tiên, 5 sinh viên vào kí túc xá thứ hai, 4 sinh viên vào kí túc xá thứ ba và
8 sinh viên còn lại vào kí túc xá thứ tư. Do đó mỗi cách chia là một hoán vị
lặp của bốn phần tử, trong đó
phần tử thứ nhất lặp lại 3 lần
phần tử thứ hai lặp lại 5 lần
phần tử thứ ba lặp lại 4 lần
phần tử thứ bốn lặp lại 8 lần.
Vậy số cách chia là

P(20;3,5,4,8) 

20!
 3.491.888.400 cách.
3!5!4!8!

Hệ quả 1.1. Giả sử tập S có n phần tử, trong đó có n1 phần tử kiểu 1, n 2 phần
tử kiểu 2,…, n k phần tử kiểu k. Khi đó số các hoán vị n phần tử của tập hợp S
là

P(n;n 1 ,n 2 ,…,n k ) 

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

1.5.2. Tổ hợp lặp
Định nghĩa 1.7. Tổ hợp lặp chập k từ n phần tử khác nhau là một nhóm
không phân biệt thứ tự gồm k phần tử trích từ n phần tử đã cho, trong đó các
phần tử có thể lặp lại.
Định lí 1.6. Nếu X có n phần tử khác nhau và gọi CR(n, k) là số tổ hợp lặp

20

chập k từ n phần tử của X thì

CR(n,k)  C(k  n  1,n  1)  C(k  n  1,k)
Chứng minh
Mỗi tổ hợp lặp chập k từ n phần tử có thể biểu diễn bằng một dãy gồm
(n – 1) dấu gạch đứng và k ngôi sao. Trong đó k ngôi sao chỉ k phần tử được
chọn và (n – 1) dấu gạch đứng chỉ phân cách giữa các loại sách với nhau.

* *

|

*

|

* … |

*

Như vậy, có k  (n  1)  n  k  1 chỗ trống để xếp k ngôi sao và (n –
1) dấu gạch đứng.
Do đó, một tổ hợp lặp chập k từ n phần tử là một cách xếp k ngôi sao
vào n  k  1 chỗ trống hay một cách xếp (n – 1) dấu gạch đứng vào n  k  1
chỗ trống.
Mỗi cách xếp k ngôi sao vào n  k  1 chỗ trống là một tổ hợp chập k
của n  k  1 phần tử. Vậy có C(k  n  1,k)
Mỗi cách xếp (n – 1) dấu gạch đứng vào n  k  1 chỗ trống là một tổ
hợp chập (n – 1) của n  k  1 phần tử. Vậy có C(k  n  1,n  1)
Tức là, CR(n,k)  C(k  n  1,n  1)  C(k  n  1,k)
Ví dụ 1.15. Trong két tiền có các loại 1 nghìn, 2 nghìn, 5 nghìn, 10 nghìn, 20
nghìn, 50 nghìn và 100 nghìn đồng, mỗi loại có ít nhất 5 tờ. Hỏi có bao nhiêu
cách chọn 5 tờ giấy bạc.
Giải
Mỗi tờ giấy bạc cùng loại là như nhau và thứ tự lấy các tờ giấy bạc là

1. Lý do chọn đề tài ……………………………………………………………………. 12. Mục đích điều tra và nghiên cứu ………………………………………………………………. 23. Đối tượng nghiên cứu và điều tra và khoanh vùng phạm vi nghiên cứu và điều tra …………………………….. 24. Nhiệm vụ điều tra và nghiên cứu ……………………………………………………………… 25. Phương pháp nghiên cứu và điều tra …………………………………………………………. 26. Ý nghĩa khoa học và thực tiễn của đề tài …………………………………….. 27. Cấu trúc luận văn ……………………………………………………………………. 3CH ƯƠNG 1. CƠ SỞ LÝ THUYẾT …………………………………………………… 41.1. TẬP HỢP VÀ CÁC PHÉP TOÁN TẬP HỢP …………………………………. 41.1.1. Khái niệm tập hợp ………………………………………………………………. 41.1.3. Lực lượng tập hợp ………………………………………………………………. 51.2. BÀI TOÁN TỔ HỢP …………………………………………………………………… 51.2.1. Cấu hình tổ hợp …………………………………………………………………. 51.2.2. Các dạng bài toán tổ hợp ……………………………………………………… 61.3. NGUYÊN LÝ CỘNG VÀ NGUYÊN LÝ NHÂN ……………………………. 61.2.1. Nguyên lý nhân ………………………………………………………………….. 61.2.2. Nguyên lý cộng ………………………………………………………………….. 81.4. CÁC CẤU HÌNH TỔ HỢP CƠ BẢN …………………………………………… 101.4.1. Chỉnh hợp lặp ………………………………………………………………….. 101.4.2. Chỉnh hợp không lặp …………………………………………………………. 111.4.3. Hoán vị …………………………………………………………………………… 131.4.4. Tổ hợp ……………………………………………………………………………. 151.5. CÁC CẤU HÌNH TỔ HỢP NÂNG CAO ……………………………………… 171.5.1. Hoán vị lặp ……………………………………………………………………… 171.5.2. Tổ hợp lặp ……………………………………………………………………….. 191.5.3. Phân hoạch thứ tự tổ hợp …………………………………………………… 211.5.4. Phân hoạch không thứ tự ……………………………………………………. 231.6. NGUYÊN LÝ BÙ TRỪ …………………………………………………………….. 241.6.1. Công thức bao hàm và loại trừ ……………………………………………. 241.6.2. Công thức Sieve ……………………………………………………………….. 25CH ƯƠNG 2. LÝ THUYẾT TỔ HỢP SỐ ………………………………………… 282.1. SỐ SQUARE-FREE ………………………………………………………………….. 282.2. HÀM TÍNH NHÂN …………………………………………………………………… 282.3. HÀM EULER  ( n ) …………………………………………………………………… 322.4. HÀM MÖBIUS  ( n ) ………………………………………………………………… 352.5. HÀM RIEMANN ZETA  ( s ) …………………………………………………….. 41CH ƯƠNG 3. ỨNG DỤNG LÝ THUYẾT TỔ HỢP SỐ …………………….. 443.1. BÀI TOÁN TÌM CÁC SỐ NGUYÊN DƯƠNG KHÔNG CHIA HẾTCHO TẬP SỐ NGUYÊN DƯƠNG ……………………………………………………. 443.2. BÀI TOÁN TÌM CÁC SỐ NGUYÊN TỐ NHỎ HƠN MỘT SỐNGUYÊN DƯƠNG NÀO ĐÓ ………………………………………………………….. 473.3. BÀI TOÁN TÌM CÁC SỐ NGUYÊN SQUARE-FREE KHÔNGVƯỢT QUÁ SỐ NGUYÊN DƯƠNG N CHO TRƯỚC ………………………… 533.4. BÀI TOÁN ĐẾM CÁC ƯỚC VÀ TÍNH TỔNG CÁC ƯỚC CỦA MỘTSỐ NGUYÊN DƯƠNG CHO TRƯỚC ………………………………………………. 543.4.1. Đếm các ước nguyên dương của một số ít nguyên dương ………….. 543.4.2. Tính tổng các ước nguyên dương của 1 số ít nguyên dương ……. 563.5. BÀI TOÁN ĐẾM SỐ TỪ TRÒN CÓ ĐỘ DÀI N ĐƯỢC LẤY TỪ MKÍ TỰ CHO TRƯỚC ………………………………………………………………………. 613.6. TÌM SỐ DƯ TRONG PHÉP CHIA MỘT LŨY THỪA CHO MỘT SỐ653. 7. GIẢI PHƯƠNG TRÌNH ĐỒNG DƯ BẬC NHẤT MỘT ẨNax  b ( mod m ) ……………………………………………………………………………… 69K ẾT LUẬN …………………………………………………………………………………… 71T ÀI LIỆU THAM KHẢO ………………………………………………………………. 72QUY ẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN THẠC SĨ ( BẢN SAO ) MỞ ĐẦU1. Lý do chọn đề tàiLý thuyết số là một ngành của toán học lý thuyết điều tra và nghiên cứu về tínhchất của số nói chung và số nguyên nói riêng, cũng như những lớp rộng hơncác bài toán mà tăng trưởng từ những điều tra và nghiên cứu của nó. Toán học tổ hợp được hình thành vào đầu thế kỷ XVII và phát triểnmạnh cùng với sự bùng nổ của công nghệ thông tin, đặc biệt quan trọng là các công trìnhnghiên cứu của các nhà toán học nổi tiếng như Pascal, Fermat, Leibnitz, Euler, … Các yếu tố tương quan đến lý thuyết tổ hợp là một bộ phận quan trọng, mê hoặc và lí thú của Toán học nói chung và toán rời rạc nói riêng. Nó có nộidung phong phú và đa dạng và được ứng dụng nhiều trong đời sống, đặc biệt quan trọng là từ khi tinhọc sinh ra. Lý thuyết tổ hợp số là một nội dung hay của lý thuyết tổ hợp, nó giảiquyết các bài toán về lý thuyết số mà có tư tưởng tổ hợp trong công thức hoặccách chứng tỏ. Tổ hợp đã được đưa vào giảng dạy ở chương trình học đại trà phổ thông, đạihọc, sau đại học và nó là một bộ môn tương đối khó so với học viên, sinhviên vì khái niệm trừu tượng và nhiều dạng toán rất khó nhưng thời lượngdành cho môn này còn hạn chế nhất là bậc trung học phổ thông. Trong nhiều kì thi học viên giỏi vương quốc, thi Olympic toán quốc tế, thiOlympic sinh viên giữa các trường ĐH, cao đẳng các bài toán liên quanđến tổ hợp hay được đề cập và thường thuộc loại rất khó nên học viên đa sốcòn lúng túng khi xử lý những bài toán loại này. Chính vì các nguyên do nêu trên, tôi quyết định hành động chọn đề tài “ Lý thuyết tổhợp số và ứng dụng ” để khám phá, nghiên cứu và điều tra nhằm mục đích Giao hàng cho công tácgiảng dạy của tôi nói chung và luyện thi học viên giỏi nói riêng sau này. 2. Mục đích nghiên cứuNghiên cứu về lý thuyết tổ hợp số và ứng dụng của lý thuyết tổ hợp sốđể giải các bài toán về số tổ hợp. 3. Đối tượng điều tra và nghiên cứu và khoanh vùng phạm vi nghiên cứu và điều tra – Đối tượng nghiên cứu và điều tra là lý thuyết tổ hợp số. – Phạm vi nghiên cứu và điều tra là số tổ hợp và ứng dụng của nó. 4. Nhiệm vụ điều tra và nghiên cứu – Tìm hiểu về lý thuyết tổ hợp, đặc biệt quan trọng là lý thuyết tổ hợp số – Tìm hiểu và kiến thiết xây dựng các ứng dụng của lý thuyết tổ hợp số5. Phương pháp điều tra và nghiên cứu – Nghiên cứu lý thuyết trải qua việc siêu tầm các loại tài liệu nhưsách, báo, tạp chí, mạng internet, thầy cô, bè bạn. Trình bày một cách có hệthống các nội dung lý thuyết đã điều tra và nghiên cứu và tìm hiểu và khám phá. Mỗi nội dung ta phảichứng minh đơn cử, rõ ràng và lấy ví dụ minh họa xác nhận, dễ hiểu. – Phân loại và mạng lưới hệ thống các dạng toán. Tìm ra các giải pháp đặctrưng để giải mỗi dạng toán đơn cử. 6. Ý nghĩa khoa học và thực tiễn của đề tài – Đề tài góp thêm phần nghiên cứu ứng dụng của lý thuyết tổ hợp số vào giảitoán tổ hợp tương thích với chuyên ngành Phương pháp toán sơ cấp. – Sau khi được cho phép bảo vệ, được sự góp ý của các thầy cô trong hộiđồng, luận văn hoàn toàn có thể dùng làm tài liệu tìm hiểu thêm cho sinh viên, giáo viên, học viên đại trà phổ thông và những ai chăm sóc đến nghành này. – Thời gian điều tra và nghiên cứu không nhiều nên hoàn toàn có thể còn một số ít nội dunghay mà luận văn chưa đề cập đến. Tôi sẽ liên tục nghiên cứu và điều tra và bổ sungthường xuyên để nội dung luận văn được nhiều mẫu mã, hoàn toàn có thể dùng làm tài liệuôn thi học viên giỏi ở bậc trung học phổ thông. 7. Cấu trúc luận vănLuận văn được trình diễn trong 3 chương  Mở đầu  Chương 1 – Cơ sở lý thuyết  Chương 2 – Lý thuyết tổ hợp số  Chương 3 – Ứng dụng của lý thuyết tổ hợp số  Kết luậnCHƯƠNG 1C Ơ SỞ LÝ THUYẾT1. 1. TẬP HỢP VÀ CÁC PHÉP TOÁN TẬP HỢP1. 1.1. Khái niệm tập hợpĐịnh nghĩa 1.1. Tập hợp được coi là xác lập nếu ta hoàn toàn có thể chỉ ra được tổng thể các phầntử của nó. Tập hợp thường được kí hiệu bằng các vần âm in hoa A, B, C, … Các thành phần của tập hợp thường được kí hiệu bằng các vần âm thườnga, b, c, … Để chỉ x là thành phần của tập X ta viếtx  X ( đọc : x thuộc X ) Để chỉ x không phải là thành phần của tập X ta viếtx  X ( đọc : x không thuộc X ) Tập không có thành phần nào gọi là tập rỗng và kí hiệu là  Mỗi thành phần của tập B đều thuộc tập A thì tập B được gọi là tập concủa tập A và được kí hiệu là B  A hoặc B  A. Các thành phần của một tập hợp được chỉ ra bằng một trong hai cách sau  Liệt kê chúng  Chỉ ra đặc thù đặc trưng của chúng1. 1.2. Các phép toán tập hợpa. Phép hiệu : Hiệu của A và B, ký hiệu A \ B là tậpA \ B   x | x  A và x  B  b. Phần bù : Cho tập X và A  X. Phần bù của A trong X là tậpAX  X \ Ac. Phép hợp : Hợp của A và B, kí hiệu A  B là tậpA  B   x | x  A hoÆc x  B  d. Phép giao : Giao của A và B, ký hiệu A  B là tậpA  B   x | x  A và x  B  1.1.3. Lực lượng tập hợpSố thành phần của tập A, ký hiệu là A hoặc card ( A ), gọi là lực lượng củatập A. Nếu A  , ta nói A là tập hữu hạn. Nếu A  , ta nói A là tập vôhạn. 1.2. BÀI TOÁN TỔ HỢPLý thuyết tổ hợp nghiên cứu và điều tra việc phân bổ, sắp xếp các thành phần của mộthoặc nhiều tập hợp, thỏa mãn nhu cầu 1 số ít điều kiện kèm theo nào đó. Mỗi cách phân bổ, sắp xếp như vậy gọi là một thông số kỹ thuật tổ hợp. 1.2.1. Cấu hình tổ hợpCho các tập hợp A1, …, An. Giả sử S là sơ đồ sắp xếp các thành phần củaA1, …, An được diễn đạt bằng các qui tắc sắp xếp và R1, …, Rm là các điều kiệnràng buộc lên mỗi sắp xếp theo sơ đồ S. Khi đó, mỗi sắp xếp các thành phần củaA1, …, An thỏa mãn nhu cầu điều kiện kèm theo R1, …, Rm gọi là một thông số kỹ thuật tổ hợp trên cáctập A1, …, An. 1.2.2. Các dạng bài toán tổ hợpCó bốn dạng bài toán tổ hợp cơ bản : Bài toán sống sót, bài toán đếm, bàitoán liệt kê và bài toán tối ưu. 1.3. NGUYÊN LÝ NHÂN VÀ NGUYÊN LÝ CỘNG1. 2.1. Nguyên lý nhânGiả sử một thông số kỹ thuật tổ hợp được kiến thiết xây dựng qua k bước, trong đóbước 1 hoàn toàn có thể thực thi n1 cách, bước 2 hoàn toàn có thể triển khai n2 cách, …, bước k hoàn toàn có thể triển khai nk cách. Khi đó số thông số kỹ thuật tổ hợp làn1. n2 … nkVí dụ 1.1. Từ A đến B có 4 đường đi, từ B đến C có 6 đường đii. Có bao nhiêu đường đi từ A đến Cii. Có bao nhiêu đường đi từ A đến C và trở lại Aiii. Có bao nhiêu đường đi từ A đến C và trở lại A nhưng không điđường nào đó quá một lần. Giảii. Có bao nhiêu đường đi từ A đến CCó 4 cách chọn đường đi từ A đến BCó 6 cách chọn đường đi từ B đến CVậy theo nguyên tắc nhân, số đường đi từ A đến C là4  6  24 cách chọn. ii. Có bao nhiêu đường đi từ A đến C và trở lại ACó 4 cách chọn đường đi từ A đến BCó 6 cách chọn đường đi từ B đến CCó 6 cách chọn đường đi từ C trở lại BCó 4 cách chọn đường đi từ B trở lại AVậy theo nguyên tắc nhân, số đường đi từ A đến C là4  6  6  4  576 cách chọn. iii. Có bao nhiêu đường đi từ A đến C và trở lại A nhưng không đi đường nàođó quá một lầnCó 4 cách chọn đường đi từ A đến BCó 6 cách chọn đường đi từ B đến CCó 5 cách chọn đường đi từ C trở lại B vì không đi lại đường cũCó 3 cách chọn đường đi từ B trở lại A vì không đi lại đường cũVậy theo nguyên tắc nhân, số đường đi từ A đến C là4  6  5  3  360 cách chọn. Ví dụ 1.2. Có bao nhiêu cách chọn phục trang cho ca sĩ Đàm Vĩnh Hưng gồmáo, quần, giày và nịt trong đêm trình diễn biết rằng có 30 kiểu áo, 21 kiểuquần, 15 kiểu giày và 8 kiểu nịt. GiảiCó 30 cách chọn áoCó 21 cách chọn quầnCó 15 cách chọn giàyCó 8 cách chọn nịtTheo nguyên lí nhân, tổng số cách chọn phục trang cho ca sĩ trên là30  21  15  8  75.600 cách chọn1. 2.2. Nguyên lý cộngGiả sử  X1, X 2, …, X n  là một phân hoạch của tập S. Khi đó : S  X1  X 2  …  X nVí dụ 1.3. Từ các chữ số 0,1, 2,3, 4,5,6 hoàn toàn có thể xây dựng được bao nhiêu số tựnhiên chẵn gồm 5 chữ số khác nhau. GiảiGọi số có 5 chữ số là a1a 2 a 3 a 4 a 5S ố tự nhiên chẵn gồm 5 chữ số khác nhau nên a5 phải là 0, 2,4,6. + Nếu a5 = 0 thì còn lại 6 số 1, 2,3,4,5,6 Có 6 cách chọn a1Có 5 cách chọn a2Có 4 cách chọn a3Có 3 cách chọn a4Vậy theo nguyên tắc nhân, toàn bộ các số tự nhiên gồm 5 chữ số khác nhau màtận cùng bằng 0 là6  5  4  3  360 số + Nếu a 5  0 thì ta chọn a 5 trước, có 3 cách chọn a 5 có 5 cách chọn a1có 5 cách chọn a2có 4 cách chọn a3có 3 cách chọn a4Theo nguyên tắc nhân, tổng thể các số tự nhiên gồm 5 chữ số khác nhau mà tậncùng bằng 2,4,6 là5  5  4  3  3  900 sốVậy theo nguyên tắc cộng, tổng các số tự nhiên chẵn gồm 5 chữ số khác nhaulà360  900  1260 sốVí dụ 1.4. Có bao nhiêu số tự nhiên gồm bốn chữ số sao cho không có chữ sốnào lặp lại đúng ba lần. GiảiGọi số tự nhiên có bốn chữ số là a1a 2 a 3 a 4T ổng các số có bốn chữ số được tạo thành ( không cần quan tâm đến điềukiện ) a 1 có 9 cách chọn ( a1  0 ) a 2 có 10 cách chọna3 có 10 cách chọna 4 có 10 cách chọnTheo nguyên tắc nhân, ta có 9  10  10  10  9.000 số có bốn chữ số. Số có bốn chữ số và có chữ số lặp lại đúng ba lần. 10T rường hợp 1 : a1  a 2  a 3 a1a 2 a 3 được coi như một thành phần, có 9 cách chọn thành phần này ( vìa1  0 ) Có 9 cách chọn a 4 ( vì a 4  a1 ) Vậy có 9  9  81 cách chọn. Tương tự cho hai trường hợp a1  a 3  a 4 và a 2  a 3  a 4, mỗi trườnghợp có 81 cách chọn. Các số có bốn chữ số trong ba trường hợp trên là khác nhau, nên có tấtcả 81  81  81  243 số có chữ số lặp lại đúng ba lần. Vậy số tự nhiên gồm bốn chữ số mà không có chữ số nào lặp lại đúngba lần là 9000  243  8757 số. 1.4. CÁC CẤU HÌNH TỔ HỢP CƠ BẢN1. 4.1. Chỉnh hợp lặpĐịnh nghĩa 1.2. Một chỉnh hợp lặp chập k của n thành phần khác nhau là một bộcó thứ tự gồm k thành phần lấy từ n thành phần đã cho. Các thành phần có thểđược lặp lại. Định lí 1.1. Nếu gọi số các chỉnh hợp lặp chập k của n thành phần là AR ( n, k ) thìAR ( n, k ) = nkChứng minhMột chỉnh hợp lặp chập k của n thành phần khác nhau được xem như làmột thành phần của tích Đề-các Xk, với X là tập hợp n thành phần. Mà X  n k11Nên AR ( n, k ) = nkVí dụ 1.5. Có bao nhiêu dãy gồm 4 vần âm được lấy từ 26 vần âm trong bảngchữ cái. GiảiMỗi cách chọn 4 vần âm là một chỉnh hợp lặp chập 4 của 26 thành phần. Vậy có AR  26,4   264  456.976 dãy. Ví dụ 1.6. Từ các chữ số 1, 2, 3, 5 hoàn toàn có thể xây dựng được bao nhiêu số chẵngồm bốn chữ số. GiảiTrong bốn số 1, 2, 3, 5 chỉ có duy nhất số 2 là số chẵn. Do đó, gọi số cóbốn chữ số là a1a 2 a 3 a 4, số a1a 2 a 3 a 4 là số chẵn khi và chỉ khi a 4  2. Mặt khác, a1, a 2, a 3 hoàn toàn có thể bằng nhau nên mỗi cách chọn a1, a 2, a 3 là mộtchỉnh hợp lặp chập 3 của bốn thành phần 1, 2, 3, 5. Vậy có A ( 3, 4 )  43  64 cách. 1.4.2. Chỉnh hợp không lặpĐịnh nghĩa 1.3. Một chỉnh hợp không lặp chập k của n thành phần khác nhau làmột bộ có thứ tự gồm k thành phần lấy từ n thành phần đã cho. Các thành phầnkhông được lặp lại. Định lí 1.2. Nếu gọi số các chỉnh hợp không lặp chập k của n thành phần làA ( n, k ) thìA  n, k   n ! ( n  k ) ! 12C hứng minhMột chỉnh hợp không lặp chập k của n thành phần khác nhau là một bộ cóthứ tự gồm k thành phần không lặp a 1 a 2 … a k được thiết kế xây dựng qua k bước kếtiếp như sau : Chọn thành phần a1 : có n năng lực, còn lại n – 1 thành phần, Chọn thành phần a2 : có n – 1 năng lực, còn lại n – 2 thành phần, Chọn thành phần a2 : có n – k + 1 năng lực, còn lại n – k thành phần. Theo nguyên lí nhân, số tổng thể các chỉnh hợp không lặp chập k của nphần tử khác nhau là : A  n, k   n. ( n  1 ) … ( n  k  1 )  n ! ( n  k ) ! Ví dụ 1.7. Một cuộc khiêu vũ có 10 nam và 5 nữ. Hỏi có bao nhiêu cách chọn3 nam và 3 nữ để ghép thành 3 cặp. GiảiMỗi cách chọn 3 nam trong 10 nam là một chỉnh hợp không lặp chập 3 của 10 thành phần. Vậy có A ( 10,3 )  10 !  10  9  8  720 cách. ( 10  3 ) ! Mỗi cách chọn 3 nữ trong 5 nữ là một chỉnh hợp không lặp chập 3 của5 thành phần. Vậy có A ( 5,3 )  5 !  5  4  3  60 cách. ( 5  3 ) ! Theo nguyên tắc nhân, tổng số cách chọn 3 cặp là : A ( 10,3 ). A ( 5,3 )  720  60  43.200 cáchVí dụ 1.8. Với các chữ số 0,1, 2,3, 4,5,6 ta hoàn toàn có thể lập được bao nhiêu số gồm134 chữ số khác nhau và trong đó phải xuất hiện chữ số 5. GiảiGọi số có 4 chữ số là a 1 a 2 a 3 a 4N ếu a1  5 thì mỗi cách chọn 3 số còn lại là một chỉnh hợp không lặpchập 3 của 6 thành phần. Vậy có A ( 6,3 )  6 !  120 số. ( 6  3 ) ! Nếu a 2  5 thì mỗi cách chọn 3 số còn lại là một chỉnh hợp không lặpchập 3 của 6 thành phần hay A ( 6,3 ), nhưng loại trừ các số mà có a1  0. Các số có 4 chữ số mà có a1  0, a 2  5 là một chỉnh hợp không lặpchập 2 của 5 thành phần hay A ( 5,2 ). Vậy có A ( 6,3 )  A ( 5,2 )  120  20  100 số. Tương tự cho các trường hợp a 3  5, a 4  5. Vậy số các số thỏa mãn nhu cầu điều kiện kèm theo bài toán là120  3  100  420 số. 1.4.3. Hoán vịĐịnh nghĩa 1.4. Một hoán vị của n thành phần khác nhau là một cách sắp xếp cácphần tử đó. Định lí 1.3. Nếu gọi số tổng thể các hoán vị của n thành phần là P ( n ) thìP ( n )  n ! Chứng minhMột hoán vị của n thành phần hoàn toàn có thể xem là một trường hợp riêng củachỉnh hợp không lặp chập k của n thành phần với n = k. 14V ậy số hoán vị của n thành phần khác nhau là : P ( n )  n. ( n  1 ) … 2.1  n ! Ví dụ 1.9. Mười học viên cùng ngồi trên một hàng ghế, chơi trò đổi chỗ. Chorằng mỗi lần đổi chỗ mất hết 1 phút. Hỏi thời hạn họ đổi chỗ hết cho nhau làbao nhiêu ? GiảiMỗi lần đổi chỗ là một hoán vị của 10 thành phần. Vậy tổng số lần đổi chỗlàP ( 10 )  10 !  3.628.800 lần. Vậy thời hạn các học viên đổi chỗ cho nhau là 3.628.800 phút hay2. 520 giờ hay gần 7 năm. Ví dụ 1.10. Một hội nghị bàn tròn có phái đoàn các nước : Nước Ta 6 người, Lào 3 người, Campuchia 2 người, Đất nước xinh đẹp Thái Lan 3 người và Trung Quốc 4 người. Có bao nhiêu cách xếp chỗ ngồi cho các phái đoàn sao cho người cùng quốctịch thì ngồi cùng nhau. GiảiCó thể mời một phái đoàn nào đó ngồi vào chỗ trước, sau đó xếp bốnphái đoàn còn lại cùng ngồi vào bàn. Vậy có, 4 !  24 cách xếp các phái đoànngồi theo cùng vương quốc của mình. trong đó có6 ! cách xếp chỗ ngồi cho người Việt Nam3 ! cách xếp chỗ ngồi cho người Lào2 ! cách xếp chỗ ngồi cho người Campuchia153 ! cách xếp chỗ ngồi cho người Thái Lan4 ! cách xếp chỗ ngồi cho người Trung QuốcVậy có 24.6 ! 3 ! 2 ! 3 ! 4 !  29.859.840. 1.4.4. Tổ hợpĐịnh nghĩa 1.5. Một tổ hợp chập k của n thành phần khác nhau là một bộ khôngkể thứ tự gồm k thành phần khác nhau lấy từ n thành phần đã cho. Hay một tổhợp chập k của n thành phần khác nhau là một tập con có k thành phần lấy từ n phầntử đã cho. Định lí 1.4. Nếu gọi số tổ hợp chập k của n thành phần là C ( n, k ) thìC  n, k   n ! k ! ( n  k ) ! Chứng minhMột tổ hợp chập k của n thành phần khác nhau là một tập con có k phần tửtừ n thành phần đã cho. Do đó : A ( n ; k )  C ( n ; k ). k ! Suy ra C  n, k   n ! k ! ( n  k ) ! Ví dụ 1.11. Có bao nhiêu đường chéo trong đa giác lồi n cạnh. GiảiNối hai đỉnh không kề nhau của đa giác ta được đường chéo của đagiác. Nối hai đỉnh kề nhau ta được một cạnh của đa giác. 16M ỗi cách nối bất kỳ hai đỉnh của đa giác là một tổ hợp chập 2 của nphần tử. Vậy cóC ( n, 2 )  n ! n  ( n  1 ) 2 !  ( n  2 ) ! Vậy số đường chéo trong đa giác lồi n cạnh là : n  ( n  1 ) n  ( n  3 ) đường.  n  Ví dụ 1.12. Cho 10 câu hỏi trong đó có 4 câu lí thuyết và 6 câu bài tập. Ngườita cấu trúc đề thi từ các câu hỏi đó. Biết rằng mỗi đề thi gồm 3 câu, trong đónhất thiết phải có 1 câu lý thuyết và 1 câu bài tập. Hỏi có bao nhiêu khả năngcấu tạo đề thi ? GiảiTrường hợp 1 : Đề thi gồm 2 câu lý thuyết và 1 câu bài tậpMỗi cách chọn 2 câu lí thuyết là một tổ hợp chập 2 của 4 thành phần hayC ( 4,2 ) Mỗi cách chọn 1 câu bài tập là một tổ hợp chập 1 của 6 thành phần hayC ( 6,1 ) Theo nguyên tắc nhân, tổng số cách chọn là : C ( 4,2 ) C ( 6,1 )  36 đềTrường hợp 2 : Đề thi gồm 1 câu lí thuyết và 2 câu bài tậpMỗi cách chọn 1 câu lí thuyết là một tổ hợp chập 1 của 4 thành phần hayC ( 4,1 ) Mỗi cách chọn 2 câu bài tập là một tổ hợp chập 2 của 6 thành phần hayC ( 6,2 ) 17T heo nguyên tắc nhân, tổng số cách chọn là : C ( 4,1 ) C ( 6,2 )  60 đềMỗi cách cấu trúc đề thi trong hai trường hợp là khác nhau nên theonguyên lý cộng, tổng số đề thi được tạo ra là36  60  96 đề. 1.5. CÁC CẤU HÌNH TỔ HỢP NÂNG CAO1. 5.1. Hoán vị lặpĐịnh nghĩa 1.6. Hoán vị lặp là hoán vị trong đó mỗi thành phần được ấn định lạimột số lần lặp lại cho trướcĐịnh lí 1.5. Số hoán vị lặp của k thành phần khác nhau, trong đó thành phần thứ nhấtlặp n1 lần, thành phần thứ hai lặp n 2 lần, …, thành phần thứ k lặp lại n k lần làP ( n ; n 1, n 2, …, n k )  n ! n1 !. n 2 ! … n k ! trong đón  n1  n 2  …  n k. Chứng minhCách xếp chỗ cho n1 thành phần thứ nhất là : C ( n ; n1 ), còn lại n  n1 chỗ, Cách xếp chỗ cho n 2 thành phần thứ hai là : C ( n  n1 ; n2 ), còn lạin  n1  n 2 chỗ, Cách xếp chỗ cho n k thành phần thứ k là : còn lại n  n1  n 2  …  n k chỗ, C ( n  n1  n 2  …  n k  1 ; nk ), 18T heo nguyên tắc nhân, số tổng thể các hoán vị lặp của k thành phần khác nhaulàP ( n ; n1, n 2, …, n k )  C ( n ; n 1 ) C ( n  n1 ; n 2 ) … C ( n  n1  …  n k  1 ; n k ) n ! ( n  n 1 ) ( n  n1  …  n k  1 ) … n1 !. ( n  n 1 ) ! n 2 !. ( n  n1  n 2 ) ! n k !. 0 ! n ! n1 !. n 2 ! … n k ! Ví dụ 1.13. Có 10 chiếc điện thoại cảm ứng giống nhau, trong đó có 4 chiếc điện thoạimàu đỏ, 3 chiếc điện thoại cảm ứng màu trắng và 3 chiếc điện thoại cảm ứng màu xanh được lắpvào 12 phòng. Hãy đếm số giải pháp lắp các điện thoại cảm ứng. Giải10 chiếc điện thoại thông minh lắp vào 12 phòng, vậy có hai phòng không có điệnthoại. Do đó, khi lắp 10 chiếc điện thoại thông minh vào 10 phòng thì gồm có 4 loại : 4 chiếc điện thoại cảm ứng màu đỏ, 3 chiếc điện thoại cảm ứng màu trắng, 3 chiếc điện thoại cảm ứng màuxanh và 2 phòng không có điện thoại thông minh. Như vậy, mỗi giải pháp lắp điện thoạilà một hoán vị lặp của bốn thành phần, trong đóphần tử thứ nhất lặp lại 4 lầnphần tử thứ hai lặp lại 3 lầnphần tử thứ ba lặp lại 3 lầnphần tử thứ bốn lặp lại 2 lần. Vậy các giải pháp lắp điện thoại thông minh làP ( 12 ; 4,3,3,2 )  12 !  554.400 cách lắp. 4 ! 3 ! 3 ! 2 ! Ví dụ 1.14. Một lớp học có 20 sinh viên. Nhà trường chia các sinh viên trênvào 4 kí túc xá khác nhau, trong đó 3 sinh viên vào kí túc xá tiên phong, 5 sinh19viên vào kí túc xá thứ hai, 4 sinh viên vào kí túc xá thứ ba và các sinh viêncòn lại vào kí túc xá thứ tư. Có bao nhiêu giải pháp phân loại như vậy. Giải20 sinh viên chia vào 4 kí túc xá khác nhau, có 3 sinh viên vào kí túc xáđầu tiên, 5 sinh viên vào kí túc xá thứ hai, 4 sinh viên vào kí túc xá thứ ba và8 sinh viên còn lại vào kí túc xá thứ tư. Do đó mỗi cách chia là một hoán vịlặp của bốn thành phần, trong đóphần tử thứ nhất lặp lại 3 lầnphần tử thứ hai lặp lại 5 lầnphần tử thứ ba lặp lại 4 lầnphần tử thứ bốn lặp lại 8 lần. Vậy số cách chia làP ( 20 ; 3,5,4,8 )  20 !  3.491.888.400 cách. 3 ! 5 ! 4 ! 8 ! Hệ quả 1.1. Giả sử tập S có n thành phần, trong đó có n1 thành phần kiểu 1, n 2 phầntử kiểu 2, …, n k thành phần kiểu k. Khi đó số các hoán vị n thành phần của tập hợp SlàP ( n ; n 1, n 2, …, n k )  n ! n1 !. n 2 ! … n k ! 1.5.2. Tổ hợp lặpĐịnh nghĩa 1.7. Tổ hợp lặp chập k từ n thành phần khác nhau là một nhómkhông phân biệt thứ tự gồm k thành phần trích từ n thành phần đã cho, trong đó cácphần tử hoàn toàn có thể lặp lại. Định lí 1.6. Nếu X có n thành phần khác nhau và gọi CR ( n, k ) là số tổ hợp lặp20chập k từ n thành phần của X thìCR ( n, k )  C ( k  n  1, n  1 )  C ( k  n  1, k ) Chứng minhMỗi tổ hợp lặp chập k từ n thành phần hoàn toàn có thể màn biểu diễn bằng một dãy gồm ( n – 1 ) dấu gạch đứng và k ngôi sao 5 cánh. Trong đó k ngôi sao 5 cánh chỉ k thành phần đượcchọn và ( n – 1 ) dấu gạch đứng chỉ ngăn cách giữa các loại sách với nhau. * * * … | Như vậy, có k  ( n  1 )  n  k  1 chỗ trống để xếp k ngôi sao 5 cánh và ( n – 1 ) dấu gạch đứng. Do đó, một tổ hợp lặp chập k từ n thành phần là một cách xếp k ngôi saovào n  k  1 chỗ trống hay một cách xếp ( n – 1 ) dấu gạch đứng vào n  k  1 chỗ trống. Mỗi cách xếp k ngôi sao 5 cánh vào n  k  1 chỗ trống là một tổ hợp chập kcủa n  k  1 thành phần. Vậy có C ( k  n  1, k ) Mỗi cách xếp ( n – 1 ) dấu gạch đứng vào n  k  1 chỗ trống là một tổhợp chập ( n – 1 ) của n  k  1 thành phần. Vậy có C ( k  n  1, n  1 ) Tức là, CR ( n, k )  C ( k  n  1, n  1 )  C ( k  n  1, k ) Ví dụ 1.15. Trong két tiền có các loại 1 nghìn, 2 nghìn, 5 nghìn, 10 nghìn, 20 nghìn, 50 nghìn và 100 nghìn đồng, mỗi loại có tối thiểu 5 tờ. Hỏi có bao nhiêucách chọn 5 tờ giấy bạc. GiảiMỗi tờ giấy bạc cùng loại là như nhau và thứ tự lấy các tờ giấy bạc là

Source: https://mindovermetal.org
Category: Ứng dụng hay