--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/combinatoric.rst	Wed Mar 09 21:23:23 2016 +0200
@@ -0,0 +1,97 @@
+
+==============
+ 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!
+