Bài toán đếm Nguyễn Thế Vinh-ĐHKH
46
tập hợp các cách bỏ thư và A
m
là tính chất lá thư thứ m bỏ đúng địa chỉ. Khi
đó theo công thức về nguyên lí bù trừ ta có:
N = n! − N
1
+ N
2
− + (−1)
n
N
n
,
trong đó N
m
(1 ≤ m ≤ n) là số tất cả các cách bỏ thư sao cho có m lá thư đúng
địa chỉ. Nhận xét rằng, N
m
là tổng theo mọi cách lấy m lá thư từ n lá, với mỗi
cách lấy m lá thư, có (n-m)! cách bỏ để m lá thư này đúng địa chỉ, ta nhận
được:
N
m
=
m
n
C (n - m)! =
n
k
!
!
và N = n!(1 −
1
1!
+
1
2!
− + (−1)
n
1
n!
),
trong đó
m
n
C =
)!(!
!
mnm
n
−
là tổ hợp chập m của tập n phần tử (số cách chọn m
đối tượng trong n đối tượng được cho). Từ đó xác suất cần tìm là: 1 −
1
1!
+
1
2!
− + (−1)
n
1
n!
. Một điều lí thú là xác suất này dần đến e
-1
(nghĩa là còn >
1
3
)
khi n khá lớn.
Số N trong bài toán này được gọi là số mất thứ tự và được ký hiệu là
D
n
. Dưới đây là một vài giá trị của D
n
, cho ta thấy D
n
tăng nhanh như thế nào
so với n:
n 2 3 4 5 6 7 8 9 10 11
D
n
1 2 9 44 265 1854 14833 133496 1334961 14684570
3.2. NGUYÊN LÍ DIRICHLET
3.2.1. Mở đầu
Giả sử có một đàn chim bồ câu bay vào chuồng. Nguyên lí chuồng
chim bồ câu phát biểu rằng: Nếu số chim nhiều hơn số ngăn chuồng thì ít
nhất trong một ngăn có nhiều hơn một con chim. Nguyên lí này dĩ nhiên là có
thể áp dụng cho các đối tượng không phải là chim bồ câu và chuồng chim.
Định lí 1: Nếu có k+1 (hoặc nhiều hơn) đồ vật được đặt vào trong k
hộp thì tồn tại một hộp có ít nhất hai đồ vật.
Bài toán đếm Nguyễn Thế Vinh-ĐHKH
47
Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn một
đồ vật. Khi đó tổng số vật được chứa trong các hộp nhiều nhất là bằng k. Điều
này trái giả thiết là có ít nhất k + 1 vật.
Nguyên lí này thường được gọi là nguyên lí Dirichlet, mang tên nhà
toán học người Đức ở thế kỷ 19. Ông thường xuyên sử dụng nguyên lí này
trong công việc của mình.
Ví dụ:1) Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai
người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật
khác nhau.
2) Trong kỳ thi học sinh giỏi, điểm bài thi được đánh giá bởi một số
nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất có bao nhiêu học sinh dự
thi để cho chắc chắn tìm được hai học sinh có kết quả thi như nhau?
Theo nguyên lí Dirichlet, số học sinh cần tìm là 102, vì ta có 101 kết
quả điểm thi khác nhau.
3) Trong số những người có mặt trên trái đất, phải tìm được hai người
có hàm răng giống nhau. Biết rằng số người trên hành tinh này không vượt
quá 4 tỉ.
Nếu xem mỗi hàm răng gồm 32 cái như là một xâu nhị phân có chiều
dài 32, trong đó răng còn ứng với bit 1 và răng mất ứng với bit 0, thì có tất cả
2
32
= 4.294.967.296 hàm răng khác nhau. Trong khi đó số người trên hành tinh
này là vượt quá 4 tỉ, nên theo nguyên lí Dirichlet ta có điều cần tìm.
3.2.2. Nguyên lí Dirichlet tổng quát
Định lí 2: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một
hộp chứa ít nhất N/k đồ vật.
(Ở đây, x là giá trị của hàm trần tại số thực x, đó là số nguyên nhỏ
nhất có giá trị lớn hơn hoặc bằng x. Khái niệm này đối ngẫu với [x] – giá trị
của hàm sàn hay hàm phần nguyên tại x – là số nguyên lớn nhất có giá trị nhỏ
hơn hoặc bằng x.)
Chứng minh:
Giả sử mọi hộp đều chứa ít hơn N/k vật. Khi đó tổng số đồ vật là
Bài toán đếm Nguyễn Thế Vinh-ĐHKH
48
≤ k (
N
k
− 1) < k
N
k
= N.
Điều này mâu thuẩn với giả thiết là có N đồ vật cần xếp.
Ví dụ: 1) Trong 100 người, có ít nhất 9 người sinh cùng một tháng.
Xếp những người sinh cùng tháng vào một nhóm. Có 12 tháng tất cả.
Vậy theo nguyên lí Dirichlet, tồn tại một nhóm có ít nhất 100/12= 9 người.
2) Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu
sinh viên để chắc chắn rằng có ít ra là 6 người cùng nhận học bổng như nhau.
Gọi N là số sinh viên, khi đó N/5 = 6 khi và chỉ khi 5 < N/5 ≤ 6 hay
25 < N ≤ 30. Vậy số N cần tìm là 26.
3) Số mã vùng cần thiết nhỏ nhất phải là bao nhiêu để đảm bảo 25 triệu
máy điện thoại trong nước có số điện thoại khác nhau, mỗi số có 9 chữ số (giả
sử số điện thoại có dạng 0XX - 8XXXXX với X nhận các giá trị từ 0 đến 9).
Có 10
7
= 10.000.000 số điện thoại khác nhau có dạng 0XX - 8XXXXX.
Vì vậy theo nguyên lí Dirichlet tổng quát, trong số 25 triệu máy điện thoại ít
nhất có 25.000.000/10.000.000 = 3 có cùng một số. Để đảm bảo mỗi máy có
một số cần có ít nhất 3 mã vùng.
3.2.3. Một số ứng dụng của nguyên lí Dirichlet
Trong nhiều ứng dụng thú vị của nguyên lí Dirichlet, khái niệm đồ vật
và hộp cần phải được lựa chọn một cách khôn khéo. Trong phần nay có một
số ví dụ như vậy.
Ví dụ: 1) Trong một phòng họp có n người, bao giờ cũng tìm được 2
người có số người quen trong số những người dự họp là như nhau.
Số người quen của mỗi người trong phòng họp nhận các giá trị từ 0 đến
n − 1. Rõ ràng trong phòng không thể đồng thời có người có số người quen là
0 (tức là không quen ai) và có người có số người quen là n − 1 (tức là quen tất
cả). Vì vậy theo số lượng người quen, ta chỉ có thể phân n người ra thành n −1
nhóm. Vậy theo nguyên lí Dirichlet tồn tai một nhóm có ít nhất 2 người, tức là
luôn tìm được ít nhất 2 người có số người quen là như nhau.
2) Trong một tháng gồm 30 ngày, một đội bóng chuyền thi đấu mỗi
ngày ít nhất 1 trận nhưng chơi không quá 45 trận. Chứng minh rằng tìm được
Bài toán đếm Nguyễn Thế Vinh-ĐHKH
49
một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho trong giai
đoạn đó đội chơi đúng 14 trận.
Gọi a
j
là số trận mà đội đã chơi từ ngày đầu tháng đến hết ngày j. Khi
đó
1 ≤ a
1
< a
2
< < a
30
< 45
15 ≤ a
1
+14
< a
2
+14 < < a
30
+14 < 59.
Sáu mươi số nguyên a
1
, a
2
, , a
30
, a
1
+ 14, a
2
+ 14, , a
30
+14 nằm giữa 1 và
59. Do đó theo nguyên lí Dirichlet có ít nhất 2 trong 60 số này bằng nhau. Vì
vậy tồn tại i và j sao cho ai
= aj
+ 14 (j < i). Điều này có nghĩa là từ ngày j + 1
đến hết ngày i đội đã chơi đúng 14 trận.
3) Chứng tỏ rằng trong n + 1 số nguyên dương không vượt quá 2n, tồn
tại ít nhất một số chia hết cho số khác.
Ta viết mỗi số nguyên a
1
, a
2
, , a
n+1
dưới dạng a
j
=
j
k
2 q
j
trong đó k
j
là
số nguyên không âm còn q
j
là số dương lẻ nhỏ hơn 2n. Vì chỉ có n số nguyên
dương lẻ nhỏ hơn 2n nên theo nguyên lí Dirichlet tồn tại i và j sao cho q
i
= q
j
= q. Khi đó a
i
=
i
k
2 q và aj =
j
k
2 q. Vì vậy, nếu k
i
≤ k
j
thì a
j
chia hết cho a
i
còn
trong trường hợp ngược lại ta có a
i
chia hết cho a
j
.
4) Trong một lưới ô vuông kích thức 5x5, người ta điền ngẫu nhiên vào
các ô một trong các giá trị -1, 0 hoặc 1, sau đó tính tổng tất cả các ô theo
hàng ; theo cột và theo hai đường chéo. Chứng minh rằng tồn tại ít nhất hai
tổng có giá trị bằng nhau.
Gọi các tổng lần lượt là S
1
, S
2
, S
12
, có tất cả 12 tổng. Ta nhận thấy rằng
các tổng này chỉ có thể nhận các giá trị là { -5, -4…0,…4, 5}. Có tất cả 11 giá
trị khác nhau từ đó suy ra điều cần chứng minh.
Ví dụ cuối cùng trình bày cách áp dụng nguyên lí Dirichlet vào lí thuyết
tổ hợp mà vẫn quen gọi là lí thuyết Ramsey, tên của nhà toán học người Anh.
Nói chung, lí thuyết Ramsey giải quyết những bài toán phân chia các tập con
của một tập các phần tử.
Bài toán đếm Nguyễn Thế Vinh-ĐHKH
50
5) Giả sử trong một nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là thù.
Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ
thù lẫn nhau.
Gọi A là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít
nhất ba người là bạn của A hoặc có ít nhất ba người là kẻ thù của A, điều này
suy ra từ nguyên lí Dirichlet tổng quát, vì 5/2 = 3. Trong trường hợp đầu ta
gọi B, C, D là bạn của A. nếu trong ba người này có hai người là bạn thì họ
cùng với A lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu
trong ba người B, C, D không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người
thù lẫn nhau. Tương tự có thể chứng minh trong trường hợp có ít nhất ba
người là kẻ thù của A.
3.3. CHỈNH HỢP 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à
một số bài toán đếm có chứa các phần tử giống nhau không phân biệt được.
Ví dụ đếm số cách khác nhau mà chữ cái của từ SUCCESS có thể được sắp
xếp lại. Trong mục này chúng ta sẽ tìm hiểu cách giải các bài toán đếm trong
đó có một số phần tử là không phân biệt được.
3.3.1. Chỉnh hợp có lặp.
Một cách sắp xếp có thứ tự k 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 k từ tập n phần tử. Đếm các chỉnh hợp
khi cho phép các phần tử lặp lại có thể thực hiện bằng cách dùng quy tắc nhân.
Ví dụ: Từ bảng chữ cái tiếng Anh có thể tạo tra được bao nhiêu xâu có
độ dài n?
Giải : Theo quy tắc nhân, vì có 26 chữ cái và vì mỗi chữ cái có thể
được dùng lại nên chúng ta có 26
n
xâu với độ dài n.
Định lí 1: Số các chỉnh hợp lặp chập k từ tập n phần tử bằng n
k
.
Chứng minh: Ta thấy có n cách chọn một phần tử từ tập có n phần tử
cho mỗi một trong k vị trí của chỉnh hợp khi cho phép các phần tử được lặp
lại. Theo quy tắc nhân có n
k
.chỉnh hợp lặp chập k của n phần tử.
Bài toán đếm Nguyễn Thế Vinh-ĐHKH
51
3.3.2. 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í 2: Số tổ hợp lặp chập k từ tập n phần tử bằng
k
kn
C
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. Chẳng hạn, tổ hợp lặp chập 6 của 4 phần
tử được biểu thị bởi:
* * | * | | * * *
mô tả tổ hợp chứa đúng 2 phần tử thứ nhất, 1 phần tử thứ hai, không có phần
tử thứ 3 và 3 phần tử thứ tư của tập hợp.
Mỗi dãy n − 1 thanh và k ngôi sao ứng với một xâu nhị phân độ dài n +
k − 1 với k số 1. Do đó số các dãy n − 1 thanh đứng và k ngôi sao chính là số
tổ hợp chập k từ tập n + k − 1 phần tử. Đó là điều cần chứng minh.
Ví dụ: 1) Có bao nhiêu cách chọn 5 tờ giấy bạc từ một két đựng tiền
gồm những tờ 1000đ, 2000đ, 5000đ, 10.000đ, 20.000đ, 50.000đ, 100.000đ.
Giả sử thứ tự mà các tờ tiền được chọn là không quan trọng, các tờ tiền cùng
loại là không phân biệt và mỗi loại có ít nhất 5 tờ.
Vì ta không kể tới thứ tự chọn tờ tiền và vì ta chọn đúng 5 lần, mỗi lần
lấy một từ 1 trong 7 loại tiền nên mỗi cách chọn 5 tờ giấy bạc này chính là
một tổ hợp lặp chập 5 từ 7 phần tử. Do đó số cần tìm là
5
157 −+
C = 462.
2) Phương trình x
1
+ x
2
+ x
3
= 15 có bao nhiêu nghiệm nguyên không
âm?
Chúng ta nhận thấy mỗi nghiệm của phương trình ứng với một cách
chọn 15 phần tử từ một tập có 3 loại, sao cho có x
1
phần tử loại 1, x
2
phần tử
loại 2 và x
3
phần tử loại 3 được chọn. Vì vậy số nghiệm bằng số tổ hợp lặp
chập 15 từ tập có 3 phần tử và bằng
15
1153 −+
C = 136.
Bài toán đếm Nguyễn Thế Vinh-ĐHKH
52
3.3.3. Hoán vị của tập hợp có các phần tử giống nhau.
Trong bài toá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.
Ví dụ: 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
phải là số hoá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. Để xác định số xâu khác nhau có thể tạo ra được ta nhận thấy có
C(7,3) cách chọn 3 chỗ cho 3 chữ S, còn lại 4 chỗ trống. Có C(4,2) cách chọn
2 chỗ cho 2 chữ C, còn lại 2 chỗ trống. Có thể đặt chữ U bằng C(2,1) cách và
C(1,1) cách đặt chữ E vào xâu. Theo nguyên lí nhân, số các xâu khác nhau có
thể tạo được là:
3
7
C .
2
4
C .
1
2
C .
1
1
C =
7 4 2 1
3 4 2 2 1 1 1 0
! ! ! !
!. !. !. !. !. !. !. !
=
7
3 2 1 1
!
!. !. !. !
= 420.
Định lí 3: Số hoán vị khác nhau của n phần tử trong đó có n
1
phần tử
như nhau thuộc loại một, n
2
phần tử như nhau thuộc loại hai, , và n
k
phần tử
như nhau thuộc loại k, bằng
!! !.
!
21 k
nnn
n
.
Chứng minh: Để xác định số hoán vị trước tiên chúng ta nhận thấy có
1
n
n
C cách giữ n
1
chỗ cho n
1
phần tử loại 1, còn lại n - n
1
chỗ trống. Sau đó có
2
1
n
nn
C
−
cách đặt n
2
phần tử loại 2 vào hoán vị, còn lại n - n
1
- n
2
chỗ trống. Tiếp
tục đặt các phần tử loại 3, loại 4, , loại k - 1vào chỗ trống trong hoán vị. Cuối
cùng có
k
k
n
nnn
C
11
−
−−−
cách đặt n
k
phần tử loại k vào hoán vị. Theo quy tắc nhân
tất cả các hoán vị có thể là:
1
n
n
C .
2
1
n
nn
C
−
k
k
n
nnn
C
11
−
−−−
=
!! !.
!
21 k
nnn
n
.
3.3.4. Sự phân bố các đồ vật vào trong hộp.
Ví dụ: Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong
4 người chơi từ một cỗ bài chuẩn 52 quân?
Bài toán đếm Nguyễn Thế Vinh-ĐHKH
53
Người đầu tiên có thể nhận được 5 quân bài bằng
5
52
C cách. Người thứ
hai có thể được chia 5 quân bài bằng
5
47
C cách, vì chỉ còn 47 quân bài. Người
thứ ba có thể nhận được 5 quân bài bằng
5
42
C cách. Cuối cùng, người thứ tư
nhận được 5 quân bài bằng
5
37
C cách. Vì vậy, theo nguyên lí nhân tổng cộng
có
5
52
C .
5
47
C .
5
42
C .
5
37
C =
52!
5 5 5 5 32!!. !. !. !.
cách chia cho 4 người mỗi người một xấp 5 quân bài.
Ví dụ trên là một bài toán điển hình về việc phân bố các đồ vật khác
nhau vào các hộp khác nhau. Các đồ vật là 52 quân bài, còn 4 hộp là 4 người
chơi và số còn lại để trên bàn. Số cách sắp xếp các đồ vật vào trong hộp được
cho bởi mệnh đề sau
Định lí 4: Số cách phân phối n đồ vật khác nhau vào trong k hộp khác
nhau sao cho có n
i
vật được đặt vào trong hộp thứ i, với i = 1, 2, , k bằng
!! !.
!
21 k
nnn
n
.
Chứng minh: Chúng ta nhận thấy rằng với hộp thứ nhất có n
1
vật có thể
nhận được
1
n
n
C cách ; hộp thứ hai có n
2
vật có thể nhận được
2
1
n
nn
C
−
. Tiếp tục
đặt vào hộp thứ k có
k
k
n
nnn
C
11
−
−−−
cách. Theo quy tắc nhân số cách phân phối n
vật khác nhau vào k hộp khác nhau sao cho có n
i
vật được đặt vào hộp thứ i sẽ
là:
1
n
n
C .
2
1
n
nn
C
−
k
k
n
nnn
C
11
−
−−−
=
!! !.
!
21 k
nnn
n
.
3.4. SINH CÁC HOÁN VỊ VÀ TỔ HỢP
3.4.1. Sinh các hoán vị
Có nhiều thuật toán đã được phát triển để sinh ra n! hoán vị của tập
{1,2, ,n}. Ta sẽ mô tả một trong các phương pháp đó, phương pháp liệt kê
các hoán vị của tập {1,2, ,n} theo thứ tự từ điển. Khi đó, hoán vị a
1
a
2
a
n
Bài toán đếm Nguyễn Thế Vinh-ĐHKH
54
được gọi là đi trước hoán vị b
1
b
2
b
n
nếu tồn tại k (1 ≤ k ≤ n), a
1
= b
1
, a
2
=
b
2
, , a
k-1
= b
k-1
và a
k
< b
k
.
Thuật toán sinh các hoán vị của tập {1,2, ,n} dựa trên thuật toán xây
dựng hoán vị liền sau. Hoán vị nhỏ nhất là {1,2, n} và hoán vị lớn nhất là {n,
n-1, 2,1} theo thứ tự từ điển.
Thuật toán sinh hoán vị liền sau :
Bước 1: hoán vị ban đầu {a
1
a
2
a
n
};
Bước 2: đi từ phải sang trái tìm a
i
đầu tiên thỏa mãn điều kiện a
i
<a
i+1
.
Nếu không tìm được thuật toán kết thúc ;
Bước 3: tìm a
j
nhỏ nhất trong đoạn từ i+1 đến n thỏa mãn điều kiện
a
j
>a
i
;
Bước 4: đổi chỗ a
j
cho a
i
;
Bước 5: đảo ngược đoạn từ i+1 đến n.
Ví dụ: Tìm hoán vị liền sau theo thứ tự từ điển của hoán vị 4736521.
Cặp số nguyên đầu tiên tính từ phải qua trái có số trước nhỏ hơn số sau
là a
3
= 3 và a
4
= 6. Số nhỏ nhất trong các số bên phải của số 3 mà lại lớn hơn 3
là số 5. Đặt số 5 vào vị trí thứ 3. Sau đó đặt các số 3, 6, 1, 2 theo thứ tự tăng
dần vào bốn vị trí còn lại. Hoán vị liền sau hoán vị đã cho là 4751236.
Procedure Hoán vị liền sau (a
1
, a
2
, , a
n
) ;
Begin
i := n − 1;
while (a
i
> a
i+1
) and (i>0) do
i := i − 1;
if (i=0) then exit;
j := n;
while (a
i
> a
j
) do
j := j -1;
tg:=a
i
; a
i
:=a
j
; a
j
:=tg;
d := n; c := i + 1;
while (d<c) do
begin
Bài toán đếm Nguyễn Thế Vinh-ĐHKH
55
tg:=a
d
; a
d
:=a
c
; a
c
:=tg;
d := d + 1 ; c := c-1;
end;
End;
3.4.2. Sinh các tổ hợp
Làm thế nào để tạo ra tất cả các tổ hợp chập k của một tập hữu hạn có n
phần tử? (n>=k). Vì tổ hợp chính là một tập con, nên ta có thể dùng phép
tương ứng 1-1 giữa các tập con của {a
1
,a
2
, ,a
n
} và xâu nhị phân độ dài n.
Ta thấy một xâu nhị phân độ dài n cũng là khai triển nhị phân của một
số nguyên nằm giữa 0 và 2
n
− 1. Khi đó 2
n
xâu nhị phân có thể liệt kê theo thứ
tự tăng dần của số nguyên trong biểu diễn nhị phân của chúng. Chúng ta sẽ bắt
đầu từ xâu nhị phân nhỏ nhất 00 00 (n số 0). Tại mỗi bước để tìm xâu liền
sau của nó, kết thúc sẽ là xâu nhị phân lớn nhất 11…11 (n số 1)
Thuật toán tìm xâu nhị phân liền sau:
Bước 1: đi từ phải sang trái tìm phần tử 0 đầu tiên (giả sử tại vị trí i).
Nếu không tìm được thuật toán kết thúc;
Bước 2: thay giá trị tại vị trí i bằng 1; trong đoạn từ i+1 đến n thay các
giá trị bằng 0.
Ví dụ: 01001111 xâu liền sau là 01010000
Ta thấy với độ dài n sẽ có 2
n
xâu nhị phân và đây cũng chính là số tập
con của tập có n phần tử. Vận dụng thuật toán trên chúng ta có thể đưa ra tất
cả các tập con của tập n phần tử, nếu coi tại vị trí thứ i bằng 1 thì phần tử a
i
sẽ
xuất hiện trong tập con và ngược lại nếu vị trí thứ i bằng 0.
Thuật toán tìm tổ hợp chập k từ n phần tử:
Mỗi tổ hợp chập k của n phần tử có thể biểu diễn bằng một xâu tăng.
Khi đó có thể liệt kê các tổ hợp theo thứ tự từ điển, bắt đầu từ tổ hợp nhỏ nhất
{1,2,…,k}. Ví dụ với n=4; k=3 ta có các tổ hợp chập 3 của 4 theo thứ tự từ
điển sẽ là: {1,2,3}; {1,2,4}; {1,3,4};{2,3,4}.
Ta dễ dàng nhận thấy giá trị cực đại của phần tử a
i
là (n − k + i). Từ đó
thuật toán xây dựng tổ hợp liền sau tổ hợp a
1
a
2
a
k
như sau:
Bước 1: hoán vị ban đầu {a
1
a
2
a
k
};
Không có nhận xét nào:
Đăng nhận xét