Introduction to Counting
1) Counting (or combinatiorics) deals with strategies for counting large numbers of combinations and arrangements
2) ‘and’ = multiply; ‘or’ = add
3) remember that listing is a good preliminary strategy that may yield further insights
Fundamental Counting Principle
1) the fundamental counting principle (FCP) says that if the first stage can be done in n_1 ways, the second in n_1 ways, etc., then the complete task can be done in N = (n_1)*(n_2)*(n_3)*etc. ways
2) if we have to arrange a set of n different items in order, the number of possible orders is the product of n times all the positive integers less than n
FCP with Restrictions
When a counting problem contains restrictions in certain stages, always do the most restrictive stage first
Factorial Notation
1) n! (Read ‘n factorial’) is the product of n and all the positive integers less than n
2) any factorial n! Is divisible by all the integers less than n and all the factorials less than n!
3) n different items can be arranged in n! unique orders
Counting What You Do not Want
1) if you are asked to count how many arrangements obey a restriction, it may be easier to count the ones that do not, and subtract them from the total
2) one clue: the word ‘not’
3) another clue: focus on a single item
Counting with Identical Items
1) if, in a set of n items, b are identical, then the total number of the distinct arrangements is (n!)/(b!)
2) if, in the set of n items, b are identical, a different c are identical, and another group of d are identical, then
N = (n!)/(b!)(c!)(d!)
3) remember listing and counting can also be helpful
Eliminating Repetition
When we count, we must eliminate repetitions. We do this by dividing by the total number of times each arrangement is repeated.
Combination
1) in a combination, we are concerned with an end-group of r individuals chosen from a pool of n, and order of selection does not matter
2) nCr is the number of ways to choose r individuals from a pool of n
3) nC1 = n
4) nCr = nC(n-r)
5) we calculate nCr starting with the FCP, and dividing to eliminate repetition
When to Use Combinations
1) order matters -> stages + FCP; order does not matter -> combinations
2) one guideline is to consider the resulting arrangement and whether switching items around in this result would matter
3) read solution sets and study how the instructor choose to view the situation
Calculating Combinations
1) remember that you can always calculate combinations by using the FCP and dividing to eliminate the repetitions
2) remember to cancel in the nCr formula, including canceling before you multiply
3) remember the shortcut formula:
nC2 = n(n-1)/2
4) Practice using Pascal’s triangle to generate values of nCr ( from row 3)
Permutations排列 and Combinations组合
Some guidelines about order
1) if we are counting the number of physical arrangements (books on shelf, row of chairs, etc.) then order matters
2) if roles are specified for each choice, then order matters
3) if choosing elements in different order produces meaningful different outcomes, then order matters
4) conversely, if the choice of individual elements does not make any meaningful different in the final set, order does not matter
Permutations vs. Combinations vs. FCP
1) the FCP is more basic, more flexible, and more widely applicable than either permutation or combinations
2) if picking with no repeats, and order does not matter, then use combinations
3) if picking with no repeats, and different orders of the final section are meaningfully different (i.e. order matters), then it is a permutation: use the FCP)
