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 ?


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.


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*}$$


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.