# Partitions of $0$ and $1$ by integers in the interval $[-N,\ldots,N]$

### Background

Often one comes across the problem of trying to find the number of ways to partition a positive integer into a sum of nonnegative integers. There are three ways to partition the number 3, for example: \begin{align} 3 &= 3+0,\\ 3 &= 1+2,\\ 3 &= 1+1+1.\\ \end{align} The first two are a partitioning of $3$ into $2$ nonnegative integers. The last is a partitioning into $3$ nonnegative integers.

### The problem statement

On the other hand one could consider the number of ways to partition a number over a different set. I am interested in the case where the numbers "doing the partitioning" are drawn from the set $$S_N = [-N,\ldots,N]$$ (with repeats allowed) and the numbers to be partitioned are $0$ and $1$. In the general case, $m$ numbers are allowed to be chosen from $S_N$ to do the partitioning.

### Example

Suppose $N = 1$, so that $S_1 = \{-1,0,1\}$. Suppose first we look for partitions into two integers -- in other words, take $m =2$. Then $0$ can be partitioned into two integers from $S_1$ in the two distinct ways as shown below: \begin{align} 0 &= 0 + 0 \\ 0 &= 1 + (-1), \end{align} $1$ may be partitioned in only one way: \begin{align} 1 &= 1 + 0. \\ \end{align} For $m=3$, $0$ may be partitioned in two distinct ways again, \begin{align} 0 &= 0 + 0 + 0\\ 0 &= 1 + (-1) + 0, \end{align} whereas $1$ can now also be partitioned into two distinct ways, \begin{align} 1 &= 1 + 0 + 0\\ 0 &= 1 + 1 + (-1). \end{align}

### Is there a solution for the general case?

I am wondering if this problem can be solved in the general case (for all $N$ and $m$) in closed form. Literature references are welcome. Thanks!

Edit: to address the comments, in the case of $0$ ($1$), what I am looking for is indeed the coefficient of $x^m y^0$ ($x^m y^1$) in the formal series defined by $$g(x,y) = \frac{1}{\prod_{k=-N}^{k=+N}(1-x y^k)}.$$

• how many pairs of additive inverses are there ? that may be a start.
– user451844
Aug 11 '17 at 17:23
• One answer is that the number of $m$-way sums adding to $0$ is the constant coefficient in the generating function $(x^{-N}+\cdots+x^N)^m$. Aug 11 '17 at 17:26
• @GregMartin That would be the case where the order of parts is important. For a true analogue of partitions (of length $m$) we might need something like $\prod_{|k|\le N} (1 - yx^k)^{-1}$ and extract the coefficient of $x^0 y^m$ from that. Aug 11 '17 at 17:37
• @ErickWong Exactly -- getting that coefficient is essentially the whole problem. I've updated the post to reflect this. (Now I see I should have added this in the beginning.) Aug 11 '17 at 17:48
• very good point Erick! Aug 12 '17 at 22:14

Let $P(k,m,N)$ denote the number of distinct partitions of some integer $k$ into $m$ parts in the integer interval $[-N,\dots,N]$.

For each integer $-N\leq n\leq N$, let $LP(n\,;k,m,N)$ denote the number of distinct partitions of some integer $k$ into $m$ parts in the integer interval $[-N,\dots,N]$ and such that the value of (one of) its least part(s) is $n$.

Then we have

$$P(k,m,N)=\sum_{n=-N}^NLP(n\,;k,m,N)$$

Now, let $p$ be some partition counted by $LP(n\,;k,m,N)$. We may associate to $p$ a unique partition $\stackrel{\sim}{p}$ of $k-m(n-1)$ into $m$ parts in the integer interval $[1,\dots,N-(n-1)]$, and such that the value of (one of) its least part(s) is $1$. To that end, simply subtract $n-1$ from each part of $p$. Notice that, at this point, $\stackrel{\sim}{p}$ is a classical partition.

We may yet alter $\stackrel{\sim}{p}$ by removing (one of) its least part(s), thus obtaining some partition $p^*$ of $k-mn+(m-1)$ into $m-1$ parts in the integer interval $[1,\dots,N-(n-1)]$.

By conjugation, $p^*$ corresponds to a unique partition $\overline{p}$ of $k-mn+(m-1)$ into at most $N-(n-1)$ parts and with largest part $m-1$. Removing one largest part, we finally obtain a partition $\hat{p}$ of $k-mn$ into at most $N-n$ parts and with largest part at most $m-1$.

In the obvious notation, let $\hat{P}(k,N,m)$ count partitions in this way -- so that, for instance, our $\hat{p}$ above obtained from our initial $p$ would be counted by $\hat{P}(k-mn,N-n,m-1)$. Then we'd have

$$P(k,m,N)=\sum_{n=-N}^N\hat{P}(k-mn,N-n,m-1)$$

Partitions counted by $\hat{P}$ have been studied and are described via Gaussian binomial coefficients (or $q$-binomial coefficients; see $q$-analog).

We use $q^n\left[f(q)\right]$ to denote the coefficient of $q^n$ in the power series expansion of $f(q)$ about $0$. With this notation, we have

$$P(k,m,N)=\sum_{n=-N}^N\,q^{k-mn}\left[\binom{m-1+N-n}{N-n}_q\right]$$

Not sure how much simpler than your original answer this is. I guess it depends on how easy or efficient it is for you to calculate the polynomials $\binom{m}r_q$.