Question

[Lê Song Phương]

 Cho bàn cờ \(C\) bất kỳ gồm \(m\) hàng và \(n\) cột, đa thức quân xe của bàn cờ \(C\) được định nghĩa như sau:

 \(R\left(C,x\right)=r_0\left(C\right)+r_1\left(C\right)x+...+r_k\left(C\right)x^k+...=\sum\limits^{\infty}_{k=0}r_k\left(C\right)x^k\)

 trong đó \(r_k\left(C\right)\) là số cách xếp \(k\) con xe không "ăn nhau" trên bàn cờ \(C\).

  a) Gọi \(C_d,C_c\) là bàn cờ tương ứng có được khi đổi chỗ hai dòng bất kì và hai cột bất kì của \(C\). Chứng minh rằng \(R\left(C,x\right)=R\left(C_d,x\right)=R\left(C_c,x\right)\)

  b) Hai bàn cờ \(A,B\) gọi là hai bàn cờ độc lập nếu không có ô vuông vào của A và B chung hàng hoặc chung cột. VD trong hình thì A và B là hai bàn cờ độc lập:

                                    

 Chứng minh rằng nếu A, B là hai bàn cờ độc lập thì \(R\left(A\cup B,x\right)=R\left(A,x\right).R\left(B,x\right)\)

 c) Ta gọi một miền ô vuông \(S\) của \(C\) là block của bàn cờ \(C\) nếu thỏa mãn các điều kiện sau:

 i) Với bất kì hai dòng \(i,i'\) chứa ô của \(S\) và cột \(j\) không chứa ô nào của \(S\) thì hai ô \(\left(i;j\right)\) và \(\left(i';j\right)\) hoặc cùng là ô vuông của \(C\) hoặc không cùng là ô vuông của \(C\).

 ii) Với bất kì hai cột \(j,j'\) chứa ô của \(S\) và dòng \(i\) không chứa ô nào của \(S\) thì hai ô \(\left(i;j\right)\) và \(\left(i;j'\right)\) hoặc cùng là ô vuông của \(C\) hoặc không cùng là ô vuông của \(C\).

 (Lưu ý: Nếu \(C\) là bàn cờ gồm các ô vuông thì mỗi ô vuông của \(C\) được xem là một block của \(C\))

 Ví dụ trong hình thì vùng màu cam là block của bàn cờ \(C\):

                                            

 Cho \(C\) là bàn cờ các ô vuông có block S nằm trên \(m\) dòng và \(n\) cột, đặt \(p=min\left\{m,n\right\}\). Với mỗi \(0\le k\le p\), kí hiệu \(D_k\left(S\right)\) là bàn cờ có được từ bàn cờ \(C\) sau khi thực hiện các bước sau:

 1. Bỏ tất cả các ô của \(S\).

 2. Bỏ tất cả các ô thuộc \(k\) dòng tùy ý trong số \(m\) dòng của \(S\).

 3. Bỏ tất cả các ô thuộc \(k\) cột tùy ý trong số \(n\) cột chứa các ô của \(S\).

Chứng minh rằng đa thức quân xe của bàn cờ \(C\) là:

 \(R\left(C,x\right)=\sum\limits^p_{k=0}r_k\left(S\right)x^kR\left(D_k\left(S\right),x\right)\).