Combinatoric

Permutation

perm(n) = n!

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

So by definition:

choose(n, 0) = 1choose(n, n) = 1

choose(n, < 0) = 0choose(n, > n) = 0

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

From this properties by induction:

choose(n, m) = n! ⁄ (n − m)! ⁄ m!

Proof:

choose(1, m) = 1 = 1! ⁄ (1 − m)! ⁄ m!, form ∈ 0, 1

Assume that we prove for n − 1, so:

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!

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.

part(m₁, ..., m_n) = (∑_{i ∈ 1..n}m_i)! ⁄ ∏_{i ∈ 1..n}m_i!

For n = 2 it is a number of combinations:

part(m₁, m₂) = choose(m₁ + m₂, m₂) = (m₁ + m₂)! ⁄ (m₁!·m₂!)

So:

part(m₁, m₂) = choose(m₁ + m₂, m₂)

= choose(m₁ + m₂ − 1, m₂) + choose(m₁ + m₂ − 1, m₂ − 1)

= part(m₁ − 1, m₂) + part(m₁, m₂ − 1)

Generalise thinking:

part(m₁, ..., m_n) = part(m₁ − 1, m₂, ..., m_n) + part(m₁, m₂ − 1, m₃, ..., m_n) + ... + part(m₁, ..., m_n − 1, m_n − 1)

Now we can prove partition formula by induction:

part(m₁, ..., m_n) = ∑_i = 1..npart(..., 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..nm_j) − 1)! ⁄ ∏_j = 1..n(m_j − 1)! ⁄ ∏_{j = 1..n, j ≠ i}m_j

= ((∑_j = 1..nm_j) − 1)! ⁄ ∏_j = 1..n(m_j − 1)!·∑_i = 1..n1 ⁄ ∏_{j = 1..n, j ≠ i}m_j

= ((∑_j = 1..nm_j) − 1)! ⁄ ∏_j = 1..n(m_j − 1)!·∑_i = 1..nm_i ⁄ ∏_j = 1..nm_j

= ((∑_j = 1..nm_j) − 1)! ⁄ ∏_j = 1..n(m_j − 1)! ⁄ ∏_j = 1..nm_j·∑_i = 1..nm_i

= ((∑_j = 1..nm_j) − 1)! ⁄ ∏_j = 1..nm_j!·∑_i = 1..nm_i

= (∑_j = 1..nm_j)! ⁄ ∏_j = 1..nm_j!