Phương Pháp Liệt Kê - BÀI GIẢNG TOÁN RỜI RẠC 1

Việc tìm một công thức cho kết quả đếm ngay cả trong trường hợp công thức truy hồi không phải dễ dàng và lúc nào cũng thực hiện được. Cho đến nay còn nhiều bài toán đếm chưa có lời giải dưới dạng một công thức. Đối với những bài toán như vậy, người ta chỉ còn cách chỉ ra một phương pháp liệt kê, theo đó có thể đi qua được tất cả các cấu hình cần đếm. Rõ ràng bản thân phương pháp liệt kê không chỉ ra được một kết quả cụ thể nào nhưng qua đó người ta có thể lập trình cho máy tính điện tử đếm hộ.

Để minh hoạ cho phương pháp liệt kê, ta xét một cấu hình tổ hợp nổi tiếng đó là các hình chữ nhật la tinh.

Giả sử S là tập gồm n phần tử. Không mất tính tổng quát ta giả sử S = {1, 2, . ., n} Một hình chữ nhật la tinh trên S là một bảng gồm p dòng, q cột sao cho mỗi dòng của nó là một chỉnh hợp không lặp chập q của S và mỗi cột của nó là một chỉnh hợp không lặp chập p của S.

Theo định nghĩa ta có pn, qn. Đặc biệt trong trường hợp q = n, mỗi dòng của hình chữ nhật la tinh là một hoán vị của S, sao cho không có cột nào chứa hai phần tử lặp lại. Hình chữ nhật la tinh dạng này được gọi là chuẩn nếu dòng đầu của nó là hoán vị 1, 2,. ., n.

Ví dụ. Hình la tinh chuẩn trên tập S = {1, 2, 3, 4, 5, 6, 7 } 1 2 3 4 5 6 7

2 3 4 5 6 7 1 3 4 5 6 7 1 2

Gọi L(p,n) là số hình chữ nhật la tinh p x n, còn K(p,n) là số hình chữ nhật la tinh chuẩn p x n ta có:

L(p,n) = n! K(p,n)

Dễ dàng nhận thấy rằng, số mất Dn là số hình la tinh chuẩn 2 x n, số phân bố Un là số hình chữ nhật la tinh chuẩn 3 x n với hai dòng đầu là:

1 2 . . . n-1 n 2 3 . . . n 1 Riodan J(1946) đã chứng minh công thức:

k n m k C n k Dn kDkU n K(3, ) 0 ( , )  2 trong đó m= [n/2], U0 = 1.

Bài toán đếm với số dòng nhiều hơn đến nay vẫn chưa được giải quyết. Người ta mới chỉ đưa ra được một vài dạng tiệm cận của L(p,n).

Nếu p=q=n, thì hình chữ nhật la tinh được gọi là hình vuông la tinh. Một hình vuông la tinh cấp n được gọi là chuẩn nếu có dòng đầu và cột đầu là hoán vị 1, 2,. .n. Thí dụ một hình vuông la tinh chuẩn cấp 7.

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 PTIT

7 1 2 3 4 5 6

Gọi ln là số các hình vuông như thế ta có L(n,n) = n!(n-1)!ln

Việc tìm một công thức cho ln đến nay vẫn bỏ ngỏ. Tuy nhiên ta có thể nhờ máy tính liệt kê tất cả các hình vuông chuẩn cấp n. Dưới đây là một vài giá trị tính được.

N 1 2 3 4 5 6 7

ln 1 1 1 4 56 9408 16942080

BÀI TẬP CHƯƠNG 2

1. Xâu thuận nghịch độc là một xâu khi viết theo thứ tự ngược lại cũng bằng chính nó. Hãy đếm số xâu nhị phân có độ dài n là thuận nghịch độc.

2. Cô dâu và chú rể mời bốn bạn đứng thành một hàng để chụp ảnh. Hỏi có bao nhiêu cách xếp hàng nếu:

a) Cô dâu đứng cạnh chú rể

b) Cô dâu không đứng cạnh chú rể c) Cô dâu đứng ở phía bên phải chú rể

3. Có bao nhiêu xâu nhị phân độ dài 10 có năm số 0 liền nhau hoặc năm số 1 liến nhau. 4. Có bao nhiêu xâu nhị phân độ dài bằng 8 có 3 số 0 liền nhau hoặc 4 số 1 liền nhau. 5. Mỗi sinh viên lớp toán học rời rạc hoặc giỏi toán hoặc giỏi tin học hoặc giỏi cả hai

môn này. Trong lớp có bao nhiêu sinh viên nếu 38 người giỏi tin (kể cả người giỏi cả hai môn), 23 người giỏi toán (kể cả người giỏi cả hai môn), và 7 người giỏi cả hai môn.

6. 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 một số khác.

7. Chứng minh rằng, trong dãy gồm n2 + 1 số thực phân biệt đều có một dãy con dài n+1 hoặc thực sự tăng, hoặc thực sự giảm.

8. 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 của nhau hoặc là kẻ thù của nhau.

9. Hãy chỉ ra rằng, trong 102 người có chiều cao khác nhau đứng thành một hàng có thể tìm được 11 người có chiều cao tăng dần hoặc giảm dần mà không cần thay đổi thứ tự của họ trong hàng.

10.Một đô vật tay tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta thi đấu ít nhất một trận, nhưng toàn bộ anh ta không thi đấu quá 125 trận. Chứng tỏ rằng, có những giờ liên tiếp anh ta thi đấu 24 trận.

11.Một nhân viên bắt đầu làm việc tại công ty từ năm 1987 với mức lương khởi điểm là 50000 đô la. Hàng năm anh ta được nhận thêm 1000 đô la và 5% lương của năm trước.

a) Hãy thiết lập hệ thức truy hồi tính lương của nhân viên đó n năm sau năm 1987. b) Lương vào năm 1995 của anh ta là bao nhiêu?

c) Hãy tìm công thức tường minh tính lương của nhân viên này n năm sau năm 1987. PTIT

12.Tìm hệ thức truy hồi cho số hoán vị của tập n phần tử. Dùng hệ thức truy hồi đó tính hoán vị của tập n phần tử.

13.Một máy bán tem tự động chỉ nhận các đồng xu một đô la và các loại tờ tiền 1 đô la và 5 đô la.

a) Hãy tìm hệ thức truy hồi tính số cách đặt n đô la vào trong máy bán hàng, trong đó thứ tự các đồng xu, các tờ tiền là quan trọng.

b) Tìm các điều kiện đầu.

c) Có bao nhiêu cách đặt 10 đô la vào máy để mua một bộ tem. 14.Giải các hệ thức truy hồi với các điều đầu sau:

a) an = an-1 + 6an-2 với n  2, a0 = 3, a1 = 6. b) an = 7an-1 - 6an-2 với n  2, a0 = 2, a1 = 1. c) an = 6an-1 - 8an-2 với n  2, a0 = 4, a1 = 10. d) an = 2an-1 - an-2 với n  2, a0 = 4, a1 = 1. e) an = an-2 với n  2, a0 = 5, a1 = -1. f) an = -6an-1 - 9an-2 với n  2, a0 = 3, a1 = -3. g) an+2 = -4an+1 + 5an với n  0, a0 = 2, a1 = 8.

15.Tìm các nghiệm đặc trưng của hệ thức truy hồi tuyến tính thuần nhất a) an = 2an-1 - 2an-2

b) Tìm nghiệm thoả mãn hệ thức truy hồi trên và các điều kiện đầu a0 =1, a1 =2. 16.a) Tìm nghiệm đặc trưng của hệ thức truy hồi tuyến tính thuần nhất an = an-4

b) Tìm nghiệm thoả mãn hệ thức truy hồi trên và các điều kiện đầu a0=1, a1=0, a2=-1, a3=1.

17.Một báo cáo về thị trường máy tính cá nhân cho biết có 65000 người sẽ mua modem cho máy tính của họ trong năm tới, 1 250 000 người sẽ mua ít nhất một sản phẩm phần mềm. Nếu báo cáo này nói rằng 1.450.000 người sẽ mua hoặc là modem hoặc là ít nhất một sản phẩm phần mềm thì sẽ có bao nhiêu người sẽ mua cả modem và mua ít nhất một sản phẩm phần mềm.

CHƯƠNG 3. BÀI TOÁN LIỆT KÊ

Nội dung bài toán đếm là đếm xem có bao nhiêu cấu hình tổ hợp thỏa mãn một số tính chất nào đó. Bài toán liệt không chỉ đếm được các cấu hình tổ hợp thỏa mãn các tính chất đặt ra mà còn xem xét từng cấu hình tổ hợp đó là gì. Đối với mỗi bài toán, khi chưa tìm được thuật giải thì liệt kê được xem là biện pháp cuối cùng để thực hiện với sự hỗ trợ của máy tính. Có thể nói, liệt kê được xem là phương pháp giải vạn năng một bài toán bằng máy tính. Nội dung chính của chương này tập chung giải quyết những vấn đề cơ bản sau:

 Giới thiệu bài toán liệt kê.

 Thuật toán và độ phức tạp tính toán.

 Giải quyết bài toán liệt kê bằng phương pháp sinh.

 Giải quyết bài toán liệt kê bằng phương pháp quay lui.

Bạn đọc có thể tìm thấy cách giải nhiều bài toán liệt kê trong các tài liệu [1] và [2] trong tài liệu tham khảo.