Archive

Archive for May, 2010

Đếm ma trận {0,1}

May 27, 2010 Leave a comment

Xét hai vector sao cho

Một kết quả quen thuộc là:

Số các ma trận với các số hạng 0,1 sao cho tổng dòng thứ i băng , tổng cột thứ j bằng , kí hiệu là B(s,t), bằng số các đồ thị lưỡng phân (có gán nhãn) với phần thứ nhất gồm m đỉnh với bậc tương ứng là bộ , phần thứ hai có n đỉnh với các bậc tương ứng là

Giả sử là ma trận vơi các số hạng 0,1. Kí hiệu là số các ma trận cấp với các số hạng 0,1 và tổng các hàng, các cột tương ứng là sao cho nếu bằng 1 thì .

Trường hợp đặc biệt thì ko có điều kiện rằng buộc gì nên .

Chú ý rằng tỉ số bằng xác suất chọn ngẫu nhiên một ma trận với các số hạng 0,1 với tổng các hàng, các cột tương ứng là s,t, và ma trận này có các số hạng bằng 0 tại các vị trí mà bằng 1.

Ta kí hiệu có nghĩa là các lấy trên các số hạng có giá trị bằng 1, có nghĩa là các lấy trên các số hạng có giá trị bằng 0.

Để ý rằng chính là hệ số của số hạng chứa trong tích

Thế thì theo công thức Cauchy về hệ số ta có:

ở đây mỗi tích phân lấy theo một đường biên đơn, đóng theo ngược chiều kim đồng hồ.

Advertisements
Categories: Combinatorics

Từ công thức Picard đến công thức Euler

May 27, 2010 2 comments

(Bài này phỏng dịch lại theo các bài viết trên tạp chí Kvant)

Lưới nguyên là tập hợp tất cả các điểm trên mặt phẳng tọa độ Đê-các vuông góc với tọa độ nguyên. Một đa giác gọi là nguyên nếu như tất cả các đỉnh của nó đều thuộc về lưới nguyên . Trong bài này chúng ta sẽ tiếp cận công thức Picard cho diện tích các đa giác nguyên và công thức Euler cũng như chỉ ra mối liên hệ giữa chúng.

I – Tam giác nguyên thủy

Một tam giác nguyên được gọi là nguyên thủy nếu như ngoại trừ các đỉnh của nó thì không có điểm nào nằm trong và trên cạnh tam giác có tọa độ nguyên

s152.photobucket.com/albums/s165/dumb_boy1988/fig001.png
Hình 1.

Định lý 1. Tam giác nguyên là nguyên thủy khi và chỉ khi có có diện tích bằng

Chứng minh.

Cho tam giác nguyên thủy , xét hình chữ nhật nguyên nhỏ nhất với các cạnh song song với các trục tọa độ, chứa tam giác

Tất cả các trường hợp có thể xảy ra biểu diễn như trên hình 2.

s152.photobucket.com/albums/s165/dumb_boy1988/fig002.png
Hình 2.

Trường hợp a., b. rõ ràng tam giác không phải là nguyên thủy vì điểm trên hình vẽ có tọa độ nguyên. Trường hợp bao hàm cả trường hợp c., nếu như giả sử đỉnh có thể nằm trên (trường hợp đặc biệt có thể trùng với . Như vậy ta chỉ cần xét trường hợp , một cách không mất tính tổng quát, xem .

Kí hiệu là số các điểm nguyên nằm bên trong nhưng không nằm trên cạnh của đa giác . Khi đó dễ thấy

Vì trong đoạn không chứa điểm nguyên nên

Tương tự

Tam giác không chứa trong nó điểm nguyên nào nên

ở đây đúng bằng số điểm nguyên nằm trong , và các điểm nguyên nằm trên cạnh , trừ điểm .

Từ đó suy ra

rút gọn ta được

Kí hiệu là diện tích của hình phẳng , thế thì

Như vậy ta đã chứng minh chiều thuận của định lý. Ngược lại, giả sử tồn tại một tam giác nguyên với diện tích bằng mà không nguyên thủy. Khi đó ta cần chứng minh rằng tam giác nguyên luôn có thể phân hoạch thành các tam giác nguyên thủy.

s152.photobucket.com/albums/s165/dumb_boy1988/fig003.png
Hình 3.

Giả sử tam giác nguyên không nguyên thủy chỉ có các điểm nằm trên cạnh là nguyên. Khi đó tồn tại một cạnh chứa trong nó các điểm nguyên, ta nối các điểm này với đỉnh (hình [3]), trong các cạnh nối này không có chứa điểm nguyên nên các tam giác được chia ra, ngoại trừ nhiều nhất hai tam giác chứa cạnh (trong trường hợp trong các cạnh chứa điểm nguyên), đều là nguyên thủy. Kí hiệu hai tam giác không nguyên thủy này là , khi đó từ ta nối tương ứng với các điểm nguyên nằm trên cạnh . Khi đó toàn bộ các tam giác được chia ra đều là nguyên thủy.

s152.photobucket.com/albums/s165/dumb_boy1988/fig004.png
Hình 4.

Giả sử tam giác chứa trong nó một số điểm nguyên nào đó (hình [4]). Ta chọn ra một điểm và nối chúng với các đỉnh , thu được 3 tam giác nhỏ hơn. Ta tiếp tục quá trình chọn và phân hoạch tam giác đối với 3 tam giác nhỏ này. Vì số điểm nguyên nằm bên trong tam giác là hữu hạn nên đến một thời điểm thì quá trình này dừng và thu được các tam giác nguyên bên trong không chứa điểm nguyên nào, có thể trên cạnh có chứa điểm nguyên, và ta tiếp tục áp dụng cách phân hoạch như đã chỉ ra ở phần trên để thu được tất các các tam giác được phân hoạch đều là nguyên thủy.

Như vậy tam giác nguyên không nguyên thủy có thể phân hoạch ít nhất là 2 tam giác nguyên thủy, mà mỗi tam giác này có diện tích là 1/2 như đã chỉ ra ở phần thuận của định lý, từ đó , mâu thuẫn này cho ta chứng minh của phần đảo.

Bài tập 1. Chứng minh rằng với bất kì số luôn tồn tại tam giác nguyên thủy mà các chiều dài cạnh của nó đều lớn hơn .

II – Công thức Picard

Trong phần này khi nhắc đến đa giác, chúng ta xem chúng như là đa giác đơn, nghĩa là đa giác bị chặn và biên của nó là đường gấp khúc không tự cắt. Hình [5] là thí dụ về đa giác không đơn

s152.photobucket.com/albums/s165/dumb_boy1988/fig005.png
Hình 5.

Định lý 2. (Picard) Với đa giác nguyên thì diện tích của nó được tính theo công thức

trong đó là số điểm nguyên nằm trong, và là số điểm nguyên nằm trên cạnh của đa giác ngoại trừ các đỉnh của nó.

s152.photobucket.com/albums/s165/dumb_boy1988/fig006.png
Hình 6.

Thí dụ, như hình [6], ta có , áp dụng công thức Picard, thế thì diện tích đa giác nguyên này là

Chứng minh.

Trước hết bạn đọc hãy tự làm bài tập nhỏ sau

Bài tập 2. Bất kì một đa giác đơn có số đỉnh lớn hơn 4 đều tồn tại một đường chéo nằm hoàn toàn trong đa giác đó.

Từ đó bằng quy nạp dễ dàng chứng minh -giác có thể phân hoạch thành tam giác mà các đỉnh của chúng là các đỉnh của đa giác ban đầu. Do đó tổng các góc trong của một giác đơn đúng bằng .

Mỗi tam giác nhận được từ cách phân hoạch giác nguyên như trên ta có thể tiếp tục chia nhỏ chúng thành các tam giác nguyên thủy như cách đã trình bày ở định lý 1. Diện tích của mỗi tam giác nguyên thủy bằng , do đó số tam giác nguyên thủy được chia ra đúng bằng và do đó không phụ thuộc vào cách chia.

Và điều ta cần chứng minh tương đương với

s152.photobucket.com/albums/s165/dumb_boy1988/fig007.png
Hình 7.

Tổng tất cả các góc thuộc các tam giác nguyên thủy được chia ra mà các góc đó có đỉnh là đỉnh của -giác bằng tổng các góc trong của đa giác này, và bằng (hình [7a]).

Tổng tất cả các góc thuộc các tam giác nguyên thủy được chia ra mà các góc đó có đỉnh nằm trên cạnh và không trùng với đỉnh của giác đúng bằng (hình [7b]).

Tổng tất cả các góc thuộc các tam giác nguyên thủy được chia ra mà các góc đó có đỉnh nằm bên trong đa giác đúng bằng (hình [7c]).

Mặc khác tổng tất cả các góc của tất cả các tam giác nguyên thủy được chia ra đúng bằng . Do dó

hay , là điều cần phải chứng minh.

Chú ý. Giả sử mặt phẳng được phân hoạch thành các hình bình hành bằng nhau bởi hai họ đường thẳng song song cắt nhau. Khi đó các đỉnh của các hình bình hành này lập thành một tập hợp gọi là lưới . Lưới nguyên là một trường hợp riêng khi mà hai họ đường thẳng song song vuông góc nhau, và mỗi hình bình hành trở thành hình vuông.

Giả sử đa giác với các đỉnh nằm trên lưới thỏa mãn công thức Picard mở rộng

Trong đó là diện tích của mỗi hình bình hành trong lưới .

III – Phân tích logic của lời giải

Chúng ta phát biểu lại một lần nữa ba khẳng định mà đã chứng minh ở phần trên

1. Với mỗi đa giác nguyên , ta có công thức Picard

2. Diện tích của mỗi tam giác nguyên thủy bằng .

3. Với bất kì sự phân hoạch đa ngác nguyên thành tam giác nguyên thủy, thế thì

Chúng ta có các lược đồ logic của chứng minh như trên hình 8.

s152.photobucket.com/albums/s165/dumb_boy1988/fig008.png
Hình 8.

Trong hình a, ta chứng minh được công thức Picard 1. một cách độc lập với 2. và 3., từ 1. suy ra 2. thì tầm thường và 3. suy ra từ 1. và 2. (xem bài tập 3)

Trong hình b, đó chính là lược đồ mà chúng ta đã chứng minh. Đầu tiên chứng minh 2. một cách độc lập, rồi từ đó nhận được 3., và công thức Picard là hệ quả của 2. và 3.

Chúng ta sẽ xem xét hai lược đồ chứng minh đáng chú ý còn lại.

Chúng ta có thể chỉ ra 3. suy ra 2. Thật vậy, chú ý rằng diện tích của bất kì tam giác nguyên luôn có dạng . Để làm rõ điều này, chúng ta ngoại tiếp tam giác nguyên này bằng hình chữ nhật nguyên nhỏ nhất có canh song song với hai trục tọa độ. Cũng như ở phần đầu, có tất cả các vị trí mô tả bằng hình [2]. Hình chữ nhật ngoại tiếp có diện tích là số nguyên và các tam giác bổ sung cũng có diện tích dạng một nửa số nguyên hoặc số nguyên, từ đó diện tích tam giác nguyên có dạng số nguyên hoặc nửa số nguyên, và rõ ràng luôn không bé hơn .

Bây giờ xét tam giác nguyên thủy , và là hình chữ nhật nhỏ nhất ngoại tiếp nó, chúng ta chia các phần bổ sung bên ngoài thành để thành thành các tam giác nguyên thủy. Đây la một sự phân hoạch thành các tam giác nguyên thủy , trong đó chứa cả .

Chúng ta cũng có thể phân hoạch thành các tam giác nguyên thủy theo một cách khác: chia đôi theo đường chéo các ô vuông đơn vị cấu thành nên . Giả sử diện tích của thì có tất cả tam giác nguyên thủy, và số tam giác nguyên thủy này là phụ thuộc vào cách phân hoạch. Quay lại các chia đầu tiên, chúng ta có

Lại có với mỗi , suy ra , và đặc biệt .

Bây giờ xem xét sự suy ra 1. từ 2. Xét hàm sau

xác định trên các đa giác nguyên (đơn).

s152.photobucket.com/albums/s165/dumb_boy1988/fig009.png
Hình 9.

Nếu phân hoạch một đa giác nguyên bởi một đường gấp khúc bên trong nó mà các đỉnh của đường gấp khúc là điểm nguyên thanh hai đa giác nguyên , chúng ta viết , xem hình [9]. Dễ dàng kiểm tra sự cộng tính của hàm

và diện tích cũng thỏa mãn sự cộng tính

Do đó nếu công thức Picard đúng cho các các đa giác nguyên thì cũng đúng cho cả . Và như đã biết, đa giác nguyên luôn phân hoạch được thành các tam giác nguyên thủy, trong khi 2. chính là trường hợp đặc biệt công thức Picard cho tam giác nguyên thủy.

Bài tập 3. Sử dụng các ngoại tiếp hình chữ nhật như đã nêu ở định lý 1. và hàm cộng tính để chứng minh 1. một cách độc lập với 2. và 3.

IV – Công thức Euler

Chúng ta gọi một bản đồ đa giác là “đúng” nếu đó là sự phân hoạch đa giác đơn thành các các đa khác đơn khác sao cho bất kì hai đa giác nào được chia ra hoặc là có một cạnh chung hoặc chỉ có một đỉnh chung, hoặc là không có điểm chung nào.

Bản đồ đa giác đúng có thể xem như là một trường hợp riêng của đồ thị phẳng. Ta gọi các đa giác trong phân hoạch là các diện, và các cạnh của các đa giác đó là cạnh của bản đồ.

Đối với đồ thị phẳng (với trường hợp riêng là bản đồ đa giác) chúng ta có công thức Euler quen thuộc liên hệ giữa số đỉnh , số cạnh và số diện

Có thể xem một ví dụ trong hình dưới

s152.photobucket.com/albums/s165/dumb_boy1988/fig010.png
Hình 10.

Từ “bản đồ” nhấn mạnh rằng công thức Euler nói chung đúng cho các phân hoạch cong (xem hình [11]), mà dạng của đường là không quan trọng mà là cách nối giữa các điểm với thỏa mãn điều kiện “đúng”, (Thí dụ, sự phân hoạch ngũ giác thành các tam giác và tứ giác như ở hình 10, ta thay thế các đoạn thẳng bằng các đoạn cong để nhận được bẳng đồ cong “đúng”).

s152.photobucket.com/albums/s165/dumb_boy1988/fig011.png
Hình 11.

Trong trường hợp các diện của bản đồ đa giác đúng đều là tam giác thì ta gọi đây là bản đồ tam giác. Hiển nhiên rằng, với một đa giác đơn trên mặt phẳng có vô hạn cách phân hoạch nó thành bản đồ tam giác. Đồng thời số các diện tam giác luôn thỏa mãn công thức (không chỉ riêng trên lưới nguyên

ở đây lần lượt là số đỉnh của bản đồ nằm trong là số đỉnh nằm trên cạnh của nó. (bạn đọc tự chứng minh công thức này)

Mặc khác, chú ý rằng là số đỉnh của bản đồ nằm trên cạnh của , nên là số cạnh hoàn toàn trong đa giác , và mỗi cạnh này là cạnh chung của hai tam giác. Tổng số cạnh của tất cả các diện tam giác của bản đồ bằng

Từ đây suy ra

Định lý 3. (Euler) Với bất kì bản đồ đa giác “đúng”, ta có đẳng thức sau

Chứng minh

s152.photobucket.com/albums/s165/dumb_boy1988/fig012.png
Hình 12.

Giả sử có bản đồ đa giác với số đỉnh , số cạnh , số diện . Chúng ta đặt trong mỗi diện của bản đồ một điểm, nối mỗi điểm đó với các đỉnh của diện chứa nó. Khi đó thu được bản đồ tam giác (xem hình [12]) với số tam giác được phân hoạch là , số đỉnh nằm trên biên của đa giác ban đầu là , số đỉnh nằm trong đa giác này là , số cạnh là . Do cách bổ sung các đỉnh nên ta có tổng số các đỉnh của

Mỗi diện của bản đồ cũ được phân hoạch thành các diện con, mà số lượng bằng số các cạnh mới được nối nằm trong diện này, do vậy số các cạnh của bản đồ mới là

Sử dụng công thức (*) ứng với bản đồ : , từ đó

Như vậy ta thu được điều phải chứng minh.

Bài tập 4. Kiểm chứng chiều đảo, có nghĩa là từ công thức suy ra đẳng thức .

Bài tập 5. Chứng minh công thức Euler một cách độc lập với công thức .

Như vậy trong bài viết chúng ta đã trình bày mỗi liên hệ logic giữa hai công thức đẹp Euler và Picard, chúng có thể được hiểu như là tương đương nhau.

s152.photobucket.com/albums/s165/dumb_boy1988/fig013.png
Hình 13.

Chúng ta có thể mở rộng hai công thức nà trong trường hợp bản đồ đúng với các “lỗ khoét”, mà mỗi lỗ khoét có dạng đa giác đơn (phần tô đậm trong hình trên)

Định lý 4. Với đa giác nguyên với “lỗ khoét” cũng là những đa giác nguyên có diện tích là

trong đó, là số đỉnh nằm bên trong đa giác và không nằm cạnh của đa giác và trên cạnh của các lỗ khoét, là số đỉnh nằm trên cạnh của đa giác và trên cạnh của các lỗ khoét.

Định lý 5. Với mỗi bản đồ đa giác với lỗ khoét thế thì

Bạn đọc hãy tự chứng minh hai định lý này xem như bài tập.

Bài tập bổ sung.

6. Xét tam giác nguyên sao cho trên cạnh của nó không chứa các điểm nguyên nào khác các đỉnh. Chứng minh rằng nếu một tam giác như vậy chứa trong nó đúng một điểm nguyên thì điểm này chính là trọng tâm của tam giác.

7. Giả sử một -giác nguyên lồi sao cho bên trong và cạnh của nó không chứa một điểm nguyên nào khác các đỉnh, chứng tỏ .

8. Chứng minh rằng với bất kì hai điểm nguyên sao cho giữa đoạn nối chúng không chứa điểm nguyên nào khác, tìm được điểm sao cho tam giác là nguyên thủy. Khoảng cách từ đến bằng bao nhiêu nếu biết độ dài .

9. Xét điểm nguyên ()sao cho bất kì ba điểm nào giữa chúng đều lập thành được tam giác mà các trung tuyến của nó không cắt một điểm nguyên nào khác. Tìm số lớn nhất có thể được.

10. Chứng mình rằng mỗi hình vuông có cạnh bằng nằm trong mặt phẳng chứa không nhiều hơn điểm nguyên.

11. Trong mỗi trường hợp trong hình [14], tính diện tích của các hình bình hành được tô đậm, trong đó cạnh của hình bình hành được chia tương ứng ra thành phần bằng nhau, và biết .

s152.photobucket.com/albums/s165/dumb_boy1988/fig015.png
Hình 14.

13. Mỗi cạnh của tam giác được chia thành ba phần bằng nhau, trên mỗi cạnh nối một điểm chia với đỉnh của tam giác đối diện với nó, như là đã chỉ ra trên hình [15]. So sánh, diện tích tam tô đậm với tam giác .

s152.photobucket.com/albums/s165/dumb_boy1988/fig016.png
Hình 15.

14. Từ trung điểm của mỗi cạnh hình vuông nối với hai đỉnh còn lại của hình vuôn đối diện với nó, như là đã chỉ ra trên hình [16], tính tỉ lệ diện tích giữa hình bát giác được tô đậm với hình vuông này.

s152.photobucket.com/albums/s165/dumb_boy1988/fig017.png
Hình 16.

15. Đặt


với là các hằng số nào đó. Giả sử hàm số này xác định trên các đa giác nguyên và thỏa mãn , nếu như được phân hoạch ra thành hai đa giác nguyên bởi một đường gấp khúc với các đỉnh nguyên. Chứng tỏ rằng .

16. Chứng minh rằng với bất kì đa giác nguyên ta luôn có đẳng thức

ở đây là kí hiệu số tất cả các điểm nằm bên trong cũng như trên các cạnh của đa giác , và là đa giác nhận từ bằng cách phóng to lên hai lần với gốc tọa độ.

17. Hãy chỉ ra trên mặt phẳng 1000 điểm sao cho không có 3 điểm nào trong chúng thẳng hàng và khoảng cách giữa hai điểm bất kì là một số vô tỉ, còn diện tích của một tam giác bất kì, mà 3 đỉnh của nó được chọn ra từ các điểm nói trên, là một số hữu tỉ.

Categories: Combinatorics

Lý thyết các quân xe


A – Mở đầu

Hoán vị với các vị trí cấm

Ta có một mô hình cho một bài toán tổng quát như sau:

Xét các tập khác rỗng và kí hiệu tập các hoán vị với độ dài bằng

Đặt \ | \ \}, tập được gọi là vị trí cấm của , các hoán vị thuộc gọi là hoán vị với các vị trí cấm (permutation with forbidden positions) tương ứng với hệ

Một hoán vị tương đương với một cách sắp đặt con xe trên bàn cờ vua ở các tọa độ (Ở đây ta đánh số các cột và các dòng bằng các số từ trái sáng sang phải và từ trên xuống dưới, là tọa độ của ô nằm ở cột thứ và hàng thứ ), dĩ nhiên là nên không có 2 con nào ăn nhau.

Nếu thì hoán vị này tương ứng với một cách sắp đặt con xe lên bàn cờ sao cho không có hai con nào ăn nhau và con xe nằm ở cột thứ thì không được phép đặt vào các ô vuông có tọa độ thuộc tập , các vị trí này gọi là vị trí cấm (dĩ nhiên với ).

Gọi là tập các cách sắp xếp mà con xe ở cột thứ được đặt vào vị trí cấm. Theo nguyên lý bao hàm-loại trừ ta có kết quả tổng quát


Gọi là số sắp đặt con xe lên bàn cờ sao cho mỗi con xe đều ở vị trí cấm, quy ước . Thế thì

Do đó

Số cách sắp đặt các quân xe

Gọi là số cách sắp đặt k con xe (rook number) lên miền ô vuông (miền ở đây không nhất thiết là phải liên thông) trên bàn cờ sao cho không có 2 con nào ăn nhau.
Hàm sinh gọi là đa thức xe (rook polynomial) của miền , quy ước .
Một miền các ô vuông trên bàn cờ có thể được đặc trưng bởi một trận trên trường với bằng 1 nếu ô nếu ô .

Một số tính chất quan trọng:

1. trong đó là một ô vuông trong , là miền ô vuông nhận được từ C khi bỏ đi là miền ô vuông nhận được từ C khi bỏ đi tất cả các ô có cùng hàng và cùng cột với .

Thật vậy, khi sắp xếp quân xe lên miền , trong đó ô cố định, thì có hai trường hợp xảy ra:

– Ô được sắp một quân xe, khi đó đối với quân xe còn lại thì không thể sắp cùng hàng hoặc cùng cột với . Số cách sắp trong trường hợp này là .

– Ô không được sắp quân xe nào, khi đó đối với quân xe có thể sắp trên miền . Số cách sắp xếp trong trường hợp này là . Vì vậy:

Từ đây dễ suy ra kết quả với dạng hàm sinh.

Miền các ô vuông gọi là một block của miền các ô vuông nếu thỏa mãn:

i. Với bất kì các dòng có chứa ô của và cột không chứa ô nào của thì ô .

ii. Với bất kì dòng i không chứa nào của , và các cột chứa ô của thì .

Ta có một mở rộng (xem thêm ở [1]) của tính chất 1 như sau:

2. Với là miền ô vuông trên bàn cờ và là một block nằm trên hàng và cột thế thì

Trong đó với là miền nhận được bằng cách bỏ các ô của sao cho:

i. Bỏ đi tất cả các ô của

ii. Bỏ đi tất cả các ô thuộc dòng trong số dòng chứa các ô của

iii. Bỏ đi tất cả các ô thuộc cột trong số cột chứa các ô của

Chứng minh này cũng không khó khăn, chi tiết xin dành cho bạn đọc.

3. với là hai miền không có hàng nào chung và cột nào chung, là miền ô vuông bao gồm tất cả các ô vuông của

Thật vậy, vì là hai miền không có hàng nào chung và cột nào chung nên mỗi cách sắp đặt quân xe lên quân xe lên sẽ ứng với mỗi cách sắp đặt quân xe lên miền , với . Vì vậy . Từ đây nhận được kết quả dưới dạng hàm sinh.
Giả sử là một miền ô vuông trên bàn cờ và là miền bù của nó trên bàn cờ , thế thì số cách đặt quân xe lên sẽ bằng số cách sắp đặt quân xe lên bàn cờ và coi các ô thuộc như là các vị trí cấm. Tương tự như phần đầu, kí hiệu với là số cắp sắp đặt mà quân xe thứ nằm vào miền cấm là .

Bằng quy tắc nhân ta tính được

Ở đây ta chú ý rằng số cách sắp quân xe lên bàn cờ bằng , với (chứng minh điều này xem như bài tập), và ta đã áp dụng cho .

Theo nguyên lý bao hàm-loại trừ, ta có

Từ đây ta có một liên hệ đẹp giữ đa thức xe của hai miền ô vuông bù nhau:

4. R_{\overline{B}}(x)=\sum_{k=0}^n\left (\sum_{s=0}^k(-1)^s \frac{(m-s)!(n-s)!}{(n-k)!(n-k)!(k-s)!}r_s(B)\right )x^k
Bài tập.

1. Kí hiệu là đa thức xe của bảng chữ nhật ô. Chứng tỏ rằng

và dạng tương tự

Từ đó suy ra

2. Kí hiệu (Đa thức Laguerre). Chứng tỏ rằng

3. Chứng minh rằng

4. Với là một bảng vuông bất kì, ta viết thay vì . Giả sử là bậc của đa thức , chứng các bất đẳng thức sau
a.
b. với .
c.
d.
e. với .
f. với
g. với

Lý thuyết các quân xe (Rook Theory) mà đối tượng của nó là đa thức xe được nghiên cứu đầu tiên bởi Kaplansky and Riordan vào năm 1946, và sau đó là các mở rộng của Goldman với sự ứng dụng của nhiều phương pháp tổ hợp hiện đại từ những năm 1970. Trong những năm gần đây Haglund đạt được nhiều thành công trong việc gắn kết đa thức xe với nhiều lĩnh vực khác như chuỗi siêu hình học, bài toán đếm ma trận trên trường hữu hạn, lý thuyết biểu diễn nhóm. Lý thuyết các quân xe có quan hệ gần gũi với nhiều ứng dụng trong lý thuyết đồ thị, người ta cũng đã vận dụng đa thức xe cùng với cơ học lượng tử và đại số Weyl. Còn trong Tổ hợp đếm nói riêng, đa thức xe liên quan đến hàng loạt các bài toán đếm về hoán vị, phân hoạch, hình vuông Latin…

Trong phần mở đầu chúng ta đã làm quen với cách tính toán ma thức xe với sự đệ quy của các miền ô vuông. Phần ứng dụng máy tính trong tính toán đa thức xe sẽ được đề cập ở cuối bài viết, xem như là phụ lục.

B – Mở rộng và ứng dụng

1. Bài toán đếm hoán vị bất hòa

Bài toán 1.
(Derangement problem) Tìm số các hoán vị sao cho .

(Bài toán được nghiên cứu đầu tiên bởi Pierre Raymond de Montmort vào năm 1713)
Lời giải

Bài toán tương đương với việc tìm số các cách sắp xếp các quân xe lên bàn cờ ô với và miền các vị trí cấm chính là đường chéo chính của bàn cờ:

Rõ ràng miền này có thể được xem là phân hoạch thành ô vuông đôi một không cùng hàng và cùng cột. Đa thức xe của mỗi ô như vậy là .

i152.photobucket.com/albums/s165/dumb_boy1988/derangement.jpg

Áp dụng tính chất 3, ta có . Suy ra .
Áp dụng bài toán hoán vị với các vị trí cấm, ta thu được công thức tính số các hoán vị thỏa mãn điều kiện bài toán:

Một hoán vị như vậy gọi là vô trật tự (derangement permutation).

Chú ý là khi thì .

Bài toán 2. (Ménage problem) Tìm số cách sắp xếp cặp cô dâu, chú rể vào một bàn tròn chỗ () sao cho các cô dâu, chú rể ngồi luân phiên nhau, nhưng không xảy ra trường hợp chú rể ngồi bên cạnh cô dâu của mình.
(Bài toán được nghiên cứu đầu tiên bởi Édouard Lucas vào năm 1891)
Lời giải

Đầu tiên, ta sắp cô dâu vào bàn, sao cho giữa hai cô dâu để trống một ghế dành cho một chú rể nào đó. Số cách sắp xếp như vậy bằng

Trong mỗi cách sắp xếp các cô dâu, đánh số họ theo chiều kim đồng hồ lần lượt là . Ghế trống bên phải cô dâu thứ ta đánh số là .

Bây giờ ta xếp các chú rể vào ghế trống này sao cho thỏa mãn yêu cầu bài toán.

Giả sử chú rể của cô dâu thứ được sắp vào ghế số .

Thế thì

Ta có thể cho tương ứng một hoán vị () như vậy bằng với một cách sắp các quân xe lên bàn cờ ô với miền các vị trí cấm là:

i152.photobucket.com/albums/s165/dumb_boy1988/menage.jpg

Áp dụng tính chất 1, đối với miền ô vuông khi bỏ đi ô ta được miền , nếu xóa đi dòng và cột chứa ô này ta được miền . Ta có:

Với miền ta loại đi ô được miền , loại đi hàng và cột chứa ô này thu được , tương tự ta nhận được

Với miền , ta loại đi ô thu được miền , loại đi hàng và cột chứa ô này thu được . Thế thì

Từ các quan hệ đệ quy trên, ta rút ra được:

Và với các trường hợp đầu tiên, ta tính được , .

Kết quả cuối cùng, tính được (có thể sử dụng hàm sinh hoặc đa thức đặc trưng):

Áp dụng bài toán hoán vị với các vị trí cấm, ta có số các hoán vị thỏa mãn điều kiện là

Đây là số cách sắp xếp chú rể vào vị trí trống như đã đánh số. Công thức của số cách sắp xếp các cô dâu chú rể thỏa mãn điều kiện bài toán là:

Trường hợp tổng quát của Bài toán 1Bài toán 2, ta gọi hoán vị sao cho -bất hòa (k-discordant). Cho đến nay người ta đã có các kết quả cho bài toán này cho . Trường hợp có thể tiếp cận một cách sơ cấp để tìm quan hệ đệ quy và hàm sinh, trong bài viết không đề cập đến do khá phức tạp, bạn đọc có thể tham khảo ở . Trong trường hợp tổng quát, vấn đề tìm một công thức chính xác để tính số hoán vị -bất hòa vẫn là bài toán mở.

Bài tập.

1. Một hoán vị được gọi là không liên tiếp (nonconsecutive) nếu như thỏa mãn với . Tìm công thức tính số các hoán vị độ dài không liên tiếp và chứng tỏ

2. Chứng minh rằng:

a.

b.

c.

d.

e.

f.

với

g.

với .

3. Tìm công thức tính số các cách sắp xếp quân xe lên bàn cờ sao cho không có hai con nào nằm trên hai đường chéo lớn của bàn cờ.

4. Với (ménage number), chứng minh rằng:
a.

b.

2. Bảng Ferrers

Với thì miền các ô vuông được xác định bởi

gọi là bảng một bảng Ferrers. Như vậy bảng Ferrers được tạo thành từ dãy các cột ô vuông với chiều cao không giảm.

Ta có các định nghĩa:

1. gọi là vector chiều cao của .

2. () với , với gọi là m-vector chiều cao của .

Chú ý rằng . Có thể hiểu một cách đơn giản rằng là vector tạo ra từ bằng cách thêm các giá trị 0 vào vị trí đầu tiên.

3. với gọi là vector m-cấu trúc của .

Dễ dàng kiểm chứng các tính chất sau:

i.

ii. với

iii. khi và chỉ khi

Ngược lại, nếu một vector gồm số nguyên thỏa mãn (i) và (ii) thì nó là một vector n-cấu trúc của một bảng Ferrers xác định duy nhất.

4. () gọi là đa thức m-giai thừa của bảng Ferrers .

Định lý 1. (Factorization theorem) Xét bảng Ferrers F với cột, với có vector m-cấu trúc và đa thức m-giai thừa thế thì

Ở đây nếu và bằng 0 nếu .

Chứng minh

Giả sử có vector chiều cao là và m-vector chiều cao

Với , xét bảng với vector chiều cao

Dễ thấy, vế phải của đẳng thức cần chứng minh đúng bằng .

Ta sẽ tính theo một cách khác. Coi , là bảng hình chữ nhật ô nằm bên dưới (hình vẽ)

i152.photobucket.com/albums/s165/dumb_boy1988/ferrers.jpg

Trong mỗi trường hợp sắp xếp quân xe lên , giả sử trên quân xe, thì số cách sắp xếp các quân xe trên bằng , khi đó còn lại quân xe sắp xếp trên . Sau loại đi cột đã bị chiếm bởi quân xe đã sắp trên thì chỉ còn cột có thể sắp xe lên được trên . Nên đối với quân xe còn lại ta xem như sắp xếp chúng lên một miền chữ nhật , có tất cả cách sắp xếp.
Vì vậy
Đẳng thức cần chứng minh được kiểm chứng với vô hạn điểm là các số tự nhiên, hơn nữa do dạng đa thức nên ta thu được kết quả cho mọi .

Hệ quả 1. Xét bảng Ferrers với thế thì

Hệ quả này suy ra từ định lý 1 với , và tương ứng .

Trường hợp đặc biệt, đối với bảng thế thì , ở đây là số Stirling loại II

Thật vậy, áp dụng hệ quả trên ta có \sum_{k=1}^n r_k [x]_{n-k}=x^n đây là phương trình quen thuộc của số Stirling loại hai.

Ngoài ra chúng ta có thể giải quyết bằng một phương án thuần túy hơn. là số các phân hoạch tập thành khối khác rỗng không giao nhau. Xét mỗi cách sắp xếp quân xe lên bảng . Quân xe được sắp ở vị trí thì ta cho tương ứng hai số nằm cùng một khối trong phân hoạch. Việc kiểm tra đây là một song ánh xin dành cho bạn đọc.

Ta định nghĩa rằng hai miền ô vuông là tương đương (rook equivalence) nếu chúng có cùng đa thức xe. Theo định lý 1 ta suy ra được rằng:

i. Hai bảng Ferrers tương đương nếu và chỉ nếu với nào đó thì đa thức -giai thừa của chúng đồng nhất nhau.

ii. Hai bảng Ferrers tương đương nếu và chỉ nếu với nào đó thì . Ở đây kí hiệu là tập có lặp gồm các thành phần của vector .

Định lý 2. Mỗi bảng Ferrers tương đương với duy nhất một bảng Ferrers với dãy chiều cao các cột là tăng ngặt.

Chứng minh

Trước hết, xét bảng Ferrer với các cột có chiều cao tăng ngặt . Thế thì , trong đó vị trí đầu tiên bằng 0. Khi đó với . Một vector m-cấu trúc như vậy xác định duy nhất một bảng Ferrers, và bảng này có các cột có chiều cao tăng ngặt.

Với là một bảng Ferrers bất kì, theo nhận xét trên ta sẽ xây dựng một bảng Ferrers tương đương với , nghĩa là có để , và các thành phần được sắp tương tự như dạng của .\\

Ta có nên các bảng tương đương thì có cùng số ô. Xét , thế thì . Giả sử là thành phần có giá trị nhỏ nhất trong . Theo tính chất của của vector m-cấu trúc thì cũng xuất hiện trong . Xét vector:

Ở đây là các phần tử của tập có lặp loại đi các phần tử và sắp thứ tự không giảm . Như vậy là một vector m-cấu trúc của một bảng Ferrers với các cột có chiều cao tăng ngặt. Hơn nữa do là phần tử nhỏ nhất trong tập có lặp nên là bảng Ferrers với các cột có chiều cao tăng ngặt duy nhất tương đương với .

Một bài toán nảy sinh là có bao nhiêu bảng Ferrers tương đương với một bảng Ferrers cho trước? Ta thấy rằng đều là các hoán vị của tập có lặp . Như vậy bài toán được giải quyết khi ta đếm được số hoán vị của tập có lặp .

Định lý 3. Số bảng Ferrers tương đương với bảng Ferrers cho trước bằng:

Ở đây là thành phần có giá trị bé nhất trong vector , và là số lần xuất hiện của phần tử trong tập có lặp .

Chứng minh công thức này có thể xem trong .

Bài tập.

1. Cho là dãy tăng bao gồm các số nguyên dương, và bảng Ferrers với . Đặt

Chứng tỏ rằng

2. Có bao nhiêu bảng Ferrers tương đương với bảng Ferrers , trong đó:

a. .

b. .

c. với

C – Lập trình tính toán

1. Sử dụng Mathematica

Bài toán của chúng ta là tìm đa thức xe trên một miền ô vuông cho trước.

Lập hàm RookPolynomial như sau để sinh đa thức xe

RookPolynomial[n_List] := Module[{stacklist, top, SameColumnValues, SameRowValues,
EntriesToEliminate, InclusionList, ExclusionList},
stacklist = {Union[n]};

While[Union[Flatten[stacklist]] =!= {1, x}, top = First[stacklist];
SameColumnValues = Position[top, {_, top[[1, 2]]}];
SameRowValues = Position[top, {top[[1, 1]], _}];
EntriesToEliminate = Union[SameColumnValues, SameRowValues];
InclusionList = Append[Delete[top, EntriesToEliminate], {x}];
ExclusionList = Delete[top, 1];
If[Length[ExclusionList] == 0, ExclusionList = {{1}}];
stacklist = Delete[Append[Append[stacklist, ExclusionList], InclusionList], 1];
While[Union[Flatten[First[stacklist]]] == {x},
stacklist = RotateLeft[stacklist]]];
Total[Apply[Times, stacklist, 2]]]

Input của hàm này là một danh sách, bao gồm tọa độ các ô của miền ô vuông cần tính toán đa thức xe.

Thí dụ. Tính với miền ô vuông .

Ta sử dụng hàm trên như sau:

RookPolynomial[{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}]

Nhấp Shift+Enter, kết quả sẽ là

Out[1]= 1 + 5 x + 10 x^2 + 10 x^3 + 5 x^4 + x^5

2. Sử dụng Maple

Như phần đầu, ta cũng có thể lập một giải thuật tương tự bằng Maple. Nhưng để tránh sự lặp lại, ta xét bài toán tìm đa thức xe trên bàn cờ với miền các vị trí cấm cho trước.

Đầu tiên ta sử dụng hàm complement_ board để tính miền cho phép đặt các quân xe trên bàn cờ, giá trị trả về là một danh sách.

> with(combinat);
> complement_board := proc (F, n)
local i, j, x, L;
L := [];
for i to n do
for j to n do
if `not`(member([i, j], F)) then L := [op(L), [i, j]] end if
end do
end do;
RETURN(L)
end proc;

Hàm non_attacking_rooks_pos tìm tất cả các cách sắp đặt quân xe trên bàn cờ , với miền các vị trí cấm cho dưới dạng một danh sách .

>non_attacking_rooks_pos := proc (F, k, n)

local i, j, ans, cols, R, pos, F0, F1, F2, m, P, x, stop0, is;

P := permute(n, n);

F0 := F; pos := [];

if k = 1 then RETURN(complement_board(F0, n)) end if;

for x in P do

stop0 := 0;

R := choose(n, k);

for is in R do

stop0 := 0;

for i in is do

if member([i, x[i]], F0) then stop0 := 1 end if

end do;

if stop0 = 0 then pos := [op(pos), [seq([i, x[i]], i = is)]] end if

end do

end do;

RETURN(convert(convert(pos, set), list))

end proc

Cuối cùng, hàm rook_polynomial để tính đa thức xe theo biến của bài toán sắp xếp các quân xe trên bàn cờ với miền các vị trí cấm là danh sách .

>rook_polynomial := proc (F, n, x)

local i, a, p;

p := 1+add(nops(non_attacking_rooks_pos(F, i, n))*x^i, i = 1 .. n);

RETURN(p)

end proc

Thí dụ. Sắp xếp các quân xe lên bàn cờ với miền các vị trí cấm là

Ta làm như sau:> rook_polynomial([[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]], 5, x);

Nhấp Enter kết quả sẽ là

1 + 20 x + 130 x^2 + 320 x^3 + 265 x^4 + 44 x ^5

Chú ý là ở đây hàm non_attacking_rooks_pos cho giá trị trả về là một danh sách các cách sắp xếp.

Ta có thể xuất ra tất cả các cách sắp xếp trong từng trường hợp của $n$, $k$ và $F$.

> array_rooks := proc (L, n)

local i, j, A;

A := array(1 .. n, 1 .. n);

for i to n do

for j to n do

A[i, j] := 0;

if member([i, j], L) then A[i, j] := R end if

end do

end do;

print(A)

end proc

Thí dụ.

L:=non_attacking_rooks_pos([[1,2],[1,3],[2,1],[2,3],

[3,2],[3,4],[3,5],[5,4]],5,5):nops(L);

for i from 1 to 4 do array_rooks(L[i],5); end do;

Khi đó kết quả trên màn hình sẽ là số các cách sắp xếp 5 quân xe lên bàn cờ 5\times 5 với miền các vị trí cấm như trên là bằng 18, và 4 cách sắp xếp đầu tiên:

i152.photobucket.com/albums/s165/dumb_boy1988/maple.jpg

Dĩ nhiên để liệt kết hết ta thay 4 trong vòng for bằng nops(L).

Giải thuật cũng áp dụng được đối với các sự sắp xếp các quân xe lên các bảng vuông không có vị trí cấm.

Thí dụ. Đa thức xe của các bảng

Ta làm như sau:

rook_polynomial([],4,x);
rook_polynomial([],5,x);

Kết quả là:

1 + 16 x + 72 x^2 + 96 x^3 + 24 x^4
1 + 25 x + 200 x^2 + 600 x^3 + 600 x^4 + 120 x^5

Tài liệu tham khảo

Abigail Mitchell, A block decomposition algorithm for computing rook polynomials}; preprint at http://arxiv.org/abs/math/0407004v1

William Oscar Jules Moser, The number of very reduced Latin rectangles; Canad. J. Math. 19 (1967) pp. 1011-1017.

Earl Glen Whitehead Jr, Four-discordant permutations; Journal of the Australian Mathematical Society (Series A)(1979), 28, pp. 369-377.

Joseph M. Santmyer, Five discordant permutations; Graphs and Combinatorics (1993), 9, pp. 279-292.

K.P. Kohas, Rook numbers and Rook Polynomials; MCCME, Moskva – 2003 (in Russian).

Richard P. Stanley, Enumerative Combinatorics, Volume 1; Cambridge University Press, 1999.

Mehdi Hassani, Derangements and Applications; Journal of Integer Sequences, Vol. 6 (2003).

Jay R. Goldman, J. T. Joichi, Dennis E. White, Rook Theory. I: Rook Equivalence of Ferrers Boards; Proceedings of the American Mathematical Society, Vol. 52, No. 1 (Oct., 1975), pp. 485-492.

Jay R. Goldman, J. T. Joichi, David L. Reiner, Dennis E. White, Rook Theory. II: Boards of Binomial Type; SIAM Journal on Applied Mathematics, Vol. 31, No. 4 (Dec., 1976), pp. 618-633.

D. C. Foata and M. P. Schutzenberger, On the Rook Polynomials of Ferrers Relations; Colloq. Math. Soc. Janos Bolyai, 4, Combinatorial Theory and its Applications, vol. 2, 1970.

John Riordan, An introdoction to Combinatorial Analysis, Moskva 1963 (in Russian)

http://www.usna.edu/Users/math/wdj/teach/sm342/rook_polynomials.html

http://mathworld.wolfram.com/notebooks/Combinatorics/RookPolynomial.nb

D. C. Fielder, A Generator of Rook Polynomials; Mathematica J. 9 (2004), pp. 371-375.

Categories: Combinatorics