Combination without Repetition

combinatorics

Definition

Combination without Repetition

A combination without repetition chooses different elements from available elements without placing them in order. Order does not matter, so choosing then gives the same combination as choosing then , and no element may be chosen twice.

For a finite set with , a combination of size is a subset

The number of such combinations is the binomial coefficient

Derivation from the Product Rule

Temporarily keep track of order. Filling positions without repetition gives choices for the first position, for the second, and for the last. By the product rule, the number of ordered selections is

The same ordered selections can be constructed differently. First choose one of the unordered combinations. Then order its selected elements in ways. Applying the product rule again gives

For and , this construction forms the following paths:

The three combinations each have two orderings, producing all six ordered selections.

Equating the two counts and solving for yields

Thus division by does not remove a fixed number of unwanted selections. It collapses each equal group of orderings into one unordered combination.

Forgetting order

For and , the six ordered variations collapse in pairs to three combinations:

Each combination has orderings, hence

Boundary Cases

There is one way to choose no elements and one way to choose every element:

Example

Choosing a committee

A three-person committee chosen from ten people is unordered, so the number of possible committees is