Generalized rook polynomials
type: Item
instance of: scholarly article
title: Generalized rook polynomials
zbMATH Open document ID: 0992.05009
author: J. Haglund
author: Jay R. Goldman
published in: Journal of Combinatorial Theory. Series A
publication date: 2002-09-11T00:00:00Z
review text: 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 factoriza…
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A30
zbMATH DE Number: 1525321
zbMATH Keywords: Ferrers board
zbMATH Keywords: rook polynomial
zbMATH Keywords: rook placement
zbMATH Keywords: factorization theorem
MaRDI profile type: Publication
full work available at URL: jcta.2000.3113
OpenAlex ID: W2090969274
cites work: Proofs from THE BOOK
cites work: Q4375247
cites work: The path-cycle symmetric function of a digraph
cites work: A short proof of the rook reciprocity theorem
cites work: On the cover polynomial of a digraph
cites work: Statistical problems involving permutations with restricted positions
cites work: Rook placements and cellular decomposition of partition varieties
cites work: An interpretation for Garsia and Remmel's \(q\)-hit numbers
cites work: Q5620607
cites work: Q-counting rook configurations and a formula of Frobenius
cites work: Q3035283
cites work: Stirling polynomials
cites work: Rook Theory. I.: Rook Equivalence of Ferrers Boards
cites work: Rook theory. III: Rook polynomials and the chromatic structure of graphs
cites work: Rook Theory-IV. Orthogonal Sequences of Rook Polynomials
cites work: Rook Theory. II: Boards of Binomial Type
cites work: Bessel polynomials
cites work: Rook theory and hypergeometric series
cites work: \(q\)-rook polynomials and matrices over finite fields
cites work: The problem of the rooks and its applications
cites work: Q5675806
cites work: Generating Functions for Bessel and Related Polynomials
cites work: Q3243274
cites work: Q3726126
DOI: 10.1006/JCTA.2000.3113
description: scientific article; zbMATH DE number 1525321