THE PRODUCT RULE: Suppose that a procedure can be broken down into a sequence of two tasks. If there are ways to do the first task and for each of these ways of doing the first task, there are ways to do the second task, then there are ways to do the procedure.
THE SUM RULE: If a task can be done either in one of ways or in one of ways, where none of the set of ways is the same as any of the set of ways, then there are ways to do the task.
THE SUBTRACTION RULE: If a task can be done in either ways or ways, then the number of ways to do the task is minus the number of ways to do the task that are common to the two different ways.
THE DIVISION RULE: There are ways to do a task if it can be done using a procedure that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to way w.
THE PIGEONHOLE PRINCIPLE
· If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.
· If N objects are placed into k boxes, then there is at least one box containing at least ⌈N/k⌉ objects.
The Basics of Counting Discrete Mathematics “Resume”
6 PERMUTATIONS: A permutation of a set S is an ordered sequence that contains every element of S exactly once
· If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are
P(n, r) = n(n − 1)(n − 2) · · · (n − r + 1), r-permutations of a set with n distinct element
· If n and r are integers with 0 ≤ r ≤ n, then .
COMBINATIONS: An r-combination of elements of a set is an unordered selection of r elements from the set. Thus, an r-combination is simply a subset of the set with r elements.
· The number of r-combinations of a set with n elements, where n is a nonnegative integer and r is an integer with 0 ≤ r ≤ n, equals
THE BINOMIAL THEOREM: A binomial expression is simply the sum of two terms, such as x + y. Let x and y be variables, and let n be a nonnegative integer. Then
PASCAL’S IDENTITY: Let n and k be positive integers with n ≥ k. Then
VANDERMONDE’S IDENTITY: Let m, n, and r be nonnegative integers with r not exceeding either m or n. Then
For full document, Download File Here