An Introduction to Combinatorics

Combinatorics has been called ``mathematics of choice or how to count without counting" by I. Niven (see the fifth reference below). It is sometimes concerned with the exact counts of things (enumeration), for example in the problem that asks how many ways twelve people can be seated at a round table if two people refuse to sit next to each other and another pair insists upon having adjacent seats. In other situations combinatorics consider whether or not the number of objects meeting some condition is at least 1 or whether it is 0 (existence). A famous problem of this sort is the ``36 officers" problem of the prolific eighteenth-century mathematician Euler. This problem asks whether 36 officers of 6 ranks and from 6 regiments can be arranged in a 6-by-6 formation so that in each row and in each column there is only one officer of each rank and only one officer from each regiment. This problem was answered negatively in 1901. However, it was shown, as recently as 1960, that the corresponding problem with 100 officers from 10 ranks and 10 regiments has a positive answer.

To obtain a detailed view of the material to be covered the student should look at the references below. Among the contents are the following topics. Enumeration: permutations and combinations, binomial and multinomial coefficients, the inclusion-exclusion principle and applications, distributions of objects into cells, linear equations with unit coefficients, recurrence relations, Fibonacci numbers, Catalan numbers, generating functions, combinatorial identities. A Brief Introduction to Graph Theory: Eulerian and planar graphs, coloring problems. Existence: systems of distinct representatives, latin squares, balanced incomplete block designs.

References:

1. G. Berman and K. D. Fryer, Introduction to Combinatorics (Academic Press).
2. K.P. Bogart, Introductory Combinatorics (Pitman).
3. R. A. Bruhaldi, Introductory Combinatorics (North-Holland).
4. R. P. Grimaldi, Discrete and Combinatorial Mathematics (Addison Wesley).
5. I. Niven, Mathematics of Choice (Random House).
6. F.S. Roberts, Applied Combinatorics (Prentice-Hall).
7. A. Tucker, Applied Combinatorics (Wiley).
8. N. Y. Vilenkin, Combinatorics, translated by A. Shenitzer and S. Shenitzer (Academic Press).

The text for the course will be announced later.

• Prerequisites: One OAC in mathematics or equivalent.
• Coordinator: J. M. N. Brown