Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
To give credit to the original sources, these polynomials (and the combinatorial interpretation in terms of the major index) were first studied in B. Gordon, Two theorems on multipartite partitions. J. London Math. Soc. 38 (1963) 459-464. However Gordon did not explicitly describe the combinatorial interpretation that he found in terms of the major index. This was done in D. P. Roselle, Coefficients associated with the expansion of certain products. Proc. Amer. Math. Soc. 45 (1974), 144-150.
What do you mean by combinatorially? Pólya's theorem is a special case of Burnside's lemma, which is proved by counting a set of ordered pairs in two different ways. The only part of the proof that you might call noncombinatorial is that the size of the orbit of a point under a finite group action is the index of the stabilizer of the point.
It seems that this theorem does not always give the exact power of $x-y$ dividing the determinant: if setting $x=y$ makes the rank go down by $k$ then $(x-y)^k$ is a factor of the determinant, but the highest power of $x-y$ dividing the determinant could be greater than $k$. I don't know of a stronger result that gives the exact power of $x-y$
The formula that Pemantle and Wilf attribute to Proctor is equivalent to a much older formula: the number of paths in the plane from the origin to the point $(a,b)$, where $a > pb$, that stay strictly below the line $x=py$, with steps $(1,0)$ and $(0,1$), is $$\frac{a-pb}{a+b}\binom{a+b}{a}.$$ This formula was apparently first stated by E. Barbier in 1887. A reference is Marc Renault, Four Proofs of the Ballot Theorem, Mathematics Magazine 80 (2007), 345--352; available online at webspace.ship.edu/msrenault/ballotproblem/….
Vladimir: I don't know of any representation-theoretic interpretation of this number. This formula is a special case of a determinant formula for counting plane partitions of a given shape with upper and lower bounds for the parts in each row (it's the case of one column). This more general formula is related to "flagged Schur functions", which are related to Schubert polynomials, but that's as far as my knowledge goes in this direction. Ralph: I have not seen a formula like your sum in the literature, and I don't know of a sign-free formula.
The polynomial is $p(j) = j^x$ where $x$ is a nonnegative integer. If $x=0$ this is $p(j)=1$. The derivation of the formula for the number of surjections from an $x$-element set to an $i$ element set, using either inclusion-exclusion or exponential generating functions, works perfectly well for $x<i$.
