### 2020–21–A

## Dr. Gili Golan

#### Time and Place:

- יום א 14:00 - 12:00
- יום ה 12:00 - 10:00

## 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.