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 analysis, mathematical modeling, sequences and dynamical systems, organizing and processing data, and algorithms and optimization.(9)

Despite their formidable titles, these themes can be represented with activities at the elementary grade level which involve both the purposeful play and simple analysis suggested for K-4 students and experimentation and abstraction appropriate at the middle grades. These five themes are discussed in the paragraphs below.

The following discussion of activities at the 7-8 grade levels in discrete mathematics presupposes that corresponding activities have taken place at the K-6 grade levels. Hence 7-8 grade teachers should review the K-2, 3-4, and 5-6 discussions of discrete mathematics and use activities similar to those described there before introducing these activities.

At the 7-8 grade level, students should be able to use permutations and combinations and other counting strategies in a wide variety of contexts. In addition to working with permutations, where the order of the items is important (see 5-6 overview and activities), they should also be able to work with combinations, where the order of the items is irrelevant. Thus, for example, the number of different three digit numbers that can be made using three different digits is 10x9x8 whereas the number of different pizzas that can be made using three of ten available toppings is (10x9x8)/(3x2x1).

An important discrete mathematical model is that of a graph, which consists of dots and lines joining the dots; the dots are often called vertices (vertex is the singular) and the lines are often called edges. (This is different from other mathematical uses of the term "graph".) Graphs can be used to represent islands and bridges, or buildings and roads, or houses and telephone cables; wherever a collection of things are joined by connectors, the mathematical model used is that of a graph. At the 7-8 grade levels, students should be able to use graphs to model situations and solve problems using the model. For example, students should be able to use graphs to scheduling a school's extracurricular activities so that no one is excluded because of conflicts. This can be done by creating a graph whose vertices are the activities, with two activities then joined by an edge if they have a person in common, so that they cannot meet at the same time. Coloring the vertices of the graph so that adjacent vertices have different colors, using a minimum number of colors, then provides a solution to the scheduling problem -- a separate time slot is needed for each color, and two activities are scheduled for the same time slot if they have the same color.

Children can recognize and work with iterative and recursive processes, extending their earlier explorations of repetitive patterns and procedures. At the 7-8 grade levels, they can combine their understanding of exponents and iteration to solve problems involving compound interest with a calculator or spreadsheet. Topics which before were viewed iteratively -- arriving at the present situation by repeating a procedure n times -- can now be viewed recursively -- arriving at the present situation by modifying the previous situation. They can apply this understanding to Fibonacci numbers, to Tower of Hanoi problems, to LOGO programs, to permutations and to other areas.

Children at the 7-8 grade levels should to explore how codes are used to communicate information, by traditional methods such as Morse code or semaphore (flags used for ship-to-ship messages) and also by current methods such as zip codes. Students should investigate and report about various codes that are commonly used, such as zip codes, UPCs (universal product codes) on grocery items, and ISBN numbers on books. They should also explore how information is processed. A useful metaphor is how a waiting line, or queue of people is handled (or "processed") in various situations; at a bank, for example, the queue is usually processed in first-in-first-out (FIFO) order, but queues in supermarkets or restaurants are handled differently.

At the 7-8 grade levels, students should be able to use algorithms to find the best solution in a number of situations -- including the shortest route from one city to another on a map, the cheapest way of connecting sites into a network, the fastest ways of alphabetizing a list of words, the optimal route for a class trip (see the vignette "Short-Circuiting Trenton" in Chapter 1), or optimal work schedules for employees at a fast-food restaurant.

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

F. use systematic listing, counting, and reasoning in a variety of different contexts.

• Students determine the number of possible different sandwiches or hamburgers can be made at the local eateries, and relate the number of pizzas that can be made with three out of the eight available toppings to Pascal's triangle.
• Students determine the number of dominoes in a set that goes up to 6:6 or 9:9, the number of candles used throughout Hannukah, and the number of gifts given in the song that begins "on the first days of Christmas", and connect the results through discussion of the triangular numbers.
• Students determine the number of ways of spelling mathematics in the array below:

  M
  A A
  T T T
  H H H H
  E E E E E
  M M M M M M
  A A A A A
  T T T T
  I I I
  C C
  S
  

• Students design different license plate systems for different sizes of populations; for example, how large would the population be before you would run out of plates which had only three numbers, or only five numbers, or two letters followed by three numbers?
• Students find the number of different rows that can be made in a "garden" if each row has six flowers which can be of two different colors, tabulate the possibilities according to the number of flowers of the first color, and explain the connection with the numbers in the sixth row of Pascal's triangle.
• Students pose and act out problems involving the number of different ways a group of people can sit around a table, using as motivation the scene of the Mad Hatter at the tea party.(10)
• Students count the number of different cubes that can be made using as faces either red or green paper.
• Students count the number of triangles or rectangles in a geometric design -- such as a 4x5 grid.
• Students determine the number of handshakes that take place if each person in a room shakes hands with each other person exactly once, and relate this total to the number of diagonals in a polygon.

• Students find the minimum number of colors needed to assign colors to all vertices in a graph so that any two adjacent vertices are assigned different colors.
• Students use graph coloring to solve problems which involve avoiding conflicts such as: to schedule the school's extra curricular activities; to schedule referees for soccer games; to determine the minimum number of aquariums needed for a specified collection of tropical fish; and to assign channels to radio stations to avoid interference.
• Students use trees to represent and analyze possible outcomes in counting problems, such as tossing two dice.
• Students determine whether or not a given group of dominos can be arranged in a line (or in a rectangular frame) so that the number of dots on the ends match.
• Students determine the minimum number of extra blocks that a police car has to drive if it must patrol each street once on a given map.
• Students use directed graphs to represent tournaments (where an arrow drawn from A to B represents "A defeats B"), food webs (where an arrow drawn from A to B represents "A eats B"), and one-way streets.
• Students find the best route for collecting recyclable paper from all classrooms in the school, and discuss different ways of deciding what is the "best".

• Students use Fibonacci numbers (see 3-4 activities) and Tower of Hanoi problems with various numbers of disks (see 5-6 activities) as examples of recursive processes, where the value of each term depends on the values of previous terms.
• Students recognize the computation of the number of permutations as a recursive process -- that is, that the number of ways of arranging 10 students is 10 times the number of ways of arranging 9 students.
• Students attempt to list the different ways they could travel 10 feet if they were a robot which moved only in one or two foot segments, and then thinking recursively determine the number of different ways this robot could travel n feet.
• Students develop binary trees in LOGO using recursion.
• Students develop arithmetic and geometric progressions on a calculator.
• Students solve problems involving compound interest using iteration on a calculator or on a spreadsheet.
• Students find square roots using the following iterative procedure. Make an estimate of the square root of a number B, divide the estimate into B, and average the result with the estimate to get a new estimate. Then repeat the procedure with the new estimate, etc. For example, if the first estimate of the square root of 10 is 3, then the second would be the average of 3 and 10/3, or 19/6. How many repetitions are required to get the estimate to agree with the square root of B provided by the calculator?
• Students develop the sequence of areas and perimeters of iterations of the constructions of the Sierpinski triangle (see K-2 activities) and Koch snowflake (see 3-4 activities), and discuss the outcome if the process were continued indefinitely.

• Students conjecture which of the following (and other) methods is the most efficient way of handing back corrected homework papers which are already sorted alphabetically: (1) the teacher walks around the room handing to each student individually; (2) students pass the papers around, each taking their own; (3) students line themselves up in alphabetical order. Students test their conjectures and discuss the results.
• Students investigate and report about various codes that are commonly used, such as zip codes, UPCs (universal product codes) on grocery items, and ISBN numbers on books.(11)
• Students are challenged to guess a secret word chosen by the teacher from the dictionary, using at most 20 yes-no questions. Is this always, or only sometimes possible?
• Students keep a scrapbook of different ways in which information is stored or processed. For example a list of events is usually stored by date, so the scrapbook might contain a picture of a pocket calendar; a queue of people at a bank is usually processed in first-in-first-out (FIFO) order, so the scrapbook could contain a picture of such a queue. (How is this different from the waiting lines in a supermarket, or at a restaurant?)
• Students determine whether it is possible to have a year in which there is no Friday the 13th, and how many times in the year the 13th can fall on Friday.
• Students predict and then explore the frequency of letters in the alphabet through examination of sample texts, computer searches, and published materials.
• Students decode messages where letters are systematically replaced by other letters without knowing the system by which letters are replaced; newspapers and games magazines are good sources for "cryptograms" and students can create their own. They also explore the history of code-making and code-breaking.(12)

• Students find the shortest route from one city to another on a New Jersey map, and discuss whether that is the best route.
• Students write and solve problems involving distances, times, and costs associated with going from towns on a map to other towns, so that different routes are "best" according to different criteria.
• Students find an optimal solution to the "muddy city" problem, involving a network of streets of minimal total length which provides access from any one location to any other location.
• Students find winning strategies for simple games such as Nim.(13)
• Students plan an optimal route for a class trip (see the vignette "Short-circuiting Trenton" in Chapter 1).
• Students devise work schedules for employees of a fast-food restaurant which meet specified conditions yet minimize the cost.
• Students compare strategies for alphabetizing a list of words, and test to see which strategies are more efficient.

(11) A good source for information about these and other codes is Codes Galore, J. Malkevitch, G. Froelich, and D. Froelich, Consortium for Mathematics and Its Applications, 1-800-77-COMAP.

(12) The videotape Discrete Mathematics: Cracking the Code of the Consortium for Mathematics and Its Applications provides a good introduction to the uses of cryptography and the mathematics behind it. For a catalog, which describes COMAP's video preview policy, call 1-800-77-COMAP.

(13) For other games, see for example Mathematical Investigations, Book One, R. Souviney et al., Dale Seymour Publications, 1990.