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

    Back This page last modified .