essential_combinatorics.tex

\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage{polski}
\usepackage[polish,english]{babel}

\usepackage{amsmath}
\usepackage{hyperref}
\usepackage[super,comma]{natbib}

\usepackage{fancyhdr}
\usepackage{lastpage}

\fancypagestyle{plain}{%
    \fancyhf{}
    \renewcommand{\headrulewidth}{0pt}
    \cfoot{Page \thepage~of \pageref{LastPage}}
}

\pagestyle{plain}

\usepackage[nodayofweek]{datetime}
\newdateformat{frontdate}{\THEDAY~\shortmonthname[\THEMONTH]~\THEYEAR}

% Abbreviations
% http://tex.stackexchange.com/a/15017
\usepackage{xspace}
\makeatletter
\newcommand*{\etc}{etc\@ifnextchar{.}{}{.\@\xspace}}
\newcommand*{\ie}{i.e\@ifnextchar{.}{}{.\@\xspace}}
\newcommand*{\eg}{e.g\@ifnextchar{.}{}{.\@\xspace}}
\newcommand*{\cf}{c.f\@ifnextchar{.}{}{.\@\xspace}}
\makeatother

\newcommand{\pl}{\textbf{PL}: }

% do not indent new paragraphs
\setlength{\parindent}{0pt}
% vertical space between paragraphs instead
\setlength{\parskip}{1em}

\begin{document}

\title{Essential combinatorics}
\author{Jan Szopinski}
\date{\frontdate\today}
\maketitle

\section{Permutations}

Order is relevant.
A permutation maps a set or multiset (a set in which some elements are repeated) onto a sequence.

\begin{otherlanguage}{polish}
    \pl
    W języku polskim, termin `permutacja' tyczy się tylko przekształceń zbioru lub multizbioru na ciąg, w którym każdy elemnt pojawia się tyle samo razy co w początkowym zbiorze lub multizbiorze.
    W pozostałych przypadkach używa się terminu `wariacja'.
\end{otherlanguage}

\subsection{Permutations}

\foreignlanguage{polish}{\pl permutacje bez powtórzeń.}

A permutation maps all members of a set onto a sequence (no repetitions result).
The number of all possible permutations of a set with $n$ elements is:
%
\begin{equation}
    ^nP = n!
\end{equation}

\underline{Justification}:
Subsequent positions have their choices limited by the elements already chosen:
%
\begin{equation*}
    n\times(n-1)\times(n-2)\times \dotsb \times 1
\end{equation*}

\subsubsection{Circular permutations}

No element is first.
Hence all sequences which result from a rotation of the sequence are equivalent.
The number of such permutation is thus reduced by the factor of $n$ giving ${(n-1)!}$

\subsection{Partial permutations}

\foreignlanguage{polish}{\pl wariacje bez powtórzeń.
Permutacja bez powtórzeń jest szczególnym przypadkiem wariacji bez powtórzeń dla $n=k$.}

A partial permutation (sometimes called a `variation') is a shorter sequence of length $k$.
The number of all possible $k$\nobreakdash-\hspace{0pt}permutations of $n$ is:
%
\begin{equation}
    ^nP_k = \frac{n!}{(n-k)!}
\end{equation}

\underline{Justification}:
The multiplication ${n\times(n-1)\times(n-2)\times \dotsb}$ ends earlier, namely after $k$ elements, the last element being $(n-k+1)$.

% TODO: How many partial permutations are there in total?
% This information would be analogous to Eq.~\ref{eq:all_comb} for combinations.
% \sum_{i=0}^{n} ^nP_i

\subsection{Permutations with replacement}

\foreignlanguage{polish}{\pl wariacje z powtórzeniami.}

A sequence of length $k$ in which elements are drawn from a set with $n$ elements with replacement.
The number of such permutations is:
%
\begin{equation}
    n^k
\end{equation}

\underline{Justification}:
Each element of the sequence is independent: $n\times n\times \dotsb$

\subsection{Multiset permutations}
\label{mulper}

\foreignlanguage{polish}{\pl permutacje z powtórzeniami.
Należy zauważyć, że określenie `z powtórzeniami' wynika z powtórzeń w początkowym multizbiorze, a nie wielokrotnego (powtórnego) używania danych elementów, tak jak ma to miejsce w wariacjach z powtórzeniami i kombinacjach z powtórzeniami.}

A multiset is a set in which certain elements are repeated and have multiplicities $m_1, m_2, \dotsc$.
An example of a multiset permutation is an anagram of a word in which certain letters are repeated.
The total number of such permutations is given by the multinomial coefficient (\cf binomial coefficient in Section~\ref{combinations})
%
\begin{equation}
    \binom{n}{m_1, m_2, \dotsc} = \frac{n!}{m_1!m_2!\dotsm}
\end{equation}

\underline{Justification}:
The number is the same as for a permutation but reduced by the number of permutations of each group of indistinguishable elements.

% TODO: Partial multiset permutations should also be a thing but a quick search didn't show anything.
% Maybe try to derive an equation.

\section{Combinations}

Order is not relevant.
A combination maps a set onto its subset (or multisubset if repetitions are allowed).

\subsection{Combinations}
\label{combinations}

The number of ways in which $k$\nobreakdash-\hspace{0pt}element subsets can be chosen from an $n$\nobreakdash-\hspace{0pt}element set is given by the binomial coefficient:
%
\begin{equation}
    ^nC_k = \binom{n}{k} = \frac{n!}{k!(n-k)!}
\end{equation}
%
read as `$n$ choose $k$'.
Note that binomial coefficients can be found from Pascal's triangle.

\underline{Justification}:
Combinations are partial permutations in which the order of the sequence is disregarded and hence their number is reduced by the number of permutations of this sequence, $k!$:
%
\begin{equation}
        ^nC_k = \frac{^nP_k}{^kP}
\end{equation}

\subsubsection{Number of all combinations}

The number of all combinations which can be formed from a set with $n$ elements:
%
\begin{equation}
    \label{eq:all_comb}
    \binom{n}{0} + \binom{n}{1} + \dotsb + \binom{n}{n}= \sum_{k=0}^{n} \binom{n}{k}
\end{equation}
%
To find this sum, binomial expansion can be used:
%
\begin{equation}
    \begin{split}
        (x+y)^n & = \binom{n}{0} x^n y^0 + \binom{n}{1} x^{n-1} y^1 + \dotsb + \binom{n}{n-1} x^1 y^{n-1} + \binom{n}{n} x^0 y^n \\
                & = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k
    \end{split}
\end{equation}
%
Using the binomial expansion for $x=y=1$, the number of all combinations can be found to be $2^k$.

\subsubsection{Other properties}

Symmetry relationship:
%
\begin{equation}
    \label{eq:symrel}
    \binom{n}{k} = \binom{n}{n-k}, \qquad 0 \le k \le n
\end{equation}

\subsection{Combinations with replacement}

Also called a $k$\nobreakdash-\hspace{0pt}multicombination or a multisubset of size $k$, a $k$\nobreakdash-\hspace{0pt}combination with replacement can be best understood using the ice cream scoops analogy.\cite{mathsisfun}
Imagine ice cream boxes with different flavours.
A robotic arm moves along the boxes and over each box it can perform one of two actions: scoop or move along (shift).
Multiple scoops as well as multiple shifts are allowed.
The sequence of actions can be noted down using symbols \eg arrows and circles.
The total number of scoops is given by $k$, while the total number of shifts must equal the number of flavours ($n$) reduced by 1.

The number of possible combinations equals the number of multiset permutations (Section~\ref{mulper}) of the symbolic notation.
The total length of the notation equals $n-1+k$.
Scoops appear $k$ times and shifts $n-1$ times.
The formula for the number of such multiset permutations can be rearranged to a binomial coefficient, namely `$n-1+k$ choose $k$':
%
\begin{equation}
    \frac{(k+n-1)!}{(n-1)!k!} = \frac{(k+n-1)!}{(k+n-1-k)!k!} = \binom{n-1+k}{k},
\end{equation}
%
which is sometimes denoted as:
%
\begin{equation*}
    \left(\!\!\!\binom{n}{k}\!\!\!\right)
\end{equation*}
%
and read as `$n$ multichoose $k$'.

\subsubsection{Properties}

Using the symmetry relation (Eq.~\ref{eq:symrel}) for binomial coefficient it can be shown that:
%
\begin{equation}
    \left(\!\!\!\binom{n}{k}\!\!\!\right) = \binom{n-1+l}{k} = \binom{n-1+k}{n-1+k-k} = \binom{n-1+k}{n-1} = \left(\!\!\!\binom{k+1}{n-1}\!\!\!\right)
\end{equation}

\begin{thebibliography}{9}

    \bibitem{wiki}
    Wikipedia entries on \href{http://en.wikipedia.org/wiki/Permutation}{Permutation}
    and
    \href{http://en.wikipedia.org/wiki/Combination}{Combination}

    \bibitem{pl}
    \pl
    \url{http://matematyka.pisz.pl/strona/3425.html} \\
    i \url{http://www.math.edu.pl/kombinatoryka}

    \bibitem{mathsisfun}
        % Manually breaking url
	% http://tex.stackexchange.com/a/78102/64793
        \href{http://www.mathsisfun.com/combinatorics/combinations-permutations.html}{\nolinkurl{http://www.mathsisfun.com/combinatorics/}}\\
	\href{http://www.mathsisfun.com/combinatorics/combinations-permutations.html}{\nolinkurl{combinations-permutations.html}}

    \bibitem{riley} K.F. Riley, M.P. Hobson, S.J. Bence, \textit{Mathematical Methods for Physics and Engineering. A Comprehensive Guide}, 3rd edition, Cambridge University Press, 2006, p. 1133-9.

\end{thebibliography}

\end{document}