TexTest < Support < TWiki

Skip to main content.

Jason is playing with LaTeX?. This is extracted from a worksheet I made for myself for MA540.

Combinatorics basics

Permutations of n distinct objects: $P(n) = n!$

Permutations of n distinct objects r at a time: $P(n,r) = \frac{n!}{(n-r)!}$

Combinations of k objects from n distinct objects:

$C(n,k) = \binom{n}{k} = \frac{P(n,k)}{P(k,k)} = \frac{n!/(n-k)!}{k!} = \frac{n!}{(n-k)!k!} = \binom{n}{n-k}$

\begin{displaymath} C(n,k) = \binom{n}{k} = \frac{P(n,k)}{P(k,k)} = \frac{n!/(n-k)!}{k!} = \frac{n!}{(n-k)!k!} = \binom{n}{n-k} \end{displaymath}

Bannana problem

\begin{displaymath} P(n;r_{1},r_{2},r_{3},\cdots,r_{m}) = \frac{n!}{r_{1}! r_{2}! r_{3}! \cdots r_{m}!} \end{displaymath}

Hot Dog problem

Hot Dog Problem (aka dashes and slashes): selection with repetition of r objects from n types

the number of ways to select r objects from n types;
or the number of ways to distribute r identical objects into n boxes
or the number of non-negative integer solutions to $x_{1}+x_{2}+x_{3}+\cdots+x_{n}=r$
is

\begin{displaymath} \binom{r+n-1}{r}= \binom{r+n-1}{n-1} \end{displaymath}

Combinatorics basics

\begin{center} \begin{tabular}{|c|c|c|} \hline &amp; arrangement or &amp; combination or\\ &amp; distribution of &amp; distribution of\\ &amp; distinct objects &amp; identical objects\\ \hline &amp; &amp; \\ no repetition &amp; $P(n,r)$ &amp; $n \choose r$ \\ &amp; &amp; \\ \hline &amp; &amp; \\ unlimited repetition &amp; $n^{r}$ &amp; $n+r-1 \choose r$ \\ &amp; &amp; \\ \hline &amp; &amp; \\ restricted repetition &amp; $\frac{n!}{r_{1}! r_{2}! r_{3}! \cdots r_{m}!}$&amp; \\ &amp; &amp; \\ \hline \end{tabular} \end{center}

Binomial Theorem

\begin{displaymath} (1+x)^{n} = \binom{n}{0} x^0 + \binom{n}{1} x^1 + \binom{n}{2} x^2 + \binom{n}{3} x^3 + \cdots + \binom{n}{n} x^n \end{displaymath}

Generating Function Identities

\begin{displaymath} \frac{{1-x}^{n+1}}{1-x} = 1 + x + x^2 + x^3 + \cdots + x^n \end{displaymath} \begin{displaymath} \frac{1}{1-x} = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + \cdots \end{displaymath} \begin{displaymath} (1+x)^{n} = \binom{n}{0} x^0 + \binom{n}{1} x^1 + \binom{n}{2} x^2 + \binom{n}{3} x^3 + \cdots + \binom{n}{n} x^n \end{displaymath} \begin{displaymath} (1-x^m)^n = 1 - \binom{n}{1} x^m + \binom{n}{2} x^{2m} - \binom{n}{3} x^{3m} + \cdots + (-1)^n\binom{n}{n} x^{nm} \end{displaymath} \begin{displaymath} \frac{1}{(1-x)^n} = 1 + \binom{1+n-1}{1} x + \binom{2+n-1}{2} x^2 + \binom{3+n-1}{3} x^3 + \binom{4+n-1}{4} x^4 + \cdots + \binom{r+n-1}{r} x^r \end{displaymath} \begin{displaymath} = \sum_{r=0}^\infty \binom{r+n-1}{r}x^r \end{displaymath} \begin{displaymath} \frac{(1-x)^{n+1}}{1-x} = x^0 + x^2 + x^4 + \cdots + x^n \end{displaymath} n is even \begin{displaymath} e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \cdots = \sum_{r=0}^\infty \frac{x^r}{r!} \end{displaymath} \begin{displaymath} e^{-x} = 1 - x + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} - \cdots = \sum_{r=0}^\infty (-1)^n \frac{x^r}{r!} \end{displaymath} even: \begin{displaymath} \frac{e^x+e^{-x}}{2} = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \frac{x^6}{6!} + \cdots \end{displaymath} odd: \begin{displaymath} \frac{e^x-e^{-x}}{2} = x + \frac{x^3}{3!} + \frac{x^5}{5!} + \frac{x^7}{7!} + \cdots \end{displaymath}

product of generating functions

$f(x) \cdot g(x)$: take $a_k$ from $f(x)$ , $a_{n-k}$ from $g(x)$

-- JasonW - 27 Apr 2006