# counting tuples with restricted condition

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$?

-

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.

-
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$.

-
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