Generalized rook polynomials (Q1584670): Difference between revisions

A Ferrers board \((h_1,\dots, h_n)\) is a board which takes the lower \(h_i\) cells of the \(i\)th column of the \(n\times N\) chessboard where \(0\leq h_1\leq\cdots\leq h_n\). The theory of non-taking rooks on Ferrers boards was first developed by \textit{D. Foata} and \textit{M. P. Schützenberger} [Comb. Theory Appl., Colloq. Math. Soc. János Bolyai 4, 413-436 (1970; Zbl 0217.01802)]. \textit{J. R. Goldman} et al. [Proc. Am. Math. Soc. 52, 485-492 (1975; Zbl 0312.05002)] showed that their rook polynomial of a Ferrers board completely factors into linear polynomials over the nonnegative integers. In the present paper the authors introduce the \(i\)-creation rook placement rule where \(i\) new rows, on which rooks may subsequently be placed, are drawn above and to the right in the row where a rook is placed (\(i= 0\) is classic rook placement). The \(i\)-rook number \(r^{(i)}_k(B)\) of a Ferrers board \(B\) is the number of \(i\)-creation rook placements of \(k\) non-taking rooks on \(B\) where \(r^{(i)}_0(B)= 1\). The \(i\)-rook polynomial of \(B\) is \(r^{(i)}(B, x)= \sum^n_{k=0} r^{(i)}_k(B) x^{(n- k,i-1)}\) where \(x^{(n,m)}= x(x+ m)\cdots (x+ (n-1)m)\) and \(x^{(0,m)}\equiv 1\). The authors show that \(r^{(i)}(B, x)= \prod^n_{j=1} (x+ h_j+ (j-1)(i-1))\) for a Ferrers board \(B= (h_1,\dots, h_n)\). The \(m\)-jump board \(J_{n,m}\) is the Ferrers board \((0,m,2m,\dots, (n-1)m)\). From the factorization theorem, \(r^{(1)}(J_{n,1}, x)= x^{(n,1)}\) so that \(r^{(1)}_k(J_{n, 1})\) is the unsigned Stirling number of the first kind \({\mathfrak s}(n,n-k)\); two bijective proofs are also given (the superscript (i) in Theorem 3.1 should be (1)). Two bijective proofs are given that \(r^{(2)}_k(J_{n,1})\) is the number of \(k\)-edge matchings in the complete graph \(K_{n+k-1}\). Consequently, \(\sum^{n+1}_{k=0} r^{(2)}_k(J_{n+1,1}) x^k\) is the Bessel polynomial of degree \(n\). The Abel board \(A_n\) is the \(n\)-column Ferrers board \((0,n,\dots, n)\). From the factorization theorem, \(r^{(1)}(A_n, x)= x(x+ n)^{n-1}\) (a special Abel polynomial) so that \(r^{(1)}_k(A_n)\) is the number of labelled forests on \(n\) vertices composed of \(n-k\) rooted trees; a bijective proof is also given (the sum for \(r^{(1)}(A_n, x)\) in the paper should run from \(0\) to \(n-1\)). Finally, a weighted generalization of the classic rook polynomial is given and a factorization theorem and reciprocity theorem proven for them. The paper concludes by giving \(q\)-analogs of several results.