Let $F_n^{(k)}(x)= \sum_j {\binom{n+(k-1)j}{kj} x^j}$ and $G_n^{(k)}(x)= \sum_j {\binom{n+j}{kj} x^j}.$

I am interested in the coefficients ${a_{n,k,j}}$ such that $$G_n^{(k)}(x)=\sum_{j\geq0 }{a_{n,k,j}} F_j^{(k)}((-1)^ { k}x).$$ Computations suggest the following:

Let $z\sum_{j\geq 0}C_{1,j}^{(k)}z^j$ be the inverse series of $\sum_{j=1}^k (-1)^{j-1}z^j$ and let $(\sum_{j\geq 0}C_{1,j}^{(k)}z^j)^m=\sum_{j\geq 0}C_{m,j}^{(k)}z^j.$ Then $$ a_{n,k,j}=(-1)^{k j}C_{kj+1,n-(k-1)j}^{(k-1)}.$$ Any idea how to prove this?

Remark: $C_{1,n}^{(2)}=C_n$ are the Catalan numbers and

$( C_{1,n}^{(3)})_{n\geq 0}=(1,1,1,0,-4,-14,-30,-33,\dots).$ (cf. OEIS, A103779).

Edit: Perhaps the following observation may be useful. A matrix inversion theorem of Gould and Hsu implies a similar result: The coefficients $c_{n,k,j}$ which give $$\sum_j {c_{n,k,j}} F_j^{(k)}(x)=x^n$$ are $(-1)^{n-j} A_{n-j,k,kj+1}$ where $A_{n,k,r}=\frac{r}{kn+r}\binom{kn+r}{n}$ are Fuss-Catalan numbers. Here we have $\sum_{n}A_{n,k,r}x^n=(\sum_{n}A_{n,k,1}x^n)^r $ and $ x\sum_{n}A_{n,k,1}x^{(k-1)n}$ is the inverse series of $y-y^k.$ Is there a combinatorial or other reason for the appearance of these special inverse series?


1 Answer 1


These assertions can be proved using (formal) generating functions. Using that for $j\geq 0, k\geq 1$ \begin{align*} \sum_{n\geq 0} {n-j+kj \choose kj} t^n &=\frac{t^j}{(1-t)^{kj+1} }\;\;\mbox{ and }\\ \sum_{n\geq 0}{n+j \choose kj} t^n&=\frac{t^{kj-j}}{(1-t)^{kj+1}}\;\;\;, \end{align*} gives that \begin{align*} \sum_{n\geq 0} t^n F_n^{(k)}(x) &=\frac{1}{1-t}\,\frac{1}{1-\frac{xt}{(1-t)^k}}\;\;\mbox{ and }\\ \sum_{n\geq 0} t^n G_n^{(k)}(x) &=\frac{1}{1-t}\,\frac{1}{1-\frac{xt^{k-1}}{(1-t)^k}}\;\;\;, \end{align*}

(I) consider first the (simpler) Gould-Hsu case. Here $c_{n,k,j}= (-1)^{n-j} [t^{n-j} ]\, C_k(t)^{kj+1}$ where $C_k(t)$ denotes the $k$-ary tree function, which is defined by $$C_k(t)=1+tC_k(t)^k\;\;\;.$$ Thus \begin{align*} \sum_{j\geq 0} c_{n,k,j} F_j^{(k)}(x)&=\sum_{j\geq 0} F_j^{(k)}(x)(-1)^{n-j}[t^{n-j}]C_k(t)^{kj+1}\\ &=\sum_{j\geq 0} F_j^{(k)}(x)(-1)^{n-j}[t^{n}] t^j C_k(t)^{kj+1}\\ &=(-1)^n [t^n] \sum_{j\geq 0} F_j^{(k)}(x)(-1)^{j}t^j C_k(t)^{kj+1}\\ &=(-1)^n [t^n] \frac{C_k(t)}{1+tC_k(t)^k}\frac{1}{1+\frac{xtC_k(t)^k}{(1+tC_k(t)^k)}^k}\\ &=(-1)^n [t^n] \frac{1}{1+xt}=x^n\\ \end{align*}

(II) now to your case above. Here $a_{n,k,j}=(-1)^{kj}[t^{n-(k-1)j}] A_{k-1}(t)^{kj+1}$ where $yA_k(y)$ is the inverse of $y(z)=\sum_{j=1}^k (-1)^{j-1} z^j$ . A similar computation as above here gives \begin{align*} \sum_{j\geq 0} a_{n,k,j} F_j^{(k)}((-1)^kx)&=[t^n] \frac{A_{k-1}(t)}{1-T(t)} \frac{1}{1- (-1)^k\frac{T(t)x}{(1-T(t))^k}} \end{align*} where $T(t):=(-1)^kt^{k-1}A_{k-1}(t)^k$. This will simplify to the generating function for the $G_n^{(k)}$ if
$$\frac{A_{k-1}(t)}{1-T(t)}=\frac{1}{1-t}\;\;.$$ And this in turn follows (for $k\geq 2$) with simple steps after substituting $x=tA_{k-1}(t)$ in the equality $$t=\frac{x+(-1)^{k-1}x^k}{1+x}$$.

(III) The Ansatz $b_{n,k,j}=[t^n] T(t)^j Z(t)$ leads to the generating function \begin{align*} \frac{Z(t)}{1-T(t)} \frac{1}{1- \frac{T(t)x}{(1-T(t))^k}} \end{align*} for $R_n(x):=\sum_{j \geq 0} b_{n,k,j} F_j^{(k)}(x)$. One will expect this to be a simple function of $t$ only if $\frac{Z(t)}{1-T(t)}$ and $\frac{T(t)}{(1-T(t))^k}$ simplify to simple functions of $t$, i.e. can be "solved" for $t$. The targetet generating functions more or less require that $Z=C_k, T=-tC_k^k $ in case (I), resp. that $Z=A_{k-1}, T=-t^{k-1}A_{k-1}$ in case (II), this explains the appearance of these special inverse series.

  • $\begingroup$ Thank you for this beautiful answer. $\endgroup$ Jan 26 at 9:06

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.