#### Discrete Math I Math 850 Fall 2012 Class Log

 1. Aug 20, 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 22, Wed. ways to pick k objects from an n-set; permutations; combinations; binomial coefficients; binomial theorem; polynomial principle; multisets; stars and bars; compositions 3. Aug 24, Fri. Sec 1.2: basic identities for binomial coefficients; Pascal's identity; sums of binomial coefficients, sums of powers of integers; Vandermonde convolution; lattice paths; Delannoy paths and numbers 4. Aug 27, Mon. size of balls in the l1 metric; have the same cardinality; extended binomial coefficients; extended binomial theorem; multinomial coefficients; multinomial theorem; basic identities 5. Aug 29, Wed. Fermat's Little Theorem; Sec 1.3: Bertrand's ballot theorem; reflection principle; related counting of lattice paths 6. Aug 31, Fri. Catalan numbers; bijections with parenthesization, ordered rooted binary trees Sec 2.1: recurrences; counting subsets; Fibonacci numbers; induction proofs involving recurrences Sep 3, Mon. Labor Day - no class 7. Sep 5, Wed. discussion of homework; bijection proof with Fibonacci numbers; derangements, 2 recurrences; showing that a collection is counted by a sequence by showing it satisfies the recurrence; Catalan example of triangulating polygons 8. Sep 7, Fri. recurrences of multiple parameters; recurrence for Delannoy paths and balls in Z^n with radius m in the l_1 metric; Sec 2.2: solving homogeneous linear recurrences of finite order with constant coefficients; solution sequences form a vector space of dimension k; roots of characteristic polynomial give exponential solutions; formula for Fibonacci numbers 9. Sep 10, Mon. general solution for repeated roots in the characteristic polynomial; example; method for inhomogoneous recurrences; form of solutions for recurrences with inhomogeneous parts that are polynomials times exponentials 10. Sep 12, Wed. method for inhomogoneous recurrences; regions in the plane determined by n lines; generating functions; Fibonacci example 11. Sep 14, Fri. relation of characteristic polynomial to form of generating function; partial fractions and repeated roots; generating function method for inhomogoneous recurrences; regions in the plane determined by n lines; power series for powers of 1/(1-cx); generating function for the Catalan numbers 12. Sep 17, Mon. finished generating function for the Catalan numbers; example of generating function for multiply indexed sequence; Sec 3.1: combinatorial constructions of generating functions; making change with coins problem 13. Sep 19, Wed. discussion of convolutions; generating function for choosing multisubsets; permutation statistics; counting permutations by number of inversions, and generating function; counting permutations by number of cycles: recurrence and generating function; counting permutations by number of runs: Eulerian numbers 14. Sep 21, Fri. No lecture. 15. Sep 24, Mon. Worpitzky's identity; formula for Eulerian numbers; Sec 3.2: relationship between operations on sequences and their generating functions; simple examples; convolutions 16. Sep 26, Wed. Snake Oil; examples involving Fibonacci numbers, Delannoy numbers, and number of permutations with given number of cycles Sec 3.3: exponential generating functions; binomial convolution; words over an alphabet 17. Sep 28, Fri. encoding restrictions on words over an alphabet; flags on flagpoles; ordered partitions; Stirling numbers of the second kind 18. Oct 1, Mon. Stirling numbers of the first and second kind; polynomial bases; solving linear recurrences with constant coefficients using exponential generating functions Oct 2, Tues. Test #1 19. Oct 3, Wed. binomial inversion formula; formula for derangement numbers; counting labeled graphs; counting labeled connected graphs 20. Oct 5, Fri. the exponential formula; examples; recurrence for c_n 21. Oct 8, Mon. returned Test 1; Sec 3.4: Twelvefold Way; partition numbers; OGF; asymptotics for partitions when bound on the part size 22. Oct 10, Wed. bijections between different types of partitions; Ferrers diagrams; triangles with integer side lengths; Euler's identity; Sec 4.1: Principle of Inclusion-Exclusion; proof 23. Oct 12, Fri. examples of PIE: derangement numbers, Stirling numbers of the second kind, multisets with bounded repetition number; evaluating sums Oct 15, Mon. Fall break, no class. 24. Oct 17, Wed. discussion of informal feedback survey; Eulerian numbers; restricted permutations; rook polynomials; seating men and women around a table 25. Oct 19, Fri. Sec 4.2: counting under the presence of symmetry; batons; counting orbits of colorings; stabilizers; Burnside's lemma 26. Oct 22, Mon. application to batons and 4-bead necklaces; cycle structure, cycle index, pattern inventory; applications to batons and 4-bead necklaces; counting isomorphism classes of graphs with fixed number of edges 27. Oct 24, Wed. counting isomorphism classes of graphs with fixed number of edges; coloring the cube; using the pattern inventory to enumerate by cost (Pólya-Redfield counting) 28. Oct 26, Fri. counting binary strings under cyclic rotation; introduction to coding theory; encoding/channel/decoding model; binary repetition code; binary symmetric channel (BSC) and q-ary symmetric channel; statement of negative part of Shannon's theorem 29. Oct 29, Mon. error of a decoder; calculation of binary repetition code on BSC; maximum likelihood decoder; maximum a posteriori decoder; conditional probability; equivalence of MLD and MAPD under the assumption that all codewords are equally likely; Hamming distance 30. Oct 31, Wed. nearest neighbor decoding; minimum distance d of a code; can correct floor((d-1)/2)) errors; can detect d-1 errors; parity check code; sphere packing bound; definition of perfect codes; binary repetition code with n odd is perfect 31. Nov 2, Fri. k=dimension of a code; Singleton bound; linear codes; parameters; generator matrix; generator matrix; in systematic form; minimum distance and minimum weight of a codeword; parity check matrix 32. Nov 5, Mon. forming the parity check matrix from a generator matrix in systematic form; examples; computing the min distance from the parity check matrix 33. Nov 7, Wed. standard array decoding; syndrome decoding; example 34. Nov 9, Fri. parameters of codes for CDs, DVDs, and digital television; binary Hamming codes; discussion of statement of Shannon's Theorem 35. Nov 12, Mon. review of discrete probability: probability spaces; real-valued random variables; expectation; linearity of expectation; variance; variance of sums of independent random variables; Markov's Inequality; Chebyshev's Inequality; examples of Bernoulli and binomial random variables Nov 13, Tues. Test #2 36. Nov 14, Wed. entropy of a random variable; election example; average decoding failure; Shannon's theorem; first part of the proof 37. Nov 16, Fri. finished proof of Shannon's theorem 38. Nov 19, Mon. probability of decoding failure vs minimum distance; asymptotic bounds; asymptotic Singleton bound; asymptotic sphere-packing bound; Gilbert-Varshamov bound and asymptotic version Nov 21, Wed. — Nov 23, Fri. Thanksgiving break, no class. 39. Nov 26, Mon. definition of generalized Reed-Solomon codes; parameters: length, dimension, minimum distance; generator matrix and Vandermonde determinant; Lagrange interpolation 40. Nov 28, Wed. dual code of a generalized Reed-Solomon code is a generalized Reed-Solomon code; parity check matrix; syndrome polynomial; error locator polynomial and error evaluator polynomial; Key Equation 41. Nov 30, Fri. No class. 42. Dec 3, Mon. solving the Key Equation for generalized Reed-Solomon codes; uniqueness of solutions 43. Dec 5, Wed. extended Euclidean algorithm approach to decoding Reed-Solomon codes; Reed-Muller codes and parameters 44. Dec 7, Fri. overview of modern coding theory; probabilty of decoding failure vs minimum distance; turbo codes; LDPC codes; iterative, soft decoding Dec 13, Thurs, 10:00am-12:00pm. Final Exam