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
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
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
- G. Berman and K. D. Fryer, Introduction to
Combinatorics (Academic Press).
- K.P. Bogart, Introductory Combinatorics
- R. A. Bruhaldi, Introductory Combinatorics
- R. P. Grimaldi, Discrete and Combinatorial
Mathematics (Addison Wesley).
- I. Niven, Mathematics of Choice (Random House).
- F.S. Roberts, Applied Combinatorics
- A. Tucker, Applied Combinatorics (Wiley).
- 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