# Chaitanya's Random Pages

## December 14, 2014

### Basic combinatorics results

Filed under: mathematics — ckrao @ 8:11 pm

The following lists most of the introductory combinatorics formulas one might see in a first course expressed in terms of the number of arrangements of letters in which repetition or order matters.

 number of letters alphabet size letters repeated? order matters? formula comments $k$ $n$ yes yes $n^k$ samples with replacement $k$ $n$ no yes \begin{aligned} & n(n-1)\ldots (n-k+1)\\ &= \frac{n!}{(n-k)!} = P(n,k) = (n)_k\end{aligned} samples without replacement (permutations) $n$ $n$ no yes $n!$ if letters in a line $(n-1)!$ if letters in a ring and rotations are considered equivalent $(n-1)!/2$ if letters in a ring and rotations & reflections are considered equivalent $k$ $n$ no no $\frac{n!}{k!(n-k)!} = \binom{n}{k} = C(n,k)$ binomial coefficient (combinations) $n$ 2 yes: $k$ of type 1, $n-k$ of type 2 yes $\binom{n}{k}$ $n$ $m$ yes: $k_1$ of type $i$ for $i = 1,\ldots, m$ yes $\frac{n!}{k_1! k_2! \ldots k_m!} = \frac{(k_1 + k_2 + \ldots + k_m)!}{k_1! k_2! \ldots k_m!} = \binom{n}{k_1, k_2, \ldots, k_m}$ multinomial coefficient (multiset permutations) e.g. number of arrangements of “BANANA” is $\frac{6!}{3!2!1!}$ $n$ $k$ yes no $\binom{n+k-1}{k-1} = \binom{n+k-1}{n} = \left(\!\!{n \choose k}\!\!\right)$ multiset coefficient (combinations with repetition): number of non-negative integer solutions to $n_1 + n_2 + \ldots + n_k = n$ $n$ $2$ no two consecutive letters of type 1 yes $F_{n+2}$ Fibonacci number where $F_{n+2} = F_{n+1} + F_n$ and $F_1 = F_2 = 1$ e.g. number of sequences of 6 coin tosses with no two consecutive heads is $F_8 = 21$