on-combinatorics.tex

\section{Elements of combinatorics calculus}

\subsection{Permutations $P_n$}

Given a vector $\left ( a_1, \ldots, a_n \right) $ the number of
permutations (ie. the possible ways to order elements $a_i$) is
$n!$. A simple proof of that is as follow: for position 1 are
available $n$ elements, for the second position (after having choosed
an element for the first one) are available $n-1$ elements, down
to the latter position $n$ where only one element is left, hence $n!$.

It is interesting to show how to add a new element $a_{n+1}$ to
existing permutations from a set $\left \lbrace a_1, \ldots,
  a_n\right\rbrace $, moreover this is indeed another proof (by induction) to
the number $n!$ justified above.

Having permutations of length $n$ by hypothesis,
we study how is it possible to add $a_{n+1}$ into a
given permutation $w = \left ( a_1, a_2, \ldots, a_n\right) $:
\begin{displaymath}
  \begin{split}
    &\left ( a_{n+1}, a_1, a_2, \ldots, a_n\right)\\
    &\left ( a_1, a_{n+1}, a_2, \ldots, a_n\right)\\
    &\ldots\\
    &\left ( a_1, a_2, \ldots, a_{n+1}, a_n\right)\\
    &\left ( a_1, a_2, \ldots, a_n, a_{n+1}\right)\\
  \end{split}
\end{displaymath}
Those new vectors are $n+1$ because in the original permutation $w =
\left ( a_1, a_2, \ldots, a_n\right) $ there are $n-1$ ``internal
holes'' between the consecutive elements $(\ldots, a_i, \Box,
a_{i+1}, \ldots)$, plus the
left-most and right-most ``external holes'' $(\Box, a_1,...)$ and
$(..., a_n, \Box)$. So far we've considered only one permutation $w$
of $n$ elements, repeating the same reasoning for the others $w_i$
(which are $n!-1$), it must exists $n+1$ new vectors for each one of
them. So the number of permutations of $n+1$ elements is $(n+1)n! =
(n+1)!$, what we would have expected.

\subsection{Dispositions $D_{n,k}$}

A special case of permutations are dispositions, that is the number of
different ways in which $k$ elements can be chosen from a set of
length $n$, such that $n \geq k$: we have $n$ elements available for the
first choice, $n-1$ for the second choice down to $n-k+1$ elements
for the $k$-th choice, hence $D_{n,k} = n(n-1)\cdots(n-k+1)$.  We can
write an example to show how to build dispositions. Let $\Omega =
\left \lbrace a,b,c, d\right\rbrace $ and we want to build $D_{4,2}$,
that is the set of ordered pairs, paying attention that $ \forall i:
(i,i)\not \in D_{n,2}$, ie. no repetition allowed.
The following pairs are the candidates (the
pairs of the form $(i,i)$ aren't listed because after we choose $i$
for the first position it isn't possible to choose it again for the
second):
\begin{displaymath}
  \begin{split}
    \left ( a, b \right)\quad
    \left ( a, c \right)\quad
    \left ( a, d \right)\\
    \left ( b, a \right)\quad
    \left ( b, c \right)\quad
    \left ( b, d \right)\\
    \left ( c, a \right)\quad
    \left ( c, b \right)\quad
    \left ( c, d \right)\\
    \left ( d, a \right)\quad
    \left ( d, b \right)\quad
    \left ( d, c \right)\\
  \end{split}
\end{displaymath}
We've build the previous matrix because we take care about
the order in which the pairs are built. In the next section we'll see
that there exists another set that doesn't take care of the order.

\subsection{Combinations $C_{n,k}$}

A special case of dispositions are combinations. Symbol $C_{n,k}$ denotes
a set of sets $\left \lbrace \left \lbrace
    a_{i_1}, \ldots, a_{i_k} \right\rbrace , \ldots,  \left \lbrace
    a_{j_1}, \ldots, a_{j_k} \right\rbrace\right\rbrace$ without
regard to the order in which elements $a_{1}, \ldots, a_{k}$ appear in
a set $s \in C_{n,k}$.

We can see combinations as dispositions modulo the symmetric relation:
$(a_j,a_i) \in C_{n,2} \rightarrow (a_i, a_j) \not \in C_{n,2}$ and $(a_i,a_i)\not
\in C_{n,2}, \forall i$. The following sub matrix is to combinations
as the previous one is to dispositions:
\begin{displaymath}
  \begin{split}
    \left ( a, b \right)\quad
    \left ( a, c \right)\quad
    \left ( a, d \right)\\
    \quad
    \left ( b, c \right)\quad
    \left ( b, d \right)\\
    \quad
    \quad
    \left ( c, d \right)\\
    \quad
    \quad
    \\
  \end{split}
\end{displaymath}
The combinations matrix is obtained by the disposition matrix, breaking
the symmetry, only half of them belongs to $C_{4,2}$, hence:
$$C_{n,k} = {{n}\choose{k}} = \frac{D_{n,k}}{k!} =
\frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!} $$

\subsection{Binomial coefficients}

In this section we study the binomial coefficients, and in the
particular the writing $(a + b)^n$ where $n\in \mathbb{N}$. It is known that:
\begin{displaymath}
  (a+b)^n = \sum_{k=0}^{n}{{{n}\choose{k}}a^k b^{n-k} }
\end{displaymath}
Now consider $(a + b)^r = \sum_{k=0}^{r}{{{r}\choose{k}}a^k b^{r-k} }$ where
$r\in \mathbb{R}$, in particular we have to pay attention to the
binomial coefficient under $r\in \mathbb{R}$:
\begin{displaymath}
  {{r}\choose{k}}  = \frac{r(r-1)\cdots(r-k+1)}{k!}
\end{displaymath}
The previous rewriting makes sense, instead we would have had problem
with $ \frac{r!}{k!(r-k)!} $ since $r!$ isn't defined for $r \in \mathbb{R}$
because the recursion doesn't have a base case.
Now do simple manipulation:
\begin{displaymath}
  (a+b)^r = \left( a\left(1 +  \frac{b}{a}\right)\right)^r =
  a^r \left(1 +  \frac{b}{a}\right)^r
\end{displaymath}
In general we can call $z= \frac{b}{a} $ and reduce to study the
function $f(z)=(1+z)^r$, which can be expanded with Taylor near $0$:
\begin{displaymath}
  f(z) = \sum_{k \geq 0}{ \frac{f^{(k)}(0)}{k!} z^k }
\end{displaymath}
Study the derivatives of $f(z)$:
\begin{displaymath}
  \begin{split}
    f^{(0)}(0) &= 1 \\
    f^{(1)}(z) &= r(1+z)^{r-1} \quad \rightarrow
    \quad f^{(1)}(0) =    r\\
    f^{(2)}(z) &= r(r-1)(1+z)^{r-2} \quad \rightarrow
    \quad f^{(2)}(0) = r(r-1)\\
    f^{(k)}(z) &= r(r-1)\cdots(r-k+1)(1+z)^{r-k}
    \quad \rightarrow \quad f^{(k)}(0) = r(r-1)\cdots(r-k+1)\\
  \end{split}
\end{displaymath}
Now we can substitute the previous results into $f(z)$ expansion:
\begin{displaymath}
  f(z) = \sum_{k \geq 0}{ \frac{f^{(k)}(0)}{k!} z^k } =
  \sum_{k \geq 0}{ \frac{r(r-1)\cdots(r-k+1)}{k!} z^k } =
  \sum_{k \geq 0}{ {{r}\choose{k}} z^k }
\end{displaymath}
This is an important result since $k$-th coefficient of Taylor
expansion of a function $f(z) = (1+z)^r$ gives the value of ${{r} \choose {k}}$:
observe that $z$ is a dummy variable since its role is only releated to
derivation to build the expansion.

\begin{exercise}
  \label{exercise:first-on-comb-with-real}
  Compute ${{ \frac{1}{2} }\choose{3}} $.
\end{exercise}
\begin{proof}[Sol]
  It is sufficient to build a function $f(z) = (1+z)^r$ with the right
  value for $r$ and then expand $f(z)$ with Taylor, than coefficient of
  $z^3$ is the desired value ${{ r }\choose{3}} $.

  In this case $r= \frac{1}{2} $, so :
  \begin{displaymath}
      \begin{split}
          f(z) = \sqrt{1+z} &=
          {{\frac{1}{2}}\choose{0}}z^0 + {{\frac{1}{2}}\choose{1}}z^1 +
          {{\frac{1}{2}}\choose{2}}z^2 + {{\frac{1}{2}}\choose{3}}z^3 + \ldots \\
          &= 1 + \frac{z}{2} - \frac{z^{2}}{8} + \frac{z^{3}}{16} - \frac{5 z^{4}}{128} + \frac{7 z^{5}}{256} + \mathcal{O}\left(z^{6}\right)
      \end{split}
  \end{displaymath}
  Hence $ { \frac{1}{2} \choose {3} } = \frac{1}{16}$ as required \footnote{
      see \url{http://nbviewer.ipython.org/github/massimo-nocentini/pacc/blob/master/sympy-notebook/Analysis\%20of\%20Algorithms.ipynb?flush_cache=true\#First-exercise}
      for more details}.

\end{proof}

Now suppose to have ${{-n}\choose{k}}$ where $ n\in \mathbb{N}  $:
\begin{displaymath}
  {{-n}\choose{k}} =  \frac{-n(-n-1)\cdots(-n-k+1)}{k!}
\end{displaymath}
At numerator there are $k$ terms, so factor -1:
\begin{displaymath}
  \begin{split}
    {{-n}\choose{k}} &= \frac{(-1)^k (n + k-1)\cdots(n+1)n}{k!} =
    \frac{(-1)^k (n + k-1)\cdots(n+1)n(n-1)!}{k!(n-1)!}\\
    &= \frac{(-1)^k (n + k-1)!}{k!(n-1)!} = (-1)^k {{n+k-1}\choose{k}}
  \end{split}
\end{displaymath}

\subsection{Central Binomial Coefficients and Catalan Numbers}

We introduce in this section a very important class of
numbers called \emph{Catalan numbers}. We proceed step by step,
introducing a recurrence relation for ${{n}\choose{k}}$ where $n,k\in
\mathbb{N} $.

Given a set of $n$ elements $a_1, \ldots,a_n$ it is possible to
generate the set $S = C_{n,k}$ of combinations of length $k$. Now choose an
element, let say $a_j$, and partition $S$ in two set:
\begin{displaymath}
  \begin{split}
    S_{a_j}^+ &= \left \lbrace (a_{\pi(1)}, \ldots, a_{\pi(k)}) |
      \exists i: a_j = a_{\pi(i)} \right\rbrace \\
    S_{a_j}^- &= \left \lbrace (a_{\pi(1)}, \ldots, a_{\pi(k)}) |
      \forall i: a_j \not = a_{\pi(i)} \right\rbrace \\
  \end{split}
\end{displaymath}
where $\pi: \left \lbrace 1, \ldots, k \right\rbrace \rightarrow \left
  \lbrace 1, \ldots, n \right\rbrace $ is one-to-one. The following
holds:
\begin{displaymath}
  {{n}\choose{k}} = \left| S_{a_j}^+ \right| + \left| S_{a_j}^-
  \right| = {{n-1}\choose{k-1}} +  {{n-1}\choose{k}}
\end{displaymath}
\begin{proof}
  We've chosen $a_j$ to partition $S$, hence:
  \begin{itemize}
  \item $\left| S_{a_j}^+ \right| = {{n-1}\choose{k-1}}$ because
    $S_{a_j}^+$ contains sets such that everyone of them contains $a_j$
    in turn. But we can build $ S_{a_j}^+$ from scratch choosing $k-1$ elements ($a_j$
    is contained in every set of $S_{a_j}^+$, hence we have to build
    combinations of length $k-1$) from $\left \lbrace a_1, \ldots, a_n
    \right\rbrace \setminus \left \lbrace a_j \right\rbrace $ ($a_j$
    is an implicit choice, so we choose from $n-1$ elements)
  \item $\left| S_{a_j}^- \right| = {{n-1}\choose{k}}$ because $
    S_{a_j}^-$ contains sets such that everyone of them doesn't contain
    $a_j$. But we can build $ S_{a_j}^- $ from scratch choosing $k$
    elements ($a_j$ isn't contained in any set of $S_{a_j}^-$, hence
    we have to build combinations of length $k$) from $\left \lbrace
      a_1, \ldots, a_n \right\rbrace \setminus \left \lbrace a_j
    \right\rbrace $ ($a_j$ is an impossible choice, so we choose from
    $n-1$ elements)
  \end{itemize}
\end{proof}

The recurrence $ {{n}\choose{k}} = {{n-1}\choose{k-1}} +
{{n-1}\choose{k}}$ allow us to build an infinite matrix reported in
\autoref{tab:central-binomial-coefficients} with interesting numbers
written inside a ticket as $\ticket{j}$.
\begin{table}[ht]
  \caption{Central Binomial Coefficients}
  \label{tab:central-binomial-coefficients}
  \begin{center}
    \begin{tabular}{c|ccccccccc}
      & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots & $k$ \\
      \hline
      0 & $\ticket{1}$ &  &  &  & & &  &  &\\
      1 & 1 & 1 &  &  & & & && \\
      2 & 1 & $\ticket{2}$ & 1 &  & & & && \\
      3 & 1 & 3 & 3 & 1 &  & &&&  \\
      4 & 1 & 4 & $\ticket{6}$ & 4 & 1 & &&&  \\
      5 & 1 & 5 & 10 & 10 & 5 & 1&&&  \\
      6 & 1 & 6 & 15 & $\ticket{20}$ & 15 & 6& 1&&  \\
      \vdots&  &  &  &  &  & &&$\ddots$&  \\
      \vdots&  && & & & &  & ${{n-1}\choose{k-1}} $  & ${{n-1}\choose{k}} $  \\
      n&  &  & &  & &&  & & ${{n}\choose{k}} $ \\
    \end{tabular}
  \end{center}
\end{table}
The numbers ${{2h}\choose{h}}$ are called \emph{Central Binomial
  Coefficients}, while $ \frac{1}{h+1}{{2h}\choose{h}}$ are called
\emph{Catalan Numbers}, in the following pair we report the start of
these sequences of number, respectively:
$$ \left [ 1, \quad 2, \quad 6, \quad 20, \quad 70, \quad 252, \quad 924, \quad 3432, \quad 12870, \quad 48620\right ] $$
$$\quad \left [ 1, \quad 1, \quad 2, \quad 5, \quad 14, \quad 42, \quad 132, \quad 429, \quad 1430, \quad 4862\right ] $$

We finish this section on combinatorics with some exercises.
\begin{exercise}
  Compute ${{ -\frac{1}{2} }\choose{k}} $.
\end{exercise}
\begin{proof}[Sol]
  Using the approach followed in Exercise
  \autoref{exercise:first-on-comb-with-real}, we can build the
  function $f(z) = \frac{1}{\sqrt{1+z}} $ and expand it with Taylor, getting:
  $$ f(z) = \frac{1}{\sqrt{1+z}}  = 1 - \frac{z}{2} + \frac{3 z^{2}}{8} - \frac{5 z^{3}}{16} + \frac{35 z^{4}}{128} - \frac{63 z^{5}}{256} + \mathcal{O}\left(z^{6}\right) $$

  Here we use another approach that follow the definition:
  \begin{displaymath}
    \begin{split}
      {{- \frac{1}{2} }\choose{k}} &= \frac{- \frac{1}{2}(- \frac{1}{2}
        -1)(- \frac{1}{2}-2)\cdots(- \frac{1}{2}-k +1) }{k!} = \\
      &= \frac{- \frac{1}{2}(- \frac{3}{2})(- \frac{5}{2})\cdots(-
        \frac{2k-1}{2}) }{k!} =
      \frac{(-1)^k 1 3 5\cdots (2k-1) }{2^k k!} =\\
      &=\frac{(-1)^k 1 3 5\cdots (2k-1) \quad 2 4 6\cdots 2k } {2^k
        k!\quad 2 4 6\cdots 2k } = \frac{(-1)^k (2k)! }
      {2^k k!\quad 2^k(1 2 3 \cdots k) } =\\
      &= \frac{(-1)^k (2k)! } {2^k k!\quad 2^kk! } =\frac{(-1)^k}{4^k }
      {{2k}\choose{k}}
    \end{split}
  \end{displaymath}

  Evaluating for $k \in \{0, \ldots, 5\}$ we get the following list of coefficients
  \footnote{see \url{http://nbviewer.ipython.org/github/massimo-nocentini/pacc/blob/master/sympy-notebook/Analysis\%20of\%20Algorithms.ipynb?flush_cache=true\#Second-exercise} for details}:
  $$\left [ 1, \quad - \frac{1}{2}, \quad \frac{3}{8}, \quad - \frac{5}{16}, \quad \frac{35}{128}, \quad - \frac{63}{256}\right ]$$

\end{proof}