A man wants to visit at least two of the four cities A, B, C and D. how many travel itineries can he make? all cities are connected to one another.
Can somebody please explain why we need to use permutation here and not combination?
Permutation or Combination?
This topic has expert replies
-
- Junior | Next Rank: 30 Posts
- Posts: 10
- Joined: Sun Jul 08, 2012 12:35 am
-
- Senior | Next Rank: 100 Posts
- Posts: 85
- Joined: Mon Nov 12, 2012 11:12 am
- Thanked: 8 times
- Followed by:2 members
Say the man wants to visit just 2 cities of the 4 cities. Then, you have the following 6 options:
AB AC AD BC BC CD
This 6 options can be obtained by using the combination formula 4C2.
But, in this case, itinerary means AB is not the same as BA, which means you can start with either city A or city B and have two different itinerary. Hence the problem becomes a permutation problem. So, you need to multiply 6 by 2 to obtain 12 as answer for ways you can form an itinerary to visit 2 cities out of 4 cities.
Hope this makes sense.
AB AC AD BC BC CD
This 6 options can be obtained by using the combination formula 4C2.
But, in this case, itinerary means AB is not the same as BA, which means you can start with either city A or city B and have two different itinerary. Hence the problem becomes a permutation problem. So, you need to multiply 6 by 2 to obtain 12 as answer for ways you can form an itinerary to visit 2 cities out of 4 cities.
Hope this makes sense.
-
- Junior | Next Rank: 30 Posts
- Posts: 10
- Joined: Sun Jul 08, 2012 12:35 am
Thanks for your reply. so in this question is "all cities are connected to one another" the cue to decide what we need to apply here (P or C)?
-
- Senior | Next Rank: 100 Posts
- Posts: 85
- Joined: Mon Nov 12, 2012 11:12 am
- Thanked: 8 times
- Followed by:2 members
If the question asks for "how many ways the man can choose 2 or more cities for his itinerary", then it would be a combination problem. The key here is that starting from city A is not the same as starting from city B. So, AB and BA are different itineraries.
-
- Junior | Next Rank: 30 Posts
- Posts: 10
- Joined: Sun Jul 08, 2012 12:35 am
-
- Master | Next Rank: 500 Posts
- Posts: 131
- Joined: Wed Nov 14, 2012 2:01 pm
- Thanked: 39 times
- Followed by:2 members
-
- Senior | Next Rank: 100 Posts
- Posts: 85
- Joined: Mon Nov 12, 2012 11:12 am
- Thanked: 8 times
- Followed by:2 members
- The Iceman
- Master | Next Rank: 500 Posts
- Posts: 194
- Joined: Mon Oct 15, 2012 7:14 pm
- Location: India
- Thanked: 47 times
- Followed by:6 members
It's basically a problem on arrangements because order matters here.s.pharmaco wrote:A man wants to visit at least two of the four cities A, B, C and D. how many travel itineries can he make? all cities are connected to one another.
Can somebody please explain why we need to use permutation here and not combination?
First you can arrange all 4 cities. Then select three cities out of four and arrange those three cities. Lastly, select two out of the four and arrange those two cities.
4!+(4C3)*3!+4C2*2! = 60
You could also see this as 4P4 + 4P3 + 4P2, but it is easier to follow the convention using combination "C", given you are bale to apply the logic correctly.
I tried a different approach to solve this question, though its wrong but I want to understand why my approach is wrong here. Please help on that!The Iceman wrote:It's basically a problem on arrangements because order matters here.s.pharmaco wrote:A man wants to visit at least two of the four cities A, B, C and D. how many travel itineries can he make? all cities are connected to one another.
Can somebody please explain why we need to use permutation here and not combination?
First you can arrange all 4 cities. Then select three cities out of four and arrange those three cities. Lastly, select two out of the four and arrange those two cities.
4!+(4C3)*3!+4C2*2! = 60
You could also see this as 4P4 + 4P3 + 4P2, but it is easier to follow the convention using combination "C", given you are bale to apply the logic correctly.
There are 4 cites,so for each city we have 2 options either 'Yes' or 'No' making the no. of ways available = 2x2x2x2 = 16
Now, we have to make itineraries picking at least 2 cities. This can be done by eliminating 1) Where we have 'No' in all the cities, there is only one way it can happen=1 2)Where only one city is not picked, this can happen in four ways [YYYN] [YYNY] [YNYY] [NYYY] =4.
Therefore, the no. of ways itineraries can be made picking at least two cities = 16-1-4=11.
What is wrong with my approach?
GMAT/MBA Expert
- [email protected]
- Elite Legendary Member
- Posts: 10392
- Joined: Sun Jun 23, 2013 6:38 pm
- Location: Palo Alto, CA
- Thanked: 2867 times
- Followed by:511 members
- GMAT Score:800
Hi mneeti,
Your approach doesn't account for the ORDER of the stops on the itinerary.
Going to City A first and City B second is NOT THE SAME as going to City B first and City A second.
GMAT assassins aren't born, they're made,
Rich
Your approach doesn't account for the ORDER of the stops on the itinerary.
Going to City A first and City B second is NOT THE SAME as going to City B first and City A second.
GMAT assassins aren't born, they're made,
Rich
-
- Master | Next Rank: 500 Posts
- Posts: 468
- Joined: Mon Jul 25, 2011 10:20 pm
- Thanked: 29 times
- Followed by:4 members
My take 40,
the qustion asks how many travel itineries can he make if he wants to visit at least 2 cities
it means differant itineries for visiting 2 cities + differant itineries for visiting 3 cities
for 2 cities (since all cities are connected to one another)
A-B-C "A to B to C"
A-C-D
A-D-B
A-B-C
Like starting with A we have 4 itineries same for B,C and D
4+4+4+4 = 16
Smae as for 3 cities
fix A in first position, rest B,C and D can be rearranges in 6 ways
same as for B,C, and D
6+6+6+6 = 24
24 + 16 = 40 Inineries are possible
the qustion asks how many travel itineries can he make if he wants to visit at least 2 cities
it means differant itineries for visiting 2 cities + differant itineries for visiting 3 cities
for 2 cities (since all cities are connected to one another)
A-B-C "A to B to C"
A-C-D
A-D-B
A-B-C
Like starting with A we have 4 itineries same for B,C and D
4+4+4+4 = 16
Smae as for 3 cities
fix A in first position, rest B,C and D can be rearranges in 6 ways
same as for B,C, and D
6+6+6+6 = 24
24 + 16 = 40 Inineries are possible