## Mathematics Illuminated

# Combinatorics Counts

## Counting things seems so simple. Children do it intuitively, connecting a thing with fingers to say how many. Finding efficient and interesting ways to organize things and information is what the field of mathematics, known as Combinatorics, is all about.

Counting is an act of organization, a listing of a collection of things in an orderly fashion. Sometimes it’s easy; for instance counting people in a room. But listing all the possible seating arrangements of those people around a circular table is more challenging. This unit looks at combinatorics, the mathematics of counting complicated configurations. In an age in which the organization of bits and bytes of data is of paramount importance — as with the human genome — combinatorics is essential. Guests interviewed include Jenny Quinn, University of Washington, Tacoma, and Terry Gaasterland from Scripps Genome Center, University of California, San Diego.

### Unit Goals

- Combinatorics is about organization.
- Many combinatorial problems involve ways to enumerate, or count, various things in an efficient manner.
- The counting function
*C(n,k),*is a powerful tool used to count subsets of a larger set, or give coefficients in binomial expansions. - Bijection—the identification of a “one-to-one” correspondence—enables us to enumerate a set that may be difficult to count in terms of another set that is more easily counted.
- Pascal’s Triangle is an elegant illustration of the counting function
*C(n,k).* - Techniques from graph theory can help with combinatorial challenges such as finding circular permutations.
- The pigeonhole principle—the idea that if you have more pigeons than holes, some holes must have more than one pigeon—is a deceptively simple idea that can be used to prove startling results.
- Ramsey Theory explains why we sometimes find order in supposed randomness.
- Ideas from combinatorics are at play in modern methods of DNA sequencing.
- The question of whether or not
*P = NP*—whether certain types of seemingly computationally intractable combinatorial problems can be solved in reasonable amounts of time—is at the forefront of current research in both combinatorics and computer science.

### Unit Glossary

### Additional Unit Resources: Bibliography

# Bibliography

## WEBSITES

http://www.genome.gov/

http://www.claymath.org/

http://www.royal.gov.uk/output/page4944.asp

http://www.ams.org/featurecolumn/archive/mulcahy1.html

http://www.genome.gov/10001167#hgp

http://www.ornl.gov/sci/techresources/Human_Genome/project/about.shtml

Beardsley, Tim “An Express Route to the Genome?” *Scientific American*, vol. 279, issue 2 (August 1998).

Benjamin, Arthur T. and Jennifer J. Quinn. *Proofs that Really Count: The Art of Combinatorial Proof *(Dolciani Mathematical Expositions). Washington, D.C.: Mathematical Association of America, 2003.

Berlinghoff, William P. and Kerry E. Grant. *A Mathematics Sampler: Topics for the Liberal Arts*, 3^{rd} ed. New York: Ardsley House Publishers, Inc., 1992.

Bogart, Kenneth. *Combinatorics Through Guided Discovery*. (2004).

Bogart, Kenneth. *Introductory Combinatorics*, 3rd ed. Harcourt Academic Press, 2000.

Bogart, Kenneth, Clifford Stein, and Robert L. Drysdale. *Discrete Mathematics for Computer Science*(Mathematics Across the Curriculum). Emeryville, CA: Key College Press, 2006.

Devlin, Keith J. *The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time*. New York: Basic Books, 2002.

Gross, Benedict and Joe Harris. *The Magic of Numbers*. Upper Saddle River, NJ: Pearson Education, Inc./ Prentice Hall, 2004.

Hartsfield, Nora and Gerhard Ringel. *Pearls in Graph Theory: A Comprehensive Approach*. San Diego, CA: Academic Press, 1990.

Joseph, George Gheverghese.* Crest of the Peacock: The Non-European Roots of Mathematics.*Princeton, NJ: Princeton University Press, 2000.

Maor, Eli. *Trigonometric Delights*. Princeton, NJ: Princeton University Press, 1998.

Morris, S. Brent. *Magic Tricks, Card Shuffling, and Dynamic Computer Memories.* Washington D.C.: Mathematical Association of America, 1998.

Nahin, Paul J. *Dr. Euler’s Fabulous Formula: Cures Many Mathematical Ills.* Princeton, NJ: Princeton University Press, 2006.

Newman, James R. *Volume 1 of the World of Mathematics: A Small Library of the Literature of Mathematics from A’h-mose the Scribe to Albert Einstein*. New York: Simon and Schuster, 1956.

Rashed, R. *The Development of Arabic Mathematics: Between Arithmetic and Algebra*, [translated by A.F.W. Armstrong]. Boston, MA: Kluwer Academic, 1994.

Reeve, Eric C.R. (editor) *Encyclopedia of Genetics.* Chicago, IL: Fitzroy Dearborn Publishers, 2001.

Tannenbaum, Peter. *Excursions in Modern Mathematics*, 5^{th} ed. Upper Saddle River, NJ: Pearson Education, Inc., 2004.

Human Genome Program. “Genomics and Its Impact on Science and Society: A 2003 Primer.”Oak Ridge National Laboratory, U.S. Department of Energy. http://www.ornl.gov/sci/techresources/Human_Genome/publicat/primer2001/index.shtml (accessed 2007).

Venter, J. Craig, et al. “Genomics: Shotgun Sequencing of the Human Genome,” *Science*, vol. 280, Issue 5369 (June 1998). Wallis, W.D. A Beginner’s Guide to Graph Theory. New York: Birkhauser Boston, 2000.

Wujastyk, Dominik. “The Combinatorics of Tastes and Humours in Classical Indian Medicine and Mathematics,” *Journal of Indian Philosophy*, vol. 28, nos. 5-6 (December 2000).

Yu Zhang and Michael S. Waterman: “An Eulerian Path Approach to Local Multiple Alignment for DNA Sequences,” *Proceedings of the National Academy of Sciences, USA,* vol. 102, no. 5 (2005).

## MEDIA

Hardman, Robert. “A Royal Year” (Part Two: Four Seasons, Section 3: Garter Day). Silver Spring, MD: Acorn Media, 2005 Windsor Castle [videorecording (DVD)]: An RDF Media/HTI co-production for BBC Television; History Television International in association with Oregon Public Broadcasting; produced and directed by Matt Reid, (2 DVDs).