Welcome! Check out our free B-School Guides to learn how you compare with other applicants.

## Chieftang's Combinatorics Notes

This topic has 3 member replies
chieftang Really wants to Beat The GMAT!
Joined
23 Nov 2011
Posted:
218 messages
Followed by:
3 members
Thanked:
26 times
Chieftang's Combinatorics Notes Sun Dec 11, 2011 12:21 am
Elapsed Time: 00:00
• Lap #[LAPCOUNT] ([LAPTIME])
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

Thanked by: neelgandham, ariz, bhargavi2010
Need free GMAT or MBA advice from an expert? Register for Beat The GMAT now and post your question in these forums!
ariz Rising GMAT Star
Joined
17 May 2011
Posted:
70 messages
Thanked:
9 times
Mon Dec 12, 2011 10:16 am
This is very helpful, thank you for sharing Chieftang

chieftang Really wants to Beat The GMAT!
Joined
23 Nov 2011
Posted:
218 messages
Followed by:
3 members
Thanked:
26 times
Mon Dec 12, 2011 7:45 pm
Glad a couple people found it useful. I find that writing things down is a great way to remember them, so it was useful for me too!

ariz Rising GMAT Star
Joined
17 May 2011
Posted:
70 messages
Thanked:
9 times
Tue Dec 13, 2011 9:31 am
That is very true, back in the day when I was still in school I found that taking notes during class was very helpful in retaining info, despite the fact that I rarely go back and reread those notes later on.

### Best Conversation Starters

1 varun289 42 topics
2 JeneAleEngend 23 topics
3 guerrero 21 topics
4 sana.noor 20 topics
5 tycleEmetly 20 topics
See More Top Beat The GMAT Members...

### Most Active Experts

1 Brent@GMATPrepNow

GMAT Prep Now Teacher

202 posts
2 GMATGuruNY

The Princeton Review Teacher

140 posts
3 Anju@Gurome

Gurome

113 posts
4 Jim@StratusPrep

Stratus Prep

92 posts