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