ルーク多項式

長方形のm  × n のボードB _{m , n}に対して、 R _m,n := R _{B m , n}と書き、m = nの場合は、R _n := R _{m , n}と書きます。     

n  × nの正方形盤面における最初のいくつかのルーク多項式は次のとおりです。 

${\displaystyle {\begin{aligned}R_{1}(x)&=x+1\\R_{2}(x)&=2x^{2}+4x+1\\R_{3}(x)&=6x^{3}+18x^{2}+9x+1\\R_{4}(x)&=24x^{4}+96x^{3}+72x^{2}+16x+1.\end{aligned}}}$

言葉で説明すると、1  ×  1の盤面では、ルーク1個を1通りの方法で配置でき、ルーク0個を1通りの方法で配置することもできます（空の盤面）。2  ×  2の盤面では、ルーク2個を2通りの方法で配置でき（対角線上）、ルーク1個を4通りの方法で配置でき、ルーク0個を1通りの方法で配置できます。より大きな盤面についても同様です。

長方形チェス盤のルーク多項式は、次の恒等式によって一般化ラゲール多項式L _n ^α ( x ) と密接に関連している。

${\displaystyle R_{m,n}(x)=n!x^{n}L_{n}^{(mn)}(-x^{-1}).}$

ルーク多項式の先駆けとなるのは、H.E. Dudeney ^{[ 5 ]}による古典的な「8 個のルークの問題」です。この問題では、チェス盤上の攻撃しないルークの最大数は、主対角線上に配置することで 8 個になることが示されています (図 1)。問われているのは、「8 × 8 のチェス盤に 8 個のルークを配置して、どちらも他のルークを攻撃しないようにする方法は何通りあるか」です。答えは「明らかに、すべての行とすべての列にルークがなければなりません。一番下の行から始めると、最初のルークは8つの異なるマスのいずれかに置くことができることは明らかです（図1）。どこに置いたとしても、2行目の2番目のルークには7つのマスから選択できます。次に、3行目には6つのマスから、4行目には5つのマスから選択できます。以下同様です。したがって、異なる方法の数は 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320 でなければなりません（つまり、8 !です。ここで「!」は階乗です）。^{[ 6 ]}

同じ結果を少し異なる方法で得ることができます。各ルークに、そのランク番号に対応する位置番号を与え、そのファイルの名前に対応する名前を付けます。つまり、ルーク a1 は位置 1 で名前が「a」、ルーク b2 は位置 2 で名前が「b」などとなります。次に、ルークを位置順に並べたリスト (シーケンス) を作成します。すると、図 1 の図は (a,b,c,d,e,f,g,h) のシーケンスに変換されます。ルークを別のファイルに配置するには、これまで 2 番目のファイルを占めていたルークを、最初のルークが空けたファイルに移動する必要があります。たとえば、ルーク a1 を「b」ファイルに移動すると、ルーク b2 を「a」ファイルに移動する必要があります。すると、これらはそれぞれルーク b1 とルーク a2 になります。新しいシーケンスは (b,a,c,d,e,f,g,h) になります。組み合わせ論では、この操作は順列と呼ばれ、順列の結果として得られる数列は、与えられた数列の順列です。8つの要素からなる数列から8つの要素を含む順列の総数は8!（ 8の階乗）です。

「ルーク同士が攻撃してはならない」という制約の影響を評価するには、そのような制約がない場合を考えてみるのが良いでしょう。8×8のチェス盤に8個のルークを配置する方法の数は、 64個のマス目に8個のルークを配置する組み合わせの総数に等しくなります。

${\displaystyle {64 \choose 8}={\frac {64!}{8!(64-8)!}}=4,426,165,368.}$

したがって、「ルーク同士が攻撃してはならない」という制約により、許容される局面の総数は組み合わせから順列へと減少し、これは約109,776分の1になります。

人間の活動のさまざまな分野における多くの問題は、「ルーク問題」という定式化を与えることで、ルーク問題に還元することができます。例として、ある会社がn人の従業員をn種類の異なる仕事に雇用し、各仕事は1人の従業員のみが行う必要があるとします。この雇用方法はいくつあるでしょうか？

n × nのチェス盤の列に労働者を配置し、ファイルに仕事を配置します。労働者iが仕事jに任命された場合、列i とファイルjが交差するマスにルークが置かれます。各仕事は 1 人の労働者によってのみ実行され、各労働者は 1 つの仕事にのみ任命されるため、盤上にn個のルークが配置される結果、すべての列とファイルには 1 つのルークのみが含まれます。つまり、ルーク同士は攻撃しません。  

古典的なルーク問題では、ルーク多項式の最高次項の係数であるr ₈の値がすぐにわかります。実際、その結果として、8 個の攻撃しないルークを 8 × 8 のチェス盤上に配置する方法はr ₈ = 8! = 40320 通りあります。

この問題を一般化するために、 m × n の盤面、つまりm行 (ランク) とn列 (ファイル) を持つ盤面を考えてみましょう。問題は次のようになります。m × nの盤面にk 個のルークを配置して、互いに攻撃し合わないようにする方法は何通りありますか？

問題が解決可能であるためには、k はmとnの小さい方以下でなければならないことは明らかです。そうでなければ、ルークのペアをランクまたはファイル上に置くことを避けられません。この条件が満たされているとします。すると、ルークの配置は 2 つのステップで実行できます。まず、ルークを配置するk個のランクのセットを選択します。ランクの数はmであり、そのうちk を選択する必要があるため、この選択は次のように行うことができます。${\displaystyle {\binom {m}{k}}}$同様に、ルークを配置するk 個のファイルのセットは次のように選択できます。${\displaystyle {\binom {n}{k}}}$方法。ファイルの選択はランクの選択に依存しないため、積のルールによれば、${\displaystyle {\binom {m}{k}}{\binom {n}{k}}}$ルークを置くマスを選ぶ方法。

しかし、 kランクとkファイルでk ²マスが交差するため、タスクはまだ完了していません。使用されていないランクとファイルを削除し、残りのランクとファイルをまとめて圧縮すると、kランクとkファイルからなる新しい盤面が得られます。このような盤面では、k個のルークをk ! 通りの方法で配置できることがすでに示されています(互いに攻撃しないように)。したがって、攻撃しないルークの配置の総数は次のとおりです。^{[ 7 ]}

${\displaystyle r_{k}={\binom {m}{k}}{\binom {n}{k}}k!={\frac {n!m!}{k!(nk)!(mk)!}}。$

例えば、通常のチェス盤（8×8）には3つのルークを配置できます。${\displaystyle \textstyle {\frac {8!8!}{3!5!5!}}=18,816}$方法。k = m = n の場合、上記の式はr k = n ! を与え、これ_は古典的なルーク問題で得られた結果に対応します。

明示的な係数を持つルーク多項式は次のようになります。

${\displaystyle R_{m,n}(x)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}k!x^{k}=\sum _{k=0}^{\min(m,n)}{\frac {n!m!}{k!(nk)!(mk)!}}x^{k}.}$

「ルーク同士が攻撃してはならない」という制約を取り除くと、m × n のマス目から任意のk個のマス目を選ばなければならない。これは次のように行うことができる。

${\displaystyle {\binom {mn}{k}}={\frac {(mn)!}{k!(mn-k)!}}}$ 方法。

k 個のルークが何らかの点で互いに異なる場合（例えば、ラベルが付けられていたり、番号が付けられていたりする場合）、これまでに得られたすべての結果をk !（ k個のルークの順列の数）で乗算する必要があります。

ルークの問題をさらに複雑にするために、ルークが攻撃しないだけでなく、盤上で対称的に配置されることを要求してみましょう。対称性の種類によっては、これは盤を回転させたり、反転させたりすることと同等です。対称的な配置は、対称性の条件に応じて多くの問題を引き起こします。^{[ 8 ] [ 9 ] [ 10 ] [ 11 ]}

これらの配置の中で最も単純なのは、ルークが盤の中心に対して対称である場合です。n 個のルークがn列nファイルある盤上に配置された配置の数をG _nとします。次に、盤を 2 n列 2 nファイルを持つようにします。最初のファイル上のルークは、そのファイルの 2 n個のマス目のいずれにも配置できます。対称条件によれば、このルークの配置は最後のファイル上のルークの配置を決定します。つまり、最初のルークに対して盤の中心に対して対称に配置されなければなりません。最初のファイルと最後のファイル、およびルークが占めている列を取り除きます (列の数は偶数なので、取り除かれたルークは同じ列には置けません)。これにより、2 n − 2 ファイル 2 n − 2 列の盤が得られます。新しい盤上のルークの対称配置には、元の盤上のルークの対称配置が対応していることは明らかです。したがって、G _{2 n} = 2 nG _{2 n − 2} (この式の係数 2 nは、最初のルークが最初の列の 2 n個のマス目のいずれにも配置できる可能性から来ています)。上記の式を繰り返すと、2 × 2 の盤の場合に到達し、そこには (対角線上に) 2 つの対称配置があります。この繰り返しの結果、最終的な式はG _{2 n} = 2 ⁿ n ! となります。通常のチェス盤 (8 × 8) の場合、G ₈ = 2 ⁴ × 4! = 16 × 24 = 384 通りの 8 個のルークの中央対称配置があります。そのような配置の 1 つを図 2 に示します。              

奇数サイズの盤面（2 n  +  1 ランクと 2 n  +  1 ファイルを含む）では、対称的な2つを持たないマスが必ず存在します。これが盤面の中央のマスです。このマスには必ずルークが置かれなければなりません。中央のファイルとランクを取り除くと、2 n × 2 n の盤面に 2 n個のルークが対称的に配置されます。したがって、このような盤面では、再びG _{2 n + 1} = G _{2 n} = 2 ⁿ n ! となります。    

もう少し複雑な問題は、盤を 90° 回転させても変化しない非攻撃配置の数を求めることです。盤には 4 n本のファイルと 4 n段があり、ルークの数も 4 nであるとします。この場合、最初のファイルにあるルークは、角のマスを除いて、このファイルの任意のマスを占めることができます (90° 回転させた後、互いに攻撃し合う 2 つのルークが存在することになるため、ルークは角のマスには配置できません)。そのルークに対応する他の 3 つのルークがあり、それぞれ最後の段、最後のファイル、最初の段にあります (これらは最初のルークを 90°、180°、270° 回転させることで得られます)。これらのルークのファイルと段を取り除くと、必要な対称性を持つ (4 n  −  4) × (4 n − 4) の盤のルーク配置が得られます。したがって、次の漸化式が得られます。R _{4 n} = (4 n − 2) R _{4 n − 4}、ここでR _nはn × n盤の配置の数です。 繰り返して、R _{4 n} = 2 n (2 n − 1)(2 n − 3)...1 となります。 (4 n + 1) × (4 n + 1) 盤の配置の数は4 n × 4 n盤の配置の数と同じです。これは、(4 n + 1) × (4 n + 1) 盤では、1 つのルークが必ず中央に配置される必要があり、中央のランクとファイルを取り除くことができるためです。 したがって、R _{4 n + 1} = R _{4 n}です。 伝統的なチェス盤 ( n = 2 ) の場合、回転対称性を持つ可能な配置はR ₈ = 4 × 3 × 1 = 12 通りです。                                  

(4 n  +  2) × (4 n + 2) および (4 n + 3) × (4 n + 3) の盤面の場合、解の数はゼロです。各ルークには 2 つのケースが考えられます。中央に置かれているか、中央に置かれないかの 2 つのケースです。後者の場合、このルークは、盤面を 90° 回転させたときにマス目を交換するルーク カルテットに含まれます。したがって、ルークの総数は 4 n (盤面に中央のマス目がない場合) または 4 n + 1 のいずれかでなければなりません。これにより、R _{4 n + 2} = R _{4 n + 3} = 0 であることが証明されます。                

n × n盤上の、 n 個の非攻撃ルークの対角線 (確定性のために、チェス盤上の a1–h8 に対応する対角線) に対称な配置の数は、漸化式Q _n = Q _{n − 1} + ( n − 1) Q _{n − 2で定義される}電話番号で与えられます。この漸化式は次のように導出されます。最初の列のルークは、底の隅のマスにあるか、別のマスにあるかのどちらかであることに注意してください。最初のケースでは、最初の列と最初のランクを取り除くと、( n − 1) × ( n − 1) 盤上にn − 1 個のルークの対称配置になります。このような配置の数はQ _{n − 1}です。2 番目のケースでは、元のルークに対して、選択された対角線に関して最初のルークと対称な別のルークがあります。これらのルークの列と行を取り除くと、( n - 2) × ( n - 2)盤上にn - 2個のルークが対称的に配置されます。このような配置の数はQn _{- 2であり}、ルークは最初の列のn - 1マスに置くことができるため、これを行う方法は( n - 1) Qn _{- 2}通りあり、すぐに上記の漸化式が得られます。対角線対称配置の数は、次の式で与えられます_。                                  

${\displaystyle Q_{n}=1+{\binom {n}{2}}+{\frac {1}{1\times 2}}{\binom {n}{2}}{\binom {n-2}{2}}+{\frac {1}{1\times 2\times 3}}{\binom {n}{2}}{\binom {n-2}{2}}{\binom {n-4}{2}}+\cdots .}$

この式は、すべてのルーク配置をクラスに分割することによって導出されます。クラスsには、 s組のルークが対角線上にない配置が含まれます。まったく同じ方法で、 n × n盤上のn個のルーク配置のうち、互いに攻撃せず、両方の対角線に対して対称である配置の数は、漸化式B _{2 n} = 2 B _{2 n − 2} + (2 n − 2) B _{2 n − 4}およびB _{2 n + 1} = B _{2 n}で与えられることが示せます。          

別のタイプの一般化は、盤面の対称性によって互いに得られるルークの配置を 1 つとして数えるものです。たとえば、盤面を 90 度回転させることが対称性として許容される場合、90 度、180 度、または 270 度の回転によって得られる配置は、元のパターンと「同じ」とみなされます。ただし、これらの配置は、盤面が固定されている元の問題では別々に数えられます。このような問題について、Dudeney ^{[ 12 ]}は次のように述べています。「単なる反転や鏡像を異なるものとして数えない場合、何通りの配置があるかはまだ決定されていません。これは難しい問題です。」この問題は、Burnside の補題を使用して対称的な配置を数える問題に帰着します。