Counting formulas

Ordered arrangements, no repetition, $0\le r\le n$. Also the number of injective functions from an $r$-set to an $n$-set.

Unordered selections of $r$ from $n$ distinct objects, no repetition, $0\le r\le n$. Symmetry: choosing the ones taken is the same as choosing the ones left.

Unordered choice of $r$ items from $n$ kinds ($n\ge 1$) when each kind may be taken any number of times (multisets of size $r$).

Seating $n\ge 1$ distinct people round a table when rotations count as the same arrangement (reflections counted as different). If reflections are also the same and $n\ge 3$, divide by 2: $(n-1)!/2$.

Distinct arrangements of $n$ objects of which $n_i$ are alike of type $i$, $\sum n_i=n$. It is also the number of ways to split $n$ distinct objects into labelled groups of sizes $n_1,\dots ,n_k$.

Number of integer solutions ($k\ge 1$); equals the number of ways to put $n$ identical objects into $k$ distinct bins, empty bins allowed.

Every bin non-empty ($n,k\ge 1$). For a lower bound $x_i\ge a_i$, substitute $y_i=x_i-a_i$ and reduce $n$ by $\sum a_i$.

Add a slack variable $x_{k+1}=n-(x_1+\cdots +x_k)\ge 0$; the equation now has $k+1$ unknowns summing to $n$.

$S(n,k)$ = number of ways to split a set of $n$ distinct objects into $k$ non-empty unlabelled blocks. Conventions: $S(0,0)=1$, $S(n,0)=0$ for $n\ge 1$, $S(n,k)=0$ for $k>n$. Also $S(n,2)=2^{n-1}-1$. Example values: $S(4,2)=7$, $S(5,2)=15$, $S(5,3)=25$.

Number of ways to write $n$ as a sum of exactly $k$ positive integers with order ignored. Boundary values: $p(0,0)=1$; $p(n,k)=0$ if $k>n$, or if $n\ge 1$ and $k\le 0$. $p(n)$ is the total over all $k$; $p(1),\dots ,p(7)=1,2,3,5,7,11,15$.

For a non-negative integer $n$. The coefficient of $x^{n-k}{y}^k$ is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; there are $n+1$ terms. In $(x_1+\cdots +x_k{)}^n$ the coefficient of $x_1^{n_1}\cdots x_k^{n_k}$, where $n_1+\cdots +n_k=n$, is $\frac{n!}{n_1!\cdots n_k!}$.

For $n\ge 1$ and $1\le k\le n$. Split the $k$-subsets of an $n$-set by whether they contain a chosen element.

Total number of subsets of an $n$-set; from $x=y=1$ and $x=1,y=-1$. Hence even-size subsets and odd-size subsets each number $2^{n-1}$ for $n\ge 1$.

Follows from $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ (choose a committee, then its leader).

Choose $r$ from two groups of sizes $m$ and $n$ by how many come from the first (terms with $k>m$ or $r-k>n$ are 0). The case $m=n=r$ gives ${\sum }_k{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^2=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$.

For $0\le r\le n$. Sum down a diagonal of Pascal's triangle.

Counts elements with at least one of $m$ properties; for two sets, $|A\cup B|=|A|+|B|-|A\cap B|$. The number with none of the properties is $|U|$ minus this value.

Functions from an $n$-set onto a $k$-set; equals $k!S(n,k)$ and is $0$ if $n<k$.

Permutations of $n$ objects with no object in its original place. Convention $D_0=1$. Also $D_n=n{D}_{n-1}+(-1{)}^n$, and for $n\ge 1$, $D_n$ is the integer nearest to $n!/e$. $D_1=0,D_2=1,D_3=2,D_4=9,D_5=44,D_6=265$.

Choose which $k$ objects stay put, then derange the other $n-k$ (for $k=n$ this gives $D_0=1$, the identity).

For positive integers $n$, $k$. To guarantee at least $r$ objects in one of $k$ boxes you need $k(r-1)+1$ objects. It proves existence only; it does not construct the box.

Number of partitions of an $n$-set into non-empty blocks, which is also the number of equivalence relations on it (each relation corresponds to its set of equivalence classes).

Shortest paths from $(0,0)$ to $(m,n)$ using unit steps right and up: choose which $m$ of the $m+n$ steps are right. Forced points are handled by multiplying path counts of each leg.

Paths from $(0,0)$ to $(n,n)$ with right steps (along $x$) and up steps (along $y$) that never go above the line $y=x$ (touching allowed). Also: balanced bracket strings with $n$ pairs; unlabelled binary trees with $n$ nodes (left and right child distinguished); binary search trees on $n$ distinct keys; full binary trees with $n+1$ leaves; ways to parenthesise a product of $n+1$ factors; triangulations of a convex $(n+2)$-gon.

Condition on the end: a valid string ending in 0 is any valid string of length $n-1$ followed by 0; a valid string ending in 1 must end in 01, after any valid string of length $n-2$. Values: 2, 3, 5, 8, 13, 21, 34, 55 for $n=1,\dots ,8$; $a_n=F_{n+2}$ with $F_1=F_2=1$.

Number of $k$-element subsets of $\{1,2,\dots ,n\}$ with no two consecutive integers; equivalently binary strings of length $n$ with $k$ ones, no two adjacent (place the $k$ ones in the $n-k+1$ gaps around the $n-k$ zeros).