3
$\begingroup$

I've seen a number of combinatorial interpretations for the coefficients of the compositional inverse (aka reversion) of a power series. Is there a known combinatorial interpretation for the coefficients of the reciprocal of a power series?

Specifically: I'm looking for a family of combinatorially defined sets $S_0, S_1, S_2, \ldots$, with $S_n$ consisting of objects of "size" $n$, such that for a power series $a_0+a_1x+a_2x^2+\ldots$ ($a_0 \neq 0$) with reciprocal $b_0+b_1x+b_2x^2 \ldots$, $b_n$ can be understood as a weighted sum over $S_n$, with the weighting depending in some reasonable way on the $a_i$'s.

$\endgroup$
9
$\begingroup$

Since $a_0+a_1x+a_2x^2+\cdots=a_0(1+(a_1/a_0)x+(a_2/a_0)x^2+\cdots)$, we can assume $a_0=1$. Then $$ b_n = \sum (-1)^k a_{i_1}\cdots a_{i_k}, $$ where the sum is over all $2^{n-1}$ compositions $(i_1,\dots,i_k)$ of $n$. Thus we can take $S_n$ to be the set of compositions of $n$, etc.

$\endgroup$
6
$\begingroup$

In his thesis Ira Gessel provides a method which gives a combinatorial interpretation of the inverse of a counting series of a linked set. A counting series is a generalization of a generating function. Some applications on the technique in the thesis are to things like symmetric functions and formal power series in countably many variables. For the single variable case, see Theorem 4.5 on page 45 which computes the inverse of a single variable generating function for some lattice paths. I will breifly summarize and give some simple examples below to make this answer a little more self-contained.

Let $P$ be a set and $S \subseteq P^*$ be a subset of the free monoid (we actually want $S$ be a linear system which is defined in the thesis). For any $V \subseteq S$ we define its conuting series to be $\Gamma(V) = \sum_{\alpha \in V} \alpha$ which is a formal sum. We also define the alternating counting series $\bar{\Gamma}(V) = \sum_{\alpha \in V} (-1)^{r(\alpha)} \alpha$ where $r(\alpha)$ is the number of prime factors in $\alpha$ (i.e. length of the word). For any $\alpha = a_1a_2 \cdots a_n$ the links of $\alpha$ are $a_i a_{i+1}$. Take some set a links $L \subseteq P^2$ and define $C$ to be the set of $\alpha \in S$ such that all links of $\alpha$ are in $L$. Also let $\bar{C}$ be the set of $\alpha \in S$ such that all links of $\alpha$ are not in $L$. On page 37 we have Theorem 4.1 (The Inversion Theorem) we states $\Gamma(C) \bar{\Gamma}(\bar{C}) = 1$. Now let's use this for some single variable generating functions.

For a trivial example let $S = P^*$ where $P$ is a set of size $k$. Then let $L = P^2$. In this case $\Gamma(C) = \sum_{w \in P^*} w$ is the sum of all $k$-ary words and $\bar{\Gamma}(\bar{C}) = 1 - \sum_{a \in P} a$. If we subsitute $a = x$ for all $a \in P$ we get the $\Gamma(C)$ becomes $\sum_{n \geq 0} k^n x^n$ and $\bar{\Gamma}({\bar{C}})$ becomes $1 - kx$.

For a less trivial example let $S = P^* = \{a,b\}^*$ and let $L = \{aa,ab,ba\}$. Then $\Gamma(C)$ is the sum of all binary words which have no consecutive $b$'s and $\bar{\Gamma}(\bar{C}) = 1 - a - b + b^2 - b^3 + \cdots$. Again substituting $a = b = x$ we have $$1 + 2x + 3x^2 + 5x^3 + \cdots = \frac{1}{1 - 2x + x^2 - x^3 + \cdots}$$ the inverse of an "almost" Fibonacci generating function.

$\endgroup$
  • 2
    $\begingroup$ It should be pointed out that this theorem was found earlier by Ralph Fröberg, Determination of a class of Poincaré series. Mathematica Scandinavica, 37(1) 29–39, 1975 and L. Carlitz, R. Scoville, and T. Vaughan, Enumeration of pairs of sequences by rises, falls and levels. Manuscripta Mathematica, 19, 211–243, 1976. $\endgroup$ – Ira Gessel Jul 3 '16 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.