1
$\begingroup$

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

2 Answers 2

2

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.

  • 0
    I see. Thanks for the explanation.2011-10-31
1

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

  • 0
    @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$.2011-10-17