|
|
| (3 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| =Notes=
| | Basic binomial coefficients: |
| | * [[AOCP/Binomial Coefficients]] |
|
| |
|
| ==Knuth AOCP Volume 3: Sorting and Searching: Combinatorics==
| | More complicated choices: |
| | * [[LatticePaths]] |
| | * [[AOCP/Multinomial Coefficients]] |
| | * [[AOCP/Generating Functions]] |
| | * [[AOCP/Combinatorics]] |
|
| |
|
| ===Permutations and Inversions===
| | Multisets: |
| | * [[AOCP/Multisets]] |
|
| |
|
| Knuth begins talking about sorting by talking about combinatorics and permutations of items.
| | Book notes: |
| | | * [[Analytic Combinatorics]] - book by Flajolet and Sedgewick |
| Start with definition of an inversion:
| | * [[Applied Combinatorics]] - book by Keller and Trotter |
| | |
| Let <math>a_1 a_2 a_3 \dots a_n</math> be a permutation of the integers <math>{1 \dots n}</math>.
| |
| | |
| If <math>i < j</math> and <math>a_i > a_j</math>, then <math>(a_i, a_j)</math> is an inversion.
| |
| | |
| Inversions are out-of-sorts pairs.
| |
| | |
| Cramer (1750) introduced inversions - utilized to find determinant.
| |
| | |
| Can also construct an inversion table:
| |
| | |
| Let <math>b_1 b_2 \dots b_n</math> denote the inversion table of <math>a_1 a_2 \dots a_n</math>. Then <math>b_j</math> is the number of elements to the left of j that are greater than j.
| |
| | |
| Example of sequence and its inversion table:
| |
| | |
| <pre>
| |
| 5 9 1 8 2 6 4 7 3
| |
| 2 3 6 4 0 2 2 1 0
| |
| </pre>
| |
| | |
| <math>
| |
| 0 \leq b_1 \leq n-1, 0 \leq b_2 \leq n-2, \dots, 0 \leq b_{n-1} \leq 1
| |
| </math>
| |
| | |
| Hall (1956) showed that inversion tables ''uniquely determine permutations'' - these make inversion tables alternative representations for different permutations.
| |
| | |
| Transformation technique: turn counting problems into inversion table problems
| |
| | |
| Now, suppose we want to count number of elements larger than their successor. (This is the number of j such that <math>b_j = n-j</math>).
| |
| | |
| Note that this idea is related to nested for loops:
| |
| | |
| <pre>
| |
| for(int i = 0; i < N; i++ ) {
| |
| for(int j = i; j < N; j++) {
| |
| </pre>
| |
| | |
| We have <math>b_j = n - j</math>
| |
| | |
| Since we know the probability that b1 equals n-1 is <math>P(b_1 = n-1) = \frac{1}{n}</math>,
| |
| | |
| and independently the probability that b2 equals n-2 is <math>P(b_2 = n-2) = \frac{1}{n-1}</math>,
| |
| | |
| and so on, then we can say:
| |
| | |
| <math>
| |
| \dfrac{1}{n} + \dfrac{1}{n-1} + \dots + 1 = H_{n}
| |
| </math>
| |
| | |
| These are the harmonic numbers.
| |
| | |
| ===Counting Inversions with Generating Functions===
| |
| | |
| Now, to analyze a sorting algorithm, we are interested in how many permutations of n elements have exactly k inversions. Number of inversions is denoted I, so this number is denoted <math>I_n(k)</math>
| |
| | |
| To pose this problem slightly differently: we can think of <math>I_n(k)</math> as a number that is produced by some kind of ''generating function'' into which we plug our n and our k, and out pops <math>I_n(k)</math>.
| |
| | |
| In fact, we can do this by defining an infinite series polynomial whose kth coefficient is precisely <math>I_n(k)</math>.
| |
| | |
| Also note that <math>I_n = \left( \binom{n}{2} - k \right) = I_n(k)</math>.
| |
| | |
| We define the generating function <math>G_n(z)</math> for a sequence containing n elements as:
| |
| | |
| <math>
| |
| G_n(z) = I_n(0) + I_n(1)z + I_n(2) z^2 + \dots = \sum_{k \geq 0} I_n(k) z^k
| |
| </math>
| |
| | |
| Now, we know that when we choose a particular item b as the next element of our sequence <math>b_1 b_2 b_3 \dots b_n</math>, that choice is independent of all other b's. Another thing we can observe is, there are two possible ways (two possible cases) for a sequence with n elements and k inversions:
| |
| * Either we take a sequence of length n-1 and k inversions, and add an item to it that does not change k; | |
| * Or, we take a sequence of length n and k-1 inversions, and we change an item such that we add an inversion k.
| |
| | |
| From these, we can construct the recursive relationship:
| |
| | |
| <math>
| |
| I_n(k) = I_n(k-1) + I_{n-1}(k) \qquad \mbox{for } k < n
| |
| </math>
| |
| | |
| Knuth then performs some magic, which he says is "not difficult to see," stating:
| |
| | |
| <math>
| |
| G_n(z) = (1 + z + \dots + z^{n-1}) G_{n-1}(z)
| |
| </math>
| |
| | |
| and therefore he is able to simplify the generating function to:
| |
| | |
| <math>
| |
| (1+z+\dots+z^{n-1}) ( \dots )(1+z+z^2+z^3)(1+z+z^2)(1+z)(1) = \dfrac{ (1-z^n)( \dots )(1-z^2)(1-z) }{ (1-z)^n }
| |
| </math>
| |
| | |
| ===Knuth Goes To Outer Space===
| |
| | |
| It is at this point that Knuth launches into a few pages of extremely difficult to follow material. Individual statements are sensible and logical, but how he gets them and where he's going with all of it is completely unclear...
| |
| | |
| Start by defining the generating function of n, divided by n factorial, as the generating function for the probability distribution of the number of inversions in a random permutation of n elements.
| |
| | |
| <math>
| |
| \dfrac{G_n(z)}{n!} = g_n(z)
| |
| </math>
| |
| | |
| Further, let us define the function
| |
| | |
| <math>
| |
| h_k(z) = \dfrac{(1+z+z^2+\dots+z^{k-1})}{k}
| |
| </math>
| |
| | |
| This is the generating function for the uniform distribution of a random non-negative integer that is less than k.
| |
| | |
| Now, we can write g in terms of h:
| |
| | |
| <math>
| |
| g_n(z) = h_1(z) h_2(z) \dots h_n(z)
| |
| </math>
| |
| | |
| Next, Knuth uses the following property:
| |
| | |
| <math>
| |
| E(g_n) = E(h_1) + E(h_2) + \dots + E(h_n)
| |
| </math>
| |
| | |
| <math>
| |
| Var(g_n) = Var(h_1) + Var(h_2) + \dots + Var(h_n)
| |
| </math>
| |
| | |
| (again, completely unclear where he gets this...)
| |
| | |
| ===Multiset Permutations===
| |
| | |
| Suppose we have a multiset
| |
| | |
| <math>
| |
| M = \{ a, a, a, b, b, c, d, d, d, d\} = \{ 3 \cdot a, 2 \cdot b, c, 4 \cdot d \}
| |
| </math>
| |
| | |
| and we wish to determine the number of permutations of this multiset into words of the form "aaabbcdddd". | |
| | |
| If each character were distinct, we have 10 characters, so there would be 10! configurations. But many of these are duplicated. To be more precise, for the case of a, where there are 3 a's, there will be exactly 3! configurations that are duplicates. So, we can eliminate these by dividing 10! by 3!. Next, for b, there will be exactly 2! configurations that are duplicates. And so on.
| |
| | |
| Then we can determine the number of permutations of M via:
| |
| | |
| <math>
| |
| N_{perm} = \dfrac{10!}{3! 2! 1! 4!}
| |
| </math>
| |
| | |
| In general, the number of permutations of a multiset is the ''multinomial coefficient'' defined as
| |
| | |
| <math>
| |
| \binom{n}{n_1, n_2, \dots} = \dfrac{n!}{n_1! n_2! \dots}
| |
| </math>
| |
| | |
| Knuth notes that these were known in ancient times: "The Hebrew Book of Creation (300 AD), which was the earliest literary product of Jewish philosophical mysticism, gives the correct values of the first seven factorials, after which it says 'Go on and obtain numbers which the mount cannot express and the ear cannot hear.'"
| |
| | |
| First appearance of permutations of multisets appeared in 1150, ''Lilavati'' of Bhascara Acharya.
| |
| | |
| Interesting note: he gives the formula for the sum of the permutations of this multiset as:
| |
| | |
| <math>
| |
| \dfrac{(4+8+5+5+5) \cdot 120 \cdot 11111}{5 \cdot 6} = 48555 + 45885 + \dots
| |
| </math>
| |
| | |
| Foata (1969) provided an extension called the "intercalation product" that makes it possible to extend ideas and results from sets to multisets fairly easily.
| |
| | |
| First, assume the elements of the multiset are ordered in some way. Now consider the two-line notation:
| |
| * The top line will contain the elements of M in non-decreasing order | |
| * The bottom line will contain the permutation itself
| |
| | |
| The intercalation product a T b of the top and bottom lines is done by expressing a and b in the two-line notation, then sorting columns into STABLE, non-decreasing order of the top line. Stable means, if there is a tie on the top line, break the tie using the original left-to-right order of the bottom row.
| |
| | |
| Example: the intercalation of these two multisets <code>c a d a b</code> and <code>b d d a d</code> would be:
| |
| | |
| <pre>
| |
| a a b c d
| |
| c a d a b
| |
| | |
| a b d d d
| |
| b d d a d
| |
| | |
| Intercalation:
| |
| a a a b b c d d d d
| |
| c a b d d a b d a d
| |
| </pre>
| |
| | |
| '''Example:'''
| |
| | |
| Suppose we have a string of characters a, b, c that has exactly:
| |
| * A occurrences of a
| |
| * B occurrences of b
| |
| * C occurrences of c
| |
| * k occurrences of adjacent pair ca
| |
| * l occurrences of adjacent pair cb
| |
| * m occurrences of adjacent pair ba
| |
| | |
| This can be thought of as two-line arrays of the form:
| |
| | |
| <pre>
| |
| A B C
| |
| a ... a b ... b c ... c
| |
| \______/ \______/ \_______/
| |
| (A - k - m) a's (m a's) (k a's)
| |
| \_____________________________/ \______/
| |
| (B - l) b's (l b's)
| |
| \_________________________________________________/
| |
| C c's
| |
| </pre>
| |
| | |
| When we use this representation, we can turn each row (corresponding to each symbol a, b, c) into an umber of possible ways to permute that letter.
| |
| | |
| '''enumeration of a'''
| |
| | |
| In the second line, the a's are enumerated as the product of three terms;
| |
| | |
| The first term represents the number of ways that we can distribute A a's among (A - k - m) positions (the positions in which we are free to select what comes after a):
| |
| | |
| <math>
| |
| \binom{A}{A-k-m}
| |
| </math>
| |
| | |
| The second term represents our choice of B b's to place in m slots (next to m a's, for the m 'ab' combinations):
| |
| | |
| <math>
| |
| \binom{B}{m}
| |
| </math>
| |
| | |
| The third term comes from our choice of C c's to place in k slots (next to k a's, for the k 'ac' combinations):
| |
| | |
| <math>
| |
| \binom{C}{k}
| |
| </math>
| |
| | |
| This gives the total number of possibilities for A:
| |
| | |
| <math>
| |
| \binom{A}{A-k-m} \binom{B}{m} \binom{C}{k}
| |
| </math>
| |
| | |
| '''enumeration of b'''
| |
| | |
| In the third row, the b's can be placed in the remaining positions as our choice of placing B b's plus k combinations "ac" into B-l slots:
| |
| | |
| <math>
| |
| \binom{B+k}{B-l}
| |
| </math>
| |
| | |
| (This is a little magical - I would have used B in the top, not B+k. Not sure how we know to do that, since Knuth does not explain.)
| |
| | |
| Next, we have a term representing our choice of C-k remaining c characters to couple with b characters to form l pairs of 'bc' combinations:
| |
| | |
| <math>
| |
| \binom{C-k}{l}
| |
| </math>
| |
| | |
| This brings the enumeration of ways to arrange the bs to:
| |
| | |
| <math>
| |
| \binom{B+k}{B-l} \binom{C-k}{l}
| |
| </math>
| |
| | |
| '''enumeration of c'''
| |
| | |
| Tthe remaining positions that are still vacant must be filled by c's,
| |
| | |
| <math>
| |
| \binom{C}{k}
| |
| </math>
| |
| | |
| (Again, some magic happening here - why does Knuth use C, instead of (C - k - l)?
| |
| | |
| '''total enumerations'''
| |
| | |
| This gives the total number of arrangements:
| |
| | |
| <math>
| |
| \binom{A}{A-k-m} \binom{B}{m} \binom{C}{k} \binom{B+k}{B-l} \binom{C-k}{l}
| |
| </math>
| |
|
| |
|
| =Flags= | | =Flags= |
