[

The Department of Mathematics and Statistics proposes the following course for inclusion in University Studies, Mathematics/Statistics Flag at Winona State University. This was approved by the full department on Thursday, February 1, 2001.

Course: Combinatorics and Graph Theory (MATH 220), 3 s.h.

Catalog Description: Introduction to the basic ideas and fundamental laws of combinatorics and graph theory. This should satisfy the BOT and NCATE requirements for the Mathematics Education majors. Prerequisite: MATH 110 or MATH 120 or MATH 150

This is an existing course, previously approved by A2C2.

Department Contact Person for this course:

Jeffrey R. Anderson, Mathematics and Statistics Department Chair

Email janderson@winona.edu

General Discussion of University Studies – Mathematics/Statistics Flag in relation to MATH 220:

The purpose of the Mathematics/Statistics Flag course requirement is to reinforce the outcomes specified for the basic skills area of mathematics/statistics. These courses are intended to provide students with significant practice in applying prerequisite mathematical or statistical knowledge.

Courses can merit the Mathematics/Statistics Flag if students will be required to make essential use throughout the semester of mathematical or statistical models appropriate to their prerequisite knowledge of those areas, and if the correct use of techniques based on such models will comprise a significant portion of a student's final grade. It is understood that mere rote computations, algebraic manipulations, or graphical design without inferential content would not merit a Mathematics/Statistics Flag.

a. practice the correct application of mathematical or statistical models that are appropriate to their prerequisite knowledge of those areas;

 

In MATH 220, students consider the problems of cardinalities of sets and sample spaces and the properties of graphs. Based on a few cases and a handful of examples, students deduce patterns and make conjectures that may be valid not just for the few examples that they had examined but for all the possible cases satisfying certain conditions. As in all of mathematics, it is not enough for the students to accept their tested conjectures as fact. In the end, students determine the validity of their conjectures for all the cases through symbolic arguments such as through induction. Students make certain that their methods be well-thought out and clearly explained.

b. make proper use of modern mathematical or statistical methods appropriate to their level of prerequisite knowledge, to include, if statistics is used in a substantive way, the use of a

An example of a problem in the course is the question of binomial and multinomial expansions. What will the terms look like if one were to multiply out a polynomial by itself so many times? An integral part of the course as in all of mathematics is the determination of underlying priciples and laws that may hold true not just for a particular case but for other cases as well. Students find out that the answer to the question of polynomial expansions is related to problems involving coin tosses, the formation of committees, and finding shortest paths. Students discover how these examples are all related through investigation. The final step is proving what they think to be the true relationship between these problems and stating the final theorem or principle governing these cases.

Course Title: Combinatorics and Graph Theory MATH 220

Number of Credits: 3 S.H. Frequency of Offering: Every Semester

Prerequisite(s): MATH 110 or MATH 120 or MATH 150

Grading: Grade only for all majors, minors, options, concentrations and licensures within the Department of Mathematics and Statistics. The P/NC option is available to others.

Course Description: Introduction to the basic ideas and fundamental laws of combinatorics and graph theory. This should satisfy the BOT and NCATE requirements for the Mathematics Education majors.

Statement of major focus and objectives of the course: The major focus of this course is include providing students with the ability to infer patterns in counting the number of elements in sets formed through permutations and combinations, distributions and partitions. From the patterns, the students should be able to deduce relations such as recurrence relations in the determination of the cardinality of the set being studied. The students may have to use computer software in searching for, identifying and studying the patterns that may be found. In addition, this course will provide the student the ability to make conjectures and prove the validity of their conjectures about trees and graphs.

Note that a focus of the course will be to prepare students to develop the competencies outlined in the following Minnesota Standards of Effective Teaching Practice for Beginning Teachers: Standard 1 -- Subject Matter Objectives

To develop within the future teacher ...

· the ability to use a problem-solving approach to investigate and understand mathematical content

· the ability to formulate and solve problems from both mathematical and everyday situations

· the ability to communicate mathematical ideas in writing, using everyday and mathematical language, including symbols

· the ability to communicate mathematical ideas orally, using both everyday and mathematical language

· the ability to make and evaluate mathematical conjectures and arguments and validate their own mathematical thinking

· the ability to connect mathematics to other disciplines and real-world situations

· an understanding of and the ability to apply concepts of number, number theory and number systems

· the ability to use algebra to describe patterns, relations and functions and to model and solve problems

 

The purpose of the Mathematics/Statistics Flag course requirement is to reinforce the outcomes specified for the basic skills area of mathematics/statistics. These courses are intended to provide students with significant practice in applying prerequisite mathematical or statistical knowledge.

Courses can merit the Mathematics/Statistics Flag if students will be required to make essential use throughout the semester of mathematical or statistical models appropriate to their prerequisite knowledge of those areas, and if the correct use of techniques based on such models will comprise a significant portion of a studentís final grade. It is understood that mere rote computations, algebraic manipulations, or graphical design without inferential content would not merit a Mathematics/Statistics Flag.

 These courses must include requirements and learning activities that promote students' abilities to...

a. practice the correct application of mathematical or statistical models that are appropriate to

their prerequisite knowledge of those areas; and

b. make proper use of modern mathematical or statistical methods appropriate to their level of

prerequisite knowledge, to include, if statistics is used in a substantive way, the use of a

statistical package with graphics capability when appropriate.

Course Outline of the Major Topics and Subtopics:

I. Elementary Combinatorics: Principles of Counting-Rule of Sum and Product; Permutations, Combinations, Partition, Distribution; Probability;

II. Special Counting Methods: Inclusion and Exclusion; Recurrence Relations; Generating Functions

III. Graphs: Graph Representations; Isomorphism; Connectivity; Euler and Hamiltonian Paths

IV. Trees: Spanning Trees; Rooted Trees; Sorting; Directed Graph;

 

Method of Instruction: Lecture, Discussion, Group work

Evaluation Procedure: Hour exams, Quizzes, Final exam, Group work

Textbooks or Alternatives:

Combinatorics, a Problem-Oriented Approach, Marcus

Introduction to Graph Theory, Wilson

List of References and Bibliography:

A First Course in Probability, Ross

Discrete Mathematics: Applied Combinatorics and Graph Theory, by Townsend

Probability, Ross

Discrete Mathematics, Epp

Department Recommendation: Approved Disapproved Date

Chairperson Signature Date

Dean's Recommendation: Approved Disapproved Date

Dean's Signature Date

*In the case of a Dean's recommendation to disapprove a proposal, a written rationale for the recommendation

USS Recommendation: Approved Disapproved Date

University Studies Director's Signature Date

A2C2 Recommendation: Approved Disapproved Date

A2C2 Chairperson Signature Date

Faculty Senate Recommendation: Approved Disapproved Date

FA President's Signature Date

Academic VP's Recommendation: Approved Disapproved Date

VP's Signature Date

President's Decision: Approved Disapproved Date

President's Signature Date