Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum

Monthly Update sign up
Mailing List signup

Unit 2

Combinatorics Counts

2.1 Introduction

"Mathematics may be defined as the economy of counting.  There is no problem in the whole of mathematics which cannot be solved by direct counting."

-E. Mach

DNA is the genetic information that encodes the proteins that make up living things. Human DNA is a large molecular chain consisting of sequences of four different building blocks known as nucleotides. These nucleotides, adenine, cytosine, guanine, and thymine, combine to form the different genes that make us who we are. Human DNA consists of about 3 billion pairs of these building blocks.

In 1990, the U.S. Department of Energy, in conjunction with the National Institutes of Health and an international consortium of geneticists from China, France, Germany, Japan, and the UK, set out to map the entire sequence of base pairs in human DNA. The Human Genome Project, as it was called, was projected to take fifteen years to complete. By the year 2000, just ten years later, a rough draft was announced and by 2003, the sequence was declared to be essentially complete, two years ahead of schedule.

What enabled this huge project to be completed more quickly than expected? There were many factors, most significantly improvements in technology and faster computers, which made it possible to complete time-consuming calculations within more reasonable time frames. This new generation of computers made it realistic to run powerful algorithms from the mathematics of organization, combinatorics. Combinatorics is, simply put, the mathematics of counting things—things that are generally collections of mathematically defined or encoded objects. As such, combinatorics is the branch of mathematics that is central to some basic problems inherent in our data-rich age: the organization of large sets of data and the quest to uncover relational meaning among the members of those sets. For example, when faced with a task of, say, combining "puzzle pieces" of DNA to make a complete model, combinatorics can be used to enumerate the possibilities. Not only does this tell us whether our ordering is feasible, it also provides the tools that actually accomplish this ordering.

As we already noted, the effort to determine the human genome is a modern context for applying combinatorics. A more classic problem is the infamous "traveling salesperson problem:" Suppose that you are a traveling salesperson and you wish to find the shortest route connecting a group of designated cities. A simple combinatorics problem will help you establish the number of possible itineraries. However, it turns out that finding the shortest possible route, for even a relatively small number of cities, is much more difficult—in fact, it may even be computationally intractable. These are all problems of combinatorics.

Not only can combinatorics help to organize complicated sets, but it can also reveal whether or not any organization inherently exists in large, seemingly "random" sets. This idea, known as Ramsey theory, gives some quantitative rationale as to why we see constellations in the night sky. It also explains, and debunks, some claims of the existence of hidden messages in the Bible. Ramsey theory shows mathematically that structure must exist in randomness, although it does not provide any guidance or formula for finding such structure.

In this unit, we will look at some of the uses of combinatorics, such as finding combinations and permutations and sequencing DNA. We will also learn about the general techniques of the combinatorialist, from bijection, to the "pigeonhole principle," to uses of Hamiltonian cycles in connected graphs. We will also explore a bit of the history of this incredibly useful field, from the counting problems of ancient Egypt, to the mysterious triangle of Pascal, to questions at the forefront of modern-day computing.

back to top

Next: 2.2 Egypt and India


© Annenberg Foundation 2017. All rights reserved. Legal Policy