Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Journal of Combinato...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Journal of Combinatorial Theory Series A
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Journal of Combinatorial Theory Series A
Article . 2000
License: Elsevier Non-Commercial
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Journal of Combinatorial Theory Series A
Article . 2000 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2000
Data sources: zbMATH Open
DBLP
Article . 2024
Data sources: DBLP
versions View all 5 versions
addClaim

Generalized Rook Polynomials

Generalized rook polynomials
Authors: Jay Goldman; James Haglund;

Generalized Rook Polynomials

Abstract

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.

Keywords

forests, binomial type, absolute Stirling numbers, Abel polynomials, multiset permutations, Exact enumeration problems, generating functions, rook placement, rook polynomial, Theoretical Computer Science, rook theory, factorization theorem, Computational Theory and Mathematics, \(q\)-calculus and related topics, Bessel polynomials, Discrete Mathematics and Combinatorics, Ferrers board

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    17
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
17
Top 10%
Top 10%
Average
hybrid