|
1 |
|
2 ============== |
|
3 Combinatoric |
|
4 ============== |
|
5 .. contents:: |
|
6 :local: |
|
7 |
|
8 Permutation |
|
9 =========== |
|
10 |
|
11 .. math:: perm(n) = n! |
|
12 |
|
13 Number of selecting m position from n places |
|
14 ============================================ |
|
15 |
|
16 It like a number of binary numbers length :math:`n` with :math:`m` ones. |
|
17 |
|
18 So by definition: |
|
19 |
|
20 .. math:: |
|
21 |
|
22 choose(n, 0) = 1 |
|
23 choose(n, n) = 1 |
|
24 |
|
25 choose(n, <0) = 0 |
|
26 choose(n, >n) = 0 |
|
27 |
|
28 choose(n, m) = choose(n-1, m-1) + choose(n-1, m) |
|
29 |
|
30 From this properties by induction: |
|
31 |
|
32 .. math:: choose(n, m) = n! / (n-m)! / m! |
|
33 |
|
34 Proof: |
|
35 |
|
36 .. math:: choose(1, m) = 1 = 1!/(1-m)!/m!, for m∈{0,1} |
|
37 |
|
38 Assume that we prove for :math:`n-1`, so: |
|
39 |
|
40 .. math:: |
|
41 |
|
42 choose(n, m) = choose(n-1, m-1) + choose(n-1, m) |
|
43 |
|
44 = (n-1)!/(n-m)!/(m-1)! + (n-1)!/(n-1-m)!/m! |
|
45 |
|
46 = (n-1)!/(n-1-m)!/(m-1)!·(1/(n-m) + 1/m) |
|
47 |
|
48 = (n-1)!/(n-1-m)!/(m-1)!·(m+(n-m))/(n-m)/m = n!/(n-m)!/m! |
|
49 |
|
50 Partitions |
|
51 ========== |
|
52 |
|
53 It like a number of numbers in n-base with 0 in m_1 positions, 1 in m_2 |
|
54 positions, ..., (n-1) in m_n positions. |
|
55 |
|
56 .. math:: part(m_1, ..., m_n) = (∑_{i∈1..n} m_i)! / ∏_{i∈1..n} m_i! |
|
57 |
|
58 For :math:`n=2` it is a number of combinations: |
|
59 |
|
60 .. math:: part(m_1, m_2) = choose(m_1+m_2, m_2) = (m_1+m_2)! / (m_1!·m_2!) |
|
61 |
|
62 So: |
|
63 |
|
64 .. math:: |
|
65 |
|
66 part(m_1, m_2) = choose(m_1+m_2, m_2) |
|
67 |
|
68 = choose(m_1+m_2 - 1, m_2) + choose(m_1+m_2 - 1, m_2 - 1) |
|
69 |
|
70 = part(m_1 - 1, m_2) + part(m_1, m_2 - 1) |
|
71 |
|
72 Generalise thinking: |
|
73 |
|
74 .. math:: |
|
75 |
|
76 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) |
|
77 |
|
78 Now we can prove partition formula by induction: |
|
79 |
|
80 .. math:: |
|
81 |
|
82 part(m_1, ..., m_n) = ∑_{i=1..n} part(..., m_{i-1}, m_i - 1, m_{i+1}, ...) |
|
83 |
|
84 = ∑_{i=1..n} (m_i - 1 + ∑_{j=1..n, j≠i} m_j)! / (m_i - 1)! / ∏_{j=1..n, j≠i} m_j! |
|
85 |
|
86 = ∑_{i=1..n} ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} (m_j - 1)! / ∏_{j=1..n,j≠i} m_j |
|
87 |
|
88 = ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} (m_j - 1)! · ∑_{i=1..n} 1 / ∏_{j=1..n,j≠i} m_j |
|
89 |
|
90 = ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} (m_j - 1)! · ∑_{i=1..n} m_i / ∏_{j=1..n} m_j |
|
91 |
|
92 = ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} (m_j - 1)! / ∏_{j=1..n} m_j · ∑_{i=1..n} m_i |
|
93 |
|
94 = ((∑_{j=1..n} m_j) - 1)! / ∏_{j=1..n} m_j! · ∑_{i=1..n} m_i |
|
95 |
|
96 = (∑_{j=1..n} m_j)! / ∏_{j=1..n} m_j! |
|
97 |