Home > Combinatorics > Lý thyết các quân xe

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
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: