2020–21–A
Dr. Gili Golan
Time and Place:
Course topics
- Introduction: Sets, subsets, permutations, functions, partitions. Indistinguishable elements, multisets, binary algebra of subsets. Rules of sum and product, convolutions, counting pairs. Binomial and multinomial coefficients. Stirling numbers of second kind, definition and a recurrenat formula.
- Graphs: General notions and examples. Isomorphism. Connectivity. Euler graphs. Trees. Cayley’s theorem. Bipartite graphs. Konig’s theorem, P. Hall’s theorem.
- The inclusion-exclusion method: The complete inclusion-exclusion theorem. An explicit formula for the Stirling numbers. Counting permutations under constraints, rook polynomials.
- Generating functions: General notion, combinatorial meaning of operations on generating functions. Theory of recurrence equations with constant coefficients: the general solution of the homogeneous equation, general and special cases of nonhomogeneity. Catalan numbers. Partitions of numbers, Ferrers diagrams. Exponential generating functions, counting words, set partitions, etc.