What alternatives are there to the binomial poset theory of generating function families?

Question

A natural question in combinatorics is, why are certain families of generating functions combinatorially useful, like $\Sigma_n a_n x^n$ and $\Sigma_na_n\frac{x^n}{n!}$, why are other families are not, like $\Sigma_na_n\frac{x^n}{n^2+1}$? Doubilet, Rota, and Stanley proposed in this 1972 paper that $\Sigma a_n\frac{x^n}{B_n}$ is combinatorially useful if and only if $B_n$ is the factorial function of some binomial poset. They justify this on the basis of an isomorphism between the reduced incidence algebra of a binomial poset and the ring of formal power series (viewed as an algebra).

But my question is, what alternate theories are there concerning when a family of generating function is and is not combinatorially useful?

This 1978 paper by Richard Stanley contains the following statement:

Two abstract theories of generating functions have been formulated to try to solve this problem - the Doubilet-Rota-Stanley theory of “reduced incidence algebras”, and the Bender-Goldman theory of “prefabs” (cf. also the “dissect” theory of M. Henley which combines features of both the preceding theories).

But I’m not familiar with either the prefab theory or the dissect theory, so can anyone tell me what alternative account they give for which families of generating functions are combinatorially meaningful? And also have additional theories been developed since Stanley wrote this in 1978? For instance, does Joyal’s theory of combinatorial species address which families of generating functions are combinatorially meaningful?

Answer 1

This is just a comment, but too long to fit in the 600 character limit. It would be interesting for someone to compile a list of all functions $B(n)$ for which some combinatorial use has been found for a generating function $\sum a_n\frac{x^n}{B(n)}$. Moreover, for which of these functions $B(n)$ can an example of such a generating function be given that can be explained in a natural way by some existing theory (binomial posets, prefabs, dissects, species, $\dots$)? For example, what about $B(n)=(q^n-1)(q^n-q)\cdots(q^n-q^{n-1})$, which occurs in the enumeration of linear transformations over $\mathbb{F}_q$ (EC1, second ed., Section 1.10)? This function $B(n)$ is the factorial function of a binomial poset (see EC1, second ed., Example 3.18.3(c) and last sentence of Example 3.18.3(e)), but can this poset actually be used to obtain some of the generating functions in EC1, Section 1.10?

Answer 2

For Bender and Goldman's theory of prefabs, see http://www.iumj.indiana.edu/docs/20060/20060.asp.

Michael Henle's theory of dissects is introduced in Dissection of generating functions, Studies in Appl. Math. 51 (1972), 397–410. A follow-up paper is available at https://www.ams.org/journals/tran/1975-202-00/S0002-9947-1975-0357133-8/S0002-9947-1975-0357133-8.pdf.

Joyal’s theory of combinatorial species does not address which families of generating functions are combinatorially meaningful.

Answer 3

Let $\mathcal{E}$ be the poset of all idempotent matrices over $\mathbb{F}_q$ having only finitely many nonzero entries with the ordering $A \leq B$ iff $AB=BA=A$. Then $\mathcal{E}$ is a binomial poset with factorial function $B(n) = \frac{\gamma_n}{(q-1)^n} $ where $\gamma_n = |GL_n(\mathbb{F}_q)|$. Here are some examples of generating functions of the form $\sum_{n \geq 0}a_n\frac{x^n}{B(n)}$ that stem directly from the binomial poset $\mathcal{E}$ and the isomorphism from the reduced incidence algebra to the ring of formal power series. Let $E_{\mathcal{E}}(u) = \sum_{n \geq 0}\frac{u^n}{B(n)} $

Let $a_n$ be the number of idempotent matrices in $\text{Mat}_n(\mathbb{F}_q)$.

$\displaystyle \sum_{n \geq 0}a_n \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}= E_\mathcal{E}^2(u)$

Let $a_{n,k}$ be the number of idempotent matrices in $\text{Mat}_n(\mathbb{F}_q)$ having rank $k$.

$\displaystyle \sum_{n \geq 0}\sum_{k=0}^{n} a_{n,k} v^k \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}= E_\mathcal{E}(v u) E_\mathcal{E}(u)$

Let $a_n$ be the number of relations in the poset $\mathcal{E}_n$, i.e., the number of ordered pairs $(A,B)$ such that $A \leq B$ with $A,B \in \mathcal{E}_n $.

$\displaystyle \sum_{n \geq 0}a_n \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}= E_\mathcal{E}^3(u)$

Let $a_n$ be the number of covering relations in the poset $\mathcal{E}_n$, i.e., the number of ordered pairs $(A,B)$ such that $A$ is covered by $ B$ with $A,B \in \mathcal{E}_n $.

$\displaystyle \sum_{n \geq 0}a_n \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}= u E_\mathcal{E}^2(u)$

Let $a_n$ be the number of diagonalizable matrices in $\text{Mat}_n(\mathbb{F}_q)$.

$\displaystyle \sum_{n \geq 0}a_n \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}= E_\mathcal{E}^q(u)$

Let $a_n$ be the number of diagonalizable matrices in $\text{Mat}_n(\mathbb{F}_q)$ having rank $k$.

$\displaystyle \sum_{n \geq 0}\sum_{k=0}^{n}a_{n,k}v^k \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}= E_\mathcal{E}(u) E_\mathcal{E}^{q-1}(v u)$

Let $a_{n,k}$ be the number of diagonalizable matrices in $GL_n(\mathbb{F}_q)$ with exactly $k$ distinct eigenvalues.

$\displaystyle \sum_{n \geq 0}\sum_{k=0}^{q}a_{n,k}v^k \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}=(v E_\mathcal{E}( u) - v +1)^q$

Let $a_{n}$ be the number of direct sum decompositions of $\mathbb{F}_q^n$.

$\displaystyle \sum_{n \geq 0}a_n \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}= \exp(E_{\mathcal{E}}(u) -1)$

Let $a_{n,k}$ be the number of direct sum decompositions of $\mathbb{F}_q^n$ into exactly $k$ subspaces.

$\displaystyle \sum_{n \geq 0}\sum_{k=0}^{q}a_{n,k}v^k \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}=\exp(v (E_{\mathcal{E}}(u) -1))$

Let $a_n$ be the number of periodic matrices, i.e., elments that are contained in some (maximal) subroup of $\text{Mat}_n(\mathbb{F}_q)$. In other words, $ \displaystyle a_n = \sum_{e \in \mathcal{E}_n}|G_e|$.

$\displaystyle \sum_{n \geq 0}a_n \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}=E_{\mathcal{E}}(u) /(1- (q-1)u)$

Let $a_{n,k}$ be the number of ordered direct sum decompositions of $\mathbb{F}_q^n$ into exactly $k$ subspaces.

$\displaystyle \sum_{n \geq 0}\sum_{k=0}^{q}a_{n,k}v^k \frac{u^n}{\frac{\gamma_n}{(q-1)^n}}=1/(1- v (E_{\mathcal{E}}(u) -1))$

Substituting $v = -1$ in the generating function above gives $\frac{1}{E_{\mathcal{E}}(u)}$ (the image of the Moebius function $\mu$ under our isomorphism). So for the poset $\mathcal{E}_n$, we have that $\mu(\hat{0},\hat{1})$ is equal to the number of ordered direct sum decompositions of $\mathbb{F}_q^n$ into an even number of subspaces minus the number of such decompositions into an odd number of subspaces. This is an instance of Phillip Hall's Theorem.