Example:

D = the set of the diagonals of a regular pentagon. #D = 5.

Each such choice is called

Example : From a class of 20 students you choose 5 students in a particular order.
Such a choice is a variation of 20 elements choose 5.

There are 20 possibilities to choose the first student.
For the choice of the second student there are only 19 possibilities. And so on.

In general:

How many variations are there?

Well, there are n possibilities to choose the first element.

There are n-1 possibilities to choose the second element.

There are n-2 possibilities to choose the third element.

...

There are n-(p-1) possibilities to choose the p-th element.

So, the number of all variations of n elements choose p is n.(n-1).(n-2). ... .(n-p+1).

We write this number as V(n,p)

Example 2

From a box with 7 different cakes you have to choose three cakes.

The first choice is a cake for your brother.
The second is for your sister; the third is for yourself.

Mind that you have to choose the cakes in a specific order.
You have to make one variation of 7 elements choose 3.
There are V(7,3)=7.6.5=210 possibilities to make that choice.

Each such choice is called

Example: Take a class of 20 students. Put the 20 students in a row.
This can be done in many different ways.
Each choice is a permutation of the 20 elements.
Forming such a row is actually a special variation.
It's the variation of 20 elements choose 20.

In general:

A permutation of n different elements is a variation of n elements choose n.

So, the total number of permutations of n elements = V(n,n) = n.(n-1).(n-2). ... .2.1 .

We write this number as P(n) = n.(n-1).(n-2). ... .2.1 = n! .

Example:

Arrange 5 different marbles in one row. There are P(5) = 5! = 120 different possibilities.

Such a choice is called a

The order of the elements in that subset has no importance at all. Choosing a subset of p elements in S can be done in many different ways. We write this number of choices as C(n,p).

Example

From a team of 5 racers, A,B,C,D,E, we choose 3 racers. The order of the selected racers has no importance. Such a choice is a combination of 5 elements choose 3. The number of such choices is C(5,3).

To construct a formula for C(5,3), we shall compare variations with combinations. We make two columns. In the first column we write all the variations of the 5 racers choose 3. In the second column we write the corresponding combinations.

variations combinations ABC ABC ACB BAC BCA CAB CBA ABD ABD ADB BDA BAD DAB DBA ... ... etc etcFrom this table it is obvious that each combination corresponds with 6 variations. So, there are six times more variations than combinations.

We have V(5,3) = C(5,3). 3!

In general:

We have V(n,p) = C(n,p) . p!

Or, C(n,p) = V(n,p) / p!

Since V(n,p) = n.(n-1).(n-2). ... .(n-p+1) , we have

n.(n-1).(n-2). ... .(n-p+1) C(n,p) = --------------------------- p! n.(n-1).(n-2). ... .(n-p+1).(n-p). ... .1 <=> C(n,p) = --------------------------------------------------- p! . (n-p). ... .1 n! <=> C(n,p) = ------------ p!.(n-p)!Example 2:

Out of a collection of twenty books, you take four books to read them at home.

We'll calculate the number of choices.

n = 20 ; p = 4

The order of the selected books has no importance.

The number of such choices is C(20,4) = 4845

a) C(n,p) = C(n,n-p)

b) C(n,p) = C(n-1,p) + C(n-1,p-1) (Pascal's formula)

n ( ) p

(a + b)To prove this theorem we use mathematical induction.^{n}= a^{n}+ C(n,1)a^{n-1}b + C(n,2)a^{n-2}b^{2}+ C(n,3)a^{n-3}b^{3}+ ... + C(n,n) b^{n}

It is easy to verify that the theorem holds for n = 2 .

Now, assume it holds for n = k. We'll show it holds for n= k+1.

(a + b)Since C(k,k)= C(k+1,k+1)= 1 and appealing on Pascal's formula^{k+1}= (a + b).(a + b)^{k}=(a+b).(a^{k}+ C(k,1)a^{k-1}b + C(k,2)a^{k-2}b^{2}+ C(k,3)a^{k-3}b^{3}+ ... C(k,k)b^{k}) = a^{k+1}+ C(k,1)a^{k}b + C(k,2)a^{k-1}b^{2}+ C(k,3)a^{k-2}b^{3}+ ... C(k,k)a b^{k}+ a^{k}b + C(k,1)a^{k-1}b^{2}+ C(k,2)a^{k-2}b^{3}+ ...+ C(k,k-1)a b^{k}+ C(k,k) b^{k+1}

C(n,p) = C(n-1,p) + C(n-1,p-1) , we find

= aThis proves the theorem.^{k+1}+ C(k+1,1)a^{k}b + C(k+1,2)a^{k-1}b^{2}+ C(k+1,3)a^{k-2}b^{3}+ ... + C(k+1,k+1) b^{k+1}

(2x + 4)^{3}= (2x)^{3}+ C(3,1)(2x)^{2}.4 + C(3,2)(2x).4^{2}+ 4^{3}= 8x^{3}+ 48x^{2}+ 96x + 64 (3x - 4y)^{4}= (3x)^{4}- C(4,1) (3x)^{3}(4y) + C(4,2)(3x)^{2}(4y)^{2}- C(4,3)(3x)(4y)^{3}+ (4y)^{4}= 81x^{4}- 432 y x^{3}+ 864 x^{2}y^{2}- 768 x y^{3}+ 256 y^{4}(x^{3}- 1/(2x))^{5}= (x^{3})^{5}- C(5,1)(x^{3})^{4}(1/(2x)) + C(5,2)(x^{3})^{3}(1/(2x))^{2}- C(5,3)(x^{3})^{2}(1/(2x))^{3}+ C(5,4)(x^{3})(1/2x)^{4}- (1/(2x))^{5}= x^{15}- 2.5 x^{11}+ 2.5 x^{7}-1.25 x^{3}+ 0.3125 x^{-1}- 0.03125 x^{-5}

The first term contains xFind the term without x in the expansion of (x - 2/x)^{4}The second term contains x^{3}The third term contains x^{2}We calculate the third term. C(4,2) (2x)^{2}.1^{2}= . . . = 24x^{2}

The first term contains xFind the term in x^{4}. The second term contains x^{3}. 1/x = x^{2}The third term contains x^{2}.( 1/x)^{2}= x^{0}. We calculate the third term. C(4,2) x^{2}(-2/x)^{2}= 24

The first term contains (x^{2})^{5}= x^{10}The second term contains (x^{2})^{4}.(1/x) = x^{7}The third term contains (x^{2})^{3}.(1/x)^{2}= x^{4}. We calculate the third term. C(5,2) (x^{2})^{3}(1/3x)^{2}= C(5,2) (1/9) x^{4}= (10/9) x^{4}

It is permitted to indicate the same element several times! The row of the indicated elements is called a

Example

S = { a,b,c } p = 4 The following rows are variations with repetition of 3 elements choose 4 a,c,a,a b,a,c,c c,a,a,b b,c,b,b b,b,b,b b,c,b,c . . . . etc To make such a variation, you have to choose 4 times. Each time you choose, there are 3 possibilities. So, there are 3In general^{4}different variations with repetition of 3 elements choose 4

Take a set S of n different elements.

Successively, we point p times to an element of S.

Each pointing can be done in n different ways.

So, there are n^{p} different variations with repetition of n elements choose p.
We write this number as

V'(n,p) = nExample 2^{p}

Think of a number of 3 digits made with the digits 1, 4, 7 and 8.

This number is a variation with repetition of 4 elements choose 3.
There are 4^{3} = 64 possible outcomes

448 174 117 711 888 ... etc

Take 3 red marbles, 2 blue marbles, and 5 yellow ones. Place this marbles in a specific order.

We call this a permutations with repetition of the 10 marbles.

Now, we'll calculate the number of such permutations.

- Take 10 numbered compartments.
- Place each of the three red marbles in a compartment.
- This gives C(10,3) possibilities.
- Place each of the two blue marbles in a remaining compartment.
- Now there are C(10-3,2) possibilities.
- At last, we place the 5 yellow marbles in the remaining places.

The total number of possibilities is C(10,3).C(10-3,2) 10! 7! = -------.------- 3!.7! 2!.5! 10! = -------------- 3! . 2! . 5!This method can easily be generalized. Take 'a' equal elements of a first type, 'b' equal elements of the second type and 'c' equal elements of the third type. The number of different ways to put all these elements in a row, is:

(a+b+c)! = -------------- a! . b! . c!Work in the same way for any other number of types.

Example 2:

Make a 4-digit number using an arrangement of the 4 digits 1,2,2,3 examples : 2231 ; 1232; 3122; .... The total number of possibilities is 4! -------- = 12 1!.2!.1!

Point to p elements from this row, one after another, and order the indicated elements in the same order as the given elements. It is permitted to indicate the same element several times! The equal elements are placed in succession The result is called a

We write the number of all possible combinations with repetition of n elements choose p as C'(n,p).

Example:

We'll create combinations with repetition of 5 elements choose 6

A = (a,b,c,d,e) and p = 6

Then (a, a, b, d, d, d) ; (b, b, b, c, d, e) ; (c, c, c, c, c, c)

are combinations with repetition of 5 elements choose 6.

We can represent unambiguously such combination by means
of a symbol with points and slashes. A slash means 'go to next element'.

(a,a,b,d,d,d) <=> .././/.../ (b,b,b,c,d,e) <=> /.../././. (c;c;c;c;c;c) <=> //......//Each symbol consists of 10 places with exactly 6 points and four slashes. With each combination there is just one symbol and with each symbol corresponds just one combination.

We can build a symbol putting exactly 6 points in 10 places.

Afterwards, the spare places are filled with slashes.

This can be done in C(10,6) ways.

So, C'(5,6) = C(5+6-1,6)

Generalizing, one can prove that C'(n,p) = C(n+p-1,p)

Example :

You have a box with red sweets, a box with yellow sweets and a box with black sweets. In how many ways can you choose 5 sweets?

The possible choices are combinations with repetition of three elements choose 5. The number of different choices is C'(3,5) = C(7,5) = 21.

Example 2:

Find the number of non negative integer solutions to the equation p+q+r < 11. |

Take the characters a,b,c and d. Point 10 times to one of these characters. Sort the result alphabetically. Now you have string of 10 characters. For example aabbbcdddd

With this string corresponds exactly one solution of p + q + r < 11.

Let p = the frequency of a, q = the frequency of b, r = the frequency of c in the string. In the string aabbbcdddd is p=2, q=3, r=1 and p + q + r <11.

Conversely, with each solution of p + q + r <11 corresponds exactly one string. For example with p=3, q=3 ,c=2 corresponds aaabbbccdd.

Examples:

aabbbcdddd <=> 2+3+1 < 11 bbbccccddd <=> 0+3+4 < 11 bbbbbbbbbb <=> 0+10+0 < 11 dddddddddd <=> 0+0+0 < 11 aaaabbbccc <=> 4+3+3 < 11The number of different strings that can be made is the number of combinations with repetition of 4 elements choose 10. This number is C'(4,10) = C(13,10) = C(13,3).

- Basic Probability Theory
- INTRODUCTION TO PROBABILITY
- Introduction to Probability
- Probability and distributions
- Links to Probability subjects

- Permutation and Combination
- Binomial Theorem
- Permutations and Combinations

The tutorial address is http://home.scarlet.be/math/

Copying Conditions

Send all suggestions, remarks and reports on errors to Johan.Claeys@ping.be The subject of the mail must contain the flemish word 'wiskunde' because other mails are filtered to Trash