Permutations,combinations & probabability

[jangok]

Arranging Objects

The number of ways of arranging n unlike objects in a line is n! (pronounced ‘n factorial’). n! = n × (n – 1) × (n – 2) ×…× 3 × 2 × 1

Example
How many different ways can the letters P, Q, R, S be arranged?
The answer is 4! = 24.

This is because there are four spaces to be filled: _, _, _, _
The first space can be filled by any one of the four letters. The second space can be filled by any of the remaining 3 letters. The third space can be filled by any of the 2 remaining letters and the final space must be filled by the one remaining letter. The total number of possible arrangements is therefore 4 × 3 × 2 × 1 = 4!
The number of ways of arranging n objects, of which p of one type are alike, q of a second type are alike, r of a third type are alike, etc is:
n!/(p! q! r!) …

Example

In how many ways can the letters in the word: STATISTICS be arranged?
There are 3 S’s, 2 I’s and 3 T’s in this word, therefore, the number of ways of arranging the letters are:
10! = 50 400
3! 2! 3!
<font face="Tahoma"></font id="Tahoma">

Rings and Roundabouts

The number of ways of arranging n unlike objects in a ring when clockwise and anticlockwise arrangements are different is (n – 1)!
When clockwise and anti-clockwise arrangements are the same, the number of ways is ½ (n – 1)!

Example

Ten people go to a party. How many different ways can they be seated?
Anti-clockwise and clockwise arrangements are the same. Therefore, the total number of ways is ½ (10-1)! = 181 440
Combinations
The number of ways of selecting r objects from n unlike objects is:
nCr = n!/r! (n – r)!

Example

There are 10 balls in a bag numbered from 1 to 10. Three balls are selected at random. How many different ways are there of selecting the three balls?
10C3 = 10! = 10 × 9 × 8 = 120
3! (10 – 3)! 3 × 2 × 1


Permutations

A permutation is an ordered arrangement.
The number of ordered arrangements of r objects taken from n unlike objects is:
nPr = n!/(n – r)!

Example

In the Match of the Day’s goal of the month competition, you had to pick the top 3 goals out of 10. Since the order is important, it is the permutation formula which we use.
10P3 = 10!/7! = 720

There are therefore 720 different ways of picking the top three goals.


Probability

The above facts can be used to help solve problems in probability.

Example

In the National Lottery, 6 numbers are chosen from 49. You win if the 6 balls you pick match the six balls selected by the machine. What is the probability of winning the National Lottery?
The number of ways of choosing 6 numbers from 49 is 49C6 = 13 983 816 .
Therefore the probability of winning the lottery is 1/13983816 = 0.000 000 071 5 (3sf), which is about a 1 in 14 million chance

The probability of an event occurring is the chance or likelihood of it occurring. The probability of an event A, written P(A), can be between zero and one, with P(A) = 1 indicating that the event will certainly happen and with P(A) = 0 indicating that event A will certainly not happen.

Probability = the number of successful outcomes of an experiment
the number of possible outcomes
So, for example, if a coin were tossed, the probability of obtaining a head = ½, since there are 2 possible outcomes (heads or tails) and 1 of these is the ‘successful’ outcome.


Using Set Notation

Probability can be studied in conjunction with set theory, with Venn Diagrams being particularly useful in analysis.
The probability of a certain event occurring, for example, can be represented by P(A). The probability of a different event occurring can be written P(B). Clearly, therefore, for two events A and B,
P(A) + P(B) - P(AnB) = P(AuB)
P(AnB) represents the probability of A AND B occurring. P(AuB) represents the probability of A OR B occurring.


Mutual Exclusive Events

Events A and B are mutually exclusive if they have no events in common. In other words, if A occurs B cannot occur and vice-versa. On a Venn Diagram, this would mean that the circles representing events A and B would not overlap.

If, for example, we are asked to pick a card from a pack of 52, the probability that the card is red is ½ . The probability that the card is a club is ¼. However, if the card is red it can't be a club. These events are therefore mutually exclusive.
If two events are mutually exclusive, P(AnB) = 0, so
P(A) + P(B) = P(AuB)


Independent Events

Two events are independent if the first one does not influence the second. For example, if a bag contains 2 blue balls and 2 red balls and two balls are selected randomly, the events are:
a) independent if the first ball is replaced after being selected
b) not independent if the first ball is removed without being replaced. In this instance, there are only three balls remaining in the bag so the probabilities of selecting the various colours have changed.
Two events are independent if (and only if):
P(AnB) = P(A)P(B)
This is known as the multiplication law.


Conditional Probability

Conditional probability is the probability of an event occurring, given that another event has occurred. For example, the probability of John doing mathematics at A-Level, given that he is doing physics may be quite high. P(A|B) means the probability of A occurring, given that B has occurred. For two events A and B,
P(AnB) = P(A|B)P(B)
and similarly P(AnB) = P(B|A)P(A).
If two events are mutually exclusive, then P(A|B) = 0 .

Example

A six-sided die is thrown. What is the probability that the number thrown is prime, given that it is odd.
The probability of obtaining an odd number is 3/6 = ½. Of these odd numbers, 2 of them are prime (3 and 5).
P(prime | odd) = P(prime and odd) = 2/6 = 2/3
P(odd) 3/6

[wood]

Erin, many people in this forum already asked me to provide good probability, combination links and I believe this old post by jangok is pretty concise and enough for the GRE.

Therefore, I think it would be a good idea to stick this topic out, since it is one of the most demanding topics in the GRE, and many people suffer from having a base from where to start.

[feynman]

Note on Circular permutations
-----------------------------
Many Earthlings find circular permutations confusing. So I'm adding a note which will probably clear up things as to why circular permutation is usually (n-1)!.
Suppose you have to seat 10 people in a circle. Think of it this way. You first seat one person. Now we're left with 9 people for 9 places which is just like a linear permutation. This can be done in 9! ways. Extending this concept to n objects, we get circular permutation of n unlike objects = (n-1)!

[eagle]

Thanks Jangok!- my biggest math problem now has its answer at 1 place.

[ranjani]

wow,i always hated this probability,permu n combinations..but now life seems simpler..will get a print-out n study the mtrl..

[vknittala]

These are definetly helpful.

Thanks

[naidu_jyothi]

Originally posted by jangok

Arranging Objects

The number of ways of arranging n unlike objects in a line is n! (pronounced ‘n factorial’). n! = n × (n – 1) × (n – 2) ×…× 3 × 2 × 1

Example
How many different ways can the letters P, Q, R, S be arranged?
The answer is 4! = 24.

This is because there are four spaces to be filled: _, _, _, _
The first space can be filled by any one of the four letters. The second space can be filled by any of the remaining 3 letters. The third space can be filled by any of the 2 remaining letters and the final space must be filled by the one remaining letter. The total number of possible arrangements is therefore 4 × 3 × 2 × 1 = 4!
The number of ways of arranging n objects, of which p of one type are alike, q of a second type are alike, r of a third type are alike, etc is:
n!/(p! q! r!) …

Example

In how many ways can the letters in the word: STATISTICS be arranged?
There are 3 S’s, 2 I’s and 3 T’s in this word, therefore, the number of ways of arranging the letters are:
10! = 50 400
3! 2! 3!
<font face="Tahoma"></font id="Tahoma">

Rings and Roundabouts

The number of ways of arranging n unlike objects in a ring when clockwise and anticlockwise arrangements are different is (n – 1)!
When clockwise and anti-clockwise arrangements are the same, the number of ways is ½ (n – 1)!

Example

Ten people go to a party. How many different ways can they be seated?
Anti-clockwise and clockwise arrangements are the same. Therefore, the total number of ways is ½ (10-1)! = 181 440
Combinations
The number of ways of selecting r objects from n unlike objects is:
nCr = n!/r! (n – r)!

Example

There are 10 balls in a bag numbered from 1 to 10. Three balls are selected at random. How many different ways are there of selecting the three balls?
10C3 = 10! = 10 × 9 × 8 = 120
3! (10 – 3)! 3 × 2 × 1


Permutations

A permutation is an ordered arrangement.
The number of ordered arrangements of r objects taken from n unlike objects is:
nPr = n!/(n – r)!

Example

In the Match of the Day’s goal of the month competition, you had to pick the top 3 goals out of 10. Since the order is important, it is the permutation formula which we use.
10P3 = 10!/7! = 720

There are therefore 720 different ways of picking the top three goals.


Probability

The above facts can be used to help solve problems in probability.

Example

In the National Lottery, 6 numbers are chosen from 49. You win if the 6 balls you pick match the six balls selected by the machine. What is the probability of winning the National Lottery?
The number of ways of choosing 6 numbers from 49 is 49C6 = 13 983 816 .
Therefore the probability of winning the lottery is 1/13983816 = 0.000 000 071 5 (3sf), which is about a 1 in 14 million chance

The probability of an event occurring is the chance or likelihood of it occurring. The probability of an event A, written P(A), can be between zero and one, with P(A) = 1 indicating that the event will certainly happen and with P(A) = 0 indicating that event A will certainly not happen.

Probability = the number of successful outcomes of an experiment
the number of possible outcomes
So, for example, if a coin were tossed, the probability of obtaining a head = ½, since there are 2 possible outcomes (heads or tails) and 1 of these is the ‘successful’ outcome.


Using Set Notation

Probability can be studied in conjunction with set theory, with Venn Diagrams being particularly useful in analysis.
The probability of a certain event occurring, for example, can be represented by P(A). The probability of a different event occurring can be written P(B). Clearly, therefore, for two events A and B,
P(A) + P(B) - P(AnB) = P(AuB)
P(AnB) represents the probability of A AND B occurring. P(AuB) represents the probability of A OR B occurring.


Mutual Exclusive Events

Events A and B are mutually exclusive if they have no events in common. In other words, if A occurs B cannot occur and vice-versa. On a Venn Diagram, this would mean that the circles representing events A and B would not overlap.

If, for example, we are asked to pick a card from a pack of 52, the probability that the card is red is ½ . The probability that the card is a club is ¼. However, if the card is red it can't be a club. These events are therefore mutually exclusive.
If two events are mutually exclusive, P(AnB) = 0, so
P(A) + P(B) = P(AuB)


Independent Events

Two events are independent if the first one does not influence the second. For example, if a bag contains 2 blue balls and 2 red balls and two balls are selected randomly, the events are:
a) independent if the first ball is replaced after being selected
b) not independent if the first ball is removed without being replaced. In this instance, there are only three balls remaining in the bag so the probabilities of selecting the various colours have changed.
Two events are independent if (and only if):
P(AnB) = P(A)P(B)
This is known as the multiplication law.


Conditional Probability

Conditional probability is the probability of an event occurring, given that another event has occurred. For example, the probability of John doing mathematics at A-Level, given that he is doing physics may be quite high. P(A|B) means the probability of A occurring, given that B has occurred. For two events A and B,
P(AnB) = P(A|B)P(B)
and similarly P(AnB) = P(B|A)P(A).
If two events are mutually exclusive, then P(A|B) = 0 .

Example

A six-sided die is thrown. What is the probability that the number thrown is prime, given that it is odd.
The probability of obtaining an odd number is 3/6 = ½. Of these odd numbers, 2 of them are prime (3 and 5).
P(prime | odd) = P(prime and odd) = 2/6 = 2/3
P(odd) 3/6

[naidu_jyothi]

hi jankog,
Thankyou very much for detailed information regd probability.

In conditional probability the example you gave, is the answer is 1/6 or not??

anyone clarify my doubt

Thanks

[vknittala]

A six-sided die is thrown. What is the probability that the number thrown is prime, given that it is odd.
The probability of obtaining an odd number is 3/6 = ½. Of these odd numbers, 2 of them are prime (3 and 5).
P(prime | odd) = [P(prime and odd)/P(odd)] = (2/6)/(3/6) = 2/3

or take this way :
number of prime numbers = 2, 3, 5
odd prime numbers = 3, 5
now P(odd|prime) = 2/3

Thanks

[ursula]

Originally posted by gmatfordays

OK -- after reviewing this, I see that this is a mistake. people are unlike objects, yes.. But each is distinguishable from the other. Therefore, anticlockwise and clockwise arrangements are different not the same as jangok suggests. So it should be 9! instead of 1/2 (9)!.

Am I correct here?

I think the clockwise/counterclockwise distinction argument is related to which object (or person) ends up being adjacent to which other object (or person).
For example, let's say you seat Adam, Bob, Chuck, Dave, and Ed around a circular table, clockwise in alphabetical order. If you seated them counterclockwise instead, you would still end up with Bob between Adam and Chuck etc., so the two arrangements are mirror-images of each other. They could be considered functionally equivalent - you'd still get the same dinner table conversation [|)]
On an actual GMAT question, I would expect the question to tell you whether clockwise and counterclockwise arrangements should be considered equivalent. If unspecified, I would probably use the interpretation above.