Combinatorics

First consider a collection of $r$ distinct objects selected from a set of $n$ distinct objects.
Permutations and combinations
A permutation of such a set is distinguished by another such permutation by the ordering of the objects. The first item of an $r$ -permutation of $n$ things $P(n,r)$ can be chosen $n$ ways, the second in $n-1$ ways, and so forth, so that

$P(n,r)=n(n-1)\cdots (n-r+1)={n!\over (n-r)!}\equiv (n)_r$

These numbers have a recursion relation

$P(n,r)=P(n-1,r)+rP(n-1,r-1)$

If we allow for unrestricted repetition, then the first object can be selected $n$ ways, the second selected $n$ ways, and so on, so

$U(n,r)=n^r$

(this is also called sampling with replacement).

A combination of $r$ distinct objects of (selected from $n$ objects) can be ordered in $r!$ ways, therefore

$r!\, C(n,r)=P(n,r), \quad C(n,r)={n!\over r!(n-r)!}\equiv {n\choose r}$

Combinations can be counted by developing a recursion relation. Divide combinations into classes, for example those that contain the the first object, and those that don’t. $r$ -combinations of $n$ things that do contain the first of the $n$ objects are then $C(n-1,r-1)$ since selecting one item reduces both $n$ and $r$ . The number of $r$ -combinations that do not contain the first item is then $C(n-1,r)$ , and we use the rule of sum

$C(n,r)=C(n-1,r-1)+C(n,r-1), \quad C(n,r)=0\quad\mbox{if}\quad r<0\quad r>n$

Generating or enumerating functions
are functions that let us solve recursion relations. Define

$F_n(t)=\sum_{r=0}^n C(n,r)\, t^r$

in which $t$ is just a formal symbol. Let’s define $C(n,0)=1$ , and apply the recursion relation

$F_n(t)=\sum_{r=0}^n C(n,r)\, t^r=F_n(t)=\sum_{r=0}^{n} C(n-1,r-1)\, t^r+\sum_{r=0}^{n-1} C(n-1,r)\, t^r$

$=\sum_{r=1}^{n-1} C(n-1,r-1)\, t^r+\sum_{r=0}^{n-1} C(n-1,r)\, t^r=tF_{n-1}+F_{n-1}$

so we deduce that

$F_n=(1+t)F_{n-1}=(1+t)^nF_0(t)=(1+t)^n$

This is referred to as a generating function since we can get any $C(n,r)$ by expanding it out and reading the coefficient of $t^r$ , or alternatively by calculus operations

$r!C(n,t)={d^r\over dt^r}F_n(t)\Big{|}_{t=0}, \qquad C(n,r)=\oint_C {dt\over 2\pi i}{F_n(t)\over t^{n+1}}$

(in the integral let $C$ be a unit circle, i.e. let $t=e^{i\theta}$ ).\\
We have shown that

$(1+t)^n=\sum_{r=0}^n {n\choose r} t^r$

so $C(n,r)={n\choose r}$ is a binomial coefficient. The Persian poet-mathematician Omar Khayyam produced the following calculation of binomial coefficients several hundred years before it was rediscovered by Pascal

$1$

$1\qquad 1$

$1\qquad 2\qquad 1$

$1\qquad 3\qquad 3\qquad 1$

$1\qquad 4\qquad 6 \qquad 4 \qquad 1$

$1\qquad 5\qquad 10 \qquad 10 \qquad 5 \qquad 1$

Despite the fact that the combinatorial interpretation is preposterous if either $n$ or $r$ are negative, we can still continue the definition of a symbol such as ${-n\choose r}$ in the following way;

${-n\choose r}={(-n)(-n-1)(-n-2)(-n-3)\cdots (-n-r+1)(-n-r)(-n-r-1)\cdots\over r! (-n-r)(-n-r-1)\cdots}\] \[={(-n)(-n-1)(-n-2)(-n-3)\cdots (-n-r+1)\cdots\over r!}$

which actually makes perfect sense. We can extract all of the negative signs

${-n\choose r}={(-n)(-n-1)(-n-2)(-n-3)\cdots (-n-r+1)\cdots\over r!}$

$=(-1)^r{(n+r-1)(n+r-2)\cdots(n+1)(n)\over r!}$

$=(-1)^r{(n+r-1)!\over r! (n-1)!}$

and so

${-n\choose r}=(-1)^r {n+r-1\choose r}$

This is very handy for quickly evaluating rational functions.
The binomial coefficients possess a very large number of summation identities that are easy to prove using the generating relation. For example

$(1+t)^{2n}=(1+t)^n \, (1+t)^n$

gives us

$\sum_{m=0}^{2n} {2n\choose m} t^m=\sum_{p=0}^{n} {n\choose p} t^q \,\sum_{q=0}^{n} {n\choose q} t^q$

from which we pick out the coefficient of $t^m$ from both sides

${2n\choose m}=\sum_{p+q=m}{n\choose p}{n\choose q}$

This is a good starting point from which to derive lots of other useful things, for example in this expression let $m=n$ ;

${2n\choose n}=\sum_{p+q=n}{n\choose p}{n\choose q}=\sum_{p=0}^n{n\choose p}{n\choose n-p}$

but ${n\choose n-p}={n\choose p}$ giving us

${2n\choose n}=\sum_{p=0}^n{n\choose p}^2$

an identity that we make use of more often than you may think in quantum theory.
A useful tool for constructing identities on the binomial coefficients is the fact that

$\int_0^{2\pi} e^{im\theta} \, {d\theta\over 2\pi}=0, \qquad m\ne 0$

provided that $m$ is an integer. The integral is of course one if $m=0$ , and this works because $e^{2\pi i m}=1$ for all integral $m$ . \\
A good example of how this is used to select coefficients from the product of generating functions is

$(1+t)^k (1+t)^p=\sum_{n,m} {k\choose m}{p\choose n} t^{n+m}$

Then select the coefficient of $t^j$ with

$\int_0^{2\pi} {d\theta\over 2\pi} (1+t e^{i\theta})^k (1+t e^{i\theta})^p \, e^{-ij\theta}= \int_0^{2\pi} {d\theta\over 2\pi} (1+t e^{i\theta})^{k+p} \, e^{-ij\theta}={k+p\choose j}$

so that

$\sum_{m+n=j}{k\choose m}{p\choose n}={k+p\choose j}$

Compositions

Generating functions provide a way to construct solutions to combinatorics problems, this is illustrated nicely by compositions and partitions.
Compositions $Q(n,r)$ of $n$ objects into $r$ classes can be thought of as dividing $n$ ordered identical objects into $r$ non-empty connected groups. Create an enumerating function for one of the $r$ classes $t+t^2+t^3+\cdots={t\over 1-t}$ . The exponent of $t$ tells how many objects are in the class. Next create an enumerating function for the whole set of $r$ classes

$\Big({t\over 1-t}\Big)^r=\sum_{n=1}^\infty Q(n,r)\, t^n=t^r(1-t)^{-r}=\sum_{p=0}^\infty {-r\choose p}t^{r+p}$

$=\sum_{p=0}^\infty {r-1+p\choose p}t^{r+p}$

so $Q(n,r)={n-1\choose n-r}={n-1\choose r-1}$ . The most basic composition problem is to take $n$ volumes of the same book, place them in a row on a shelf, and now find the number of ways of inserting $r-1$ dividers between them