==============

 Combinatoric

==============

.. contents::

   :local:

Permutation

===========

.. math:: perm(n) = n!

Number of selecting m position from n places

============================================

It like a number of binary numbers length :math:`n` with :math:`m` ones.

So by definition:

.. math::

  choose(n, 0) = 1

  choose(n, n) = 1

  choose(n, <0) = 0

  choose(n, >n) = 0

  choose(n, m) = choose(n-1, m-1) + choose(n-1, m)

From this properties by induction:

.. math:: choose(n, m) = n! / (n-m)! / m!

Proof:

.. math:: choose(1, m) = 1 = 1!/(1-m)!/m!, for m∈{0,1}

Assume that we prove for :math:`n-1`, so:

.. math::

   choose(n, m) = choose(n-1, m-1) + choose(n-1, m)

   = (n-1)!/(n-m)!/(m-1)! + (n-1)!/(n-1-m)!/m!

   = (n-1)!/(n-1-m)!/(m-1)!·(1/(n-m) + 1/m)

   = (n-1)!/(n-1-m)!/(m-1)!·(m+(n-m))/(n-m)/m = n!/(n-m)!/m!

Partitions

==========

It like a number of numbers in n-base with 0 in m_1 positions, 1 in m_2

positions, ..., (n-1) in m_n positions.

.. math:: part(m_1, ..., m_n) = (∑_{i∈1..n} m_i)! / ∏_{i∈1..n} m_i!

For :math:`n=2` it is a number of combinations:

.. math:: part(m_1, m_2) = choose(m_1+m_2, m_2) = (m_1+m_2)! / (m_1!·m_2!)

So:

.. math::

   part(m_1, m_2) = choose(m_1+m_2, m_2)

   = choose(m_1+m_2 - 1, m_2) + choose(m_1+m_2 - 1, m_2 - 1)

   = part(m_1 - 1, m_2) + part(m_1, m_2 - 1)

Generalise thinking:

.. math::

   part(m_1, ..., m_n) = part(m_1 - 1, m_2, ..., m_n) + part(m_1, m_2 - 1, m_3, ..., m_n) + ... + part(m_1, ..., m_{n-1}, m_n - 1)

Now we can prove partition formula by induction:

.. math::

   part(m_1, ..., m_n) = ∑_{i=1..n} part(..., m_{i-1}, m_i - 1, m_{i+1}, ...)

   = ∑_{i=1..n} (m_i - 1 + ∑_{j=1..n, j≠i} m_j)! / (m_i - 1)! / ∏_{j=1..n, j≠i} m_j!

   = ∑_{i=1..n} ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} (m_j - 1)! / ∏_{j=1..n,j≠i} m_j

   = ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} (m_j - 1)! · ∑_{i=1..n} 1 / ∏_{j=1..n,j≠i} m_j

   = ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} (m_j - 1)! · ∑_{i=1..n} m_i / ∏_{j=1..n} m_j

   = ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} (m_j - 1)! / ∏_{j=1..n} m_j · ∑_{i=1..n} m_i

   = ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} m_j! · ∑_{i=1..n} m_i

   = (∑_{j=1..n} m_j)! / ∏_{j=1..n} m_j!