# Permutations and Combinations

A **permutation** is an *X*-string in which all are distinct.

A **combination** is a way of selecting several things out of a larger group, where order does not matter.

## Permutation with Repetition

The number of *n*-ary strings of length are

\[ n \cdot n \cdot … \cdot n ~ \text{(k times}) = n^k \]

## Permutation without Repetition

The number *n*-letter words where no letter used more than once are

\[ P(26, n) = \frac{26!}{(26 - n)!} \]

In general,

:= number of permutations of elements chosen from a set of size

\[ P(m, n) = \frac{m!}{(m - n)!} \]

## Circular Permutation

The number of ways to arrange distinct objects along a fixed circle is

\[ P_n = (n - 1)! \]

## Permutations of sets with some indistinguishable objects

If you have total objects and unique objects, call the number of indistinguishable objects of type 1, indistinguishable objects of type 2, … and the number of indistinguishable objects of type , then the number of different permutations of these objects is

\[ {n \choose n_1, n_2, …, n_k} = \frac{n!}{n_1! \cdot n_2! \cdot … \cdot n_k!} \]

Hint: *MISSISSIPPI* problem. Also known as Multinomial Theorem.

## Combination with Repetition

The number of ways to choose a subset of size from an *n*-set, allowing repetition, are

\[ {n + k - 1 \choose k - 1} \]

## Combination without Repetition

The number of ways to choose a subset of size from an *n*-set are

\[ {n \choose k} = \frac{n!}{k! (n - k)!} \]

**Proposition:**

\[ {n \choose k} = {n \choose n - k} \hskip2em \forall ~ n, k \geqslant 0, k \leqslant n \]

## Distributing distinguishable balls into distinguishable bins

\[ k^n \]

## Distributing distinguishable balls into indistinguishable bins

The number of surjections from to is

\[ S(n, k) = \sum_{m=0}^k (-1)^m {k \choose m} (k - m)^n \]

## Distributing indistinguishable balls into distinguishable bins

\[ {n + k - 1 \choose k - 1} \]

## Distributing indistinguishable balls into indistinguishable bins

The number of integer partitions of an integer that has parts. Further reading: Integer Partition.

## Binomial Coefficient

Let and be real numbers with , and are non-zero then

\[ (x + y)^n = \sum_{i = 0}^n {n \choose i} x^i y^{n - i} \]