Giáo trình Toán rời rạc - Chương II: Bài toán đếm

CHƯƠNG II

BÀI TOÁN ĐẾM

Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu

sự phân bố các phần tử vào các tập hợp. Thông thường các phần tử này là hữu hạn và

việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo yêu cầu

của bài toán cần nghiên cứu. Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp. Chủ

đề này đã được nghiên cứu từ thế kỹ 17, khi những câu hỏi về tổ hợp được nêu ra trong

những công trình nghiên cứu các trò chơi may rủi. Liệt kê, đếm các đối tượng có những

tính chất nào đó là một phần quan trọng của lý thuyết tổ hợp. Chúng ta cần phải đếm các

đối tượng để giải nhiều bài toán khác nhau. Hơn nữa các kỹ thuật đếm được dùng rất

nhiều khi tính xác suất của các biến cố.

2.1. CƠ SỞ CỦA PHÉP ĐẾM.

2.1.1. Những nguyên lý đếm cơ bản:

1) Quy tắc cộng: Giả sử có k công việc T₁, T₂, ..., T_k. Các việc này có thể làm tương

ứng bằng n₁, n₂, ..., n_kcá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 k việc đó là n₁+n₂+ ... + n_k.

Thí dụ 1: 1) 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 và 19 bài. Vì vậy, theo quy tắc cộng có 23 + 15 + 19 = 57

cách chọn bài thực hành.

2) Giá trị của biến m bằng bao nhiêu sau khi đoạn chương trình sau được thực hiện?

m := 0

for i₁:= 1 to n₁

m := m+1

for i₂:=1 to n₂

m := m+1

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

for i_k:= 1 to n_k

m := m+1

Giá trị khởi tạo của m bằng 0. Khối lệnh này gồm k vòng lặp khác nhau. Sau mỗi

bước lặp của từng vòng lặp giá trị của k được tăng lên một đơn vị. Gọi T_ilà việc thi

hành vòng lặp thứ i. Có thể làm T_ibằng n_icách vì vòng lặp thứ i có n_ibước lặp. Do các

vòng lặp không thể thực hiện đồng thời nên theo quy tắc cộng, giá trị cuối cùng của m

bằng số cách thực hiện một trong số các nhiệm vụ T_i, tức là m = n₁+n₂+ ... + n_k.

Quy tắc cộng có thể phát biểu dưới dạng của ngôn ngữ tập hợp như sau: Nếu A₁,

A₂, ..., A_klà các tập hợp đôi một rời nhau, khi đó số phần tử của hợp các tập hợp này

bằng tổng số các phần tử của các tập thành phần. Giả sử T_ilà việc chọn một phần tử từ

22

tập A_ivới i=1,2, ..., k. Có |A_i| cách làm T_ivà không có hai việc nào có thể được làm

cùng một lúc. Số cách chọn một phần tử của hợp các tập hợp này, một mặt bằng số phần

tử của nó, mặt khác theo quy tắc cộng nó bằng |A₁|+|A₂|+ ... +|A_k|. Do đó ta có:

|A₁ A₂... A_k| = |A₁| + |A₂| + ... + |A_k|.

2) Quy tắc nhân: Giả sử một nhiệm vụ nào đó được tách ra thành k việc T₁, T₂, ..., T_k.

Nếu việc T_icó thể làm bằng n_icách sau khi các việc T₁, T₂, ... T_i-1đã được làm, khi đó

có n₁.n₂....n_kcách thi hành nhiệm vụ đã cho.

Thí dụ 2: 1) 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 một trong 100 số nguyên dương. Quy tắc nhân chỉ ra rằng có 26.100=2600

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ế.

2) Có bao nhiêu xâu nhị phân có độ dài n.

Mỗi một trong n bit của xâu nhị phân có thể chọn bằng hai cách vì mỗi bit hoặc

bằng 0 hoặc bằng 1. Bởi vậy theo quy tắc nhân có tổng cộng 2ⁿxâu nhị phân khác nhau

có độ dài bằng n.

3) Có thể tạo được bao nhiêu ánh xạ từ tập A có m phần tử vào tập B có n phần tử?

Theo định nghĩa, một ánh xạ xác định trên A có giá trị trên B là một phép tương

ứng mỗi phần tử của A với một phần tử nào đó của B. Rõ ràng sau khi đã chọn được ảnh

của i - 1 phần tử đầu, để chọn ảnh của phần tử thứ i của A ta có n cách. Vì vậy theo quy

tắc nhân, ta có n.n...n=n^mánh xạ xác định trên A nhận giá trị trên B.

4) Có bao nhiêu đơn ánh xác định trên tập A có m phần tử và nhận giá trị trên tập B có n

phần tử?

Nếu m > n thì với mọi ánh xạ, ít nhất có hai phần tử của A có cùng một ảnh, điều

đó có nghĩa là không có đơn ánh từ A đến B. Bây giờ giả sử m  n và gọi các phần tử

của A là a₁,a₂,...,a_m. Rõ ràng có n cách chọn ảnh cho phần tử a₁. Vì ánh xạ là đơn ánh

nên ảnh của phần tử a₂phải khác ảnh của a₁nên chỉ có n - 1 cách chọn ảnh cho phần tử

a₂. Nói chung, để chọn ảnh của a_kta có n - k + 1 cách. Theo quy tắc nhân, ta có

n!

n(n  1)(n  2)...(n  m + 1) =

(n  m)!

đơn ánh từ tập A đến tập B.

5) Giá trị của biến k bằng bao nhiêu sau khi chương trình sau được thực hiện?

m := 0

for i₁:= 1 to n₁

for i₂:= 1 to n₂

23

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

for i_k:= 1 to n_k

k := k+1

Giá trị khởi tạo của k bằng 0. Ta có k vòng lặp được lồng nhau. Gọi T_ilà việc thi

hành vòng lặp thứ i. Khi đó số lần đi qua vòng lặp bằng số cách làm các việc T₁, T₂, ...,

T_k. Số cách thực hiện việc T_jlà n_j(j=1, 2,..., k), vì vòng lặp thứ j được duyệt với mỗi giá

trị nguyên i_jnằm giữa 1 và n_j. Theo quy tắc nhân vòng lặp lồng nhau này được duyệt

qua n₁.n₂....n_klần. Vì vậy giá trị cuối cùng của k là n₁.n₂....n_k.

Nguyên lý nhân thường được phát biểu bằng ngôn ngữ tập hợp như sau. Nếu A₁,

A₂,..., A_klà các tập hữu hạn, khi đó số phần tử của tích Descartes của các tập này bằng

tích của số các phần tử của mọi tập thành phần. Ta biết rằng việc chọn một phần tử của

tích Descartes A₁x A₂x...x A_kđược tiến hành bằng cách chọn lần lượt một phần tử của

A₁, một phần tử của A₂, ..., một phần tử của A_k. Theo quy tắc nhân ta có:

|A₁x A₂x ... x A_k| = |A₁|.|A₂|...|A_k|.

2.1.2. Nguyên lý bù trừ:

Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để

tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm

vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả

hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. Cho A₁, A₂là

hai tập hữu hạn, khi đó

|A₁ A₂| = |A₁| + |A₂|  |A₁ A₂|.

Từ đó với ba tập hợp hữu hạn A₁, A₂, A₃, ta có:

|A₁ A₂ A₃| = |A₁| + |A₂| + |A₃|  |A₁ A₂|  |A₂ A₃|  |A₃ A₁| + |A₁ A₂ A₃|,

và bằng quy nạp, với k tập hữu hạn A₁, A₂, ..., A_kta có:

| A₁ A₂ ...  A_k| = N₁ N₂+ N₃ ... + (1)^k-1N_k,

trong đó N_m(1  m  k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho,

nghĩa là

N_m=

| A  A  ...  A |

i₂i_m



i₁

1i₁i₂...i_mk

Bây giờ ta đồng nhất tập A_m(1  m  k) với tính chất A_mcho trên tập vũ trụ hữu

hạn U nào đó và đếm xem có bao nhiêu phần tử của U sao cho không thỏa mãn bất kỳ

một tính chất A_mnào. Gọi

= N  | A₁ A₂ ...  A_k| = N  N₁+ N₂ ... + (1)^kN_k,

trong đó N_mlà tổng các phần tử của U thỏa mãn m tính chất lấy từ k tính chất đã cho.

N là số cần đếm, N là số phần tử của U. Ta có:

N

Công thức này được gọi là nguyên lý bù trừ. Nó cho phép tính

trường hợp các số này dễ tính toán hơn.

N qua các N_mtrong

24

Thí dụ 3: Có n lá thư và n phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các

phong bì. Hỏi xác suất để xảy ra không một lá thư nào đúng địa chỉ.

Mỗi phong bì có n cách bỏ thư vào, nên có tất cả n! cách bỏ thư. Vấn đề còn lại

là đếm số cách bỏ thư sao cho không lá thư nào đúng địa chỉ. Gọi U là tập hợp các cách

bỏ thư và A_mlà 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₁+ N₂ ... + (1)ⁿ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_mlà 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!

1

 ... + (1)ⁿ),

n!

N_m= C_n^m(n - m)! =

và

N

= n!(1 

+

k!

1!

2!

n!

trong đó C_n^m

=

là tổ hợp chập m của tập n phần tử (số cách chọn m đối

m!(n  m)!

1

tượng trong n đối tượng được cho). Từ đó xác suất cần tìm là: 1 

+

 ... + (1)ⁿ

1!

2!

1

. Một điều lý thú là xác suất này dần đến e^-¹(nghĩa là còn > ) khi n khá lớn.

n!

3

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_ntăng nhanh như thế nào so với n:

n

2

1

3

2

4

9

5

6

7

8

9

10

11

D_n

44 265 1854 14833 133496 1334961 14684570

2.2. NGUYÊN LÝ DIRICHLET.

2.2.1. Mở đầu:

Giả sử có một đàn chim bồ câu bay vào chuồ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.

Mệnh đề (Nguyên lý): 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.

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.

Thí dụ 4: 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.

25

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. 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³²=

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á 5 tỉ, nên theo nguyên lý Dirichlet ta có điều cần tìm.

2.2.2. Nguyên lý Dirichlet tổng quát:

Mệnh đề: 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à

N

 k (] [  1) < k

= N.

k

Điều này mâu thuẩn với giả thiết là có N đồ vật cần xếp.

Thí dụ 5: 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⁷= 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.

2.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ó vài thí dụ như vậy.

26

Thí dụ 6: 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 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_jlà số trận mà đội đã chơi từ ngày đầu tháng đến hết ngày j. Khi đó

1  a₁< a₂< ... < a₃₀< 45

15  a₁+14 < a₂+14 < ... < a₃₀+14 < 59.

Sáu mươi số nguyên a₁, a₂, ..., a₃₀, a₁+ 14, a₂+ 14, ..., a₃₀+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₁, a₂,..., a_n+1dưới dạng a_j= 2^k^jq_jtrong đó k_jlà số nguyên

không âm còn q_jlà 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= 2^kⁱq và aj =

2^k^jq. Vì vậy, nếu k_i k_jthì a_jchia hết cho a_icòn trong trường hợp ngược lại ta có a_i

chia hết cho a_j.

Thí 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ử.

Thí dụ 7. 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.

27

2.3. CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG.

2.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ử. Nếu A là tập gồm n phần tử đó thì mỗi

chỉnh hợp như thế là một phần tử của tập A^k. Ngoài ra, mỗi chỉnh hợp lặp chập k từ tập

n phần tử là một hàm từ tập k phần tử vào tập n phần tử. Vì vậy số chỉnh hợp lặp chập k

từ tập n phần tử là n^k.

2.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.

Mệnh đề 1: Số tổ hợp lặp chập k từ tập n phần tử bằng C_n^k_k1

.

Chứng minh. Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một dãy n1

thanh đứng và k ngôi sao. Ta dùng n  1 thanh đứng để phân cách các ngăn. Ngăn thứ i

chứa thêm một ngôi sao mỗi lần khi phần tử thứ i của tập xuất hiện trong tổ hợp. 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.

Thi dụ 8: 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à C₇⁵_51= 462.

2) Phương trình x₁+ x₂+ x₃= 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₁phần tử loại 1, x₂phần tử loại 2 và x₃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à

15

3151

bằng C

= 136.

2.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. Ta xét thí dụ sau.

28

Thí dụ 9: 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à:

7!4!2!1!

7!

C₇³

.

C₄²

.

C₂¹.C₁¹=

=

= 420.

3!.2!.1!.1!

3!.4!.2!.2!.1!.1!.1!.0!

Mệnh đề 2: Số hoán vị của n phần tử trong đó có n₁phần tử như nhau thuộc loại 1, n₂

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

n!

.

n₁!.n₂!....n_k!

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

1

chỗ cho n₁phần tử loại 1, còn lại n - n₁chỗ trống. Sau đó có C_nⁿ_²_ncách đặt n₂phần tử

1

loại 2 vào hoán vị, còn lại n - n₁- n₂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ó C_nⁿ_^k_{n ...n}cách đặt n_kphần tử loại

1

k1

k vào hoán vị. Theo quy tắc nhân tất cả các hoán vị có thể là:

n!

C_nⁿ

.

C_nⁿ_²_n....C_nⁿ_^k_{n ...n}

=

.

1

k1

n₁!.n₂!....n_k!

2.3.4. Sự phân bố các đồ vật vào trong hộp.

Thí dụ 10: 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?

Người đầu tiên có thể nhận được 5 quân bài bằng C₅⁵₂cách. Người thứ hai có thể

được chia 5 quân bài bằng 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 C₄⁵₂cách. Cuối cùng, người thứ tư nhận được 5 quân bài bằng

C₃⁵₇cách. Vì vậy, theo nguyên lý nhân tổng cộng có

52!

C₅⁵₂C₄⁵₇C₄⁵₂C₃⁵₇

. . . =

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.

Thí 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

Mệnh đề 3: Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau sao cho

có n_ivật được đặt vào trong hộp thứ i, với i = 1, 2, ..., k bằng

29

n!

.

n₁!.n₂!....n_k!.(n  n₁...  n_k)!

2.4. SINH CÁC HOÁN VỊ VÀ TỔ HỢP.

2.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₁a₂...a_nđược gọi là đi trước hoán vị

b₁b₂...b_nnếu tồn tại k (1  k  n), a₁= b₁, a₂= b₂,..., 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 thủ tục xây dựng hoán vị

kế tiếp, theo thứ tự từ điển, từ hoán vị cho trước a₁a₂...a_n. Đầu tiên nếu a_{n 1}< a_nthì rõ

-

ràng đổi chỗ a_{n 1}và a_ncho nhau thì sẽ nhận được hoán vị mới đi liền sau hoán vị đã cho.

-

Nếu tồn tại các số nguyên a_jvà a_j+1sao cho a_j< a_j+1và a_j+1> a_j+2> ... > a_n, tức là tìm cặp

số nguyên liền kề đầu tiên tính từ bên phải sang bên trái của hoán vị mà số đầu nhỏ hơn

số sau. Sau đó, để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất

trong các số lớn hơn a_jcủa tập a_j+1, a_j+2, ..., a_n, rồi liệt kê theo thứ tự tăng dần của các số

còn lại của a_j, a_j+1, a_j+2, ..., a_nvào các vị trí j+1, ..., n. Dễ thấy không có hoán vị nào đi

sau hoán vị xuất phát và đi trước hoán vị vừa tạo ra.

Thí dụ 11: 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

và a₄= 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₁, a₂, ..., an) (hoán vị của {1,2,...,n} khác (n, n1, ..., 2, 1))

j := n  1

while a_j> a_j+1

j := j  1 {j là chỉ số lớn nhất mà a_j< a_j+1}

k := n

while a_j> a_k

k := k - 1 {a_klà số nguyên nhỏ nhất trong các số lớn hơn a_jvà bên phải a_j}

đổi chỗ (a_j, a_k)

r := n

s := j + 1

while r > s

đổi chỗ (a_r, a_s)

r := r - 1 ; s := s + 1

{Điều này sẽ xếp phần đuôi của hoán vị ở sau vị trí thứ j theo thứ tự tăng dần.}

30

2.4.2. Sinh các tổ hợp:

Làm thế nào để tạo ra tất cả các tổ hợp các phần tử của một tập hữu hạn? 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₁,a₂,...,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ⁿ 1. Khi đó 2ⁿ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). Mỗi bước để tìm xâu liền sau ta tìm vị trí đầu tiên tính từ phải qua

trái mà ở đó là số 0, sau đó thay tất cả số 1 ở bên phải số này bằng 0 và đặt số 1 vào

chính vị trí này.

procedure Xâu nhị phân liền sau (b_n-1b_n-2...b₁b₀): xâu nhị phân khác (11...11)

i := 0

while b_i= 1

begin

b_i:= 0

i := i + 1

end

b_i:= 1

Tiếp theo chúng ta sẽ trình bày thuật toán tạo các tổ hợp chập k từ n phần tử

{1,2,...,n}. Mỗi tổ hợp chập k 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. Có thể xây dựng tổ hợp liền sau tổ hợp a₁a₂...a_kbằng cách

sau. Trước hết, tìm phần tử đầu tiên a_itrong dãy đã cho kể từ phải qua trái sao cho a_i n

 k + i. Sau đó thay a_ibằng a_i+ 1 và a_jbằng a_i+ j  i + 1 với j = i + 1, i + 2, ..., k.

Thí dụ 12: Tìm tổ hợp chập 4 từ tập {1, 2, 3, 4, 5, 6} đi liền sau tổ hợp {1, 2, 5, 6}.

Ta thấy từ phải qua trái a₂= 2 là số hạng đầu tiên của tổ hợp đã cho thỏa mãn

điều kiện a_i 6  4 + i. Để nhận được tổ hợp tiếp sau ta tăng a_ilên một đơn vị, tức a₂=

3, sau đó đặt a₃= 3 + 1 = 4 và a₄= 3 + 2 = 5. Vậy tổ hợp liền sau tổ hợp đã cho là

{1,3,4,5}. Thủ tục này được cho dưới dạng thuật toán như sau.

procedure Tổ hợp liền sau ({a₁, a₂, ..., a_k}: tập con thực sự của tập {1, 2, ..., n} không

bằng {n  k + 1, ..., n} với a₁< a₂< ... < a_k)

i := k

while a_i= n  k + i

i := i  1

a_i:= a_i+ 1

for j := i + 1 to k

a_j:= a_i+ j  i

31

2.5. HỆ THỨC TRUY HỒI.

2.5.1. Khái niệm mở đầu và mô hình hóa bằng hệ thức truy hồi:

Đôi khi ta rất khó định nghĩa một đối tượng một cách tường minh. Nhưng có thể

dễ dàng định nghĩa đối tượng này qua chính nó. Kỹ thuật này được gọi là đệ quy. Định

nghĩa đệ quy của một dãy số định rõ giá trị của một hay nhiều hơn các số hạng đầu tiên

và quy tắc xác định các số hạng tiếp theo từ các số hạng đi trước. Định nghĩa đệ quy có

thể dùng để giải các bài toán đếm. Khi đó quy tắc tìm các số hạng từ các số hạng đi

trước được gọi là các hệ thức truy hồi.

Định nghĩa 1: Hệ thức truy hồi (hay công thức truy hồi) đối với dãy số {a_n} là công

thức biểu diễn a_nqua một hay nhiều số hạng đi trước của dãy. Dãy số được gọi là lời

giải hay nghiệm của hệ thức truy hồi nếu các số hạng của nó thỏa mãn hệ thức truy hồi

này.

Thí dụ 13 (Lãi kép): 1) Giả sử một người gửi 10.000 đô la vào tài khoản của mình tại

một ngân hàng với lãi suất kép 11% mỗi năm. Sau 30 năm anh ta có bao nhiêu tiền

trong tài khoản của mình?

Gọi P_nlà tổng số tiền có trong tài khoản sau n năm. Vì số tiền có trong tài khoản

sau n năm bằng số có sau n  1 năm cộng lãi suất của năm thứ n, nên ta thấy dãy {P_n}

thoả mãn hệ thức truy hồi sau:

P_n= P_{n 1}+ 0,11P_{n 1}= (1,11)P_{n 1}

-

với điều kiện đầu P₀= 10.000 đô la. Từ đó suy ra P_n= (1,11)ⁿ.10.000. Thay n = 30 cho

ta P₃₀= 228922,97 đô la.

2) Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n

và không có hai số 0 liên tiếp. Có bao nhiêu xâu nhị phân như thế có độ dài bằng 5?

Gọi a_nlà số các xâu nhị phân độ dài n và không có hai số 0 liên tiếp. Để nhận

được hệ thức truy hồi cho {a_n}, ta thấy rằng theo quy tắc cộng, số các xâu nhị phân độ

dài n và không có hai số 0 liên tiếp bằng số các xâu nhị phân như thế kết thúc bằng số 1

cộng với số các xâu như thế kết thúc bằng số 0. Giả sử n  3.

Các xâu nhị phân độ dài n, không có hai số 0 liên tiếp kết thúc bằng số 1 chính là

xâu nhị phân như thế, độ dài n  1 và thêm số 1 vào cuối của chúng. Vậy chúng có tất cả

là a_{n 1}. Các xâu nhị phân độ dài n, không có hai số 0 liên tiếp và kết thúc bằng số 0, cần

-

phải có bit thứ n  1 bằng 1, nếu không thì chúng có hai số 0 ở hai bit cuối cùng. Trong

trường hợp này chúng có tất cả là a_{n 2}. Cuối cùng ta có được:

-

a_n= a_{n 1}+ a_{n 2}với n  3.

-

Điều kiện đầu là a₁= 2 và a₂= 3. Khi đó a₅= a₄+ a₃= a₃+ a₂+ a₃= 2(a₂+ a₁) + a₂= 13.

2.5.2. Giải các hệ thức truy hồi.

Định nghĩa 2: Một hệ thức truy hồi tuyến tính thuần nhất bậc k với hệ số hằng số là hệ

thức truy hồi có dạng:

32

a_n= c₁a_{n 1}+ c₂a_{n 2}+ ... + c_ka_n-k,

-

trong đó c₁, c₂, ..., c_klà các số thực và c_k 0.

Theo nguyên lý của quy nạp toán học thì dãy số thỏa mãn hệ thức truy hồi nêu

trong định nghĩa được xác định duy nhất bằng hệ thức truy hồi này và k điều kiện đầu:

a₀= C₀, a₁= C₁, ..., a_k-1= C_k-1.

Phương pháp cơ bản để giải hệ thức truy hồi tuyến tính thuần nhất là tìm nghiệm

dưới dạng a_n= rⁿ, trong đó r là hằng số. Chú ý rằng a_n= rⁿlà nghiệm của hệ thức truy

hồi a_n= c₁a_{n 1}+ c₂a_{n 2}+ ... + c_ka_{n k}nếu và chỉ nếu

-

rⁿ= c₁r^{n 1}+ c₂r^{n 2}+ ... + c_kr^{n k}hay r^k c₁r^{k 1} c₂r^{k 2} ...  c_{k 1}r – c_k= 0.

-

Phương trình này được gọi là phương trình đặc trưng của hệ thức truy hồi, nghiệm của

nó gọi là nghiệm đặc trưng của hệ thức truy hồi.

Mệnh đề: Cho c₁, c₂, ..., c_klà các số thực. Giả sử rằng phương trình đặc trưng

-

r^k c₁r^{k 1} c₂r^{k 2} ...  c_{k 1}r – c_k= 0

-

có k nghiệm phân biệt r₁, r₂, ..., r_k. Khi đó dãy {a_n} là nghiệm của hệ thức truy hồi a_n=

n

c₁a_{n 1}+ c₂a_{n 2}+ ... + c_ka_{n k}nếu và chỉ nếu a_n= ₁r₁+ ₂r₂+ ... + _kr_k, với n = 1, 2, ...

-

trong đó ₁, ₂, ..., _klà các hằng số.

Thí dụ 14: 1) Tìm công thức hiển của các số Fibonacci.

Dãy các số Fibonacci thỏa mãn hệ thức f_n= f_n-1+ f_n-2và các điều kiện đầu f₀= 0

1 5

1 5

và f₁= 1. Các nghiệm đặc trưng là r₁=

1 5

và r₂=

. Do đó các số Fibonacci

2

1 5

được cho bởi công thức f_n= ₁(

1 5

)ⁿ+ ₂(

)ⁿ. Các điều kiện ban đầu f₀= 0 =

2

1 5

1

₁+ ₂và f₁= 1 = ₁(

) + ₂(

). Từ hai phương trình này cho ta ₁=

,

2

5

1

₂= -

. Do đó các số Fibonacci được cho bởi công thức hiển sau:

5

1

1 5

1

1 5

f_n=

(

)ⁿ-

(

)ⁿ.

2

5

2) Hãy tìm nghiệm của hệ thức truy hồi a_n= 6a_{n 1}- 11a_{n 2}+ 6a_{n 3}với điều kiện

-

ban đầu a₀= 2, a₁= 5 và a₂= 15.

Đa thức đặc trưng của hệ thức truy hồi này là r³- 6r²+ 11r - 6. Các nghiệm đặc

trưng là r = 1, r = 2, r = 3. Do vậy nghiệm của hệ thức truy hồi có dạng

a_n= ₁1ⁿ+ ₂2ⁿ+ ₃3ⁿ.

Các điều kiện ban đầu

a₀= 2 = ₁+ ₂+ ₃

a₁= 5 = ₁+ ₂2 + ₃3

a₂= 15 = ₁+ ₂4 + ₃9.

Giải hệ các phương trình này ta nhận được ₁= 1, ₂= 1, ₃= 2. Vì thế, nghiệm duy

nhất của hệ thức truy hồi này và các điều kiện ban đầu đã cho là dãy {a_n} với

33

a_n= 1  2ⁿ+ 2.3ⁿ.

2.6. QUAN HỆ CHIA ĐỂ TRỊ.

2.6.1. Mở đầu:

Nhiều thuật toán đệ quy chia bài toán với các thông tin vào đã cho thành một hay

nhiều bài toán nhỏ hơn. Sự phân chia này được áp dụng liên tiếp cho tới khi có thể tìm

được lời giải của bài toán nhỏ một cách dễ dàng. Chẳng hạn, ta tiến hành việc tìm kiếm

nhị phân bằng cách rút gọn việc tìm kiếm một phần tử trong một danh sách tới việc tìm

phần tử đó trong một danh sách có độ dài giảm đi một nửa. Ta rút gọn liên tiếp như vậy

cho tới khi còn lại một phần tử. Một ví dụ khác là thủ tục nhân các số nguyên. Thủ tục

này rút gọn bài toán nhân hai số nguyên tới ba phép nhân hai số nguyên với số bit giảm

đi một nửa. Phép rút gọn này được dùng liên tiếp cho tới khi nhận được các số nguyên

có một bit. Các thủ tục này gọi là các thuật toán chia để trị.

2.6.2. Hệ thức chia để trị:

Giả sử rằng một thuật toán phân chia một bài toán cỡ n thành a bài toán nhỏ,

n

trong đó mỗi bài toán nhỏ có cỡ (để đơn giản giả sử rằng n chia hết cho b; trong thực

b

n

tế các bài toán nhỏ thường có cỡ [ ] hoặc ] [). Giả sử rằng tổng các phép toán thêm

b

vào khi thực hiện phân chia bài toán cỡ n thành các bài toán có cỡ nhỏ hơn là g(n). Khi

đó, nếu f(n) là số các phép toán cần thiết để giải bài toán đã cho thì f thỏa mãn hệ thức

truy hồi sau:

n

f(n) = af( ) + g(n)

b

Hệ thức này có tên là hệ thức truy hồi chia để trị.

Thí dụ 15: 1) Thuật toán tìm kiếm nhị phân đưa bài toán tìm kiếm cỡ n về bài toán tìm kiếm

phần tử này trong dãy tìm kiếm cỡ n/2, khi n chẵn. Khi thực hiện việc rút gọn cần hai phép so

sánh. Vì thế, nếu f(n) là số phép so sánh cần phải làm khi tìm kiếm một phần tử trong danh sách

tìm kiếm cỡ n ta có f(n) = f(n/2) + 2, nếu n là số chẵn.

2) Có các thuật toán hiệu quả hơn thuật toán thông thường để nhân hai số nguyên.

Ở đây ta sẽ có một trong các thuật toán như vậy. Đó là thuật toán phân nhanh, có dùng

kỹ thuật chia để trị. Trước tiên ta phân chia mỗi một trong hai số nguyên 2n bit thành

hai khối mỗi khối n bit. Sau đó phép nhân hai số nguyên 2n bit ban đầu được thu về ba

phép nhân các số nguyên n bit cộng với các phép dịch chuyển và các phép cộng.

Giả sử a và b là các số nguyên có các biểu diễn nhị phân độ dài 2n là

a = (a_2n-1a_2n-2... a₁a₀)₂và b = (b_2n-1b_2n-2... b₁b₀)₂.

Giả sử a = 2ⁿA₁+ A₀, b = 2ⁿB₁+ B₀, trong đó

A₁= (a_2n-1a_2n-2... a_n+1a_n)₂, A₀= (a_{n 1}... a₁a₀)₂

-

B₁= (b_{2n 1}b_{2n 2}... b_n+1b_n)₂, B₀= (b_{n 1}... b₁b₀)₂.

-

Thuật toán nhân nhanh các số nguyên dựa trên đẳng thức:

34

ab = (2²ⁿ+ 2ⁿ)A₁B₁+ 2ⁿ(A₁- A₀)(B₀- B₁) + (2ⁿ+ 1)A₀B₀.

Đẳng thức này chỉ ra rằng phép nhân hai số nguyên 2n bit có thể thực hiện bằng cách

dùng ba phép nhân các số nguyên n bit và các phép cộng, trừ và phép dịch chuyển.

Điều đó có nghĩa là nếu f(n) là tổng các phép toán nhị phân cần thiết để nhân hai số

nguyên n bit thì

f(2n) = 3f(n) + Cn.

Ba phép nhân các số nguyên n bit cần 3f(n) phép toán nhị phân. Mỗi một trong các phép

cộng, trừ hay dịch chuyển dùng một hằng số nhân với n lần các phép toán nhị phân và

Cn là tổng các phép toán nhị phân được dùng khi làm các phép toán này.

n

Mệnh đề 1: Giả sử f là một hàm tăng thoả mãn hệ thức truy hồi f(n) = af( ) + c với

b

mọi n chia hết cho b, a  1, b là số nguyên lớn hơn 1, còn c là số thực dương. Khi đó

O(n^{log a}), a  1

b



f(n) =

.







O(logn),a  1

n

Mệnh đề 2: Giả sử f là hàm tăng thoả mãn hệ thức truy hồi f(n) = af( ) + cn^dvới mọi

b

n = b^k, trong đó k là số nguyên dương, a  1, b là số nguyên lớn hơn 1, còn c và d là các

số thực dương. Khi đó

O(n^log^b^a), a  b^d





f(n) = O(n^dlog n), a  b^d

.





O(n^d) ,a  b^d





Thí dụ 16: Hãy ước lượng số phép toán nhị phân cần dùng khi nhân hai số nguyên n bit

bằng thuật toán nhân nhanh.

Thí dụ 15.2 đã chỉ ra rằng f(n) = 3f(n/2) + Cn, khi n chẵn. Vì thế, từ Mệnh đề 2 ta

suy ra f(n) = O(n^{log 3}). Chú ý là log₂3  1,6. Vì thuật toán nhân thông thường dùng

2

O(n²) phép toán nhị phân, thuật toán nhân nhanh sẽ thực sự tốt hơn thuật toán nhân

thông thường khi các số nguyên là đủ lớn.

BÀI TẬP CHƯƠNG II:

1. Trong tổng số 2504 sinh viên của một khoa công nghệ thông tin, có 1876 theo học

môn ngôn ngữ lập trình Pascal, 999 học môn ngôn ngữ Fortran và 345 học ngôn ngữ C.

Ngoài ra còn biết 876 sinh viên học cả Pascal và Fortran, 232 học cả Fortran và C, 290

học cả Pascal và C. Nếu 189 sinh viên học cả 3 môn Pascal, Fortran và C thì trong

trường hợp đó có bao nhiêu sinh viên không học môn nào trong 3 môn ngôn ngữ lập

trình kể trên.

35

2. Một cuộc họp gồm 12 người tham dự để bàn về 3 vấn đề. Có 8 người phát biểu về

vấn đề I, 5 người phát biểu về vấn đề II và 7 người phát biểu về vấn đề III. Ngoài ra, có

đúng 1 người không phát biểu vấn đề nào. Hỏi nhiều lắm là có bao nhiêu người phát

biểu cả 3 vấn đề.

3. Chỉ ra rằng có ít nhất 4 người trong số 25 triệu người có cùng tên họ viết tắt bằng 3

chữ cái sinh cùng ngày trong năm (không nhất thiết trong cùng một năm).

4. Một tay đô vật tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta có ít

nhất một trận đấu, nhưng toàn bộ anh ta có không quá 125 trận. Chứng tỏ rằng có những

giờ liên tiếp anh ta đã đấu đúng 24 trận.

5. Cho n là số nguyên dương bất kỳ. Chứng minh rằng luôn lấy ra được từ n số đã cho

một số số hạng thích hợp sao cho tổng của chúng chia hết cho n.

6. Trong một cuộc lấy ý kiến về 7 vấn đề, người được hỏi ghi vào một phiếu trả lời sẵn

bằng cách để nguyên hoặc phủ định các câu trả lời tương ứng với 7 vấn đề đã nêu.

Chứng minh rằng với 1153 người được hỏi luôn tìm được 10 người trả lời giống

hệt nhau.

7. Có 17 nhà bác học viết thư cho nhau trao đổi 3 vấn đề. Chứng minh rằng luôn tìm

được 3 người cùng trao đổi một vấn đề.

8. Trong kỳ thi kết thúc học phần toán học rời rạc có 10 câu hỏi. Có bao nhiêu cách gán

điểm cho các câu hỏi nếu tổng số điểm bằng 100 và mỗi câu ít nhất được 5 điểm.

9. Phương trình x₁+ x₂+ x₃+ x₄+ x₅= 21 có bao nhiêu nghiệm nguyên không âm?

10. Có bao nhiêu xâu khác nhau có thể lập được từ các chữ cái trong từ MISSISSIPI,

yêu cầu phải dùng tất cả các chữ?

11. Một giáo sư cất bộ sưu tập gồm 40 số báo toán học vào 4 chiếc ngăn tủ, mỗi ngăn

đựng 10 số. Có bao nhiêu cách có thể cất các tờ báo vào các ngăn nếu:

1) Mỗi ngăn được đánh số sao cho có thể phân biệt được;

2) Các ngăn là giống hệt nhau?

12. Tìm hệ thức truy hồi cho số mất thứ tự D_n.

13. Tìm hệ thức truy hồi cho số các xâu nhị phân chứa xâu 01.

14. Tìm hệ thức truy hồi cho số cách đi lên n bậc thang nếu một người có thể bước một,

hai hoặc ba bậc một lần.

15. 1) Tìm hệ thức truy hồi mà R_nthoả mãn, trong đó R_nlà số miền của mặt phẳng bị

phân chia bởi n đường thẳng nếu không có hai đường nào song song và không có 3

đường nào cùng đi qua một điểm.

b) Tính R_nbằng phương pháp lặp.

16. Tìm nghiệm của hệ thức truy hồi a_n= 2a_{n 1}+ 5a_{n 2}- 6a_{n 3}với a₀= 7, a₁= -4, a₂= 8.

-

36