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.