Change of a variable in a generating function

217 Views Asked by At

Assuming I have a generating function

$$\sum_n c(m,n,k)x^n=\left(x\frac{1-x^m}{1-x~~~}\right)^k$$

(mentioned in this answer where $c$ represents the number of compositions of $n$ to $k$ parts of size at most $m$)

Is there some way to transform this generating function so that it would generate the same sequence with respect to $m$ ? In other words, how can

$$\sum_m c(m,n,k)x^m$$

be expressed ?

2

There are 2 best solutions below

0
On BEST ANSWER

Probably not.

Suppose you want to find $$ h_{n,k}(y) = \sum_{m\geq1} c(m,n,k)y^m = \sum_{m\geq 1}y^m [x^n]\left(x\frac{1-x^m}{1-x}\right)^k = \sum_{m\geq1}y^m [x^n]g_{m,k}(x). $$ You basically need to find the $n$-th coefficient in the generating function, and then re-sum over $m$. This is harder than summing the generating function over $m$, and this probably isn't some simple transformation of $g_{m,k}(x)$ because the new generating function will be a power series in a different variable ($y$, not $x$) with the index $m$ independent of $n$.

Trying to compute $c(m,n,k)$ as the coefficient of $x^n$ in $g_{m,k}(x)$, I get $$ c(m,n,k) = \sum_{p\geq0} \left(\begin{array}{c}n-mp-1\\k-1\end{array}\right) \binom{k}{p}(-1)^p [n\geq mp+k]. $$

It is possible that $h_{n,k}(y)$ has a closed form, and I can't quite rule out that it has a closed form in terms of a generalized hypergeometric function in $y$, but it is unlikely that it has one. The (inner) sum $$ \sum_{0\leq m\leq (n-k)/p} \left(\begin{array}{c}n-mp-1\\k-1\end{array}\right) y^m $$ does not have a closed form that I could find, for example. Also, if you note that $c(m,n,k)$ as expressed above is a polynomial $q_{n,k}(m)$ of degree $k-1$ in $m$, then $$ h_{n,k}(y) = \sum_{m\geq0}q_{n,k}(m) y^m = q_{n,k}(\vartheta_y)\frac1{1-y}, \qquad \vartheta_y = y \frac{d}{dy}, $$ i.e. given by applying a degree-$(k-1)$ polynomial of a differential operator to $(1-y)^{-1}$. Neither of these approaches suggests that there might exist a closed form.

0
On

This doesn't answer your question in any nice way, but is too long for a comment. Here we express the coefficients $c(m,n,k)$ as a sum over multinomial coefficients.

We have $c(1,n,k)=\delta_{n k}$. Assume $m\ge 2$. Applying the multinomial theorem we find $$\begin{eqnarray*} \left(x\frac{1-x^m}{1-x}\right)^k &=& \left(\sum_{j=1}^m x^{j}\right)^k \\ &=& \sum_{k_1+\ldots +k_m=k}{k\choose k_1,\ldots,k_m} \prod_{1\le j\le m} (x^j)^{k_j} \\ &=& \sum_{k_1+\ldots +k_m=k}{k\choose k_1,\ldots,k_m} x^{\sum_{j=1}^m j k_j} \\ &=& \sum_{k_1,\ldots,k_{m-1}=0}^k {k\choose k_1,\ldots,k_{m-1},k-\sum_{j=1}^{m-1}k_j} x^{m k - \sum_{j=1}^{m-1} k_j(m-j)} \\ &=& \sum_{n=k}^{m k} c(m,n,k)x^{n}, \end{eqnarray*}$$ where $$\begin{eqnarray*} c(m,n,k) &=& \sum_{k_1,\ldots,k_{m-2}=0}^k {k\choose k_1,\ldots,k_{m-2},\hat k_{m-1},\hat k_m} \\ \hat k_{m-1} &=& m k - n - \sum_{j=1}^{m-2}k_j(m-j) \\ \hat k_m &=& n - k(m-1) + \sum_{j=1}^{m-2}k_j (m-j-1). \end{eqnarray*}$$ (The bounds on $n$ are got by enforcing the condition $\hat k_{m-1},\hat k_m \ge 0$.)

Case $m=2$: $$\begin{eqnarray*} c(2,n,k) &=& {k\choose 2k-n,n-k} \\ &=& {k\choose n-k} \end{eqnarray*}$$ Therefore, $$\begin{eqnarray*} \sum_{n=k}^{2k}c(2,n,k)x^n &=& \sum_{n=k}^{2k}{k\choose n-k}x^n \\ &=& x^k(1+x)^k \\ &=& \left(x\frac{1-x^2}{1-x}\right)^k \end{eqnarray*}$$ as expected.

Case $m=3$: $$\begin{eqnarray*} c(3,n,k) &=& \sum_{j=0}^k {k\choose j,3k-n-2j,n-2k+j} \\ &=& \sum_{j=0}^k {3k-n-j\choose 3k-n-2j} {k\choose n-2k+j} \end{eqnarray*}$$