Number of ways in which a sum can be split into a certain number of summands

Suppose you have a sum $R$ and you need to divide the sum into $2n+1$ summands or summing parts.

Let's call the summands $r_i$, $i=1,2,3, \ldots ,2n+1$.

And each summing part $r_i$ is a non-negative integer, satisfying the inequality $0\le r_i \le N$.

Now the question is: In how many ways can you divide the sum $R$ into the $2n+1$ summands?

Example: For $R=3$, $N=2$, $n=1$, we have the following ways $(0,1,2)$ and $(1,1,1)$. That is, there will be $2$ ways.

MY ATTEMPT: Say, in the summing pattern, we get $b_j$ $j$'s where $j=1,2,3, \ldots ,N$.

So we get each $\sum_j b_j=2n+1$ and $\sum_j jb_j=R$ as per the problem.

Now the fact is that, the summands $r_i$ in this case are indistinguishable. That is, as in the above stated example, $(1,0,2)$, $(0,2,1)$, $(1,2,0)$, $(2,0,1)$, $(2,1,0)$ and $(0,1,2)$ are all the same and count as one.

But if the summands $r_i$ are taken to be distinguishable, that is we consider all these $6$ patterns above, then the answer will be $\sum _\limits{k=0}^{\lfloor\frac{R}{N+1}\rfloor}(-1)^k\binom{2n+1}{k}\binom{R-(N+1)k+2n}{2n}$ as per the answers to this question.

So can I proceed from hereon? Any possible ways?

Or is there some better method? Hope my question is clear.

• It looks like you are asking for restricted partitions, both in maximum partsize and maximum number of parts simultaneously. I unfortunately don't have any references in my collection that I know about asking about this specific restriction (it is usually only one or the other, not both). – JMoravitz Jan 28 '17 at 19:44
• Thinking of them as Ferrer's diagrams, you should be able to come up with an argument that they correspond somehow to lattice paths with a specific number of vertices. Not sure if it helps, but it might be something to search for. – JMoravitz Jan 28 '17 at 19:47

1 Answer

For each $R$, $n$ and $N$, you seem to be asking for the number $a_{R,2n+1,N}$ of unordered ways to write $R$ as a sum of $2n+1$ terms where each term is between $0$ and $N$. If that's really the case, there's a nice generating function that models your problem. Let the variable $x$ mark the contribution of each term to the sum, and let the variable $y$ mark the number of terms. Then, $a_{R,2n+1,N}$ would be the coefficient of $x^R y^{2n+1}$ in the product

\begin{align*} 0\text{'s}:\quad&(1+y+y^2+y^3+\cdots)\times \\ 1\text{'s}:\quad&(1+xy+(xy)^2+(xy)^3+\cdots)\times\\ 2\text{'s}:\quad&(1+x^2y+(x^2y)^2+(x^2y)^3+\cdots)\times\\ &\quad\vdots\\ N\text{'s}:\quad&(1+x^Ny+(x^Ny)^2+(x^Ny)^3+\cdots). \end{align*} Each factor in this product is a geometric series, so $$a_{R,2n+1,N}=[x^Ry^{2n+1}]\prod_{i=0}^N\frac1{1-x^iy}.$$ It is unlikely that there is a nice closed-form expression for this coefficient. However, there are approximations for products of this type with Schur's theorem in combinatorics.

Example

In your example, you have a sum of $R=3$. This corresponds to the coefficient of the $x^3$ term in the generating function. You also have a number of summands being $2n+1=3$ in your example. This corresponds to the coefficient of the $y^3$ term in the generating function. Putting these together, we need to consider the coefficient of $x^3y^3$ in the generating function. The bound of $N=2$ for the summands means that the generating function will have three factors (one for the 0's, one for the 1's and one for the 2's). The two ways that you listed are shown in red for $\color{red}{\text{no 0's, three 1's and no 2's}}$ and in blue for $\color{blue}{\text{one 0, one 1 and one 2}}$. $$\begin{array}{rcrcrcrl} (\color{red}{1} & + & \color{blue}{y} & + & y^2 & + & y^3 & +\cdots)\times \\ (1 & + & \color{blue}{xy }& + & (xy)^2 & + & \color{red}{(xy)^3} & +\cdots)\times \\ (\color{red}{1} & + & \color{blue}{x^2y} & + & (x^2y)^2 & + & (x^2y)^3 & +\cdots) \end{array}$$

For a reference, you might look at the generating function part of the wikipedia page for partitions of integers, although there are some differences. For instance, their generating function for all partitions doesn't keep track of the number of summands (as the $y$ variable does here). Also, their generating function has no bound on the size of the summands, so their $N=\infty$. Another good place to look is in Wilf's generatingfunctionology book, section 3.16.

• Thanks for the answer. Can you add some derivation of this generating function, or perhaps add some link where I can find a detailed explanation of this generating function. – SchrodingersCat Jan 31 '17 at 5:26
• I added a description of the example you provided, but in terms of the generating function, as well as a couple links. – Rus May Jan 31 '17 at 22:18