Lesson BASICS - Permutations & Combinations

Source code of 'BASICS - Permutations & Combinations'

This Lesson (BASICS - Permutations & Combinations) was created by by longjonsilver(2297)

: View Source, Show
About longjonsilver: I have a new job in September, teaching

Introduction
This topic is one of the worst to teach for me. This is because i can sometimes miss some of the intricacies of the English if i am not concentrating 100%. I am used to "classic" maths questions that i can apply algebraic rules to directly, and follow a recipe-like approach to my maths.

Permutations and Combinations are not that straight forward, since the question is formed in English, which needs to be first understood and then be formulated into maths. From that point, i would be fine.

Right, then. Here goes...

PERMUTATIONS
A permutation is "a re-arrangement of elements of a set".

So, what does this mean? It means a permutation is ONLY interested in re-arranging the elements of the set... Any duplications of the collected elements in different orders is fine.

A permutation therefore tends to be a large number.

Example:
Taking the 4 letters, ABCD, write down all the permutations of 3 of these leters:

ABC BAC CAB DAB
ACB BCA CBA DBA
ABD BAD CAD DAC
ADB BDA CDA DCA
ACD BCD CBD DBC
ADC BDC CDB DCB

--> there are 24 permutations. In other words, just taking each letter and collecting them into sets of 3 from the 4 and writing them out, gives 24 variations. Done.

Here, if you like, the order matters, since ABC is different to ACB and different to BCA and different to CAB etc. Permutations see these as all different answers.

COMBINATIONS
A combination is "one or more elements selected from a set without regard to the order"

The "without regard" means that the collection matters rather than order in combinations, so in the above example, the fact we ABC, ACB, BAC, BCA, CAB, CBA... for combinations, these are all 1 combination of letters A, B and C.

So, questions concerning picking a team of 5 people from a squad of 11... you would need combinations, since it is having "Bert, Ernie, Fred, Bill and Bob" that matters, not the fact that you have so many different permutations of these 5 people.

Example:
Taking the 4 letters, ABCD, write down all the combinations of 3 of these leters:

ABC ABD ACD BCD

--> there are just 4 combinations. You cannot pick any other 3 letters from ABCD, that is not part of the above 4 combinations. It is enlightening to see the letter missing in each: in order we have "no D", "no C", "no B" and finally "no A"... this sometimes helps you to "see" all the possible answers.

To calculate combinations, it is a 2-stage process:

1. you calculate all the equivalent permutations first.
2. you then correct this list by cutting out any duplicates.

As you can see from this, combinations are a subset of Permutations.

Mathematics of Permutations
To find the number of permutations of r elements from a set of n, the formula is:

{{{P(n,r) = (n!)/(n-r)!}}}

So, the above example would be {{{P(4,3) = (4!)/(4-3)!}}}
{{{P(4,3) = (4!)/1!}}}
{{{P(4,3) = (4*3*2*1)/1}}}
{{{P(4,3) = 24}}}

Mathematics of Permutations
To find the number of combinations of k elements from a set of n, the formula is:

{{{C(n,k) = (n!)/(k!(n-k)!)}}}

So, the above example would be {{{C(4,3) = (4!)/(3!(4-3)!)}}}
{{{C(4,3) = (4!)/(3!(1)!)}}}
{{{C(4,3) = (4*3*2*1)/(3*2*1*1)}}}
{{{C(4,3) = 4}}}

EXAMPLE:
Q: From a squad of 16 members, find the total number of different arrangements of 9 players.

A: Now, the question, as usual has no mention of "permutation" or "combination", so we have to figure it out. Having read the above explanations now, hopefully you will appreciate that the question is one about combinations.

It is asking "find the number of combinations of 9 players from a squad of 16.

solution is: {{{C(16,9) = (16!)/(9!(16-9)!)}}}

{{{C(16,9) = (16!)/(9!7!)}}}

use a calculator or work it out long handed:
{{{C(16,9) = (16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1)/(9*8*7*6*5*4*3*2*1*7*6*5*4*3*2*1)}}}

with cancelling, we have {{{C(16,9) = (16*15*14*13*12*11*10)/(7*6*5*4*3*2*1)}}}

with further cancelling, we have {{{C(16,9) = (16*15*14*13*12*11)/(7*6*4*3)}}}
{{{C(16,9) = (16*15*14*13*11)/(7*6)}}}
{{{C(16,9) = (16*15*2*13*11)/(6)}}}
{{{C(16,9) = (16*15*13*11)/(3)}}}
{{{C(16,9) = (16*5*13*11)}}}
which gives C(16,9) = 11440.

Further intricacies to consider
There are the added complications of having doubled elements:

EXAMPLE:
Q. How many different 4 letter "words" can you make from the word DAFFODIL?

A: The number of permutations is P(8,4) since permutations do not distinguish between DAFF and DAFF, for example: If I had written DAFfOdIL instead, you can now see the differences as DAFf and DAfF.

The question is one of permutations and not combinations, since in this example, we are definitely interested in DAFF, ADFF, FFAD, FADF etc being different "words" rather than duplicate versions of the same "combination" of 4 letters.

So, the total number of permutations is 1680. However, 1680 is not the correct answer, since we have 2 D's and 2 F's.

The correct answer is 1680/(2.2) --> 420.