tailieunhanh - Discrete Math for Computer Science Students

In the example of the voting primaries above there are 236 or about 70 billion subsets. Of course, we cannot deal with this many subsets in a practical problem, but fortunately we are usually interested in only a few of the subsets. The most interesting subsets are those which can be defined by means of a simple rule such as “the set of all logical possibilities in which C loses at least two primaries”. It would be diffi- cult to give a simple description for the subset containing the elements {P1, P4, P14, P30, P34}. On the other hand, we shall see in the next section how to define. | Discrete Math for Computer Science Students Ken Bogart Dept. of Mathematics Dartmouth College Scot Drysdale Dept. of Computer Science Dartmouth College Cliff Stein Dept. of Industrial Engineering and Operations Research Columbia University ii Kenneth P. Bogart Scot Drysdale and Cliff Stein 2004 Contents 1 Counting 1 Basic Counting. 1 The Sum Principle. 1 Abstraction. 2 Summing Consecutive Integers. 3 The Product Principle. 3 Two element subsets. 5 Important Concepts Formulas and Theorems. 6 Problems . 7 Counting Lists Permutations and Subsets. 9 Using the Sum and Product Principles. 9 Lists and functions. 10 The Bijection Principle . 12 fc-element permutations of a set. 13 Counting subsets of a set . 13 Important Concepts Formulas and Theorems. 15 Problems . 16 Binomial Coefficients. 19 Pascal s Triangle. 19 A proof using the Sum Principle . 20 The Binomial Theorem . 22 Labeling and trinomial coefficients . 23 Important Concepts Formulas and Theorems. 24 Problems . 25 Equivalence Relations and Counting Optional . 27 The Symmetry Principle . 27 .

• Toán học
• dismissed
• resulting
• decision making processes
• perspectives as possible
• Reaching decisions
• trade off between
• answer and simply
• elusive
• however