Counting depends on whether order matters and whether repetition is allowed. Those two questions decide whether a problem uses permutations, combinations, or a different model such as stars and bars.

Permutations: order matters

A $k$-permutation of an $n$-element set is an ordered arrangement of $k$ distinct elements. Here $n$ and $k$ are nonnegative integers with $k\le n$. There are

such arrangements. The factorial notation means

The first position has $n$ choices, the second has $n-1$, and the $k$th has $n-k+1$. Their product is $n!/(n-k)!$.

Example: assigning three offices

From a class of $20$ students, choose a president, a vice-president, and a secretary. The offices are different, so order matters:

This is also

When $k=n$, every element is used. This is a full permutation, and

For example, the set $\{1,2,3,4,5\}$ has

permutations.

Combinations: order does not matter

A $k$-combination of an $n$-element set is a subset with exactly $k$ elements, where $n,k\in\mathbb Z_{\ge0}$ and $k\le n$. Its order does not matter. The notation

is read “$n$ choose $k$” and is called a binomial coefficient.

Every group of $k$ selected elements has $k!$ possible orders. Dividing the permutation count by $k!$ removes those repeated arrangements:

Example: forming a committee

A three-student committee from a class of $20$ has no assigned offices. The same three students were counted $3!=6$ times by the ordered calculation, so

Example: poker hands and flushes

A five-card hand is a set of five cards chosen from a deck of $52$, so the number of hands is

To count five-card hands in which every card has the same suit:

1. choose one of the four suits;
2. choose five of the thirteen cards in that suit.

The product principle gives

Example: bit strings with four zeros

A length-$10$ bit string containing exactly four zeros is determined by the four positions occupied by those zeros. Therefore,

The remaining six positions automatically contain ones.

Stars and bars

Use stars and bars when identical objects are distributed among distinct categories and a category may receive more than one object.

Suppose a store has seven chocolate flavors, and we choose four bars. Purchase order does not matter, and repeated flavors are allowed. Represent each bar by a star and use six dividers to split the stars among seven flavors.

For example,

**|*||*|||

represents two bars of the first flavor, one of the second, none of the third, one of the fourth, and none of the last three.

Every purchase corresponds to a string with four stars and six dividers. The string has ten positions, and choosing the four star positions gives

More generally, if $r\ge0$ and $n\ge1$ are integers, distributing $r$ identical objects among $n$ categories gives

possibilities when zero objects in a category are allowed.

There are $r$ stars and $n-1$ dividers, hence $r+n-1$ positions in total. Choosing the $r$ star positions produces the formula.

Two binomial identities

A combinatorial proof shows that two expressions are equal by showing that they count the same collection in two different ways.

Symmetry

The first identity is

A length-$n$ bit string with $k$ zeros has $n-k$ ones. We can count the same strings by choosing either:

• the $k$ positions occupied by zeros, giving $\binom nk$; or
• the $n-k$ positions occupied by ones, giving $\binom n{n-k}$.

Both expressions count exactly the same strings, so they are equal.

The factorial formula gives the same identity algebraically:

Pascal's identity

For integers $n\ge1$ and $1\le k\le n$, Pascal's identity is

Consider a class of $n+1$ students, including one particular student called student $0$. Count the $k$-student committees by splitting them into two disjoint cases:

1. Student $0$ is on the committee. Choose the other $k-1$ members from the remaining $n$ students, giving $\binom n{k-1}$ committees.
2. Student $0$ is not on the committee. Choose all $k$ members from the remaining $n$ students, giving $\binom nk$ committees.

The cases do not overlap and include every committee. The sum principle gives Pascal's identity.

At the boundary, use $\binom n0=\binom nn=1$. If Pascal's identity is to include the endpoints, adopt the convention $\binom nr=0$ when $r<0$ or $r>n$.

Pascal's triangle

Pascal's identity calculates each interior binomial coefficient by adding the two entries above it. The boundary values are

The first five rows are

For example,

This gives a recursive way to calculate binomial coefficients using addition instead of factorials.