Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given positive numbers $n,m,d$, what is the number of tuples $(z_1,\dots,z_n),$ such that $z_i\in \mathbb{Z}^{(\geq 0)}\forall i=1,\dots,n$ and $z_1+2z_2+\dots+nz_n=m, z_1+\dots+z_n=d$?

share|cite|improve this question
up vote 2 down vote accepted

Let $\Sigma_n(m,d)$ denote the set of solutions and $\sigma_n(m,d)$ its cardinal. Let $n\geqslant2$ and $(z_1,\ldots,z_n)$ in $S_n(m,d)$. Then $z_2+2z_3+\cdots+(n-1)z_n=m-d$ and $z_2+\cdots+z_n=d-z_1$ hence $(z_2,\ldots,z_n)$ is in $\Sigma_{n-1}(m-d,d-z_1)$. The correspondance is one-to-one hence $\sigma_n(m,d)=\sum\limits_{k\leqslant d}\sigma_{n-1}(m-d,k)$. Introducing the generating functions of the families of coefficients $(\sigma_n(m,d))_{m,d}$, one gets $$ S_n(x,y)=\sum\limits_{m,d\geqslant0}\sigma_n(m,d)x^my^d=\sum\limits_{m,d}\sum\limits_{k\leqslant d}\sigma_{n-1}(m-d,k)x^{m}y^d. $$ Using the change of indices $p=m-d$, $$ S_n(x,y)=\sum\limits_{p,k\geqslant0}\sigma_{n-1}(p,k)t_{p,k}(x,y),\qquad t_{p,k}(x,y)=\sum\limits_{m,d}x^my^d[d\geqslant k,m=p+d]. $$ One sees that $$ t_{p,k}(x,y)=\sum\limits_{d=k}^{+\infty}y^dx^{p+d}=x^p(xy)^k(1-xy)^{-1}, $$ hence, for every $n\geqslant2$, $$ S_n(x,y)=\sum\limits_{p,k\geqslant0}\sigma_{n-1}(p,k)x^p(xy)^k(1-xy)^{-1}=S_{n-1}(x,xy)(1-xy)^{-1}. $$ Iterating this and using the fact that $\sigma_1(m,d)=[m=d]$ hence $S_1(x,y)=(1-xy)^{-1}$, one gets, for every $n\geqslant1$, $$ S_n(x,y)=(1-xy)^{-1}(1-x^2y)^{-1}\cdots(1-x^ny)^{-1}. $$ Extracting(1) the coefficient of $y^d$, one gets $$ \sum\limits_{m\geqslant0}\sigma_n(m,d)x^m=\sum\limits_{k=1}^nx^{dk}\prod\limits_{1\leqslant i\leqslant n}^{i\ne k}(1-x^{i-k})^{-1}. $$ Formula from which one could finally extract the coefficient of $x^m$ to get $\sigma_n(m,d)$.

(1) To do so, one considers $S_n(x,y)$ as a rational fraction in $y$. Since the denominator is the product of the distinct irreducible monomials $1-x^ky$, the partial fraction decomposition of $S_n(x,y)$ is a sum of $c_k(x)(1-x^ky)^{-1}$, for some coefficients $c_k(x)$ that are rational fractions in $x$. To compute $c_k(x)$, one multiplies $S_n(x,y)$ by $1-x^ky$ and one evaluates the result at $y=x^{-k}$. Expanding each $(1-x^ky)^{-1}$ as a power series in $y$, one sees that the coefficient of $y^d$ in $S_n(x,y)$ is the sum over $k$ of $c_k(x)x^{kd}$. Done.

share|cite|improve this answer
I did not follow the extraction of the y-coefficient, but the expression before corresponds exactly to the sum of my final expression as a consequence of the q-binomial theorem. – Phira Oct 31 '11 at 11:32
@Phira, see added footnote. Thanks for your feedback. – Did Oct 31 '11 at 12:44
I see. Thanks for the explanation. – Phira Oct 31 '11 at 12:53

For a partition $\lambda_1\ge \lambda_2\ge \dots$, we can instead cound the numbers $z_i$ of cycles of length $i$.

Therefore, you want to count partitions of $m$ that have $d$ parts of size at most $n$.

It is well-known that the generating function of partitions of at most $a$ parts of site at most $b$ is given by the $q$-binomial coefficient $$\left[\begin{smallmatrix}a+b\\a\end{smallmatrix}\right]_q=\frac{\prod_{k=1}^{a+b}(1-q^k)}{\prod_{k=1}^{a}(1-q^k)\prod_{k=1}^{b}(1-q^k)}.$$

If you first remove 1 from each part, you see that your generating function is $$q^d\left[\begin{smallmatrix}d+n-1\\d\end{smallmatrix}\right]_q,$$

where you want to extract the coefficient of $q^m$.

share|cite|improve this answer
I want to know how the calculate this number, does there exists a reference for such type of question? As you mention: " the number of permutations of m elements with d cycles of size at most n ." – ougao Oct 16 '11 at 14:44
Thanks Phira, perhaps this is what I want, although it still needs some calculation. Since I expect a close formula that only involves the given number $n,m,d$ to express the answer. – ougao Oct 16 '11 at 23:02
it seems that your answer is not right, consider$n=2,m=5,d=4$,only one choice is possible$(z_1,z_2)=(3,1)$ – ougao Oct 17 '11 at 4:12
@ougao Your example now is the coefficient of $q^5$ in $q^4(1-q^5)/(1-q)$ which is the coefficient of $q$ in $1+q+q^2+q^3+q^4$. – Phira Oct 17 '11 at 13:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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