5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ how many pairs of additive inverses are there ? that may be a start. $\endgroup$
    – user451844
    Aug 11 '17 at 17:23
  • 1
    $\begingroup$ 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$. $\endgroup$ Aug 11 '17 at 17:26
  • 1
    $\begingroup$ @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. $\endgroup$
    – Erick Wong
    Aug 11 '17 at 17:37
  • 1
    $\begingroup$ @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.) $\endgroup$
    – foneyoscar
    Aug 11 '17 at 17:48
  • $\begingroup$ very good point Erick! $\endgroup$ Aug 12 '17 at 22:14
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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