Discrete math shows up in many engineering subjects, from digital logic and coding to network routing, but its name rarely comes with a definition. This page gives one in two steps. It first pins down the word discrete, and then it works through three typical problems with their solutions.

What is "Discrete Math" ?

It is easy to ask, but hard to answer. The short answer is that discrete math studies objects you can count one by one, such as integers, sets, graphs and sequences. It does not study quantities that change smoothly.

• What does Discrete mean ?
• What do typical discrete math problems look like ?

What does Discrete mean ?

Every definition of the subject rests on this one word, so the word comes first. The dictionary gives several definitions of it, and they describe the same idea from different sides.

Let's first think of what it mean by "Discrete". I just googled out several different definition for "Discrete" as follows :

• individually separate and distinct
• defined only for an isolated set of points
• a set only taking certain values

Is it clear enough ?

Don't worry if it is not very clear to you... (to be honest, it would not be clear even to me if I heard of it for the first time).

If you are familiar with the concept of "Continuous", you may define "Discrete" as "Not Continuous".

As you may guess, "Discrete Math" is a branch of mathematics that deals with "Discrete Values (or Discrete set)".

I know it may not be so clear to you.. to make it things even worse, Discrete Math is not something that we learned in high school math.

Very simply put (with a little risk of misleading), any bunch of objects you can count with your fingers can be called 'Discrete Object'. A branch of mathematics deals with discrete objects is called Discrete Mathematics.

Let's make the finger counting picture precise, because it is the part that can mislead. A set is discrete when you can list its elements one after another, as a first, a second, a third and so on. The list may be finite, like the 26 letters of the alphabet. It may also be endless, like the integers 0, 1, -1, 2, -2 and so on. The real numbers cannot be listed this way. Between any two real numbers there is always another one, and calculus relies on that property.

This difference changes the tools. Continuous math uses limits, derivatives and integrals. Discrete math uses counting, logic, induction and recurrence relations. A derivative dy/dx becomes a difference y_n+1 - y_n, and an integral becomes a sum. The usual topics of a discrete math course follow from this. They are logic and proof, sets and functions, counting, recurrence relations, number theory and graph theory.

Digital engineering is a natural home for these tools. A computer stores bits, a sampled signal is a sequence of numbers, and a network is a graph of nodes and links. So much of what an engineer computes is discrete, even when the physics behind it is continuous.

• Discrete means countable : the elements can be listed one by one, in a finite list or in an endless one.
• Continuous is the opposite case : the real numbers cannot be listed, and between two of them there is always another.
• The tools change with the objects : sums, differences, counting and induction take the place of integrals, derivatives and limits.

What do typical discrete math problems look like ?

I think the best way to understand the concept is to go through a lot of examples and just get familiar with them and then you would get your own intuitive understanding of the concept even though you may not be able to explain it clearly.

The three examples below come from three different topics of discrete math. The first is a recurrence relation, the second is a counting problem, and the third is a proof principle. Each example first asks you only to look at the objects. A short solution after it then shows the discrete tools at work.

Example 1

A young pair of rabbits (one of each sex) is placed on an island. A pair of rabbits does not breed until they are 2 months old. After they are 2 months old, each pair of rabbits produces another pair each month. How many Rabits will be there after 10 month ?

==> You don't have to solve this problem now. Just think about the objects used in this problem. They are rabbits which are clearly countable (even with your fingers). These are discrete objects. The problem ask you to derive a certain 'rule' about the discrete object. so this can be a category of discrete math.

Let's solve it now. Let f_n be the number of pairs at the end of month n. At the end of month 1 there is one pair, and it does not breed during month 2, so f₁ = f₂ = 1. At the end of month n, the pairs are the f_n-1 pairs that were already alive, plus one new pair for each pair that is at least two months old. There are f_n-2 such pairs, so f_n = f_n-1 + f_n-2.

This is the Fibonacci recurrence. The sequence runs 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, so after 10 months there are 55 pairs, which is 110 rabbits. The count depends on the convention, though. If the first pair already breeds at the end of month 2, every value moves one month earlier, and the answer becomes 89 pairs.

• A recurrence relation describes growth step by step : you do not need a closed formula for f_n to compute f₁₀. The rule and two start values are enough.

Example 2

In how many different ways can eight identical cookies be distributed among three distinct children if each child receives at least two cookies and no more than four cookies?

==> Now you may sense immediately that Cookies and children in this problem are all discrete objects.

Let x₁, x₂ and x₃ be the numbers of cookies the three children receive. We need x₁ + x₂ + x₃ = 8, with each x_i at least 2 and at most 4. First give every child the minimum of two cookies. That leaves 2 cookies to share, so y₁ + y₂ + y₃ = 2 with y_i = x_i - 2.

The upper limit, y_i at most 2, removes nothing here, because the total is only 2. The number of ways to split 2 identical items among 3 distinct children is C(2 + 3 - 1, 2) = C(4, 2) = 6. The six distributions are (4,2,2), (2,4,2), (2,2,4), (3,3,2), (3,2,3) and (2,3,3).

• Identical items into distinct boxes is a stars and bars count : n identical items go into k distinct boxes in C(n + k - 1, k - 1) ways.
• Lower limits are removed first : hand out the minimum to every box, and then count only what is left.

Example 3

If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

==> This may sounds abstract and may not be very clear. This is about a positive integer which has discrete characteristics. More clearly, if  you think about 'boxes', you can intuitively know it is discrete object. So this statement can fall into Discrete Math. Actually this is a very famous principle called 'The Pigeon Hole Principle'.

The proof is a short contradiction. Suppose every box holds at most one object. Then the k boxes hold at most k objects, which is fewer than k + 1. So at least one box must hold two or more objects.

The general form is more useful in practice. If N objects go into k boxes, at least one box holds at least ⌈N/k⌉ objects. For example, among 13 people at least two share a birth month, because ⌈13/12⌉ = 2. Among 100 people at least 9 share a birth month, because ⌈100/12⌉ = 9.

• The principle proves existence without finding the box : it tells you that a crowded box exists, but not which one it is.