Proving that $\frac{(N+p-1)!}{p!(p-1)!N!}$ is an integer?

Question

Consider the quantity:

$$\frac{(N+p-1)!}{p!(p-1)!N!}$$ where $N$ and $p$ are positive integers. How can we show that this is always an integer (which I believe has to be the case since it represents the number of ways $N$ identical particles can be put into $p$ identical boxes, I think).

Answer 1

You've miscounted.

I see that you are essentially taking the number of solutions to $x_1+x_2+\cdots+x_p=N$ and dividing by $p!$. But if $x_i=x_j$ then not all permutations give a different solution.

The number of solutions to $x_1+x_2+\cdots +x_p=N$ with $x_1\leq x_2\leq \cdots \leq x_p$ is a much more complicated value.

These are called "integer partitions" of $N$ into at most $p$ parts, and there id no simple formula for counting these. See Wikipedia.

Answer 2

It's not always an integer. Consider the case $N=p=2$. You obtain $3!/2!1!2!=3/2$.

Answer 3

The number of ways to distribute $N$ indistinguishable objects amongst $p$ distinguishable containers is the number of weak compositions of $N$ into $p$ parts, which is

$$\binom{N+p-1}{p-1}=\frac{(N+p-1)!}{N!(p-1)!}\;.$$

However, you can’t simply divide by $p!$ to get the number of distributions into $p$ indistinguishable containers: the divisor for a given arrangement depends on the arrangement, since only containers with the same number of objects in them are treated identically.

What you want is the something much messier: $\sum_{k=1}^pp(N,k)$, where $p(n,k)$ is the number of partitions of $n$ into $k$ parts. There’s a useful recurrence,

$$p(n,k)=p(n-1,k-1)+p(n-1,k)\;,$$

but no nice closed form. For more information see this link, especially after equation $(58)$.