-
chieftang
- Master | Next Rank: 500 Posts
- Posts: 218
- Joined: Wed Nov 23, 2011 8:05 pm
- Thanked: 26 times
- Followed by:4 members
Chieftang's Combinatorics Notes
1. Counting Assignments
Remember: The number of ways to assign n values to each of k items is n^k
Examples:
A car can be painted white, red, blue, green, or silver. In how many ways can 4 cars be painted?
Answer: n=5, k=4. 5^4 = 5*5*5*5 = 625
A six-sided die is rolled 3 times. How many possible outcomes are there?
Answer: n=6, k=3. 6^3 = 6*6*6 = 216
A coin is flipped 5 times. How many possible outcomes are there?
Answer: n=2, k=5. 2^5 = 2*2*2*2*2 = 32
2. Counting Permutations
Remember: The number of ways n distinct items can be arranged is n! (n factorial, n * (n-1) * (n-2) * ... * 1)
Examples:
How many ways can the letters A, B, C, D be arranged?
Answer: n=4. 4! = 4*3*2*1 = 24
There are nine players in a baseball lineup. How many different batting orders are there?
Answer: n=9. 9! = 9*8*7*6*5*4*2*1 = 362880
3. Ordered Selections
Remember: The number of ways to make k selections from a group of n items in a specific order is n!/(n - k)!
Examples:
15 horses enter the Kentucky Derby. How many different ways are there to award 1st, 2nd, and 3rd place prizes assuming all 15 horses will finish the race?
Answer: n=15, k=3. 15!/(15-3)! = 15!/12! = 15*14*13 = 2730
How many ways are there to form a sequence of 3 lower case letters, if no letter can be repeated in the sequence?
Answer: n=26, k=3. 26!/(26-3)! = 26!/23! = 26*25*24 = 15600
4. Unordered Selections
Remember: The number of ways to make k selections from a group of n items in no specific order is nCk "n choose k" or n!/((n - k)! * k!)
Examples:
15 horses enter the Kentucky Derby. How many different groups of 3 horses might be the first three across the finish line assuming all 15 horses will finish the race?
Answer: n=15, k=3. 15C3 = 15!/((15 - 3)! * 3!) = 15!/(12! * 3!) = (15*14*13)/(3*2*1) = 455
In how many ways can we choose a set of 3 lower case letters?
Answer: n=26, k=3. 26C3 = 26!/((26-3)! * 3!) = 26!/(23! * 3!) = (26*25*24)/(3*2) = 2600
5. Orderings With Identical Items
Remember: If there are n items, some identical, then the n items can be divided into k groups of sizes i1, i2,...,ik where items within a group are identical and items in different groups are distinguishable, and the number of different distinguishable orders of the n items is n!/(i1! * i2! * ... *ik!).
Examples:
How many different anagrams of the word "error" are there?
Answer: n=5, i1=3, i2=1, i3=1. 5!/(3!*1!*1!) = 5!/3! = 5*4 = 20
Note: There are three groups of letters here. One group i1 = {r, r, r} (size 3), another group i2 = {e} (size 1), and another group i3 = {o} (size 1).
In how many ways can we arrange in a line three red ping pong balls, four blue ping pong balls, and five green ping pong balls?
Answer: n=12, i1=3, i2=4, i3=5. 12!/(3! * 4! * 5!) = (12*11*10*9*8*7*6)/(4!*3!) = 3991680 / 144 = 27720
6. Distribution of Objects in to Bins
a. Identical Objects
Remember: n identical items can be distributed in to m bins in (n+m-1)Cn or (n+m-1)!/((m-1)! * n!) ways. Note: some bins can contain 0 items.
Examples:
In how many ways can 4 biscuits be distributed to 3 dogs?
Answer: n=4, m=3. (4+3-1)C4 = 6C4 = 6!/(2! * 4!) = (6*5)/2 = 15
b. Distinguishable Objects
Remember: If there are n items, some distinguishable and some identical, then the n items can be divided into k groups of sizes i1, i2,...,ik where items within a group are identical and items in different groups are distinguishable, and there are (n+m-1)!/((m-1)! * i1! * i2! * ... * ik!) possible distibutions in to m bins.
Examples:
In how many ways can 3 biscuits and 2 bones be distributed to 4 dogs?
Answer: n=5, m=4, i1=3, i2=2. (5+4-1)!/((4-1)! * 3! * 2!) = 8! / (3! * 3! * 2!) = (8*7*6*5*4)/(3*2*2) = 560
1. Counting Assignments
Remember: The number of ways to assign n values to each of k items is n^k
Examples:
A car can be painted white, red, blue, green, or silver. In how many ways can 4 cars be painted?
Answer: n=5, k=4. 5^4 = 5*5*5*5 = 625
A six-sided die is rolled 3 times. How many possible outcomes are there?
Answer: n=6, k=3. 6^3 = 6*6*6 = 216
A coin is flipped 5 times. How many possible outcomes are there?
Answer: n=2, k=5. 2^5 = 2*2*2*2*2 = 32
2. Counting Permutations
Remember: The number of ways n distinct items can be arranged is n! (n factorial, n * (n-1) * (n-2) * ... * 1)
Examples:
How many ways can the letters A, B, C, D be arranged?
Answer: n=4. 4! = 4*3*2*1 = 24
There are nine players in a baseball lineup. How many different batting orders are there?
Answer: n=9. 9! = 9*8*7*6*5*4*2*1 = 362880
3. Ordered Selections
Remember: The number of ways to make k selections from a group of n items in a specific order is n!/(n - k)!
Examples:
15 horses enter the Kentucky Derby. How many different ways are there to award 1st, 2nd, and 3rd place prizes assuming all 15 horses will finish the race?
Answer: n=15, k=3. 15!/(15-3)! = 15!/12! = 15*14*13 = 2730
How many ways are there to form a sequence of 3 lower case letters, if no letter can be repeated in the sequence?
Answer: n=26, k=3. 26!/(26-3)! = 26!/23! = 26*25*24 = 15600
4. Unordered Selections
Remember: The number of ways to make k selections from a group of n items in no specific order is nCk "n choose k" or n!/((n - k)! * k!)
Examples:
15 horses enter the Kentucky Derby. How many different groups of 3 horses might be the first three across the finish line assuming all 15 horses will finish the race?
Answer: n=15, k=3. 15C3 = 15!/((15 - 3)! * 3!) = 15!/(12! * 3!) = (15*14*13)/(3*2*1) = 455
In how many ways can we choose a set of 3 lower case letters?
Answer: n=26, k=3. 26C3 = 26!/((26-3)! * 3!) = 26!/(23! * 3!) = (26*25*24)/(3*2) = 2600
5. Orderings With Identical Items
Remember: If there are n items, some identical, then the n items can be divided into k groups of sizes i1, i2,...,ik where items within a group are identical and items in different groups are distinguishable, and the number of different distinguishable orders of the n items is n!/(i1! * i2! * ... *ik!).
Examples:
How many different anagrams of the word "error" are there?
Answer: n=5, i1=3, i2=1, i3=1. 5!/(3!*1!*1!) = 5!/3! = 5*4 = 20
Note: There are three groups of letters here. One group i1 = {r, r, r} (size 3), another group i2 = {e} (size 1), and another group i3 = {o} (size 1).
In how many ways can we arrange in a line three red ping pong balls, four blue ping pong balls, and five green ping pong balls?
Answer: n=12, i1=3, i2=4, i3=5. 12!/(3! * 4! * 5!) = (12*11*10*9*8*7*6)/(4!*3!) = 3991680 / 144 = 27720
6. Distribution of Objects in to Bins
a. Identical Objects
Remember: n identical items can be distributed in to m bins in (n+m-1)Cn or (n+m-1)!/((m-1)! * n!) ways. Note: some bins can contain 0 items.
Examples:
In how many ways can 4 biscuits be distributed to 3 dogs?
Answer: n=4, m=3. (4+3-1)C4 = 6C4 = 6!/(2! * 4!) = (6*5)/2 = 15
b. Distinguishable Objects
Remember: If there are n items, some distinguishable and some identical, then the n items can be divided into k groups of sizes i1, i2,...,ik where items within a group are identical and items in different groups are distinguishable, and there are (n+m-1)!/((m-1)! * i1! * i2! * ... * ik!) possible distibutions in to m bins.
Examples:
In how many ways can 3 biscuits and 2 bones be distributed to 4 dogs?
Answer: n=5, m=4, i1=3, i2=2. (5+4-1)!/((4-1)! * 3! * 2!) = 8! / (3! * 3! * 2!) = (8*7*6*5*4)/(3*2*2) = 560
