# Discrete Mathematics

### 2018–19–A

## Dr. Gili Golan

### Time and Place

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

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

## Course Content

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