#### Combinatorics Math 850 Fall 2009 Class Log

 1. Aug 24, Mon. course overview and logistics; initial student survey; what is combinatorics? Sec 1.1: basic counting principles: sum, product, counting in two ways, bijection 2. Aug 26, Wed. ways to pick k objects from an n-set; permutations; combinations; binomial coefficients; polynomial principle; binomial theorem 3. Aug 28, Fri. discussion of multivariate polynomial principle; stars and bars; compositions; Sec 1.2: basic identities for binomial coefficients; Pascal's identity; sums of binomial coefficients 4. Aug 31, Mon. lattice paths; sums of binomial coefficients; sums of powers of integers; Vandermonde convolution; extended binomial coefficients; extended binomial theorem 5. Sep 2, Wed. Delannoy paths and numbers; size of balls in the l1 metric; have the same cardinality 6. Sep 4, Fri. Sec 1.3: basic graph theory definitions; counting graphs on [n]; Cayley's formula; bijection Sep 7, Mon. Labor Day - no class 7. Sep 9, Wed. counting trees with specified degrees; multinomial coefficients; multinomial theorem; basic properties of multinomial coefficients; Fermat's Little Theorem; Bertrand's ballot theorem; reflection principle 8. Sep 11, Fri. Catalan numbers; bijections with parenthesization, ordered rooted binary trees, triangulations; Sec 2.1: recurrences; regions formed by lines in the plane; Fibonacci numbers 9. Sep 14, Mon. discussion of homework; adjusted Fibonacci numbers; some identities involving the Fibonacci numbers; derangements and recurrence 10. Sep 16, Wed. Catalan recurrence; number of triangulations of convex polygons; recurrences with multiple parameters; recurrence for Delannoy paths and balls in Z^n with radius m in the l_1 metric; Sec 2.1: solving recurrences; linear recurrences of order k with constant coefficients 11. Sep 18, Fri. method of characteristic equations; formula for Fibonacci numbers; repeated roots; example 12. Sep 21, Mon. method for inhomogoneous recurrences; regions in the plane determined by n lines; generating functions; Fibonacci example 13. Sep 23, Wed. finished Fibonacci example; generating function method for inhomogeneous recurrences; regions in the plane determined by n lines; power series for powers of 1/(1-cx); generating function for the Catalan numbers 14. Sep 25, Fri. Stirling's formula; Sec 3.1: combinatorial constructions of generating functions; convolution; making change with coins problem 15. Sep 28, Mon. permutation statistics: by inversion number; by cycle number (recurrence and generating function); Eulerian numbers; Worpitzky's identity 16. Sep 30, Wed. proof of Worpitzky's identity; formula for Eulerian numbers Sec 3.2: relationship between operations on sequences and their generating functions; simple examples 17. Oct 2, Fri. convolutions; Snake Oil; examples involving Fibonacci numbers, Delannoy numbers, and number of permutations with given number of cycles 18. Oct 5, Mon. Sec 3.3: exponential generating functions; binomial convolution; words over an alphabet; flags on flagpoles 19. Oct 7, Wed. ordered partitions; Stirling numbers of the first and second kind; polynomial bases Oct 8, Thurs. Test #1 20. Oct 9, Fri. binomial inversion formula; formula for derangement numbers; solving linear recurrences using exponential generating functions 21. Oct 12, Mon. returned Test 1; the exponential formula; examples; recurrence for c_n 22. Oct 14, Wed. Sec 3.4: the Twelvefold Way; partitions of an integer n; ordinary generating functions; asymptotics 23. Oct 16, Fri. bijections between different types of partitions; Ferrers diagrams; triangles with integer side lengths; Euler's identity Oct 19, Mon. Fall break, no class. 24. Oct 21, Wed. discussion of informal feedback; Sec 4.1: Principle of Inclusion-Exclusion; proof; derangement numbers 25. Oct 23, Fri. No class. 26. Oct 26, Mon. examples applying PIE: combinations of multisets; Stirling numbers of the second kind; Eulerian numbers 27. Oct 28, Wed. restricted permutations; rook polynomials; seating men and women around a table 28. Oct 30, Fri. sums via PIE; Sec 4.2: counting under the presence of symmetry; batons; counting orbits of colorings; stabilizers 29. Nov 2, Mon. Burnside's lemma; application to 4-bead necklaces; cycle structure, cycle index, pattern inventory; application to 4-bead necklaces 30. Nov 4, Wed. coloring the cube; counting isomorphism classes of graphs with fixed number of edges; using the pattern inventory to enumerate by cost 31. Nov 6, Fri. introduction to coding theory; encoder, channel, and decoder; binary repetition code; binary symmetric channel; binary erasure channel; error of a decoder; maximum likelihood decoder; on BSC; Hamming distance; nearest neighbor decoding 32. Nov 9, Mon. Shannon's theorem for BSC; binary entropy function; discussion; nearest neighbor decoding; packing Hamming balls 33. Nov 11, Wed. relation of minimum distance of coding and number of correctable errors; parity code; sphere packing bound; volume of Hamming ball; linear codes; parameters; generator matrix; minimum distance and minimum weight of a codeword; parity check matrix 34. Nov 13, Fri. finding parity check matrix; dual codes; orthogonality in characteristic p; binary Hamming code; parameters; relation between min dist and linear indep of columns of parity check matrix 35. Nov 16, Mon. binary Hamming codes are perfect; standard array decoding; coset leaders; syndrome decoding; syndrome decoding for Hamming codes 36. Nov 18, Wed. demonstration of Hamming code decoding; Gilbert-Varshamov bound; fraction of linear codes that attain Gilbert-Varshamov bound Nov 19, Thurs. Test #2 37. Nov 20, Fri. No class. 38. Nov 23, Mon. Singleton bound; examples of MDS codes; asymptotic bounds; asymptotic Singleton bound; q-ary entropy function; lower and upper bounds on size of Hamming ball Nov 25, Wed. — Nov 27, Fri. Thanksgiving break, no class. 39. Nov 30, Mon. asymptotic versions of sphere packing bound and Gilbert-Varshamov bound; plots of asymptotic bounds; definition of generalized Reed-Solomon codes; Vandermonde determinant; dimension and minimum distance 40. Dec 2, Wed. dual code of GRS is also GRS with same code locators; generator matrix and encoding; polynomial interpretation 41. Dec 4, Fri. conventional RS codes; form of parity check matrix; generator polynomial; started decoding of GRS codes; syndrome polynomial; evaluations 42. Dec 7, Mon. error locator polynomial and error evaluator polynomial; properties; key equation relating ELP, EEP, and syndrome polynomial; solving the key equation using a linear system 43. Dec 9, Wed. Snow day - no class. 44. Dec 11, Fri. correctness of GRS decoding algorithm; example; burst errors, interleaving, and CD encoding; modern coding theory Dec 15, Tue, 10:00am-12:00pm. Final Exam