Art Beads



Combinatorics Definitions and Examples

Multiplication principle, or rule of product:

The number of ways to make n consecutive independent choices is the product of the number of alternatives for each choice.

Example: There are 3 x 4 x 5 = 60 outfits possible when choosing to wear one of 3 shirts, 4 pairs of pants, and 5 hats.

Summation principle, or rule of sum:

The number of ways to make a single choice from among disjoint sets of alternatives is the sum of the number of alternatives in each set.

Example: There are 5 = 3 + 2 ways to choose to put on one of 3 possible pairs of shorts, or 2 possible pairs of pants. Nonexample: the number of ways to roll either a multiple of 2 or of 3 on a single die is not 5 = 3 ways to roll a multiple of 2 (2, 4, or 6) + 2 ways to roll a multiple of 3 (3 or 6). This is because the possibilities are not disjoint: 6 is a multiple both 2 and of 3. The number of multiples of 2 or 3 is 4 (2,3,4, or 6).

Permutations

The number of ways to arrange n different objects in a row is

n x (n-1) x (n-2) x ( x 3 x 2 x 1 (also written n! and called “n factorial”)

Example: The number of ways to arrange 5 books on a shelf is

5! = 5 x 4 x 3 x 2 x 1 = 120

k-Permutations

The number of ways to arrange k out of n objects (that is, choose k from the n and then arrange those k) is n x (n-1) x ( x (n-k+1) = n!/(n-k)!

In other words, it is a product of k factors, starting at n and going down.

This is often written as P(n,k) or as nPk

Example: The number of ways to arrange 3 books on a shelf selected from 5 books is

5 x 4 x 3 = 5!/2! = 60,

Combinations

The number of ways to choose k out of n objects (ignoring their order) is

nPk / k! = n!/k!(n-k)! and is written C(n,k), or nCk, or [pic]. (Read “n choose k”)

Example: The number of ways to choose 3 books from 5 books is

(5 x 4 x 3) / 2! = 5! / 3! 2! = 30

Notice that C(n,k) = C(n,(n-k)) because choosing k items is the same as choosing to exclude the remaining n-k items.

Tricks

There are many different tricks that we can use to help us count. The tricks, together with the basic techniques above, allow us to solve many more problems. Here are a few tricks.

• Simplify the problem by overcounting and then correcting your count by the amount you overcounted. Often, such correction is obtained either by division or subtraction.

Example: the number of necklaces with 5 different colored beads is not 5!, because this counts each bracelet 10 times: one for each rotation clockwise by one position, and one for the same bracelets flipped over. We therefore divide by 10 to get 5! / 10 = 12 different necklaces. Here we divide by the number of symmetries.

Example: the number of ways to roll a single die and obtain either a multiple of 2 or 3 is not 5 (since, as discussed above, we’ve counted “6” twice), but the correct answer is obtained by correcting: subtract the number of items that were counted twice to get 5 – 1 = 4.

• Separate into cases and use the summation principle.

Example: the number of ways to roll a number less than or equal to 4 when rolling two dice is computed by adding together the separate answers for the number of ways to roll 2, 3, or 4: 1 (1-1) + 2 (1-2 or 2-1) + 3 (1-3, 2-2, or 3-1) =6.

• Instead of counting the possibilities you are interested in, count all the other possibilities instead, and subtract from the total number.

Example: a die is rolled 3 times in succession. How many different outcomes have a “6” occurring at least once? You could break this into three cases (a 6 occurs once, a 6 occurs twice, and a 6 occurs thrice). But it is easiest to consider the number of different ways no 6 can occur, and subtract from the total number of possible outcomes. By the multiplication principle, there are 5 x 5 x 5 = 125 possible outcomes when the die is rolled three times (we assume order matters) without obtaining a 6. There are 6 x 6 x 6 = 216 possible outcomes in all. Consequently, the number of three-roll sequences that contain at least one 6 is exactly 216 – 125 = 91.

• mix and match all of the above tricks, and the various principles.

Probability

Many probability problems are really just counting problems. Identify a set S of possible outcomes. The probability that the event T occurs is defined to be the fraction of the S possibilities for which T holds also. Thus, the probability that a number is rolled on a die that is a multiple of 2 or of 3 is 4/6 = 2/3, because there are 6 possible outcomes for the die, and of these, 4 of them are multiples of 2 and/or 3.

In probability problems, the numerator and the denominator are often best dealt with as separate combinatorial counting problems.

Example: If 5 kids line up for recess in a random order, what is the probability that Arnie and Becky are next to each other? There are 5! = 120 ways for the kids to line up. Among these, 48 in which Arnie and Becky are together, so the probability is 48/120 = 2/5. (Where did 48 come from? Treat Arnie/Becky as one object, and there are then 4! = 24 ways to arrange them with the other 3 people. But we’ve undercounted because each of these can occur with Arnie first, or with Becky first. So, we multiply by 2 to count all of the possibilities.

Example: What is the probability of getting a full house in a 5-card hand? The denominator is the number of possible 5-card hands, which is C(52,5). For the numerator of the probability, we must answer: How many of these are full-houses? That is, consist of a pair and a triplet? The number of ways to choose the rank of the cards that form the pair and the triplet is C(13,2). But we also need to choose which of the 4 cards of the given ranks are to be included. For the triplet, there are 4 = C(4,1) possibilities (leave out the clubs, leave out the hearts, …). For the pair, there are C(4,2) possibilities (choose two suits from among the 4). Using the multiplication principle, the numerator is then C(13,2) x C(4,1) x C( 4,2).

Pascal’s Triangle

The kth element in the nth row of Pascal’s triangle is [pic].

Note for algebra teachers: this entry in Pascal’s triangle is also the coefficient of akbn-k when (a+b)n is multiplied out.

Another note. There are zillions of interesting properties and activities related to Pascal’s triangle. Surf the web.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download