2018–19–A

Dr. Gili Golan

Time and Place

יום א 14:00 - 12:00 בגוטמן [32] חדר 206
יום ד 14:00 - 12:00 בגוטמן [32] חדר 307

Course Content

  1. 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.
  2. Graphs: General notions and examples. Isomorphism. Connectivity. Euler graphs. Trees. Cayley’s theorem. Bipartite graphs. Konig’s theorem, P. Hall’s theorem.
  3. The inclusion-exclusion method: The complete inclusion-exclusion theorem. An explicit formula for the Stirling numbers. Counting permutations under constraints, rook polynomials.
  4. 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.

Course Catalogue: 201.1.2201