Descriptive Statement

Discrete mathematics is the branch of mathematics that deals with arrangements of distinct objects. It includes a wide variety of topics and techniques that arise in everyday life, such as how to find the best route from one city to another, where the objects are cities arranged on a map. It also includes how to count the number of different combinations of toppings for pizzas, how best to schedule a list of tasks to be done, and how computers store and retrieve arrangements of information on a screen. Discrete mathematics is the mathematics used by decision-makers in our society, from workers in government to those in health care, transportation, and telecommunications. Its various applications help students see the relevance of mathematics in the real world.

Meaning and Importance

During the past 30 years, discrete mathematics has grown rapidly and has evolved into a significant area of mathematics. It is the language of a large body of science and provides a framework for decisions that individuals will need to make in their own lives, in their professions, and in their roles as citizens. Its many practical applications can help students see the relevance of mathematics to the real world. It does not have extensive prerequisites, yet it poses challenges to all students. It is fun to do, is often geometry based, and can stimulate an interest in mathematics on the part of students at all levels and of all abilities.

K-12 Development and Emphases

Although the term "discrete mathematics" may seem unfamiliar, many of its themes are already present in the classroom. Whenever objects are counted, ordered, or listed, whenever instructions are presented and followed, whenever games are played and analyzed, teachers are introducing themes of discrete mathematics. Through understanding these themes, teachers will be able to recognize and introduce them regularly in classroom situations. For example, when calling three students to work at the three segments of the chalkboard, the teacher might ask In how many different orders can these three students work at the board? Another version of the same question is How many different ways, such as ABC, can you name a triangle whose vertices are labeled A, B, and C? A similar, but slightly different question is In how many different orders can three numbers be multiplied?

Two important resources on discrete mathematics for teachers at all levels are the 1991 NCTM YearbookDiscrete Mathematics Across the Curriculum K-12 and the 1997 DIMACS Volume Discrete Mathematics in the Schools: Making an Impact. The material in this chapter is drawn from activities that have been reviewed and classroom-tested by the K-12 teachers in the Rutgers University Leadership Program in Discrete Mathematics over the past nine years; this program is funded by the National Science Foundation.

Students should learn to recognize examples of discrete mathematics in familiar settings, and explore and solve a variety of problems for which discrete techniques have proved useful. These ideas should be pursued throughout the school years. Students can start with many of the basic ideas in concrete settings, including games and general play, and progressively develop these ideas in more complicated settings and more abstract forms. Five major themes of discrete mathematics should be addressed at all K-12 grade levels - systematic listing, counting, and reasoning; discrete mathematical modeling using graphs (networks) and trees; iterative (that is, repetitive) patterns and processes; organizing and processing information; and following and devising lists of instructions, called "algorithms," and using algorithms to find the best solution to real-world problems. These five themes are discussed in the paragraphs below.

Students should use a variety of strategies to systematically list and count the number of ways there are to complete a particular task. For example, elementary school students should be able to make a list of all possible outcomes of a simple situation such as the number of outfits that can be worn using two coats and three hats. Middle school students should be able to systematically list and count the number of different four-block-high towers that can be built using blue and red blocks (see example below), or the number of possible routes from one location on a map to another, or the number of different "words" that can be made using five letters. High school students should be able to determine the number of possible orderings of an arbitrary number of objects and to describe procedures for listing and counting all such orderings. These strategies for listing and counting should be applied by both middle school and high school students to solve problems in probability.

Following is a list of all four-block-high towers that can be built using clear blocks and solid blocks. The 16 towers are presented in a systematic list - the first 8 towers have a clear block at the bottom and the second 8 towers have a solid block at the bottom; within each of these two groups, the first 4 towers have the second block clear, and the second 4 towers have the second block solid; etc.

If each tower is described alphabetically as a sequence of C's and S's, representing "clear" and "solid" - the tower at the left, for example, would be C-C-C-C, and the third tower from the left would be C-C-S-C, reading from the bottom up - then the sixteen towers would be in alphabetical order:

There are other ways of systematically listing the 16 towers; for example, the list could contain first the one tower with no solid blocks, then the four towers with one solid block, then the six towers with two solid blocks, then the four towers with three solid blocks, and finally the one tower with four solid blocks.

Discrete mathematical models such as graphs (networks) and trees (such as those pictured below) can be used to represent and solve a variety of problems based on real-world situations.

In the left-most graph of the figures above, all seven dots are linked into a network consisting of the six line segments emerging from the center dot; these six line segments form the tree at the far right which is said to "span" the original graph since it reaches all of its points. Another example: if we think of the second graph as a street map and we make the streets one way, we can represent the situation using a directed graph where the line segments are replaced by arrows.

Elementary school students should recognize that a street map can be represented by a graph and that routes can be represented by paths in the graph; middle school students should be able to find cost-effective ways of linking sites into a network using spanning trees; and high school students should be able to use efficient methods to organize the performance of individual tasks in a larger project using directed graphs.

Iterative patterns and processes are used both for describing the world and in solving problems. An iterative pattern or process is one which involves repeating a single step or sequence of steps many times. For example, elementary school students should understand that multiplication corresponds to repeatedly adding the same number a specified number of times. They should investigate how decorative floor tilings can often be described as the repeated use of a small pattern, and how the patterns of rows in pine cones follow a simple mathematical rule. Middle school students should explore how simple repetitive rules can generate interesting patterns by using spirolaterals or Logo commands, or how they can result in extremely complex behavior by generating the beginning stages of fractal curves. They should investigate the ways that the plane can be covered by repeating patterns, called tessellations. High school students should understand how many processes describing the change of physical, biological, and economic systems over time can be modeled by simple equations applied repetitively, and use these models to predict the long-term behavior of such systems.

Students should explore different methods of arranging, organizing, analyzing, transforming, and communicating information, and understand how these methods are used in a variety of settings. Elementary school students should investigate ways to represent and classify data according to attributes such as color or shape, and to organize data into structures like tables or tree diagrams or Venn diagrams. Middle school students should be able to read, construct, and analyze tables, matrices, maps and other data structures. High school students should understand the application of discrete methods to problems of information processing and computing such as sorting, codes, and error correction.

Students should be able to follow and devise lists of instructions, called "algorithms," and use them to find the best solution to real-world problems - where "best" may be defined, for example, as most cost-effective or as most equitable. For example, elementary school students should be able to carry out instructions for getting from one location to another, should discuss different ways of dividing a pile of snacks, and should determine the shortest path from one site to another on a map laid out on the classroom floor. Middle school students should be able to plan an optimal route for a class trip (see the vignette in the Introduction to this Framework entitled Short-circuiting Trenton), write precise instructions for adding two two-digit numbers, and, pretending to be the manager of a fast-food restaurant, devise work schedules for employees which meet specified conditions yet minimize the cost. High school students should be conversant with fundamental strategies of optimization, be able to use flow charts to describe algorithms, and recognize both the power and limitations of computers in solving algorithmic problems.

In summary, discrete mathematics is an exciting and appropriate vehicle for working toward and achieving the goal of educating informed citizens who are better able to function in our increasingly technological society; have better reasoning power and problem-solving skills; are aware of the importance of mathematics in our society; and are prepared for future careers which will require new and more sophisticated analytical and technical tools. It is an excellent tool for improving reasoning and problem-solving abilities.

Note: Although each content standard is discussed in a separate chapter, it is not the intention that each be treated separately in the classroom. Indeed, as noted in the Introduction to this Framework, an effective curriculum is one that successfully integrates these areas to present students with rich and meaningful cross-strand experiences.

References

Kenny, M. J., Ed. Discrete Mathematics Across the Curriculum K-12. 1991 Yearbook of the National Council of Teachers of Mathematics (NCTM). Reston, VA, 1991.

Rosenstein, J. G., D. Franzblau, and F. Roberts, Eds. Discrete Mathematics in the Schools: Making an Impact. Proceedings of a 1992 DIMACS Conference on "Discrete Mathematics in the Schools." DIMACS Series on Discrete Mathematics and Theoretical Computer Science. Providence, RI: American Mathematical Society (AMS), 1997. (Available online from this chapter in http://dimacs.rutgers.edu/archive/nj_math_coalition/framework.html/.)