Permutation

• A permutation of a set $S$ with $n$ elements is a bijection $\sigma :S\to S$.
• A permutation can be viewed as a rearrangement of the elements of $S$ where $\sigma (i)=j$ means that the element $i$ is moved to the position of element $j$.
• The number of permutations of a set with $n$ elements is: $P(n)=n!$
• The number of bijective functions between two sets of the same size $n$

Partial Permutation

$P(n,k)=\frac{n!}{(n-k)!}=n(n-1)\cdots (n-k+1)$

• k-permutations of a set with $n$ distinct elements.
• The number of ways to arrange $k$ distinct objects in order, chosen from $n$ available objects.
• The number of ways to distribute $k$ distinct balls into $n$ distinct cells, where each cell can contain either one or no ball.
• The number of injective (one-to-one) functions from a set of size $k$ to a set of size $n$. ($n\ge k$)

Permutations of Multisets

$P(n;k_1,...,k_i)=\left(\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_i}\right)=\frac{n!}{k_1!\cdots k_i!}=\left(\genfrac{}{}{0ex}{}{k_1}{k_1}\right)\left(\genfrac{}{}{0ex}{}{k_1+}{k_2}\right)\cdots \left(\genfrac{}{}{0ex}{}{k_1+\cdots +k_i}{k_i}\right)$

• Multinomial Coefficient
• The number of ways to arrange a multiset of size $n$ where $k_1,\dots ,k_i$ are the multiplicities of the elements of the multiset. (i.e. $k_1+\cdots +k_i=n$)

Permutations with Repetition

$n^k$

• The number of ways to form a string of length $k$ from an alphabet of size $n$ (repetition allowed)
• The number of ways to distribute $k$ distinct balls into $n$ distinct cells (a cell can be empty, or contain any number of balls)

Number of Surjective Functions

$n!\left\{\genfrac{}{}{0ex}{}{k}{n}\right\}=\sum _{i=0}^{n-1}(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})(n-i{)}^k$

• The number of surjective (onto) functions from a set of size $k$ to a set of size $n$. ($k\ge n$)
• The number of ways to distribute $k$ distinct balls into $n$ distinct cells, where each cell must contain at least one ball.

$\{\genfrac{}{}{0ex}{}{k}{n}\}=S(k,n)$ is Second kind (Stirling partition number)

Other

• Distribute $k$ distinct balls into $n$ distinct cells, where the first $a$ cells must contain at least $b$ balls total $\sum _{i=0}^{a-1}\left(\genfrac{}{}{0ex}{}{k}{b+i}\right)\cdot a^{(b+i)}\cdot (n-a{)}^{(k-(b+i))}$
• The number of ways to distribute $k$ distinct balls into $n$ distinct cells, where the order of balls within the cells is matter $k!\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)=\frac{(n+k-1)!}{(n-1)!}=(n+k-1{)}^{\underline{k}}$

Derangement

• A derangement of a set $S$ with $n$ elements is a permutation $\sigma :S\to S$ such that $\forall i\in S,\sigma (i)\ne i$.
  • A derangement can represent an arrangement of a sequence of elements such that no element appears in its original position.
  • A derangement is a permutation that has no fixed points.
  • (aka: אי סדר מלא, בלבול, תמורה ללא נקודות שבת)
• The number of derangements of a set of size $n$ is known as the subfactorial of $n$ or the $n$-th derangement number, denoted by $!n$ or $D_n$ and is given by any of the following formulas:
  • $!n=D_n=(n-1)(D_{n-2}+D_{n-1})$ for $n\ge 2$ with $D_0=1$ and $D_1=0$.
  • $!n=n!\sum _{i=0}^n\frac{(-1{)}^i}{i!}$
  • $!n=\sum _{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})(n-i)!$
  • $!n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor$

A000166

$n$	0	1	2	3	4	5	6	7	$\dots$
$!n$	1	0	1	2	9	44	265	1854	$\dots$

Derivation by inclusion–exclusion principle

$!n=n!-\left|S_1\cup \cdots \cup S_n\right|=n!{\sum }_{i=0}^n\frac{(-1{)}^i}{i!}$

For $1\le k\le n$ we define $S_k$ to be the set of permutations of $n$ objects that fix the $k$-th object.

Dis. objects into indist. boxes of size r

• The number of ways to distribute $n$ distinguishable objects into $k$ indistinguishable boxes each of size $r$ (where $n=kr$) is given by $\frac{n!}{(r!{)}^{k}k!}$