Unordered sampling without replacement1 can be thought of as determining how many ways there are to divide nn objects into rr groups. Here we are choosing the number of dividers of the object (not the number of objects per se). For example, if we have seven objects which we want to divide, we choose how many dividers to put between the objects:

O  |  O   O  |  O   O   O  |  O

With 3 dividers we can put the objects into 4 groups, i.e. we only specify r-1r-1 dividers. There are n-1n-1 spaces between the objects, so n-1n-1 ways in which to choose these r-1r-1 dividers.

Note this is specifically if each group must contain at least one object.

So this gives the result that there are Cr-1n-1Cr-1n-1 distinct positive (note not non-negative) integer-valued vectors (n1,n2,⋯,nr)(n1,n2,⋯,nr) satisfying the condition n1+n2+⋯+nr=nn1+n2+⋯+nr=n. (Remember this is for nk≥1,∀k:k∈[1,r]nk≥1,∀k:k∈[1,r]).

Notice the result and bear in mind the conditions

         Cr-1n-1Cr-1n-1,      for   n1+n2+⋯+nr=nn1+n2+⋯+nr=n,      where   nk≥1nk≥1.

So in general the sum of the individual groups gives the value to be used in the top position of the combination formula.

Now we turn to the situation where we have nk≥jnk≥j.

If we can get the sum of a series that satisfied the condition that each term in that series is ≥1≥1 then we will be able to substitute the sum of this series for nn in the combination formula given above.

Note that although we have changed the condition from nk≥1nk≥1 to nk≥jnk≥j, we must still have the condition that n1+n2+⋯+nr=nn1+n2+⋯+nr=n, otherwise we could end up with a different number of objects than we started with after dividing them into the groups.

So what term is ≥1≥1 when nk≥jnk≥j?

What we have to start with is nk≥1nk≥1. So if nk≥1nk≥1, this means that nk-j≥0nk-j≥0, and therefore nk-j+1≥1nk-j+1≥1.

All that we need to do now is to sum this series and substitute the result of this sum for nn in the combination formula given above.

The sum of this series is

Rearranging so that all of the terms in nn are together, and summing the common (-j+1)(-j+1) term rr-times, we get

as the sum of our series.

Now, recall that we still have the condition that n1+n2+⋯+nr=nn1+n2+⋯+nr=n. Using this fact, and rewritting -j+1-j+1 as 1-j1-j, we get

as the sum of our series.

We can substitute this sum into the combination formula from "The Basic Case " (in place of the nn term in this formula). So that

Giving the final result of this paper, that:

There are Cr-1n+1-jr-1Cr-1n+1-jr-1 number of ways to group nn objects into rr groups when nk≥jnk≥j2 and n1+n2+⋯+nr=nn1+n2+⋯+nr=n3.

Ross, Sheldon, A First Course in Probability, Eigth Edition, Pearson Education, 2008.

Special Thanks to Dr. Stephen Connor from the University of York, on whose notes this article is based.