However, discrete mathematics has many practical applications that are useful for solving some of the problems of our society and that are meaningful to our students. Its problems make mathematics come alive for students, and helps them see the relevance of mathematics to the real world. Discrete mathematics does not have extensive prerequisites, yet poses challenges to all students. It is fun to do, is often geometrically based, and stimulates an interest in mathematics on the part of students at all levels and of all abilities.

Students should learn to recognize examples of discrete mathematics in familiar settings, and should explore and solve a variety of problems for which discrete techniques have proved useful. These ideas should be pursued throughout the school years. Students should 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 and trees; repetitive patterns and processes; organizing and processing information; and finding the best solution to problems using algorithms.(14)

The following discussion of activities at the 9-12 grade levels in discrete mathematics presupposes that corresponding activities have taken place at the K-8 grade levels. Hence high school teachers should review the discussions of discrete mathematics at earlier grade levels and use activities similar to those described there before introducing these activities.

At the high school level, students are becoming familiar with algebraic and functional notation, and their understanding of all of the themes of discrete mathematics and their ability to generalize earlier activities should be enhanced by their algebraic skills and understandings. Thus, for example, they should use formulas to express the results of problems involving permutations and combinations, relate Pascal's triangle to the binomial expansion of (x+y)^n, calculate chromatic polynomials which record the number of different ways of coloring a graph using x colors, explore models of growth using various algebraic models, explore iterations of functions, and discuss methods for dividing an estate among several heirs.

At the high school level, students are particularly interested in applications; they ask "What is all of this good for?" In all five areas of discrete mathematics, students should focus on how discrete mathematics is used to solve practical problems. Thus, for example, they should be able to apply their understanding of counting techniques to analyze lotteries; of graph coloring, to schedule traffic lights at a local intersection; of paths in graphs, to devise patrol routes for police cars; of iterative processes, to analyze and predict fish populations in a pond or concentration of medicine in the bloodstream; of codes, to understand how bar-code scanners detect errors and how CD's correct errors; and of optimization, to understand the 200 year old debates about apportionment and to find efficient ways of scheduling the components of a complex project.

Experiences will be such that all students in grades 9-12, building upon the K-8 expectations:

K. understand and use basic principles, including permutations and combinations and mathematical induction and recursion, to solve combinatorial and algorithmic problems.

• Students determine the number of ways a committee of three members could be selected from the class, and the number of ways three people with specified roles could be selected, and generalize this activity to finding a formula which would provide the number of people of an n person committee selected from a class of m people, and the number of ways n people with specified roles can be selected from a class of m people.
• Students relate the possible outcomes of tossing five coins with the binomial expansion of (x+y)^5 and the fifth row of Pascal's triangle.
• Students find the number of ways of lining up the thirty students in the class, and compare that to other large numbers, for example, the number of raindrops (volume = .1 cc) it would take to fill the earth (radius = 6507 KM).
• Students investigate the lotteries in various states, and compare their expected values.
• Students determine the number of ways of dividing out 52 cards among four players, as in the game of bridge, and compare the number of ways of obtaining a flush (five cards of the same suit) and a full house (three cards of one denomination and two cards of another) at the game of poker.
• Students develop formulas for counting paths on grids or other simple street maps.
• Students find the number of cuts needed in order to divide a giant pizza so that each student in the school gets a piece.
• Students play Nim (and similar games) and discuss winning strategies using binary representations of numbers.

• Students study the four color theorem and its history.
• Students determine the number of ways a graph can be colored, and calculate the chromatic polynomial for simple graphs.
• Students using graph coloring to determine the minimum number of guards (or cameras) needed for museums of various shapes (and similarly for placement of lawn sprinklers or motion-sensor burglar alarms).
• Students use directed graphs to construct one-way orientations of streets in a given town which involve the least inconvenience to drivers.
• Students use trees to analyze the play of games such as tic-tac-toe or Nim.
• Students use tree representations for the solutions of weighing problems. Example: Given 12 coins one of which is "bad", find the bad one, and determine whether it is heavier or lighter, using three weighings.
• Students using graph coloring to schedule the school's final examinations so that no student has a conflict, or to schedule traffic lights at an intersection.
• Students devise graphs for which there is, or for which there is no path that covers each edge of the graph exactly once, based on an understanding of necessary and sufficient conditions for the existence of such paths (called "Euler paths") in a graph.
• Students make models of polyhedra with straws and string, and explore the relationship between the numbers of edges, faces, and vertices.
• Students use graphs to solve problems like the "fire-station problem": Given a city where the streets are laid out in a grid composed of many square blocks, how many fire stations are needed to provide adequate coverage of the city if each fire station services the square block it is on and the four square blocks adjacent to that one? (The Maryland Science Center in Baltimore has a hands-on exhibit involving a fire-station problem for 35 square blocks arranged in a six-by-six grid with one corner designated a park.)

• Students analyze the Fibonacci sequence as a recurrence relation with connections to the golden ratio.
• Students explore iteration by choosing a function key on a calculator and pressing it repeatedly. Do this for several different function keys. Then use the graphs of these functions to discuss why some result in a fixed value and others don't.
• Students explore examples of linear growth, using the recursive model based on the formula P(n+1) = P(n) + (common difference), and convert it to an explicit linear formula.
• Students explore examples of population growth, using the recursive model based on the formula P(n+1) = P(n) x (growth rate), convert it to an explicit formula using exponents, and apply it to both economics (interest problems) and biology (concentration of medicine in blood supply).
• Students explore logistic growth models of population growth, using the recursive model based on the formula P(n+1) = P(n) x (1-P(n)) x (growth rate), where P(n) is now the fraction of the carrying capacity of the environment, and apply this to the population of fish in a pond. Using a spreadsheet, students experiment with various values of the initial value P(1) and the growth rate, and describe the relationship between the values chosen and the long-run behavior of the population.
• Students explore the pattern resulting from repeated multiplication of the matrix
  

  --     --
  | 1   1 |
  | 1   0 |
  --     --
  

• Students use a calculator or a computer to study simple Markov chains, such as weather predicting and population growth models.
• Students explore iterating the function defined by the two cases
  

       f(x) = x + 1/2     for x between 0 and 1/2
       f(x) = 2 - 2x      for x between 1/2 and 1
  

  Some interesting initial values are 1/2, 2/3, 5/9, and 7/10, all of which can be computed by hand or by calculator. Then, using a calculator or computer, try the initial values .501, .667, and .701 and compare the behavior of the sequences generated by these values to the sequences generated by the "nice" initial values which differ by a small amount.

• Students discuss how scanners of bar codes (zip codes, UPCs, and ISBNs) are able to detect errors in reading the codes, and evaluate and compare how error-detection is accomplished in different codes.
• Students use trees to keep track of possibilities that have already been tried when solving a puzzle or a maze.
• Students discuss various algorithms used for sorting large numbers of items alphabetically or numerically, and explain why some sorting algorithms are substantially faster than others.
• Students devise experiments to find out what types of errors are most common in transmitting numbers (credit card numbers, UPC numbers, phone numbers) in writing or by phone; are these codes protected against the most common errors?
• Students investigate methods of error correction used to transmit digitized pictures from space (Voyage or Mariner probes, or the Hubble space telescopes) over noisy or unreliable channels, and used to ensure the fidelity of a scratched CD recording.
• Students read about coding and code-breaking machines and their role in World War II.
• Students research topics appearing in current newspaper articles, such as public-key encryption.
• Students discuss the Morse code and the rationale for using codewords (dashes and dots) of varying lengths versus codewords of fixed length, as in the ASCII code.

• Students find the best route when a number of alternate routes are possible. For example, in which order should you pick up the six friends you are driving to the school dance? In which order should you make the eight deliveries for the drug store where you work? In which order should you visit the seven must-see sites on your vacation trip? In each case, you want to find the "best route", the one which involves the least total distance, or least total time, or least total expense. Students make up their own problems, using actual locations and the actual distances, and find the best route. For a larger project, students can try to improve the route taken by their school bus.
• Students study the role of apportionment in American history, focusing on the 1790 census (acting out the positions of the thirteen original states and discussing George Washington's first use of the presidential veto), and the disputed election of 1876, and discuss the relative merits of different systems of apportionment that have been proposed and used. (This activity provides an opportunity for mathematics and history teachers to work together.)
• Students analyze several methods for dividing an estate among various heirs.
• Students devise a student government where the seats are fairly apportioned among all constituencies.
• Students discuss various methods that can be used for determining the prom king and queen if every student votes by listing their preferences.
• Students discuss, after an election involving three of more candidates, how the results might have been affected had methods involving preference schedules or approval voting been used. With preference schedules, each voter ranks the candidates and the individual rankings are combined using various techniques, to obtain a group ranking; preference schedules are used, for example, in ranking sports teams or determining entertainment awards. In approval voting, each voter can vote once for each candidate which she finds acceptable; the candidate who receives the most votes then wins the election.
• Students use various search strategies to solve mazes.
• Students find an efficient way of doing a complex project (like preparing an airplane for its next trip) given which tasks precede which and how much time each task will take.
• Students find an efficient way of dividing up the songs on the two sides of an audio tape so that the discrepancy between the two sides is minimized.
• Students apply algorithms for matching in graphs to schedule when contestants play each other in the different rounds of a tournament.
• Students devise a strategy for finding a "secret number" from 1 to 1000 using questions of the form "Is your number bigger than 837?" and determine how many such questions are needed at worst to find the secret number.