Unordered selections

We notice that an unordered selection without repetition is just a subset.

Definition: Binomial numbers

Let be a set of size . Then which are called binomial numbers, pronounced choose .

Theorem

Let such that . Then Proof:
Let be a set of size and . Any -subset of either contains or doesn't, and is the number of ones that do contain , and is the number of ones that don't.

The fact that Pascal's triangle contains binomial numbers follows directly from this theorem.

Theorem

Let such that . Then Proof:
Can be shown with induction using Pascal's triangle. Alternatively, we know that is the number of ordered selections of elements from without repetition, so dividing by removes the ordering, obtaining the formula above.

Theorem

The number of unordered selections with repetition of objects from is Proof:
Informally, we imagine placing "separators" in a list of places and let the empty places represent the chosen elements; specifically if an empty place is between separator and separator , the separator represents element being chosen.

Theorem: The Binomial theorem

Let . Then Proof:
Follows from commutativity of multiplication; the number of 's is the number of way to choose 's among the factors .