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

Chieftang's Combinatorics Notes

This topic has 3 member replies
Bookmark
Previous Topic Next Topic
chieftang Really wants to Beat The GMAT! Default Avatar
Joined
23 Nov 2011
Posted:
218 messages
Followed by:
3 members
Thanked:
25 times
Chieftang's Combinatorics Notes Post Sat Dec 10, 2011 11:21 pm
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
    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 Default Avatar
    Joined
    17 May 2011
    Posted:
    70 messages
    Thanked:
    9 times
    Post Mon Dec 12, 2011 9:16 am
    This is very helpful, thank you for sharing Chieftang Smile

    chieftang Really wants to Beat The GMAT! Default Avatar
    Joined
    23 Nov 2011
    Posted:
    218 messages
    Followed by:
    3 members
    Thanked:
    25 times
    Post Mon Dec 12, 2011 6: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 Default Avatar
    Joined
    17 May 2011
    Posted:
    70 messages
    Thanked:
    9 times
    Post Tue Dec 13, 2011 8: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 GmatKiss 152 topics
    2 karthikpandian19 68 topics
    3 fangtray 66 topics
    4 ronnie1985 36 topics
    5 amit.trivedi@ymai... 34 topics
    See More Top Beat The GMAT Members...

    Most Active Experts
    1 image description Bill@VeritasPrep

    Veritas Prep

    		 294 posts
    2 image description GMATGuruNY

    The Princeton Review Teacher

    		 202 posts
    3 image description Anurag@Gurome

    Gurome

    		 121 posts
    4 image description Stuart Kovinsky

    Kaplan GMAT Teacher

    		 90 posts
    5 image description Jon@PrecisionEssay

    Precision Essay

    		 80 posts
    See More Top Beat The GMAT Experts