Counting non-negative integral solutions

Question

I'm reading this passage and wondering why

Number of ways in which k identical balls can be distributed into n distinct boxes =

$$\binom {k+n-1}{n-1}$$

could someone explain it to me please?

Answer 1

The proof technique is what is often referred to as stars and bars.

Imagine if you will you have $n$ distinct boxes and $k$ identical balls.

We arrange a sequence of $k$ $\star$'s and $n-1$ $|$'s to denote how the balls are distributed. The number of stars to the left of the leftmost bar will correspond to the number of balls in the first box. The number of stars between the $(i-1)$'st and $i$'th bar will correspond to the number of balls in the $i$'th box. And the number of stars after the $(n-1)$'st bar will correspond to the number of balls in the $n\text{'th}$ box.

E.g.: with $n=4$ and $k=5$ the sequences below correspond to the following arrangements:

$\star|\star\star|\star|\star$ corresponds to $(1,2,1,1)$

$\star\star\star\star|||\star$ corresponds to $(4,0,0,1)$

Recognize now that there is a bijection between the ways to arrange the balls in the boxes and the ways to arrange the stars and bars in a line. If we know how to count the number of possibilities for one of these problems, then it must be the same answer for the other as well.

The number of ways to arrange $n-1$ $|$'s and $k$ $\star$'s will be $\binom{n+k-1}{k} = \binom{n+k-1}{n-1}$.

This is a common enough problem, that it even receives its own special notation. $\left(\!\!\binom{n}{k}\!\!\right)$. Multichoose @ WolframMathworld

---

As an aside, from the conversation here, some people are taught how to answer the question where every box must contain at least one ball first, and use that result to derive the result above.

With $n$ distinct boxes, and $n+k$ identical balls, where each box must contain at least one ball, imagine laying $n+k$ $\star$'s in a line. We place dividers between the balls to designate as above where one box ends and another box begins. Due to the constraint that every box must have at least one ball, we must pick $n-1$ spaces from the $n+k-1$ available spaces in which to place dividers.

There are then $\binom{n+k-1}{n-1}$ solutions with all positive integers. Removing one ball from every box then makes it so there are $k$ balls total to place and it is now allowed to be non-negative as opposed to strictly positive, yielding the same result as the first method of explaining.

Answer 2

Imagine you lay out $k$ balls in a straight line. Then you divide them up into boxes by setting out markers splitting them up. For example, if you have $10$ balls and $3$ boxes, you might do

$$\text{b, b, MARKER, b, b, b, MARKER, b, b, b, b, b}$$

and this sequence means two balls in the first box, three in the second, and five in the fifth.

Now hopefully it's clear that determining how many balls to put into which box is akin to placing $n-1$ dividers between them. So if you take a line of $n+k-1$ spots, you have to choose $k-1$ spots to put the divider.

Answer 3

This is what is called "stars and bars" combinatorics

Suppose there are $15$ balls, and $3$ boxes.

The balls could be variously distributed, e.g.

$\Large\bullet\bullet\bullet+\bullet\bullet\bullet\bullet\bullet+\bullet\bullet\bullet\bullet\bullet\bullet\bullet= 15$

I have used $+$ for a divider ("bar" in stars and bars)
Note that for $3$ boxes, only $2$ dividers are needed, for $n$ boxes, only $n-1$ will be needed

You could have situations here where $1-2$ boxes remain empty, e.g.

$\Large 0 +\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet +\bullet\bullet\bullet\bullet\bullet\bullet\bullet= 15\;$ [ Box $1$ empty]

or $\;\Large\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet+\; 0 +\bullet\bullet\bullet\bullet\bullet\bullet\bullet= 15\;$ [ Box $2$ empty]

or $\;\Large\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet +\;0 +\;0 = 15\;$ [ Boxes $2$ and $3$ empty ]

The balls are $15$ "stars", and the $+'s$ are $2$ "bars",
which have to be placed somewhere in the $15+2$ symbols, thus the generalised formula $\binom{k+n-1}{n-1}$