Latest revision as of 10:22, 22 July 2017

Basic binomial coefficients:

AOCP/Binomial Coefficients

More complicated choices:

Multisets:

AOCP/Multisets

Book notes:

Analytic Combinatorics - book by Flajolet and Sedgewick
Applied Combinatorics - book by Keller and Trotter

Flags

@@ Line 1: / Line 1: @@
-=Notes=
+Basic binomial coefficients:
+* [[AOCP/Binomial Coefficients]]
-==Knuth AOCP Volume 3 Sorting and Searching==
+More complicated choices:
+* [[LatticePaths]]
+* [[AOCP/Multinomial Coefficients]]
+* [[AOCP/Generating Functions]]
+* [[AOCP/Combinatorics]]
-===5.1 Combinatorics===
+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>
-9 1 8 2 6 4 7 3
-3 6 4 0 2 2 1 0
-</pre>
-<math>
-\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.
 =Flags=

Algorithms/Combinatorics: Difference between revisions

From charlesreid1

Latest revision as of 10:22, 22 July 2017

Flags