Utente:Grasso Luigi/sandbox4/Polinomio della torre

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Una disposizione di 8 torri su una griglia 8×8, con due qualsiasi torri che non hanno riga o colonne in comune.

In matematica combinatoria, un polinomio della torre o polinomio di Riordan (dal matematico che ne diede il nome) si riferisce ad un polinomio generatore che fornisce informazioni sul numero di modi di inserire delle torri in posizioni non adiacenti su una griglia (notazione $\operatorname {B}$ che sta per board) simile ad una scacchiera; quindi due torri qualsiasi non possono stare sulla stessa riga o colonna. Il profilo o griglia è un sottoinsieme qualsiasi dei quadrati di una scacchiera rettangolare con m righe e n colonne; la immaginiamo come le caselle in cui è consentito mettere una torre. Il profilo B diventa la normale scacchiera se tutti i quadrati sono permessi con m = n = 8 oppure di dimensione qualsiasi con m = n. In genere il polinomio ha la seguente notazione

$\operatorname {R} _{B}(x)\ =\ \operatorname {R} (x,B)\ =\ 1+r_{1}x_{1}+\ldots +r_{k}x_{k}+\ldots +r_{n}x_{n}$

Il valore di $r_{0}=1$ indica una board B senza torri. Il coefficiente del generico elemento x ^k indica il numero di modi di disporre k torri, con il vincolo di non adiacenza (le torri sono disposte in modo tale che non ci siano coppie di torri nella stessa riga o colonna), sui quadretti del profilo B. Tale disposizione colloca le torri su un profilo immobile; ma anche se ruotiamo o riflettiamo B il polinomio non cambia. Lo stesso dicasi se scambiamo righe o colonne.

Il termine "polinomio della torre" was coined by John Riordan. Despite the name's derivation from chess, the impetus for studying rook polynomials is their connection with counting permutations (or partial permutations) with restricted positions.

Interest in rook placements arises in pure and applied combinatorics, group theory, number theory, and statistical physics. The particular value of rook polynomials comes from the utility of the generating function approach, and also from the fact that the zeroes of the rook polynomial of a board provide valuable information about its coefficients, i.e., the number of non-attacking placements of k rooks.

Definizioni

Profilo generico e concetto di non adiacenza della torre posizionata nel punto (m,1)

Il polinomio delle torri R(x) di una griglia B formata da N quadretti è la funzione generatrice che indica il numero di collocazioni di torri con il vincolo a priori di non adiacenza:

$\operatorname {R} (x,B_{N})\ =\ \operatorname {R} _{B_{N}}(x)\ =\sum _{k=0}^{\leqslant \min {(m,n)}}r_{k}(B_{N})\ x^{k}\quad B_{N}\subseteq B_{m,n}$

dove $r_{k}(B_{N})$ è il numero di modi a posizionare k torri non adiacenti sul profilo B. Esiste un numero massimo di torri non adiacenti che il profilo può contenere; in effetti, non possono esserci più torri del numero di righe o colonne del profilo rettangolare che lo contiene. (cioè $\min(m,n)$).

Profili completi (quadrati o rettangoli) senza vincoli

Il polinomio di un insieme di quadretti a forma rettangolare m × n che si denota B_m,n, ha la scrittura

$\operatorname {R} _{m,n}(x)\ =\ \operatorname {R} (x,B_{m,n})\ =\ \sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}\ k!\ x^{k}\ =\ n!x^{n}L_{n}^{(m-n)}(-x^{-1})$

la prima forma verrà dimostrata nella sezione sui profili completi, mentre la seconda stabilisce un legame con il polinomio di Laguerre generalizzato L_n^α(x). In particolare per un insieme quadrato, $m=n$ abbiamo

$\operatorname {R} _{n}(x)\ =\ \operatorname {R} (x,B_{n})\ =\ =\ \sum _{k=0}^{n}\ {\binom {n}{k}}^{2}\ k!\ x^{k}=\ r_{0}x^{0}+r_{1}x^{1}+\cdots r_{n}x^{n}$

dove la successione di numeri $r\ =\ (r_{0},\ r_{1},\cdots ,r_{k},\cdots ,r_{n})$ vengono detti numeri delle torri. Riportiamo i primi 5 polinomi, detti a quadretti bianchi (w dall'inglese white) o senza vincoli di posizione:

${\begin{aligned}R_{1}(x)&=1+x&&r=(1,1)\\R_{2}(x)&=1+4x+2x^{2}&&r=(1,4,2)\\R_{3}(x)&=1+9x+18x^{2}+6x^{3}&&r=(1,9,18,6)\\R_{4}(x)&=1+16x+72x^{2}+96x^{3}+24x^{4}&&r=(1,16,72,96,24)\\R_{5}(x)&=1+25x+200x^{2}+600x^{3}+600x^{4}+120x^{5}&&r=(1,25,200,600,600,120).\end{aligned}}$

da notare che il termine $r_{n}={\binom {n}{n}}^{2}\ n!=n!$ ed indica il numero di permutazioni (o disposizioni sulla board) effettuabili sull'insieme di numeri od oggetti $X=\{1,2,\ldots ,n\}$, mentre $r_{k}$ indica il numero di configurazioni sulla board che si possono effettuare con insiemi di oggetti o numeri $X=\{1,2,\ldots ,k\}$. Quindi, ciò vuole dire che su un profilo 1 × 1, 1 torre si può collocare in un solo modo, e 0 torri possono stare in 1 solo modo (profilo B vuoto); su 2 × 2 board, 2 torri possono essere posizionate in 2 modi (sulle diagonali), 1 torre si colloca in 4 modi, 0 torri in 1 modo; stesso per profili n × n.

Profili completi (quadrati o rettangoli) con vincoli

Adesso per la board si utilizza la notazione

$B_{n}^{b}=\{(i,j)|i,j=1,2,\ldots ,n\}$

dove le coppie indicano le posizioni di vincolo sul quadrato e l'apice b indica quadretti grigio-scuro (b-black) sulla board. L'altra board da considerare è quella del complemento o il profilo dei quadretti bianchi o senza vincoli (w-white). Possiamo associare i seguenti due polinomi:

$\operatorname {R} (x,B_{n}^{b})=\sum _{k=0}^{n}\ r_{k}\ x^{k}=\ r_{0}x^{0}+r_{1}x^{1}+\cdots r_{n}x^{n}$

adesso i numeri torri vincolate non si possono calcolare in maniera semplice come prima ma occorre tenere conto del particolare profilo dei quadretti di vincoli. Si parte da profili semplici. si utilizzano le due proprietà fondamentali:

1. Formula di espansione
2. Formula del prodotto nell'ipotesi di board disgiunte

per giungere al polinomio della torre. Calcolato $\operatorname {R} (x,B_{n}^{b})$, è semplice calcolare quella della board complemento come segue:

$\operatorname {R} (x,B_{n}^{w})=\sum _{k=0}^{n}\ (-1)^{k}\ R_{n-k}\ r_{k}^{b}\ x^{k}=\ R_{n}r_{0}^{b}x^{0}-R_{n-1}r_{1}^{b}x^{1}+\cdots R_{0}r_{n}^{b}x^{n}$

ottenenendo i numeri torre libere $r^{w}\ =\ (r_{0}^{w},r_{1}^{w},\ldots ,r_{n}^{w})$, in particolare l'ultimo numero indica il numero di permutazioni che soddisfano ai vincoli imposti alla loro posizione $(i,\pi (i)=j)$.

For incomplete square n × n boards, (i.e. rooks are not allowed to be played on some arbitrary subset of the board's squares) computing the number of ways to place n rooks on the board equivale a calcolare il permanente di una matrice formata da 0–1.

Permutazioni e profili quadrati

Consideriamo una generica permutazione nelle due notazioni comuni

$\pi _{2l}={\begin{pmatrix}1&2&3&\cdots &i&\cdots &n\\\pi (1)&\pi (2)&\pi (3)&\cdots &\pi (i)&\cdots &\pi (n)\end{pmatrix}}.$

$\pi _{1l}=\pi (1)\;\pi (2)\;\pi (3)\;\cdots \;\pi (i)\cdots \;\pi (n)$

Un profilo B sottinsieme di una griglia quadrata formata da n × n quadretti corrisponde ad una permutazione degli n oggetti, cioè dell'insieme $X=\{1,2,\ldots ,n\}$, in modo che il numero j = π(i) nella i-esima posizione delle notazioni comuni corrisponde al numero di colonna di una casella o quadretto nella riga i di B.

Polinomi di accoppiamento

Un polinomio della torre è un caso particolare di un tipo di polinomio di accoppiamento, cioè una funzione generatrice del numero di accoppiamenti di k-archi in un grafo.

The rook polynomial R_m,n(x) corresponds to the complete bipartite graph K_m,n . The rook polynomial of a general board B ⊆ B_m,n corresponds to the bipartite graph with left vertices v₁, v₂, ..., v_m and right vertices w₁, w₂, ..., w_n and an edge v_iw_j whenever the square (i, j) is allowed, i.e., belongs to B. Thus, the theory of rook polynomials is, in a sense, contained in that of matching polynomials.

We deduce an important fact about the coefficients r_k, which we recall given the number of non-attacking placements of k rooks in B: these numbers are unimodal, i.e., they increase to a maximum and then decrease. This follows (by a standard argument) from the theorem of Heilmann and Lieb about the zeroes of a matching polynomial (a different one from that which corresponds to a rook polynomial, but equivalent to it under a change of variables), which implies that all the zeroes of a rook polynomial are negative real numbers.

Profili B completi

Problema delle 8 torri

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Fig. 1. The maximal number of non-attacking rooks on an 8 × 8 chessboard is 8. Rook + dots mark the number of squares on a rank, available to each rook, after placing the rooks on the lower ranks.

A precursor to the rook polynomial is the classic "Eight rooks problem" by H. E. Dudeney in which he shows that the maximum number of non-attacking rooks on a chessboard is eight by placing them on one of the main diagonals (Fig. 1). The question asked is: "In how many ways can eight rooks be placed on an 8 × 8 chessboard so that neither of them attacks the other?" The answer is: "Obviously there must be a rook in every row and every column. Starting with the bottom row, it is clear that the first rook can be put on any one of eight different squares (Fig. 1). Wherever it is placed, there is the option of seven squares for the second rook in the second row. Then there are six squares from which to select the third row, five in the fourth, and so on. Therefore the number of different ways must be 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320" (that is, 8!, dove la notazione "!" indica l'operazione di fattoriale).

The same result can be obtained in a slightly different way. Let us endow each rook with a positional number, corresponding to the number of its rank, and assign it a name that corresponds to the name of its file. Thus, rook a1 has position 1 and name "a", rook b2 has position 2 and name "b", etc. Then let us order the rooks into an ordered list (sequence) by their positions. The diagram on Fig. 1 will then transform in the sequence (a,b,c,d,e,f,g,h). Placing any rook on another file would involve moving the rook that hitherto occupied the second file to the file, vacated by the first rook. For instance, if rook a1 is moved to "b" file, rook b2 must be moved to "a" file, and now they will become rook b1 and rook a2. The new sequence will become (b,a,c,d,e,f,g,h). In combinatorics, this operation is termed permutation, and the sequences, obtained as a result of the permutation, are permutations of the given sequence. The total number of permutations, containing 8 elements from a sequence of 8 elements is 8! (factorial of 8).

${\begin{aligned}\operatorname {R} (x,B)&=\sum _{k=0}^{8}\ {\binom {8}{k}}^{2}\ k!\ x^{k}={\binom {8}{0}}^{2}\ 0!\ x^{0}+{\binom {8}{1}}^{2}\ 1!\ x^{1}+{\binom {8}{2}}^{2}\ 2!\ x^{2}+{\binom {8}{3}}^{2}\ 3!\ x^{3}+{\binom {8}{4}}^{2}\ 4!\ x^{4}+{\binom {8}{5}}^{2}\ 5!\ x^{5}+{\binom {8}{6}}^{2}\ 6!\ x^{6}+{\binom {8}{7}}^{2}\ 7!\ x^{7}+{\binom {8}{8}}^{2}\ 8!\ x^{8}\\&=1+64x+1568x^{2}+18816x^{3}+117600x^{4}+376320x^{5}+564480x^{6}+322560x^{7}+40320x^{8}\\\end{aligned}}$

To assess the effect of the imposed limitation "rooks must not attack each other", consider the problem without such limitation. In how many ways can eight rooks be placed on an 8 × 8 chessboard? This will be the total number of combinations of 8 rooks on 64 squares:

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

Thus, the limitation "rooks must not attack each other" reduces the total number of allowable positions from combinations to permutations which is a factor of about 109,776.

A number of problems from different spheres of human activity can be reduced to the rook problem by giving them a "rook formulation". As an example: A company must employ n workers on n different jobs and each job must be carried out only by one worker. In how many ways can this appointment be done?

Let us put the workers on the ranks of the n × n chessboard, and the jobs − on the files. If worker i is appointed to job j, a rook is placed on the square where rank i crosses file j. Since each job is carried out only by one worker and each worker is appointed to only one job, all files and ranks will contain only one rook as a result of the arrangement of n rooks on the board, that is, the rooks do not attack each other.

Problema delle 8 torri generalizzato

Il classico problema delle torri fornisce immediatamente il valore di r₈, il coefficiente davanti al termine di ordine più alto del polinomio delle torri. Infatti, il suo risultato è che 8 torri non adiacenti possono essere disposte su una griglia con 8 × 8 quadretti in r₈ = 8! = 40320 modi. Generalizzando consideriamo una griglia con m × n quadretti, ovvero un profilo B con m righe ed n colonne Il problema diventa: in quanti modi si possono disporre k torri sulla griglia $\operatorname {B} _{m,n}$ in modo che non siano adiacenti?

È chiaro che affinché il problema sia risolvibile, k deve essere minore o uguale al più piccolo tra m e n; altrimenti non si può evitare di posizionare una coppia di torri sulla stessa riga o sulla stessa colonna (vincolo di non adiacenza). Cioè:

$k\leqslant \operatorname {min} (m,n)$

Quindi la disposizione delle torri può essere eseguita in due passaggi. Per prima cosa, scegliamo l'insieme di k righe su cui posizionare le torri. Poiché il numero di righe è m, di cui k devono essere scelte, questa scelta può essere fatta in ${\binom {m}{k}}$ modi. Allo stesso modo, l'insieme di k colonne su cui posizionare le torri può essere scelto in ${\binom {n}{k}}$ modi. Poiché la scelta delle colonne non dipende dalla scelta delle righe, secondo la regola dei prodotti ci sono ${\binom {m}{k}}{\binom {n}{k}}$ modi per scegliere la casella su cui posizionare la torre.

However, the task is not yet finished because k ranks and k files intersect in k² squares. By deleting unused ranks and files and compacting the remaining ranks and files together, one obtains a new board of k ranks and k files. It was already shown that on such board k rooks can be arranged in k! ways (so that they do not attack each other). Therefore, the total number of possible non-attacking rooks arrangements is:

$r_{k}={\binom {m}{k}}{\binom {n}{k}}k!={\frac {n!m!}{k!(n-k)!(m-k)!}}.$

For instance, 3 rooks can be placed on a conventional chessboard (8 × 8) in $\textstyle {\frac {8!8!}{3!5!5!}}=18,816$ ways. For k = m = n, the above formula gives r_k = n! that corresponds to the result obtained for the classical rooks problem.

The rook polynomial with explicit coefficients is now:

$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!(n-k)!(m-k)!}}x^{k}.$

If the limitation "rooks must not attack each other" is removed, one must choose any k squares from m × n squares. This can be done in:

${\binom {mn}{k}}={\frac {(mn)!}{k!(mn-k)!}}$ ways.

If the k rooks differ in some way from each other, e.g., they are labelled or numbered, all the results obtained so far must be multiplied by k!, the number of permutations of k rooks.

Symmetric arrangements

As a further complication to the rooks problem, let us require that rooks not only be non-attacking but also symmetrically arranged on the board. Depending on the type of symmetry, this is equivalent to rotating or reflecting the board. Symmetric arrangements lead to many problems, depending on the symmetry condition.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Fig. 2. A symmetric arrangement of non-attacking rooks about the centre of an 8 × 8 chessboard. Dots mark the 4 central squares that surround the centre of symmetry.

The simplest of those arrangements is when rooks are symmetric about the centre of the board. Let us designate with G_n the number of arrangements in which n rooks are placed on a board with n ranks and n files. Now let us make the board to contain 2n ranks and 2n files. A rook on the first file can be placed on any of the 2n squares of that file. According to the symmetry condition, placement of this rook defines the placement of the rook that stands on the last file − it must be arranged symmetrically to the first rook about the board centre. Let us remove the first and the last files and the ranks that are occupied by rooks (since the number of ranks is even, the removed rooks cannot stand on the same rank). This will give a board of 2n − 2 files and 2n − 2 ranks. It is clear that to each symmetric arrangement of rooks on the new board corresponds a symmetric arrangement of rooks on the original board. Therefore, G_2n = 2nG_2n − 2 (the factor 2n in this expression comes from the possibility for the first rook to occupy any of the 2n squares on the first file). By iterating the above formula one reaches to the case of a 2 × 2 board, on which there are 2 symmetric arrangements (on the diagonals). As a result of this iteration, the final expression is G_2n = 2ⁿn! For the usual chessboard (8 × 8), G₈ = 2⁴ × 4! = 16 × 24 = 384 centrally symmetric arrangements of 8 rooks. One such arrangement is shown in Fig. 2.

For odd-sized boards (containing 2n + 1 ranks and 2n + 1 files) there is always a square that does not have its symmetric double − this is the central square of the board. There must always be a rook placed on this square. Removing the central file and rank, one obtains a symmetric arrangement of 2n rooks on a 2n × 2n board. Therefore, for such board, once again G_2n + 1 = G_2n = 2ⁿn!.

A little more complicated problem is to find the number of non-attacking arrangements that do not change upon 90° rotation of the board. Let the board have 4n files and 4n ranks, and the number of rooks is also 4n. In this case, the rook that is on the first file can occupy any square on this file, except the corner squares (a rook cannot be on a corner square because after a 90° rotation there would 2 rooks that attack each other). There are another 3 rooks that correspond to that rook and they stand, respectively, on the last rank, the last file, and the first rank (they are obtained from the first rook by 90°, 180°, and 270° rotations). Removing the files and ranks of those rooks, one obtains the rook arrangements for a (4n − 4) × (4n − 4) board with the required symmetry. Thus, the following recurrence relation is obtained: R_4n = (4n − 2)R_4n − 4, where R_n is the number of arrangements for a n × n board. Iterating, it follows that R_4n = 2n(2n − 1)(2n − 3)...1. The number of arrangements for a (4n + 1) × (4n + 1) board is the same as that for a 4n × 4n board; this is because on a (4n + 1) × (4n + 1) board, one rook must necessarily stand in the centre and thus the central rank and file can be removed. Therefore R_4n + 1 = R_4n. For the traditional chessboard (n = 2), R₈ = 4 × 3 × 1 = 12 possible arrangements with rotational symmetry.

For (4n + 2) × (4n + 2) and (4n + 3) × (4n + 3) boards, the number of solutions is zero. Two cases are possible for each rook: either it stands in the centre or it doesn't stand in the centre. In the second case, this rook is included in the rook quartet that exchanges squares on turning the board at 90°. Therefore, the total number of rooks must be either 4n (when there is no central square on the board) or 4n + 1. This proves that R_4n + 2 = R_4n + 3 = 0.

The number of arrangements of n non-attacking rooks symmetric to one of the diagonals (for determinacy, the diagonal corresponding to a1–h8 on the chessboard) on a n × n board is given by the telephone numbers defined by the recurrence Q_n = Q_n − 1 + (n − 1)Q_n − 2. This recurrence is derived in the following way. Note that the rook on the first file either stands on the bottom corner square or it stands on another square. In the first case, removal of the first file and the first rank leads to the symmetric arrangement n − 1 rooks on a (n − 1) × (n − 1) board. The number of such arrangements is Q_n − 1. In the second case, for the original rook there is another rook, symmetric to the first one about the chosen diagonal. Removing the files and ranks of those rooks leads to a symmetric arrangement n − 2 rooks on a (n − 2) × (n − 2) board. Since the number of such arrangements is Q_n − 2 and the rook can be put on the n − 1 square of the first file, there are (n − 1)Q_n − 2 ways for doing this, which immediately gives the above recurrence. The number of diagonal-symmetric arrangements is then given by the expression:

$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 .$

This expression is derived by partitioning all rook arrangements in classes; in class s are those arrangements in which s pairs of rooks do not stand on the diagonal. In exactly the same way, it can be shown that the number of n-rook arrangements on a n × n board, such that they do not attack each other and are symmetric to both diagonals is given by the recurrence equations B_2n = 2B_2n − 2 + (2n − 2)B_2n − 4 and B_2n + 1 = B_2n.

Arrangements counted by symmetry classes

A different type of generalization is that in which rook arrangements that are obtained from each other by symmetries of the board are counted as one. For instance, if rotating the board by 90 degrees is allowed as a symmetry, then any arrangement obtained by a rotation of 90, 180, or 270 degrees is considered to be "the same" as the original pattern, even though these arrangements are counted separately in the original problem where the board is fixed. For such problems, Dudeney observes: "How many ways there are if mere reversals and reflections are not counted as different has not yet been determined; it is a difficult problem." The problem reduces to that of counting symmetric arrangements via Burnside's lemma.

Esempi

Famous examples include the number of ways to place n non-attacking rooks on:

• an entire n × n chessboard, which is an elementary combinatorial problem;

• consideriamo una board con i quadretti sulla diagonale proibiti; cioè un problema di calcolo sulle dismutazioni o "hat-check" (this is a particular case of the problème des rencontres);

$\operatorname {R} (x,B_{n}^{b})=\sum _{k=0}^{n}\ r_{k}\ x^{k}=\ r_{0}x^{0}+r_{1}x^{1}+\cdots r_{n}x^{n}$

calcolato $\operatorname {R} (x,B_{n}^{b})$, è semplice calcolare quella della board complemento come segue:

$\operatorname {R} (x,B_{n}^{w})=\sum _{k=0}^{n}\ (-1)^{k}\ R_{n-k}\ r_{k}^{b}\ x^{k}=\ R_{n}r_{0}^{b}x^{0}-R_{n-1}r_{1}^{b}x^{1}+\cdots R_{0}r_{n}^{b}x^{n}$

ed infine i polinomi hit diventano

$\operatorname {H} (x,B_{n}^{b})=\sum _{k=0}^{n}\ r_{k}^{b}\ (n-k)!\ (x-1)^{k}=\sum _{k=0}^{n}\ {\binom {n}{k}}\ (n-k)!\ (x-1)^{k}\ =\ \sum _{k=0}^{n}\ h_{k}x^{k}$

che ci danno la sequenza dei numeri rencontres $h^{b}=(h_{0},h_{1},\ldots ,h_{n})$, mentre l'altro polinomio è semplice da calcolare:

$\operatorname {H} (x,B_{n}^{w})=\sum _{k=0}^{n}\ r_{k}^{w}\ (n-k)!\ (x-1)^{k}=\sum _{k=0}^{n}\ h_{n-k}^{b}x^{k}$

cioè la sequenza invertita $h^{w}=(h_{n}^{b},h_{n-1}^{b},\ldots ,h_{0}^{b})$.

• consideriamo una board come prima, e aggiungiamo i quadretti sopra la diagonale e il quadretto in basso a sinistra, che viene associata per trovare la soluzione del problema dei ménages.

Note

Postille