As our society increasingly relies upon information processing and computer technology, the applications of discrete mathematics, and therefore the need for students to develop fluency with the concepts and processes of discrete mathematics, continue to grow. The National Council of Teachers of Mathematics (NCTM) clearly recognizes this importance, as evidenced by their publication of the 1991 Yearbook: Discrete Mathematics Across the Curriculum K-12 (Kenney, 1991) and Discrete Mathematics and the Secondary Mathematics Curriculum (1990), as well as by their inclusion of a discrete mathematics standard for grades 9-12 in the Curriculum and Evaluation Standards for School Mathematics (1989). However, in Principles and Standards for School Mathematics: Discussion Draft (1998), the message of the importance of the integration of discrete mathematics topics and themes throughout the mathematics curriculum is not as strong.

Treatment of Discrete Mathematics in the Discussion Draft

The message comes across most clearly in the high school grade band. The grades 9-12 overview states that "every student should take a minimum of three years of mathematics courses that include substantial mathematics drawn from the areas of algebra and functions, geometry, data analysis, and discrete mathematics" (NCTM, 1998, p. 273). In addition, the discussion of Standard 6: Problem Solving advocates an emphasis on discrete mathematical tools including networks, graph theory, and recursive and algorithmic thinking. The discussion of Standard 10: Representation continues the emphasis on discrete mathematics, noting matrices, tree diagrams, and recursive forms of functions as new means of representation for high school students.

The discussions in the other standards for this grade band provide further elaboration of these ideas. For example, Standard 3: Geometry and Spatial Sense includes an example of finding a minimal spanning tree for a network in the context of trying to minimize the total distance of roads to be paved in a town while permitting travel between all points in the network. Standard 2: Patterns, Functions, and Algebra includes a thorough discussion of an application using recursive formulas and a spreadsheet to analyze residual medicine in a patientís system. Here the document highlights the usefulness of recursive models when closed form models cannot be found.

The document also emphasizes developing fluency with matrix representations and their applications at the high school level. Standard 3: Geometry and Spatial Sense presents an extended activity relating matrices and transformations of figures in a plane. Other topics from discrete mathematics appear scattered throughout the document. For example, a focus area under the second bullet for Standard 1: Numbers and Operations indicates that high school students should "continue to develop an understanding of permutations and combinations in increasingly complex situations" (NCTM, 1998, p. 275).

Despite the careful attention to include discrete mathematical language at each of the grade bands and to thoroughly develop discrete mathematical topics in high school, treatment of such topics in the earlier grade bands is quite superficial. The focus areas for grades 6-8 under the second bullet for Standard 1: Numbers and Operations indicate that middle school students should "extend understanding of counting to include elementary combinatorics," (NCTM, 1998, p. 217) but the topic is not addressed in the discussion. Furthermore, there is no mention of counting in the context of combinations anywhere in the Pre-K-5 standards. In fact, the entire document contains a total of four sentences dedicated to the topic of combinatorics.

The second bullet for Standard 3: Geometry and Spatial Sense explicitly includes graph theory as a topic of study for all students across all of the grade bands. However, the focus areas, elaboration, and discussion of this expectation make absolutely no reference to graph theory until grades 6-8. At this level, students are expected to "explore use of other representation systems, particularly networks," as students in the middle grades "will benefit from experience with other representational models, such as networks," which "can provide students with additional tools to use in analyzing and solving problems" (NCTM, 1998, p. 230). No further explanation or illustrative examples are given.

Following the pattern for the other topics from discrete mathematics, recursion also receives no attention until grades 6-8. The discussion sections in both of the elementary grade bands overlook opportunities to connect the description of growing patterns to recursive ideas. In the middle grades, the focus areas under the first bullet for Standard 2: Patterns, Functions, and Algebra indicate that students should pay "particular attention to patterns that have a recursive nature" (NCTM, 1998, p. 221). There is no emphasis, however, on representing patterns recursively.

Suggested Changes

A Separate Discrete Mathematics Standard

The scattering of discrete mathematics topics throughout the standards suggests that topics in discrete mathematics have less significance than those of algebra, geometry, and data analysis, which each appear in a separate standard. Furthermore, their inclusion is easily overlooked. Students in Dr. Cooperís Trends in Mathematics Education course at University of Maryland each chose a standard and prepared a summary of the discussion of that standard based on the presentation of that standard in the Pre-K-12 overview, the Pre-K-2 chapter, and the grades 3-5 chapter. The summaries for Standard 1: Numbers and Operations, Standard 2: Patterns, Functions, and Algebra, Standard 3: Geometry and Spatial Sense, Standard 6: Problem Solving, and Standard 10: Representation made no mention of counting techniques, graph models, or recursive thinking. This indicates that an elementary school teacher would not get an impression that discrete mathematics is important from reading grade-appropriate discussions of these standards.

The discussion at the middle grades assumes that teachers, as part of the audience for the document, already have an understanding and appreciation of the applications of graph theory. Teachers at the middle school level would need to understand how and why to use networks as tools for problem solving in order to incorporate this expectation, as it is currently written, into their instruction . I probably have a more substantial mathematics background than the average middle school teacher, and I did not know how to accomplish this expectation until I read and tried several examples from outside sources. However, it only took a few examples of how graph models can be used to solve real-life problems to generate excitement in me about the possibilities. The writers of the final document should capitalize on the opportunity to generate this kind of excitement in teachers.

The creation of a distinct discrete mathematics standard would allow for more thorough explanation of the topics and processes that students should learn at each grade level. This accomplishes the dual task of sparking teacher interest and of providing guidelines for appropriate development at the various grade levels. If left open and vague, "it is not unusual for the same topic and problem to be treated at several different grade levels" without thoughtful development. The final document should provide a clear outline to distribute the content of discrete mathematics into a "meaningful developmental sequence" (Kenney, 1996).

Most significantly, a separate standard for discrete mathematics Pre-K-12 would ensure treatment of important topics and themes at earlier grades. Mathematics is not universally embraced. In fact, many students form negative attitudes towards mathematics at a fairly young age, and this attitude persists into adulthood. Numerous teachers and researchers have found that discrete mathematics has widespread appeal. Topics in discrete mathematics, rich in real-life applications, lend themselves naturally to engaging activities. These topics generally require a much smaller knowledge base than continuous mathematics, making them accessible to all students. The different modes of thinking involved in solving problems in discrete mathematics allow new "experts" to emerge, transforming traditionally "weak" students into active contributors (Biehl, 1997; Carney, 1997; Cozzens, 1997; DeBellis, 1997; Hart, 1997; Hoyer, 1997; Kowalczyk, 1997; Picker, 1997; Friedler, 1996). Why wait to "fix" misperceptions of mathematics? Why not shape broader views of mathematics from the beginning?

Introducing concepts earlier allows students more time to explore them and gradually incorporate them into their mathematical "tool kit" as their understanding deepens. Students who need more time to make connections between ideas will have the opportunity to revisit topics with improved understanding resulting from the natural maturing of lessons learned from previous experiences . This helps to provide a strong foundation upon which to build in later grades, allowing a wider range of students to attack more complex, and thus more realistic, situations in high school. Earlier introduction also prevents students who are more successful in areas of continuous mathematics from developing mental blocks to thinking in discrete terms.

I struggled to overcome this obstacle with my gifted and talented freshmen in Algebra II last year. I attempted to incorporate applications involving annuities and amortization into our study of sequences. Many of the students had considerable trouble generating recursive formulas because they had always carried calculations all the way through to look for patterns in the numbers themselves, rather than in the process, and they resisted the idea that a closed form was out of reach. We encountered similar difficulties in distinguishing between the mathematical and the contextual domains for a continuous mathematical model of a situation that dictates a discrete domain. I believe that we would not have encountered such difficulty if students had had early experiences with this mode of thinking.

One might think that discrete mathematical topics and processes, once reserved for study at the college level, are too advanced for children in grades Pre-K-5. However, research suggests that students have tremendous success with carefully chosen and developed activities from this field. Several teachers report student success in using concrete models to enumerate the different possible combinations of two types of items, when presented with a small number of choices for each type of item, as young as four years-old (DeBellis, 1997; English, 1992). In fact, with early exposure to combination problems, students begin to develop improving strategies around age 7 (English, 1992) and, by grade 3, have efficient strategies for obtaining the correct answer, which they are able to generalize to solve similar problems without the need for drawing (Maher & Martino, 1992). "Developing [counting] strategies at a formal level is appropriate only after a great deal of concrete exploration and investigating" (Graham, 1991). Introducing these activities in the elementary grades provides that foundation on which to build the formal representations of counting strategies.

Students in first grade are able to compare and contrast the task of counting the number of different outfits possible given a choice of two shirts and two shorts and the task of counting the number of different colors of paint that can be created by mixing two colors given a choice of four (Schielack, 1991). Both tasks involve selecting two items from a choice of four; however, students observe important distinctions between what makes two combinations different in each case and the types of choices that are allowed. This particular activity could easily connect to art. Given the primary colors red, yellow, and blue, how many secondary colors can be made by mixing two of the three primary colors? Students encounter combinatorial problems everyday, whether itís choosing what they will wear to school that day or what they will eat for lunch. These experiences allow for intuitive understandings of this topic.

There are also numerous accounts of student success in exploring and using graph theory in the elementary grades. Students are able to color the vertices of large-scale networks formed by masking tape on the floor as young as three years old (Casey, 1997). Through the use of stories and games, they can learn about the various characteristics and properties of graphs before the introduction of formal terminology at later grades. In fact, elementary students have successfully solved optimization problems using graph theory, including variations of the minimal spanning tree problem which appears as an example in the grades 9-12 standards mentioned above (Casey & Fellows, 1997; Rosenstein, 1996). If students as young as fourth grade can solve the kinds of graph optimization problems currently expected of high school students, imagine the level of sophistication possible in high school with the proper development beginning Pre-K.

Elementary students also naturally think recursively in the early grades. This is usually the first step in pattern analysis, but "the actual [recursive] structure is often bypassed to move quickly to establishing formulas for the nth terms in arithmetic and geometric sequences .... In doing so, students are rushed pass the central notions of change and rate of change" (Dossey, 1997). In the grades Pre-K-2 discussion of Standard 2: Patterns, Functions, and Algebra, an example is given in which students record the costs corresponding to various numbers of fruit roll-ups in a table. "[I]f one fruit roll-up costs $0.10 and 2 cost $0.20, then how much would 3 cost? How much would 7 cost?" The draft indicates that "within the pattern there is the seed of the general function rule, 'the cost of n is 10n'" (NCTM, 1998, p. 118). While students at this age are not yet ready for this general function rule, they can verbally describe the relation in terms of how to get from one cost to the next. This shows a process of repeated addition, which provides another link to multiplication, as well as to the idea of a constant increase. This approach serves as a precursor not only to the idea of function, but also to notions of linearity.

Students in grades 3-5 can handle more complicated recursive thinking. Fourth graders presented with the situation that $0.10 per day is added to a piggy bank understood that they needed to know how much was is the bank to start in order to determine how much money would be in the bank at the end of one year (Kowalczyk, 1997). This necessity of an initial condition in recursive situations is a point frequently overlooked by my gifted and talented freshmen, perhaps because closed forms, which do not have this requirement, are so familiar to them and recursive forms so foreign. Fourth graders also see the recursive pattern in the Fibonacci sequence. They can model Fibonacci's rabbit problem using rabbit cutouts until the pattern emerges. Students are then able to verbally explain the recursive nature of the sequence and use this information to extend the sequence to determine the population after one year (Kowalczyk, 1997). This investigation allows for numerous connections to science, history, and art.

A Proposal for Standard 11: Discrete Mathematics

Mathematics instructional programs should include attention to discrete mathematics so that all students--

* develop and use counting techniques to solve combinatorial problems:

        * use concrete models to enumerate and count the possible combinations of two types of items when given a small number
          of choices for each item;

        * describe methods for keeping track of combinations;

        * understand the meaning of "different" in the context of combinations.

* use vertex-edge graphs to model and analyze problems in real contexts:

Activities at this grade should focus on concrete examples and be playful in nature. The idea here is to provide students with experiences that will help them to make sense of more abstract situations in later grades.

Counting and Combinations:

When first introducing counting activities in the context of combinations, teachers should actually provide students with the items from which they may choose. For example, present students with actual pairs of shoes and sporting equipment to ask how many ways they can choose a pair of shoes and a sport. Students in kindergarten may need the teacher to lead them through acting out the process of choosing. The teacher could ask for a volunteer to choose a pair of shoes and a sport. Following this selection, the teacher could then ask for another volunteer to make a different selection, allowing students to continue making selections until all possibilities have been found. Large arrows can be used to show the various combinations that students have selected to facilitate counting the different selections. Once students have the idea, then more items can gradually be added to each category (DeBellis, 1997).

Students can also explore counting techniques in smaller groups or individually by choosing outfits for a small cardboard bear, selecting a shirt and a pair of pants from various color choices. Some students may need help clarifying what constitutes a different outfit. For example, some students may not count an outfit consisting of a blue shirt and blue pants as different because the colors are the same. Other students may be confused as to whether an outfit consisting of a white shirt and blue pants differs from an outfit consisting of a yellow shirt and blue pants since the pants are the same. Some students may not want to count outfits that do not match in their minds (English, 1992). Students should discuss these questions with each other and develop a clear understanding of what "different" means in the context of combinations.

As students gain experience with counting combinations of items, teacher questions should focus students' attention to their processes. How are you keeping track of your combinations? Have you counted any combinations twice? Are there any more possibilities? Are you sure? How do you know? By the end of grade 2, students should have sufficient strategies for systematically listing the possible combinations of two types of items.

Graph Theory:

Again, students' experiences with graph models at this grade level should be concrete and playful. Students can make human graph models, with students representing the vertices and possible passes of a ball between students representing the edges. Students can begin to explore the properties of graphs by trying to pass a ball through the network so that everyone touches the ball at least once before it returns to the start. Notions of optimization can then arise in the context of trying to find a path for the ball so that fewer people touch the ball twice, and eventually students can search for a Hamiltonian circuit, trying to pass the ball so that everyone receives the ball exactly once before it returns to the start. Students can then vary their arrangement and examine the effect on the path of the ball. Second grade students show surprising insight, noting that the path of the ball is the same whether students form a circle, a square, a triangle, or even a line, even though these shapes differ significantly (DeBellis, 1997).

Students can also explore directed graphs in which they represent the vertices using the context of a tournament. Students should be in small groups, four or five students per group, to play a simple game such as rolling large dice. Arrows in the network point from the winner of a game to the loser. Students practice counting techniques by keeping track of games to ensure that everyone in the group plays everyone else exactly once. Students can then search for a winning sequence, a listing of the students in the group so that each player defeated the next player on the list, which provides students with an experience in finding a Hamiltonian path (DeBellis, 1997).

Large-scale networks formed by masking tape on the floor provide another means for students to investigate graph models in the early grades. Stories and games to help students explore the characteristics and properties of networks using this method are available on the world wide web at http://www.c3.lanl.gov/mega-math. These kinds of activities in the early grades provide students with experiences which they can call upon in later grades when they try to make generalizations about the relationships between various characteristics and properties of graphs.

Students should understand what it means to color a map or a graph, deciding what constitutes a shared boundary. For example, where four regions come together, is the shared point of opposite regions considered a shared boundary? Once students have worked out these questions for themselves, they can color maps and also coloring books. Pictures in coloring books can be colored following the same rules as for maps, coloring pictures so that no two regions with a common border are the same color. As students become comfortable with coloring activities, they should be challenged to try to use as few colors as possible. This allows time for students to develop and improve strategies for finding the least number of colors necessary, a skill which they will use for optimization problems in later grades.

Recursive Thinking:

In kindergarten, students can generate sequences of multiples using calculators. Students should then try to find a pattern that would allow them to extend the sequence without use of the calculator, focusing on the recursive property of adding the same number to each term to obtain the next term. In first grade, students can practice skip counting by extending arithmetic sequences using recursive processes. Students should gain experience extending exponential patterns which result in increasing powers of a whole number in second grade, using calculators to multiply each term by the constant ratio. Students can explore how long their parents could afford to double their allowance every day beginning with a penny.

Students should also gain experiences in extending iterative geometric patterns. For example (see fig. 1), students can extend the pattern to draw successive images. They can also count the number of squares at each stage and describe how the number of squares is changing.

 

Optimization:

Students in kindergarten can begin to search for shortest paths using large scale graph models on the floor. Large counters can be used to indicate the distances represented by each edge. As students progress to grade 2, they can measure distances within the classroom or on the playground, draw a graph to represent the information they have gathered, and challenge each other to find shortest paths.

Students in grade 2 should also begin to discuss their strategies for finding the fewest number of colors necessary to color a map or graph. Teachers should challenge students to justify their strategies by asking them how they know that fewer colors could not be used.

Grades 3-5 Focus Areas:

* develop and use counting techniques to solve combinatorial problems:

* extend counting techniques to situations involving greater numbers of choices;

Activities in the upper elementary grades should build upon students' experiences in the earlier grades. Students should increasingly focus their attention on their strategies in order to increase their efficiency. Students should also begin to generalize their techniques to model more complex and abstract situations.

Counting and Combinations:

Students should generalize their counting techniques to be able to account for a greater number of choices. For example, students may count the number of different outfits that can be generated from a small number of shirts, pants, and shoes. The number of items within each category should gradually increase to appropriately challenge students as they become more efficient at handling these types of problems to encourage further refinement and generalization.

Students in grade five can investigate how many different sandwiches are possible from a choice of white or wheat bread, ham or turkey, and American or Swiss cheese. Students will have to determine whether or not all sandwiches need to include both meat and cheese. They should explain how this consideration changes the problem. While students will probably agree that one can have a plain ham sandwich or a plain cheese sandwich, is two pieces of bread with nothing in between considered a sandwich? Students can generate a tree diagram to show the possibilities based upon their conclusions.

Students should also differentiate between choices across categories and choices within categories. For example, suppose an ice cream shop has 4 different flavors of ice cream. How many different double dip cones are possible? Students will have to decide whether a choice of two scoops of the same flavor is acceptable as well as whether chocolate/vanilla differs from vanilla/chocolate. "Early experiences in the need to identify such characteristics when counting provides a meaningful basis on which to build the symbolic representations of counting procedures" (Schielack, 1991).

Graph Theory:

Students should create graph models in which edges represent a relationship between vertices. For example, suppose a school is trying to schedule after-school activities. Vertices could represent the various activities, and the edges would represent conflicts between activities due to shared students.

Students should also explore various tournament arrangements. They can create trees for single-elimination tournaments, using a directed graph to model the outcomes. They can also incorporate counting strategies to determine how many games are played in the NCAA basketball tournament, which consists of 64 teams. Scheduling a round-robin tournament, in which everyone plays everyone else exactly once, poses the same situation as the handshake problem. As in the earlier grades, students can use a directed graph of the outcomes to try to find a winning sequence. Students should investigate such questions as whether or not the first person in the sequence is necessarily the winner of the tournament, assuming that the winner is determined by the most games won, and whether or not a winning sequence always exists. As a precursor to induction, students should describe how they would, in general terms, add a new team to the winning sequence.

Recursive Thinking:

Students should expand their experiences with arithmetic and geometric sequences to include shrinking as well as growing patterns. They should also examine general geometric sequences with an initial term other than 1, rather than limiting their experience to powers of a whole number as in the earlier grades. Students descriptions of these sequences should focus on the process of obtaining successive terms from the previous term, and they should use their descriptions of the recursive process to extend these patterns, using calculators as necessary. By the end of fifth grade, students should be able to write an informal rule for how to generate a given sequence. "Informal introduction to difference equations, as ways of thinking about processes, should enter the school mathematics curriculum in the upper elementary grades" (Dossey, 1997).

Students should also examine second-order recursive patterns. Students can model the Fibonacci rabbit problem using rabbit cutouts until the pattern emerges. Students should then be able to describe the pattern recursively and extend the pattern to determine how many rabbits there would be at any given time. Students could explore the occurrence of Fibonacci numbers in patterns in nature.

Students can generate another second-order recursive model which incorporates counting techniques. Ask students to create the first four or five rows of a triangle in which, for example, the fourth row indicates how many ways a coin tossed four times could result in an outcome of exactly 0 heads, 1 head, 2 heads, 3 heads, and 4 heads respectively. While gaining practice in counting techniques, students will generate Pascal's triangle. Students should be able to describe the process for obtaining successive rows of the triangle and then use the process to extend the triangle. Students should have numerous opportunities in the elementary grades to observe how patterns in process can be used to extend our knowledge beyond the information given a problem in order to answer questions within the context of the problem situation.

Optimization:

Students should use real-life maps to calculate shortest routes. For example, students could choose a small number of cities between Boston and Miami, perhaps considering how an airline or a motorist might select cities, and use the distances or the times on the map to determine an optimal route. As students progress from third to fifth grade, they can select an increasing number of cities to include along the route.

Given a grid network to represent the streets of a city, students should explore finding optimal routes for a postal carrier or garbage truck. Students should also explore "muddy roads" problems. Given a small network of areas within a town, students should decide which roads to pave so that everyone has access to all areas, even if they have to drive through another area, and so that the least pavement is necessary.

Using their graph model of the student activity conflicts described earlier, students should choose colors to represent the various time slots after school and use graph coloring to schedule the after-school activities so that students who participate in multiple activities do not have conflicts. Experiences in the elementary grades should demonstrate to students that sometimes problems have more than one optimal solution, and sometimes different people may have different criteria and/or approaches for determining an optimal solution. Students should have ample opportunity to refine their optimization techniques and strategies within a variety a real-lie contexts.

Grades 6-8 Focus Areas:

* develop and use counting techniques to solve combinatorial problems:

In the middle grades, students should continue to refine and generalize the techniques they have developed in the elementary grades. Teachers need to ensure that students are challenged by increasingly complex and abstract problem situations. Students will begin to formalize their understanding of discrete mathematical topics at this time.

Counting and Combinations:

Students in the middle grades can explore counting situations ranging from the number of value meals possible which include a choice of sandwich, drink, and fries to the number of possible phone numbers, realizing that phone numbers never begin with a zero, or the number of license plates possible using three letters followed by three numbers. Students can then analyze why so many new area codes are being added in states all across the country and whether or not they believe we will need to expand the number of characters on our license plates.

In another example, suppose a warehouse has three security stations separated by nine rows of lockers on one end and by five rows of lockers at the other end (see fig. 2).

The night security guard wants to vary his patrol routes to cover the entire warehouse while not having a predictable patrol. Students can explore how many paths are possible from Station A to Station C through Station B. How many paths are possible from Station A, through Station B, to Station C, back through Station B, and returning to Station A (Cozzens, 1997).

Students should also explore the impact of varying conditions in counting situations. For example, in how many ways can the teacher select three students from the class to demonstrate a problem? How does the problem change if the teacher assigns roles to the students as they are chosen? Connections to probability and graph theory should expand as students progress through the middle grades.

Given the minimum number of colors necessary to color a particular graph, in how many ways can the graph be colored? Students can also count the number of routes from one vertex to another within a network. This serves as a demonstration as to why optimization problems within large networks, which contain correspondingly large numbers of possible routes, becomes such a difficult task. This can be linked to probability by asking for the number of ways a taxi can drive from vertex A to vertex C, driving only north and west, and how many of those ways include vertex B, where a passenger is standing. Students can then determine the probability that the taxi will drive by the passenger.

Graph Theory:

Students should explore the common characteristics and properties of networks that are traversible and determine necessary and sufficient criteria for traversibility of a network. Similarly, students can explore when a map is two-colorable. Informal induction can be sued to show that a closed curve is always two-colorable (Casey and Fellows, 1997).

Students should identify graph theory applications by problem type. For example, Euler paths are used in situations such as planning snow plow routes, garbage collection routes, or mail delivery routes. Hamiltonian paths are used to minimize cost, distance, or time or to rank players in a tournament. Hamiltonian circuits are used in situations like the traveling salesperson problem such as, pay phone collection, ATM machine maintenance, or a robot in an automated warehouse. Minimal spanning trees arise in problems like the muddy roads scenarios or phone lines. Students should recognize the similarity between various problem situations and use algorithms they have developed for handling previous problems to solve similar problems in new contexts.

Recursive Thinking:

Many of the topics developed in the middle grades can be presented or analyzed recursively. Factorial notation can be introduced recursively. For example, present students with 10! = 10(9!) and have them determine what ! means (Hart, Maltas, & Rich, 1990). Students can test their theories by applying their understanding of factorial to calculate 5! and then comparing their answer to that generated by a calculator.

Linear situations can be modeled by NEXT/NOW formulas. Students can explore more complicated situations utilizing recursive formulas and a calculator or spreadsheet. For example, suppose you invest $1000 at 8% interest compounded monthly. Students can investigate how much money will be in the account after one year using recursion and a calculator. Since NEXT = 1.08(NOW), students can enter 1000 in their calculators, then the recursive formula 1.08(ANS), and press enter 12 times. For determining the amount of money in the account for longer periods of time, students can use a spreadsheet.

Students can also explore recursive patterns that arise in fractals. Consider the following pattern (see fig. 3) which shows the first three stages of a fractal pattern.

Students can determine the process which produces successive images in the pattern and extend the pattern. The can also explore the patterns in the number of new branches and the total number of branches at each stage, using recursive formulas for the nth stage. Similar activities can be performed using Sierpinski's triangle, generating triangles at various stages and counting the number of uncolored triangles.

Games like the Tower of Hanoi allow students to explore iterative processes, essential in understanding many problems in programming. Students explore the process for playing the game using the least number of moves for a small number of rings. Students should increase the number of rings until they can develop an algorithm for completing the game in the least number of moves which can be generalized to any number of rings by explaining how many additional moves are necessary when a ring is added. Legend warns that the world will end when the game is solved for 100 rings; do we need to worry? This question can be explored using a spreadsheet once the students have determined the effect of adding a ring to the game.

Optimization:

Using counting techniques, students should begin to appreciate the impossibility of checking all routes in a large network. They should establish a sense of understanding the meaning of "optimal" in various situations. For a wide variety of accessible optimization problems, see (Roberts, 1997; Althoen, Brown, & Bumcrot, 1991).

Grades 9-12 Focus Areas:

* develop and use counting techniques to solve combinatorial problems:

High school students should pull together their accumulated knowledge of discrete mathematics to tackle more complex, more realistic problems. Study at this level should also be more formalized, with students using standard notation and terminology.

Students should be able to recognize when combination and permutation formulas apply, as well as situations in which exponential or other counting methods are necessary. Students should be able to give general formulas for the number of ways one can choose a committee of m people from a group of n members in situations where the roles of committee members are assigned and where they are not. Students should be able to justify why _nC_m = _nC_n-m using an informal argument.

Card games provide opportunities for students to apply counting techniques to problems in probability. Genetic scenarios also allow the incorporation of counting techniques and probability while making a connection to biology.

Graph Theory:

Students should justify the necessary and sufficient conditions for traversibility of a network and be able to explain the various properties and characteristics of graphs using standard terminology. Students should be able to both recognize and create situations that can be modeled discretely. The focus of graph theory in high school should be on applications, particularly in optimization problems.

Recursive Thinking:

Students should use standard subscript notation for recursive formulas, modeling arithmetic and geometric sequences both explicitly and recursively. Students should understand how to represent recursive processes on a calculator, on a spreadsheet, and in programming.

Problems which are inaccessible to high school students without the use of recursive formulas and appropriate technology should be used to demonstrate the power and usefulness of recursive techniques. An example follows.

The Car Problem:

It is spring of your junior year of college, and you are faced with the prospect of buying a car. While your classmates are busy studying advertisements and sifting through reports by J.D. Power and Associates, you prudently decide to utilize your knowledge of discrete dynamical systems to aid in your decision. You have narrowed your choices to a Geo Metro ($12,000), a Pontiac Sunfire ($16,000), and Nissan Altima ($19,000). Based on an assessment of your financial situation, you realize that you should pay no more than $400 per month. Furthermore, you have decided to try to pay off your loan in four years. The First of America Bank has agreed to give you a loan for the cost of the car at a very reasonable annual interest rate of 8% compounded monthly. Assume that you make no down payment, and that the cost of the automobiles listed above includes tax, title, and licensing.

For this problem, students need only knowledge of simple interest to generate a recursive expression for the balance of the loan after n months :

Using the recursive formula and table option on graphing calculator or using a spreadsheet, students can answer the first two questions in a matter of minutes. The Metro takes 34 months to pay off, the Sunfire takes 47 months, and the Altima takes 58 months. Given the four year term limit, the Metro and the Sunfire are affordable under the given restrictions. To answer the third question, students can enter the cost of the Altima as the initial balance and adjust the monthly payment in the recursive formula so that

where M is the new monthly payment, until the balance becomes negative within the time constraint of four years.

Student responses may vary. Monthly payments of $470 with a final payment of $122.38 will pay off the loan in four years, as will monthly payments of $465 with a final payment of $397.30. The latter plan keeps payments more even, but students may argue that an extra $5 per month is worth the extra savings in the final month.

The equilibrium value for a system occurs when the system stabilizes at a particular value. For example, in this problem, the balance of the loan remains constant each month at the equilibrium value. In other words, each month the student pays the cost of the interest without ever paying off any of the principal.

Substituting $400 for M, students learn that if a $60,000 luxury car is purchased, then the loan will never be paid off with monthly payments of $400. Entering $60,000 as the initial condition in the calculator or spreadsheet, students can see that the monthly balance remains constant at $60,000.

The next two problems came straight out of a college text on Discrete Mathematics, Discrete Dynamical Systems: Theory and Applications (Sandefur, 1990). While the text suggests more advanced techniques for solving the problems, high school students can generate solutions using recursive formulas and appropriate technology.

Annuities:

You start a savings account paying 8% annual interest compounded monthly. You make an initial deposit of $1000 and decide to deposit $100 each month thereafter. How much is in the account after 5 years?

Each month the account grows by a factor of .08/12, and then an additional $100 is deposited. Thus, the account balance after n months is given by the recursive formula,

Entering this into the calculator or spreadsheet as before, students can quickly determine that the balance after 5 years corresponds to A₆₀, or $8837.53.

Amortization:

You are looking to buy a house. You can obtain a 30-year mortgage at 10% annual interest compounded monthly, and you can afford to pay $800 per month. How much can you afford to borrow?

Modifying the recursive formula for the car payments, students can adjust the initial balance (the amount of the loan) until the loan is paid off in 30 years (360 monthly payments). A first try of $100,000 will actually result in an increasing balance on the loan. Students should recognize that this means that the $800 monthly payments did not even cover the interest payments, so they will have to try a lower balance. Strategic guessing should enable students to determine within a small number of trials that a loan of $91,150 can be paid off in 30 years with monthly payments of $800 and a final payment of $583.74.

As a further investigation, students can then manipulate the monthly payment to determine how much they would have to pay each month to pay off that same loan of $91,150 in 20 years instead of 30. Monthly payments of $880 and a final payment of $584.49 will pay off the mortgage in just 20 years. Students may find it interesting to compare the total interest paid in each scenario. With a 30-year mortgage, the payments total $287,783.74, making the total interest paid $196,633.74. Whereas with a 20-year mortgage, the payments total $210,904.49, making the total interest paid $119,754.49. Thus, paying an extra $80 per month saves $76,879.25 in interest payments.

Students might also investigate finance charges issued by major credit card companies. What happens if a students charges $500 and only pays the minimum amount due each month? Students might explore this question for various percentage rates. Ask students how they think credit card companies compute the minimum amount due. What is their motivation for doing it that way?

Students can explore an endless number of questions using recursive formulas and appropriate technology. Financial situations provide considerable motivation for students, and perhaps they will generate their own questions for further exploration. In doing so, students gain valuable experience with a key mathematical theme and might learn some crucial lessons about the spiral effect of debt and the long-term effect of compounded interest.

Optimization:

Students should have varied opportunities to apply the algorithms they have developed for finding optimal solutions using discrete models. At the same time, students need to recognize the limitations of optimization algorithms, particularly as problems increase in complexity. For example, students should learn that it is currently an unsolved problem in mathematics to develop an efficient algorithm for finding the least number of colors necessary to color a large network. Using their knowledge of their own algorithms and counting techniques, students should be able to explain some of the reasons for the difficulty of this task.

Graph Coloring:

A manufacturer of chemicals ships its products by railroad tank cars. To reduce the danger that might occur through accidental spills of chemicals, the company specifies that the train must be made up in segments in such a way that

A reaction table is given indicating the dangerous interactions among the twelve chemicals. The students can represent the situation using a conflict graph in which the vertices represent the chemicals, and the edges represent a dangerous interaction between two chemicals. Using a greedy algorithm, students will find a 5-coloring of the graph model in which the colors represent chemical groupings. Each of the five chemical groupings must be separated by a pair of open gondolas of sand, plus a pair at the end before the caboose. Thus, 10 open gondolas of sand are required.

Critical Path Analysis:

You have been chosen to work on your school's yearbook and have been given a list of tasks to supervise. The order of the tasks and the amount of time for each task are listed in figure 4. As you make a schedule for these tasks, you must decide whether or not you can have the yearbook ready for the printers in four months (16 weeks). Can you?

Students can create a tree diagram depicting when each task may begin. This can then be translated into a directed graph in which each vertex represents a task, and each edge is labeled with the time needed to complete the originating task. This yields three possible paths from task A to finish with distances of 11, 10, and 16 weeks. Since enough time must be allowed to complete all tasks, 16 weeks is the minimum amount of time necessary, so the yearbook will be ready in time provided those "critical tasks" are completed on schedule.
 
 

Tasks to be done	Time required	Preceding tasks
A. Decide name and length of yearbook	1 week	None
B. Obtain printing estimates	3 weeks	A
C. Select a printer	1 week	B
D. Put up posters for stories and photos	1 week	A
E. Collect material submitted	5 weeks	D
F. Select material for yearbook	3 weeks	A, E
G. Decide layout	3 weeks	C, F
H. Final review of book	2 weeks	G
I. Send to printer	1 week	H

Integer Programming:

Typical linear programming problems dictate discrete domains for the variable quantities. Generally, we tend to treat these problems continuously, writing the problem so that the vertices of the solution region have integer coordinates. Yet, in real life, this will not always happen. Integer programming involves solving linear programming problems allowing only integer values for the variables. Consider the following optimization problem:

Suppose you and a partner make hand-knit wool sweaters on the weekends to sell to a local boutique for extra money. Solid color crew-neck sweaters sell for $40, and jacquard patterned cardigan sweaters sell for $70. Each crew-neck sweater takes 3 hours of your labor and 1 hour of your partner's labor. Each cardigan sweater requires 5 hours from each of you. If you have 15 hours to devote to this project each weekend, and your partner has 10 hours, how many of each type of sweater should you make each weekend to maximize your profit?

This corresponds to the following programming system:
 

Objective Quantity:     40x + 70y

           Constraints:     x>0, y>0

                                 3x + 5y < 15

                                  x + 5y < 10
                                                                                                        (adapted from Wampler & Newman, 1996)
 

Other Areas for Emphasis:

Besides the creation of a separate discrete mathematics standard, the NCTM needs to emphasize the importance of models and methods from discrete mathematics in the other standards, where appropriate. For example, the discussion of Standard 6: Problem Solving for grades 6-8 lists several problem solving heuristic including "looking for patterns, solving a simpler problem, making a table, and working backwards" (NCTM, 1998, p. 246). This standard should also mention making a graph model and reducing to the previous case. Similarly, the discussion of Standard 10: Representations should include the NEXT/NOW model. In the discussion of the first bullet for Standard 1: Numbers and Operations for grades 9-12, the investigation of arithmetic and geometric sequences should suggest that students develop recursive, as well as explicit, formulas for these sequences.

Additionally, throughout the Standards, attention must be given to the significance of a discrete domain in given problem situations. For example, we commonly assume a continuous model in solving problems concerning sports averages, ignoring the fact that a batting average of .312 really represents an average within the range from .3115 to .3125. As such, we present problems that have a single solution when approached continuously but which have several solutions when approached realistically, from a discrete perspective. We make a similar mistake in graphing linear inequalities. Consider the following scenario:

The high school charges $2 admission for students and $3 admission for adults. How many tickets must the school sell to achieve a revenue of $500 for Friday night's game?

Typically, we teach students to treat this scenario just as we would the problem of solving 2x + 3y > 500, perhaps with the additional constraint that our solution region is contained in the first quadrant. However, our solution region for the contextualized problem is also constrained to lattice points of the solution region for the mathematical problem. One problem has finitely many solutions, the other has infinitely many. It is important for students to make these kinds of distinctions and recognize the significance of the context on the solution of the problem.

Summary

The area of discrete mathematics provides numerous opportunities for students to investigate real-life problems with limited understanding of traditional topics in continuous mathematics. Teachers need to tap into the excitement that such investigations can create in the classroom, perhaps encouraging some students to pursue mathematics beyond the minimal requirements. Problems from discrete mathematics reflect a wide range of applications and connections within and outside of mathematics and easily incorporate the major themes of problem solving, representation, communication, and reasoning. As such, the inclusion of examples from discrete mathematics supports the overall message of the Standards.

Due to the history of specialized treatment of discrete mathematics, many teachers need additional clarification of the expectations involving discrete mathematics presented in the Discussion Draft. While the language of discrete mathematics appears scattered throughout the document, and some topics receive considerable attention, a few topics deserve more focused development. Most significantly, introduction of these topics must begin at the elementary grades in order for all students to reach their full potential in mathematics. It is my hope that the final version of the Standards 2000 will include more specific treatment and earlier introduction of combinatorics, graph theory, and recursion, as well as more careful attention to discrete models and reasoning throughout the document.

References: