# Connexions

You are here: Home » Content » Unordered Sampling Without Replacement

### Recently Viewed

This feature requires Javascript to be enabled.

# Unordered Sampling Without Replacement

Module by: Avinash Hathiramani. E-mail the author

Summary: This article introduces the method of calculating the number of unordered arrangements of objects without replacement. It is a brief article which attempts to explain this concept from an intuitive perspective making it easy to understand and derive the formulae.

## The Basic Case

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 nk1,k:k[1,r]nk1,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   nk1nk1.

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

## The Generalised Case

Now we turn to the situation where we have nkjnkj.

If we can get the sum of a series that satisfied the condition that each term in that series is 11 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 nk1nk1 to nkjnkj, 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 11 when nkjnkj?

What we have to start with is nk1nk1. So if nk1nk1, this means that nk-j0nk-j0, and therefore nk-j+11nk-j+11.

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

n 1 - j + 1 + n 2 - j + 1 + + n r - j + 1 n 1 - j + 1 + n 2 - j + 1 + + n r - j + 1
(1)

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

n 1 + n 2 + + n r + - j + 1 r n 1 + n 2 + + n r + - j + 1 r
(2)

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

n + 1 - j r n + 1 - j r
(3)

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

C r - 1 n - 1 C r - 1 n + 1 - j r - 1 C r - 1 n - 1 C r - 1 n + 1 - j r - 1
(4)

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 nkjnkj2 and n1+n2++nr=nn1+n2++nr=n3.

## References

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

## Footnotes

1. Also known as the balls in boxes' or balls in urn' problem.
2. I.e. We must have at least jj objects in each group.
3. I.e. We must allocate exactly the number of objects that we started with in the beginning.

## Content actions

### Give feedback:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks