Discrete mathematics: some personal thoughts

Summary

Contrary to what one would think, judging from the recent stream of textbooks on “Discrete Mathematics for Computer Scientists”, this subject is not the union of all subjects in mathematics that are not in the calculus course, but necessary for computer science. This note will try to show what discrete mathematics really is.

In the description below we will assume that students have had some calculus, linear algebra (maybe even elementary probability theory) and know what mathematical reasoning is. A course in logic could precede or follow the discrete mathematics; it is not part of it.

We will concentrate on principles, ideas, and the way of thinking which are the essence of discrete mathematics. The following diagram illustrates the comments below.

The main topics in the study of finite structures are existence questions, constructions, counting, and also studying properties of the objects in question.

One should stress the occurrence in many different situations of similar principles, e.g. in construction one has:

1. a) using several small objects to construct one large one.

2. b) recursive constructions.

3. c) using algebraic techniques to construct combinatorial objects.

In counting one uses:

1. a) generating functions (either ignoring convergence, questions or cleverly using them),

2. b) symmetry principles (e.g. permutation groups),

3. c) 1 – 1 mappings of seemingly different objects onto each other.

There are many combinatorial or just “finite” objects to study. Some are mentioned in the diagram. The “tools” are themselves objects of study in discrete mathematics.