Trần Quốc Chiến

Tổ hợp

Chương 1: Nhập môn tổ hợp
1.1. Sơ lược lịch sử
Có thể nói tư duy tổ hợp ra đời từ rất sớm. Vào thời nhà Chu Trung
quốc người ta đã biết đến những hình vuông thần bí. Thời cổ Hi-lạp, thế
kỷ thứ 4 trước Công nguyên, nhà triết học Kxenokrat đã biết cách tính
số các từ khác nhau lập từ bảng chữ cái cho trước. Nhà toán học Pitagor
và học trò đã tìm ra được nhiều số có tính chất đặc biệt. Chẳng hạn 36
không những là tổng 4 số chẵn và 4 số lẻ đầu tiên, mà còn là tổng lập
phương của 3 số tự nhiên đầu tiên
36 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 13 + 23 + 33
Từ định lý Pitagor người ta cũng đã tìm ra những số mà bình
phương của nó bằng tổng bình phương của 2 số khác. Các bài toán như
vậy đòi hỏi phải có nghệ thuật tổ hợp nhất định. Tuy nhiên có thể nói
rằng, lý thuyết tổ hợp được hình thành như một ngành toán học mới vào
thế kỷ 17 bằng một loạt công trình nghiên cứu của các nhà toán học xuất
sắc như Pascal, Fermat, Euler, Leibnitz,...
Các bài toán tổ hợp có đặc trưng bùng nổ tổ hợp với số cấu hình tổ
hợp khổng lồ. Việc giải chúng đòi hỏi một khối lượng tính toán khổng lồ
(có trường hợp mất hàng chục năm). Vì vậy trong thời gian dài, khi mà
các ngành toán học như Phép tính vi phân, Phép tính tích phân, phương
trình vi phân,.. phát triển như vũ bão, thì dường như nó nằm ngoài sự
phát triển và ứng dụng của toán học. Tình thế thay đổi từ khi xuất hiện
máy tính và sự phát triển của toán học hữu hạn. Nhiều vấn đề tổ hợp đã
được giải quyết trên máy tính. Từ chỗ chỉ nghiên cứu các trò chơi, tổ
hợp đã trở thành ngành toán học phát triển mạnh mẽ, có nhiều ứng dụng
trong các lĩnh vực toán học, tin học ...
Chúng ta sẽ tìm hiểu một số bài toán tổ hợp nổi tiếng trong lịch sử.

 Bài toán tháp Hà nội

Chương 1. Nhập môn tổ hợp

1-1


Trần Quốc Chiến

Tổ hợp

Bài toán này do Edouard Lucas đưa ra ở cuối thế kỷ 19 (Ông cũng
là người đưa ra dãy Fibonacci). Bài toán phát biểu như sau. Có 3 cọc,
cọc thứ nhất có n đĩa kích thước khác nhau xếp chồng nhau, đĩa nhỏ
nằm trên đĩa lớn. Hãy chuyển các đĩa từ cọc thứ nhất sang cọc thứ ba, sử
dụng cọc trung gian thứ hai, sao cho luôn đảm bảo đĩa nhỏ trên đĩa lớn.
Hãy đếm số lần di chuyển đĩa. Tìm phương án di chuyển đĩa tối ưu. Số
lần di chuyển là 2n  1. Khi n = 64, ta có số lần di chuyển là:
18 446 744 073 709 551 615

 Bài toán xếp n cặp vợ chồng
Bài toán này cũng do Lucas đưa ra năm 1891. Bài toán phát biểu
như sau. Có n cặp vợ chồng cần xếp vào bàn tròn sao cho không có cặp
nào ngồi gần nhau. Có bao nhiêu cách xếp như vậy ?
Bài toán này dẫn đến việc nghiên cứu một khái niệm quan trọng là
số phân bố và mãi đến năm 1934 mới có lời giải . Số cách xếp là
2.n!.Un
trong đó Un là số phân bố. Bảng sau cho thấy sự bùng nổ tổ hợp ghê
gớm của số phân bố


n=

4

5

6

Un =

2

13 80

7

8

9

10

11

579

4 738

43 387


439 792

4 890 741

 Bài toán đường đi quân ngựa trên bàn cờ
Cho bàn cờ vua với kích thước 8  8 = 64 ô. Tìm đường đi của quân
ngựa qua tất cả các ô, mỗi ô chỉ 1 lần, và quay về ô xuất phát. Người ta
chứng minh tổng quát được rằng:
Trên bàn cờ vuông có số cạnh chẵn lớn hơn hoặc bằng 6 bao giờ
cũng tồn tại đường đi.
Đường đi của Euler (1759) có tính chất: hiệu các ô đối xứng qua
tâm bàn cờ bằng 32.
Chương 1. Nhập môn tổ hợp

1-2


Trần Quốc Chiến

Tổ hợp

37 62 43 56 35 60 41 50
44 55 36 61 42 49 34 59
63 38 53 46 57 40 51 48
54 45 64 39 52 47 58 33
1

26 15 20 7


16 19 8

32 13 22

25 14 21 6

27 2

17 10 29 4

18 9

28 3

31

23 12

24 11 30 5

Đường đi của Beverle (1848) có tính chất : tổng các ô trên cột và
hàng bằng 260.

1

30 47 52 5

48 51 2

29 44 53 6


31 46 49 4
50 3

28 43 54

25 8

27

55 42

32 45 56 41 26 7

33 62 15 20 9

24 39 58

16 19 34 61 40 57 10 23
63 14 17 36 21 12 59 38
18 35 64 13 60 37 22 11

 Hình vuông la tinh
Hình vuông la tinh cấp n là hình vuông gồm các số 1, 2, ..., n1, n
thoả mãn tổng mỗi hàng và tổng mỗi cột đều bằng nhau và bằng
1 + 2 + ... + n =

n(n  1)
2


Hình vuông la tinh chuẩn cấp n là hình vuông la tinh cấp n có dòng
đầu và cột đầu là 1, 2, ..., n.
Bảng sau đây là hình vuông la tinh chuẩn cấp 7
Chương 1. Nhập môn tổ hợp

1-3


Trần Quốc Chiến

Tổ hợp

1

2

3

4

5

6

7

2

3


4

5

6

7

1

3

4

5

6

7

1

2

4

5

6


7

1

2

3

5

6

7

1

2

3

4

6

7

1

2


3

4

5

7

1

2

3

4

5

6

Công thức tính số hình vuông la tinh đến nay vẫn còn bỏ ngỏ. Tuy
nhiên ta có thể lập chương trình liệt kê tất cả hình vuông la tinh chuẩn.
Dưới đây là một số giá trị

n=

1

2


3

4

5

ln =

1

1

1

4

56

6

7

9 408 16 942 080

(ln là số hình vuông la tinh chuẩn cấp n).

 Hình lục giác thần bí
Năm 1910 Clifford Adams đưa ra bài toán hình lục giác thần bí sau:
Trên 19 ô lục giác hãy điền các số từ 1 đến 19 sao cho tổng theo sáu
hướng của lục giác bằng nhau (= 38).

Sau 47 năm trời kiên nhẫn cuối cùng ông ta đã tìm ra lời giải.
Nhưng do sơ ý đánh mất bản thảo ông đã tốn thêm 5 năm nữa để khôi
phục lời giải. Năm 1962 Adams công bố lời giải. Đây cũng là lời giải
duy nhất.

Chương 1. Nhập môn tổ hợp

1-4


Trần Quốc Chiến

Tổ hợp

15
14
9

13
8

6
11

10
4

5
1


18

12
2

7
17

16
19

3

Chương 1. Nhập môn tổ hợp

1-5


Trần Quốc Chiến

Tổ hợp

1.2. Bài toán tổ hợp
Qua các bài toán trên ta thấy bài toán tổ hợp rất đa dạng, liên quan
tới nhiều lĩnh vực khoa học và đời sống khác nhau.
Có thể nói một cách tổng quát rằng 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, thoả 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.
 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, phân bố các
phần tử của A1, ..., An, được mô tả bằng các quy 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, phân bố các phần tử của A1, ..., An thoả mãn các đ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.
 Ví dụ. Xét sự bố trí các quân cờ trên bàn cờ vua. Mỗi thế cờ có thể coi
là một cấu hình tổ hợp. Ở đây ta có thể định nghĩa
A là tập hợp các quân cờ trắng
B

là tập hợp các quân cờ đen

S

là sơ đồ sắp xếp các quân cờ trên bàn cờ

R

là hệ thống các điều kiện được xác định bằng luật cờ vua.

 Ví dụ. Bài toán tháp Hà nội
A là tập hợp n đĩa
S

là sơ đồ sắp xếp các đĩa trên 3 cọc

R1 là điều kiện mỗi lần chuyển 1 đĩa từ một cọc sang cọc khác
R2 là điều kiện đĩa nằm dưới lớn hơn đĩa nằm trên
Cấu hình tổ hợp là một cách sắp xếp các đĩa trên 3 cọc thỏa các điều
kiện R1 và R2.

 Ví dụ. Bài toán đường đi quân ngựa trên bàn cờ
A là tập hợp các ô trên bàn cờ, có thể biểu diễn như sau
Chương 1. Nhập môn tổ hợp

1-6


Trần Quốc Chiến

Tổ hợp

A = { [i, j]  i, j = 1, ..., 8 }
S

là sơ đồ sắp xếp tất cảc các ô của A thành 1 vòng khép kín

R

là điều kiện từ mỗi ô trên vòng có thể đi đến các ô kề theo quy

tắc đi của quân ngựa.
 Các dạng bài toán tổ hợp
Với các cấu hình tổ hợp ta thường gặp các dạng bài toán sau: 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. Bài toán tồn tại
Mục tiêu của bài toán tồn tại là chứng minh sự tồn tại hoặc không
tồn tại của cấu hình tổ hợp nào đó.
Có những bài toán loại này rất khó và việc cố gắng giải chúng đã
thúc đẩy sự phát triển nhiều hướng nghiên cứu toán học.
 Ví dụ. Cho n nguyên dương

A là tập hợp n  n điểm
A = { [i, j]  i, j = 1, ..., n }
S

là tập hợp 2n điểm trong A

R

là điều kiện không có 3 điểm trong S thẳng hàng

Với 2  n  15 cấu hình tổ hợp tồn tại. Nhưng bài toán chưa có lời
giải với n > 15.
2. Bài toán đếm
Nội dung bài toán đếm là trả lời câu hỏi “Có bao nhiêu cấu hình tổ
hợp thuộc dạng đang xét ?”. Phương pháp đếm cấu hình tổ hợp thường
dựa vào một số quy tắc, nguyên lý đếm và phân rã đưa về các cấu hình
tổ hợp đơn giản. Khi việc xác định chính xác số cấu hình tổ hợp gặp khó
khăn, có thể ước lượng cận trên và cận dưới của nó. Bài toán đếm được
áp dụng vào những công việc như tính xác suất hay tính độ phức tạp
thuật toán.
Chương 1. Nhập môn tổ hợp

1-7


Trần Quốc Chiến

Tổ hợp

 Ví dụ. Đếm số tập con của một tập hợp.

 Ví dụ. Đếm số nghiệm nguyên dương của phương trình
x + y + z = 10
3. Bài toán liệt kê
Các bài toán loại này nghiên cứu những thuật toán hiệu quả để xây
dựng tất cả các cấu hình tổ hợp đã cho. Nhiều vấn đề trong các lĩnh vực
khác nhau thường được đưa về bài toán liệt kê và kiểm tra xem các cấu
hình tổ hợp có thoả mãn tính chất cho trước hay không.
 Ví dụ. Liệt kê tất cả các hoán vị của n phần tử.
4. Bài toán tối ưu tổ hợp
Trong nhiều vấn đề, mỗi cấu hình tổ hợp được gán một giá trị bằng
số (chẳng hạn như hiệu quả sử dụng, hay chi phí thực hiện). Khi đó bài
toán tối ưu tổ hợp nghiên cứu những thuật toán tìm cấu hình tổ hợp có
giá trị tối ưu (lớn nhất hoặc nhỏ nhất).
 Ví dụ (Bài toán ba lô). Một nhà thám hiểm dùng một cái ba lô trọng
lượng không quá b để mang đồ vật. Có n đồ vật 1, 2, ..., n. Đồ vật thứ j
có trọng lượng aj và giá trị sử dụng là c j, j=1,2,...,n. Hỏi nhà thám hiểm
cần mang theo những đồ vật nào để tổng giá trị sử dụng là lớn nhất ?

Chương 1. Nhập môn tổ hợp

1-8