integer partition with negative numbers

Question

Let $d > 0$. I am trying to find the ways of having $$ \lvert n_1 \rvert + \cdots + \lvert n_d \rvert =k $$ And $$ \lvert n_1 \rvert + \cdots + \lvert n_d \rvert \leq k $$ for some fixed $k \geq 0$ and $(n_1,\dots,n_d) \in \mathbb{Z}^d$. I know this problem is well known if we replace $\mathbb{Z}$ with $\mathbb{Z}_{>0}$ or $\mathbb{Z}_{\geq 0}$. But I am not sure what to do in the general case, I also suppose the second quantity is easy to compute having the first one.

Answer 1

A pretty easy way is to use generating functions. Let's denote the number of solutions $(n_1,\ldots,n_d)\in\mathbb{Z}^d$ of $|n_1|+|n_2|+\ldots+|n_d|=k$ by $N(k,d)$, and similarly use $N_{\geqslant 0}(k,d)$ for $\mathbb{Z}_{\geqslant 0}$, etc. Then $$\sum_{k\geqslant 0}N_{\geqslant 0}(k,d)z^k=(1+z+z^2+z^3+\ldots)^d=\frac{1}{(1-z)^d};\\\sum_{k\geqslant 0}N_{>0}(k,d)z^k=(z+z^2+z^3+\ldots)^d=\frac{z^d}{(1-z)^d};\\\sum_{k\geqslant 0}N(k,d)z^k=(1+2z+2z^2+2z^3+\ldots)^d=\frac{(1+z)^d}{(1-z)^d}.$$ Now the binomial series gives the well-known formula $N_{\geqslant 0}(k,d)=\binom{k+d-1}{d-1}$ (which also has a well-known combinatorial interpretation). Yet another way to get it is to use Cauchy's integral formula $$N_{\geqslant 0}(k,d)=\frac{1}{2\pi i}\oint_{|z|=r}\frac{dz}{z^{k+1}(1-z)^d},$$ say, where $0<r<1$; the substitution $z=1/w$ gives $$N_{\geqslant 0}(k,d)=\frac{1}{2\pi i}\oint_{|w|=1/r}\frac{w^{k+1}}{(1-1/w)^d}\frac{dw}{w^2}=\frac{1}{2\pi i}\oint_{|w|=1/r}\frac{w^{k+d-1}~dw}{(w-1)^d},$$ and the same formula tells now that $N_{\geqslant 0}(k,d)$ is the coefficient of $z^{d-1}$ in $(z+1)^{k+d-1}$, as expected.

For $N(k,d)$, these approaches are not that fruitful. The generating function gives the formula $$N(k,d)=\sum_{r=0}^{d}\binom{d}{r}\binom{k+r-1}{d-1}$$ (obtained by expanding $(1+z)^d$ and [re]using the expansion of $(1-z)^{-d}$). And Cauchy tells $$N(k,d)=[z^{d-1}](z+1)^{k-1}(z+2)^d=\sum_{r=1}^{d}2^r\binom{d}{r}\binom{k-1}{r-1}.$$ While both formulae do have combinatorial interpretations (which ones?..), these don't give a closed-form expression for $N(k,d)$. And I believe there's none (in a well-defined sense; one may try to state it properly, and even prove it, looking at the methods developed here). There is another book you may find interesting; the present question is dealt with in section 2.5 (essentially the same way, but the book gives a far broader view).