In grades 9-12, the mathematics curriculum should include topics from discrete mathematics so that all students can--

• represent problem situations using discrete structures such as finite graphs, matrices, sequences, and recurrence relations;
• represent and analyze finite graphs using matrices;
• develop and analyze algorithms;
• solve enumeration and finite probability problems;

and so that, in addition, college-intending students can--

• represent and solve problems using linear programming and difference equations;
• investigate problem situations that arise in connection with computer validation and the application of algorithms.

Focus

As we move toward the twenty-first century, information and its communication have become at least as important as the production of material goods. Whereas the physical or material world is most often modeled by continuous mathematics, that is, the calculus and prerequisite ideas from algebra, geometry, and trigonometry, the nonmaterial world of information processing requires the use of discrete (discontinuous) mathematics. Computer technology, too, wields an ever-increasing influence on how mathematics is created and used. Computers are essentially finite, discrete machines, and thus topics from discrete mathematics are essential to solving problems using computer methods. In light of these facts, it is crucial that all students have experiences with the concepts and methods of discrete mathematics.

Although discrete mathematics is a relatively new term, we will consider it simply to be the study of mathematical properties of sets and systems that have a countable number of elements.

Discussion

This standard neither advocates nor describes a separate course in discrete mathematics at the secondary school level; rather, it identifies those topics from discrete mathematics that should be integrated throughout the high school curriculum. The topics recommended were not selected exclusively because of their potential applications to computer science but because they represent useful mathematical ideas that have assumed increasing importance for all students. The depth and formalism of treatment should be consistent with the level of the courses in which a topic appears.

An emphasis on mathematics as a powerful representation tool pervades all the K-12 standards. Finite graphs (structures consisting of vertices and edges), together with their associated matrix representations, offer an important addition to the student's repertoire of representation schemes. For example, a complex network of one-way streets can be represented geometrically by a directed graph, which in turn can be interpreted algebraically as a matrix. An i-j entry in the matrix is 1 if and only if corresponding vertices are adjacent (i.e., connected by an edge); otherwise, the entry is 0. The general technique is illustrated by the simplified example in figure 12.1.

Fig. 12.1. A graph and its adjacency matrix

By representing the graph as a matrix S and then multiplying S by itself, students can use S² to determine the number of two-stage routes connecting the various pairs of points. Students can generalize this procedure to graphs of any size, and computer software can be used to compute powers of the corresponding route matrices, which can then be analyzed to determine numbers of multiple-stage routes as well as other characteristics of networks.

Within the context of both the geometry and the algebra strands, students should have numerous opportunities to investigate this type of problem situation as well as those involving communication networks, circuit diagrams, tournament matchings, production schedules, and mathematical relations (e.g., the relation "is a factor of" defined on a finite set of integers), which can be effectively modeled and analyzed by graphs. Special graphs, called trees, are frequently used in the solution of probability problems and in representing the order of operations in algebraic expressions.

Sequences and series, currently topics in contemporary advanced algebra courses, should receive more attention, with a greater emphasis on their descriptions in terms of recurrence relations (formulas expressing each term as a function of one or more of the previous terms). Students can use recurrence relations to model real-world phenomena. The Fibonacci sequence is one model that has many applications:

1, 1, 2, 3, 5, 8, 13, 21,......

The numbers in the Fibonacci sequence occur surprisingly often in nature. They may be found in the arrangement of leaves around the branches of various trees, scales on pinecones, and the whorls on a pineapple. The analysis of these arrangements would provide an ideal setting for integrating the study of mathematics and botany.

Consumer applications essential for daily living should be included in the curriculum for all students. Recurrence relations can be used to provide a unified approach to such topics as compound interest, home mortgages, and annuities. For example, the compound-interest equation (see equation 1) can be generalized and expressed recursively as

The method of thinking recursively applies equally well to many geometric settings. For example, to determine the maximum number of regions into which a plane is separated by n lines, no two of which are parallel and no three of which intersect at a point, students should observe the following--

• For 0 lines, there is 1 region; that is, = 1.

• If there are regions for n - 1 lines (fig. 12.2), when the nth line, l, is drawn, an additional region is formed as l intercepts each of the n - 1 lines. One more region is formed as l continues past the last line. Thus,

  

  Fig. 12.2. Counting regions using recursive thinking

The recurrence relation can be used to solve the problem for any specified n. It also could be used to generate a sequence to which the method of finite differences could be applied to obtain a polynomial representation of the solution, in this case, r = (1/2)n² + (1/2)n + 1.

Instruction should stress the role of recurrence formulas as important tools for solving enumeration problems, since they can be translated easily to computer programs to obtain solutions. College-intending students should have the opportunity to use difference-equation techniques to express recurrence relations in closed form, that is, the nth term written as a function of n.

The development and analysis of algorithms lie at the heart of computer methods of solving problems. Thus, a consistent effort should be made throughout the 9-12 curriculum to provide opportunities for students to construct mathematics from an algorithmic point of view. Students must be encouraged to develop and analyze their own algorithms, not merely carry out those that have been prescribed to them. For example, approaching polynomial evaluation from an algorithmic point of view might involve the student in the following:

1. Verifying that can also be expressed in the form
2. Designing an algorithm for evaluating p(x) using the nesting pattern above (a possible notation for expressing the algorithm is shown below):

   

3. Comparing the number of operations used to evaluate p by the algorithm with the number needed when p is evaluated in standard form
4. Generalizing the algorithm so that it will evaluate a polynomial of degree n and then generalizing the answer in (3)
5. Engaging in a class discussion of the efficiency of the algorithm

Many of the topics in the secondary school mathematics curriculum can and should be investigated and developed by students from an algorithmic perspective. Possibilities include the greatest common factor of two integers; the solution of quadratic equations; approximating roots of polynomial equations; geometric constructions; the specification of a sequence of transformations mapping one figure onto another, similar one; the construction of Logo procedures to produce figures satisfying certain conditions; determining shortest/critical paths in finite graphs; random-number generation to simulate probability problems; sums of sequences; and solutions of systems of linear (and nonlinear) equations. The development and analysis of algorithms often add clarity and precision to the student's understanding of mathematical ideas and provide a context for nurturing careful logical reasoning.

In grades K-8, counting typically involves matching the elements of a set with a finite subset of the natural numbers. But real-world problems that can be simplified to the form "How many different subsets of size k can be selected from the members of a set having n distinct members?" require an entirely different method of counting. To develop students' ability to solve problems with this structure, instruction should emphasize combinational reasoning as opposed to the application of analytic formulas for permutations and combinations. To illustrate this shift in perspective, consider a fundamental identity involving binomial coefficients: = . This identity usually is established by algebraic manipulation of the formula for combinations. In contrast, a student who reasons combinatorially may observe that represents the number of ways one can choose an r-element set from an n-element set. For each r-element set chosen, however, there corresponds a set of n - r elements not chosen. Thus, the number of ways of choosing an r-element set is equal to the number of ways of choosing an (n - r)-element set.

Just as the topics of sequences, series, and recurrence formulas provide opportunities for reviewing algebra skills in a new context, so the suggested treatment of linear programming for college-intending students provides an opportunity to review topics from both geometry and algebra in a fresh context, rich in real-world applications.

From a discrete mathematics perspective, many topics now treated in contemporary courses and cited in other standards should receive increased attention: sets and relations; deductive proof, particularly proof by mathematical induction; the algebra of matrices; recursively defined functions; mathematical modeling; and algebraic structure.