Find all School-related info fast with the new School-Specific MBA Forum

It is currently 25 Oct 2014, 21:29

Close

GMAT Club Daily Prep

Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track
Your Progress

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.

Events & Promotions

Events & Promotions in June
Open Detailed Calendar

Math: Combinatorics

  Question banks Downloads My Bookmarks Reviews Important topics  
Author Message
TAGS:
Expert Post
30 KUDOS received
CEO
CEO
User avatar
Joined: 17 Nov 2007
Posts: 3573
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth) - Class of 2011
GMAT 1: 750 Q50 V40
Followers: 367

Kudos [?]: 1856 [30] , given: 359

GMAT ToolKit User Premium Member
Math: Combinatorics [#permalink] New post 27 Nov 2009, 10:05
30
This post received
KUDOS
Expert's post
30
This post was
BOOKMARKED
The topic is not finished.

COMBINATORICS

created by: walker
edited by: bb, Bunuel

--------------------------------------------------------
Image


This post is a part of [GMAT MATH BOOK]



Image

The information will be included in future versions of GMAT ToolKit
[read more] [AppStore]

--------------------------------------------------------

Definition

Combinatorics is the branch of mathematics studying the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties.


Enumeration

Enumeration is a method of counting all possible ways to arrange elements. Although it is the simplest method, it is often the fastest method to solve hard GMAT problems and is a pivotal principle for any other combinatorial method. In fact, combination and permutation is shortcuts for enumeration. The main idea of enumeration is writing down all possible ways and then count them. Let's consider a few examples:

Example #1
Q:. There are three marbles: 1 blue, 1 gray and 1 green. In how many ways is it possible to arrange marbles in a row?
Solution: Let's write out all possible ways:
Image
Answer is 6.

In general, the number of ways to arrange n different objects in a row

Example #2
Q:. There are three marbles: 1 blue, 1 gray and 1 green. In how many ways is it possible to arrange marbles in a row if blue and green marbles have to be next to each other?
Solution: Let's write out all possible ways to arrange marbles in a row and then find only arrangements that satisfy question's condition:
Image
Answer is 4.

Example #3
Q:. There are three marbles: 1 blue, 1 gray and 1 green. In how many ways is it possible to arrange marbles in a row if gray marble have to be left to blue marble?
Solution: Let's write out all possible ways to arrange marbles in a row and then find only arrangements that satisfy question's condition:
Image
Answer is 3.


Arrangements of n different objects

Enumeration is a great way to count a small number of arrangements. But when the total number of arrangements is large, enumeration can't be very useful, especially taking into account GMAT time restriction. Fortunately, there are some methods that can speed up counting of all arrangements.

The number of arrangements of n different objects in a row is a typical problem that can be solve this way:

1. How many objects we can put at 1st place? n.
2. How many objects we can put at 2nd place? n - 1. We can't put the object that already placed at 1st place.
.....
n. How nany objects we can put at n-th place? 1. Only one object remains.

Therefore, the total number of arrangements of n different objects in a row is

N = n*(n-1)*(n-2)....2*1 = n!


Combination

A combination is an unordered collection of k objects taken from a set of n distinct objects. The number of ways how we can choose k objects out of n distinct objects is denoted as:

C^n_k

knowing how to find the number of arrangements of n distinct objects we can easily find formula for combination:

1. The total number of arrangements of n distinct objects is n!
2. Now we have to exclude all arrangements of k objects (k!) and remaining (n-k) objects ((n-k)!) as the order of chosen k objects and remained (n-k) objects doesn't matter.

C^n_k = \frac{n!}{k!(n-k)!}



Permutation

A permutation is an ordered collection of k objects taken from a set of n distinct objects. The number of ways how we can choose k objects out of n distinct objects is denoted as:

P^n_k

knowing how to find the number of arrangements of n distinct objects we can easily find formula for combination:

1. The total number of arrangements of n distinct objects is n!
2. Now we have to exclude all arrangements of remaining (n-k) objects ((n-k)!) as the order of remained (n-k) objects doesn't matter.

P^n_k = \frac{n!}{(n-k)!}

If we exclude order of chosen objects from permutation formula, we will get combination formula:

\frac{P^n_k}{k!} = C^n_k


Circular arrangements

Let's say we have 6 distinct objects, how many relatively different arrangements do we have if those objects should be placed in a circle.

Image

The difference between placement in a row and that in a circle is following: if we shift all object by one position, we will get different arrangement in a row but the same relative arrangement in a circle. So, for the number of circular arrangements of n objects we have:

R = \frac{n!}{n} = (n-1)!


Tips and Tricks

Any problem in Combinatorics is a counting problem. Therefore, a key to solution is a way how to count the number of arrangements. It sounds obvious but a lot of people begin approaching to a problem with thoughts like "Should I apply C- or P- formula here?". Don't fall in this trap: define how you are going to count arrangements first, realize that your way is right and you don't miss something important, and only then use C- or P- formula if you need them.


Resources

Combinatorics DS problems: [search]
Combinatorics PS problems: [search]

Walker's post with Combinatorics/probability problems: [Combinatorics/probability Problems]

--------------------------------------------------------

[Reveal] Spoiler: Images


Attachment:
Math_Combinatorics_6balls.png
Math_Combinatorics_6balls.png [ 28.14 KiB | Viewed 57560 times ]
Attachment:
Math_Combinatorics_6balls_b.png
Math_Combinatorics_6balls_b.png [ 41.17 KiB | Viewed 57482 times ]
Attachment:
Math_Combinatorics_6balls_l.png
Math_Combinatorics_6balls_l.png [ 43.99 KiB | Viewed 57491 times ]
Attachment:
Math_Comb_Round_t.png
Math_Comb_Round_t.png [ 17.02 KiB | Viewed 57486 times ]

_________________

HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android) - The OFFICIAL GMAT CLUB PREP APP, a must-have app especially if you aim at 700+ | PrepGame


Last edited by bb on 10 Dec 2010, 21:26, edited 1 time in total.
spelling
Kaplan Promo CodeKnewton GMAT Discount CodesManhattan GMAT Discount Codes
Intern
Intern
User avatar
Joined: 15 Dec 2009
Posts: 23
Schools: Any offering one year MBA
WE 1: Information Tech
WE 2: Event Consultant for FIFA addi events and WC
Followers: 0

Kudos [?]: 5 [0], given: 14

Re: Math: Combinatorics [#permalink] New post 12 Jan 2010, 04:17
Nice compilation walker... When can we expect the complete material. :-)
_________________

K 4 KUDOS

Manager
Manager
avatar
Joined: 10 Jan 2010
Posts: 193
Location: Germany
Concentration: Strategy, General Management
Schools: IE '15 (M)
GMAT 1: Q V
GPA: 3
WE: Consulting (Telecommunications)
Followers: 2

Kudos [?]: 22 [0], given: 7

Re: Math: Combinatorics [#permalink] New post 03 Feb 2010, 05:19
Thank you for the posted information....much appreciated!!
Senior Manager
Senior Manager
User avatar
Joined: 21 Jul 2009
Posts: 367
Schools: LBS, INSEAD, IMD, ISB - Anything with just 1 yr program.
Followers: 14

Kudos [?]: 101 [0], given: 22

Re: Math: Combinatorics [#permalink] New post 15 Feb 2010, 20:03
Do it before this April bro!!!! Gotta brush my skills!!!!
_________________

I am AWESOME and it's gonna be LEGENDARY!!!

Manager
Manager
avatar
Joined: 30 Jun 2004
Posts: 178
Location: Singapore
Followers: 1

Kudos [?]: 13 [0], given: 5

GMAT ToolKit User
Re: Math: Combinatorics [#permalink] New post 03 Mar 2010, 22:50
I missed circular arrangement while brushing up my concepts. Thanks for the good post.
Manager
Manager
avatar
Joined: 21 Jan 2010
Posts: 233
Followers: 4

Kudos [?]: 55 [0], given: 38

Re: Math: Combinatorics [#permalink] New post 01 Apr 2010, 07:42
This is very helpful!
Intern
Intern
avatar
Joined: 16 Mar 2010
Posts: 13
Followers: 0

Kudos [?]: 2 [0], given: 3

Re: Math: Combinatorics [#permalink] New post 24 Jun 2010, 17:34
Waiting for the updates..... You hit the nail on the head

"Should I apply C- or P- formula here?". Don't fall in this trap: define how you are going to count arrangements first, realize that your way is right and you don't miss something important, and only then use C- or P- formula if you need them
Intern
Intern
avatar
Affiliations: Bangladesh National Cadet Corps(Army Wing),Dhaka University Film Society
Joined: 31 Jul 2009
Posts: 2
Location: Bangladesh
Schools: Texas A&M,University of North Florida,University of Texas
Followers: 0

Kudos [?]: 0 [0], given: 1

Re: Math: Combinatorics [#permalink] New post 04 Jul 2010, 10:32
many many thanks for the whole math collection...waiting for update and new one...
Manager
Manager
avatar
Status: Waiting to hear from University of Texas at Austin
Joined: 24 May 2010
Posts: 76
Location: Changchun, China
Schools: University of Texas at Austin, Michigan State
Followers: 5

Kudos [?]: 40 [0], given: 4

Re: Math: Combinatorics [#permalink] New post 14 Jul 2010, 18:35
Just read this post and the one about probability. A great help! Now I will try some application...
Manager
Manager
avatar
Joined: 23 Oct 2009
Posts: 84
Location: New Delhi, India
Schools: Chicago Booth, Harvard, LBS, INSEAD, Columbia
Followers: 5

Kudos [?]: 13 [0], given: 76

Re: Math: Combinatorics [#permalink] New post 17 Aug 2010, 05:30
Walker,
How come no updates on this chapter? If you're too busy to complete it, could you let me know what additional concepts to add? I could send a draft to you...?!
_________________

Read about my GMAT prep at http://gmatting.blogspot.com/
1st Feb '11 -- Actual GMAT : 730 (Q48 V42) AWA 6.0

My Practice GMAT Scores
29th Jan '11 -- GMATPrep#2 : 700 (Q47 V38)
23rd Jan '11 -- MGMAT Practice Test #3 : 670 (Q45 V36)
19th Jan '11 -- GMATPrep#1 v.1 : 710 (Q49 V37)
15th Jan '11 -- GMATPrep#1 : 720 (Q47 V42)
11th Jan '11 -- MGMAT Practice Test #2 : 740 (Q47 V44)
6th Jan '11 -- Kaplan#2 : 620 (Q40 V35)
28th Dec '10 -- PowerPrep#1 : 670 (Q47 V35)
30th Oct '10 -- MGMAT Practice Test #1 : 660 (Q45 V35)
12th Sept '10 -- Kaplan Free Test : 610 (Q39 V37)
6th Dec '09 -- PR CAT #1 : 650 (Q44 V37)
25th Oct '09 -- GMATPrep#1 : 620 (Q44 V34)

If you feel like you're under control, you're just not going fast enough.
A goal without a plan is just a wish.
You can go higher, you can go deeper, there are no boundaries above or beneath you.

Expert Post
CEO
CEO
User avatar
Joined: 17 Nov 2007
Posts: 3573
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth) - Class of 2011
GMAT 1: 750 Q50 V40
Followers: 367

Kudos [?]: 1856 [0], given: 359

GMAT ToolKit User Premium Member
Re: Math: Combinatorics [#permalink] New post 17 Aug 2010, 06:38
Expert's post
gmatdelhi wrote:
Walker,
How come no updates on this chapter? If you're too busy to complete it, could you let me know what additional concepts to add? I could send a draft to you...?!


You can post here any concepts/examples you think aren't covered by my post. At least everyone who read this thread will see them. I will do my best to include them in the first post.
_________________

HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android) - The OFFICIAL GMAT CLUB PREP APP, a must-have app especially if you aim at 700+ | PrepGame

Intern
Intern
avatar
Joined: 23 Aug 2010
Posts: 1
Followers: 0

Kudos [?]: 0 [0], given: 0

Re: Math: Combinatorics [#permalink] New post 25 Aug 2010, 10:41
Hi ,

I am just confused when to use permutation and when to use combination formula while solving problems. i mean what is the basic difference between Permutation and combination.
Intern
Intern
avatar
Joined: 03 Aug 2010
Posts: 22
Followers: 0

Kudos [?]: 1 [0], given: 0

Re: Math: Combinatorics [#permalink] New post 29 Aug 2010, 21:41
Good Info! Thank you for the posted!
_________________

Welcome to my paintings website - Wholesale Art Mall.

Forum Moderator
Forum Moderator
User avatar
Status: doing good things...
Joined: 02 Jul 2009
Posts: 1245
Concentration: Entrepreneurship, Finance
GMAT 1: Q V
GMAT 2: 690 Q49 V35
GPA: 3.77
WE: Corporate Finance (Commercial Banking)
Followers: 157

Kudos [?]: 527 [0], given: 531

GMAT ToolKit User Premium Member Reviews Badge
Re: Math: Combinatorics [#permalink] New post 09 Sep 2010, 05:45
Guys please help me,
How can I apply arrangements fromula for examples 2 and 3 in section enumeration?

if n=3 than N=could equal to 6 and 3 but not 4.
Please help.
_________________

Follow me, if you find my explanations useful.

Audaces fortuna juvat!

Get the best GMAT Prep Resources with GMAT Club Premium Membership

25 KUDOS received
Retired Moderator
User avatar
Joined: 02 Sep 2010
Posts: 807
Location: London
Followers: 76

Kudos [?]: 507 [25] , given: 25

GMAT ToolKit User Reviews Badge
Re: Math: Combinatorics [#permalink] New post 20 Sep 2010, 10:22
25
This post received
KUDOS
6
This post was
BOOKMARKED
walker wrote:
You can post here any concepts/examples you think aren't covered by my post. At least everyone who read this thread will see them. I will do my best to include them in the first post.


Here are some notes on choosing subsets, which might serve as a good addition. Hope you find this useful.

Choosing subsets & their applications

Combinatorial questions almost always deal with counting certain kinds of subsets of a given set in question. For instance, the popular C(n,r) formula is used to count the number of ways to pick up r objects from a set of n objects. This is basically the same as asking the question : "If a set A contains n objects, how many subsets of A contain exactly r objects ?". Notice that we cannot use P(n,r) to count these subsets since that involves counting the ordering as well, which is irrelevant when it comes to sets ({1,2,3} is same as {3,2,1}).

An interesting and useful extension of this way of thinking about counting presents itself when we encounter a group of problems where we need to count all the possible subsets of a set. Consider the following question :

There is a basket with 5 different fruits inside. A child is given the basket and he may pick out none, one or more of the fruits. In how many ways can this choice be made ?

In this question if we an count all the possible subsets of the basket of fruits, then each subset represents one way of choosing, and hence the answer to the question.

Solution 1
Think of each fruit as a yes/no question that the child is answering. "Will this fruit be picked ?". There are 2 ways to answer that question. There are 5 fruits in all and hence, 5 yes/no questions. Each set of answers [y n y n n], [y y n n n], etc represents a way of picking. In all the number of ways would be 2x2x2x2x2=2^5

Solution 2
An alternate method is to consider the cases, that the child picks 0 fruit, picks 1 fruit, ... picks 5 fruits. And sum the possibility
This method will yield the answer to be C(5,0)+C(5,1)+C(5,2)+C(5,3)+C(5,4)+C(5,5). If you calculate this sum, it is exactly equal to 2^5

Lets now look at a special case where, the objects we are picking from are identical to each other. Consider the following question :

There is a basket with 5 identical balls. A child is given the basket and he may pick out none, one or more of the balls. In how many ways can this choice be made ?

Notice the subtlety in this question, the objects to be picked out are identical to each other. So unlike the previous case where choosing just fruit#1 is a different choice to choosing just fruit#2, here choosing one ball or the other ball constitutes the same choice as long as only 1 ball is picked because the balls are indistinguishable

Solution
Since the balls are identical, the number of ways to pick them is defined merely by the number of balls you pick. So the different ways are "pick 0 balls", "pick 1 ball", ... "pick 5 balls". The answer therefore is 5+1 (The plus 1 giving the case where you pick 0 balls)

Finally we should consider the special case where we need to pick objects out of a set such that a few of the objects are identical to each other.

There is a basket with 4 blue balls, 3 red balls and 2 yellow balls. The balls of the same color are identical. How many ways can a child pick balls out of this basket ?

Solution
We combine techniques from the 2 cases above. Consider the blue balls as one entity and instead of asking the yes/no question, ask the question how many ways to choose the balls ? This is answered using the second case, and the answer is (4+1). Combining this with the ways to choose red and yellow balls, the overall ways to choose balls would be (4+1)*(3+1)*(2+1).

Formula Summary
Number of ways to pick 0 or more objects from n non-identical objects = 2^n
Number of ways to pick 1 or more objects from n non-identical objects = 2^n - 1
Number of ways to pick 0 or more objects from n identical objects = n+1
Number of ways to pick 1 or more objects from n identical objects = n
Number of ways to pick 0 or more objects from n objects of which n1 are identical, n2 are identical, ... ,nk are identical, such that n is n1+..+nk = (n1+1)*(n2+1)*...*(nk+1)
Number of ways to pick 1 or more objects from n objects of which n1 are identical, n2 are identical, ... ,nk are identical, such that n is n1+..+nk = (n1+1)*(n2+1)*...*(nk+1) - 1

Typical Applications

Here are just a couple of questions of this type :

How many factors does a number n have ?

Consider the prime factorization of n. Let this be :
n=p_1^{a1} p_2^{a2} ... p_n^{an}

Any factor of n will be of the form
m=p_1^{b1} p_2^{b2} ... p_n^{bn} where 0<=b_i<=a_i & 1<=i<=n

To count the number of factors, we need to count all the products of p1,...,pn such that the exponent is less than or equal to ai. This is just case 3. We just count per factor, how many ways to select p1, p2, ....

Answer is (a1+1)*(a2+1)* .... *(an+1)

In a class of 10 students, in how many ways can you form a academic committee, if the committee must contain a minimum of 2 students ?

Total number of ways to form committees (case 1) = 2^10
Number of ways to form of size 0 = 1
Number of ways to form of size 1 = 10 (each student picked one at a time)
So no of ways = 1024 -1 -10 = 1013
_________________

Math write-ups
1) Algebra-101 2) Sequences 3) Set combinatorics 4) 3-D geometry

My GMAT story

Get the best GMAT Prep Resources with GMAT Club Premium Membership

2 KUDOS received
CEO
CEO
User avatar
Status: Nothing comes easy: neither do I want.
Joined: 12 Oct 2009
Posts: 2794
Location: Malaysia
Concentration: Technology, Entrepreneurship
Schools: ISB '15 (M)
GMAT 1: 670 Q49 V31
GMAT 2: 710 Q50 V35
Followers: 182

Kudos [?]: 989 [2] , given: 235

Reviews Badge
Re: Math: Combinatorics [#permalink] New post 22 Sep 2010, 13:22
2
This post received
KUDOS
nice one shrouded.

I actually do the reverse. I use P = A^a * B^b * C^c for all the combination problems.

eg....for n identical, P is of the form = a*a* .........n times where a is prime number

so number of ways of selecting n identical -> n+1 using the formula of number of divisors.[ (a+1)*(b+1)*(c+1)]

for n non-identical P is of the form = a*b*c*...........n times

so number of ways of selecting n non-identical -> (1+1)*(1+1)...n times using the formula of number of divisors.

= 2^n

similarly if the number of identical balls are given then take P = A^a * B^b * C^c where a,b,and c are the number of identical balls of type A,B,and C respectively.

Then use the number of divisor formula = (a+1)*(b+1)*(c+1)
_________________

Fight for your dreams :For all those who fear from Verbal- lets give it a fight

Money Saved is the Money Earned :)

Jo Bole So Nihaal , Sat Shri Akaal

:thanks Support GMAT Club by putting a GMAT Club badge on your blog/Facebook :thanks

Get the best GMAT Prep Resources with GMAT Club Premium Membership

Gmat test review :
670-to-710-a-long-journey-without-destination-still-happy-141642.html

Intern
Intern
avatar
Joined: 24 May 2011
Posts: 4
Followers: 0

Kudos [?]: 0 [0], given: 0

Re: Math: Combinatorics [#permalink] New post 03 Jun 2011, 08:21
Kudos ... gr8 work... helped me alot in understanding the conce3pts of combinatorics.. as i m always confused with them... thnks for the notes...
Intern
Intern
avatar
Joined: 07 Jan 2011
Posts: 25
Followers: 1

Kudos [?]: 2 [0], given: 1

Re: Math: Combinatorics [#permalink] New post 30 Aug 2011, 02:31
Thanks walker for this post is really helpful
Intern
Intern
avatar
Joined: 20 Oct 2010
Posts: 32
Schools: HBS, Yale, Darden, Haas
Followers: 0

Kudos [?]: 1 [0], given: 0

Re: Math: Combinatorics [#permalink] New post 29 Nov 2011, 07:34
Great Post thanks!
Manager
Manager
User avatar
Joined: 23 Oct 2011
Posts: 85
Followers: 0

Kudos [?]: 20 [0], given: 34

Re: Math: Combinatorics [#permalink] New post 01 Dec 2011, 04:55
walker wrote:
Combination

A combination is an unordered collection of k objects taken from a set of n distinct objects. The number of ways how we can choose k objects out of n distinct objects is denoted as:

C^n_k

knowing how to find the number of arrangements of n distinct objects we can easily find formula for combination:

1. The total number of arrangements of n distinct objects is n!
2. Now we have to exclude all arrangements of k objects (k!) and remaining (n-k) objects ((n-k)!) as the order of chosen k objects and remained (n-k) objects doesn't matter.

C^n_k = \frac{n!}{k!(n-k)!}



Permutation

A permutation is an ordered collection of k objects taken from a set of n distinct objects. The number of ways how we can choose k objects out of n distinct objects is denoted as:

P^n_k

knowing how to find the number of arrangements of n distinct objects we can easily find formula for combination:

1. The total number of arrangements of n distinct objects is n!
2. Now we have to exclude all arrangements of remaining (n-k) objects ((n-k)!) as the order of remained (n-k) objects doesn't matter.

P^n_k = \frac{n!}{(n-k)!}

If we exclude order of chosen objects from permutation formula, we will get combination formula:

\frac{P^n_k}{k!} = C^n_k


Great Post.

I believe that the formulas can be used only when N\geq K
Re: Math: Combinatorics   [#permalink] 01 Dec 2011, 04:55
    Similar topics Author Replies Last post
Similar
Topics:
Combinatorics geisends 1 09 Mar 2011, 21:08
Combinatorics amp0201 2 21 Oct 2010, 13:10
1 Combinatorics Jinglander 6 08 Aug 2010, 14:15
2 Combinatorics abhi758 4 29 Aug 2009, 22:03
Experts publish their posts in the topic Combinatorics lbsgmat 4 04 Aug 2009, 12:38
Display posts from previous: Sort by

Math: Combinatorics

  Question banks Downloads My Bookmarks Reviews Important topics  

Go to page    1   2    Next  [ 31 posts ] 



GMAT Club MBA Forum Home| About| Privacy Policy| Terms and Conditions| GMAT Club Rules| Contact| Sitemap

Powered by phpBB © phpBB Group and phpBB SEO

Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.