Counting and Probability




Counting without repetition

Number of elements in a set

If a finite set S contains n elements, then we write #S = n.

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

Variations

Take a set S of n different elements. Choose p elements in a specific order.
Each such choice is called a variation of n elements choose p.

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.

Permutations

Take a set S of n different elements. Choose the n elements in a specific order.
Each such choice is called a permutation of the n elements.

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.

Combinations

Take a set S of n different elements. Choose, in S, a subset of p elements.
Such a choice is called a combination of n elements choose p.
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      etc


From 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

Properties of combinations

With the last formula it is easy to prove that
a) C(n,p) = C(n,n-p)
b) C(n,p) = C(n-1,p) + C(n-1,p-1) (Pascal's formula)

Binomial coefficient

The number C(n,p) is also called a binomial coefficient and this also is written as
 
        n
      (   )
        p

Binomial theorem

We'll prove that
 

(a + b)n = an  + C(n,1)an-1 b + C(n,2)an-2 b2  + C(n,3)an-3 b3  +  ...


            +   C(n,n) bn
To prove this theorem we use mathematical induction.
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)k+1   = (a + b).(a + b)k


=(a+b).(ak  + C(k,1)ak-1 b  + C(k,2)ak-2 b2  + C(k,3)ak-3 b3  + ... C(k,k)bk )


= ak+1 + C(k,1)ak b  + C(k,2)ak-1 b2  + C(k,3)ak-2 b3  + ... C(k,k)a bk  +

    ak b + C(k,1)ak-1 b2  + C(k,2)ak-2 b3  + ...+ C(k,k-1)a bk + C(k,k) bk+1

Since C(k,k)= C(k+1,k+1)= 1 and appealing on Pascal's formula
C(n,p) = C(n-1,p) + C(n-1,p-1) , we find
 
= ak+1   + C(k+1,1)ak b  + C(k+1,2)ak-1 b2  + C(k+1,3)ak-2 b3  +  ...

            +   C(k+1,k+1) bk+1
This proves the theorem.

Newton's Binomium ; examples

The form (a+b)n

 

(2x + 4)3 = (2x)3 + C(3,1)(2x)2.4 + C(3,2)(2x).42 + 43

           = 8x3 + 48x2 + 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

           = 81x4 - 432 y x3 + 864 x2 y2 - 768 x y3 + 256 y4

(x3 - 1/(2x))5

             = (x3)5 - C(5,1)(x3)4 (1/(2x)) + C(5,2)(x3)3 (1/(2x))2 - C(5,3)(x3)2 (1/(2x))3
                 + C(5,4)(x3)(1/2x)4 - (1/(2x))5

             = x15 - 2.5 x11 + 2.5 x7 -1.25 x3 + 0.3125 x-1 - 0.03125 x-5

Calculation of separate terms

Find the term in x2 in the expansion of (2x + 1)4
 
   The first term contains x4

   The second term contains x3

   The third term contains x2   We calculate the third term.

   C(4,2) (2x)2.12 = . . . = 24x2
Find the term without x in the expansion of (x - 2/x)4
 
   The first term contains x4.

   The second term contains x3. 1/x =  x2

   The third term contains x2.( 1/x)2 = x0.  We calculate the third term.

   C(4,2) x2 (-2/x)2 = 24
Find the term in x4 in the expansion of (x2 + 1/(3x)5
 
  The first term contains (x2)5 = x10

  The second term contains (x2)4.(1/x) = x7

  The third term contains  (x2)3.(1/x)2 = x4.   We calculate the third term.

  C(5,2) (x2)3 (1/3x)2 =  C(5,2) (1/9) x4 = (10/9) x4

Counting with repetition

Variations with repetition

Take a set S of n different elements. Point p times to an elements of S.
It is permitted to indicate the same element several times! The row of the indicated elements is called a variation with repetition of n elements choose p.

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 34 different variations with repetition of 3 elements choose 4
In general

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 np different variations with repetition of n elements choose p. We write this number as

 
                V'(n,p) = np
Example 2

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 43 = 64 possible outcomes

 
     448
     174
     117
     711
     888
     ...
     etc

Permutations with repetition

Example :
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.

 
        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!

Combinations with repetition

Take a row of n different and ordered elements.
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 combination with repetition of n elements choose p.
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  < 11
The 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).

Solved Problems

 
You can find solved problems about counting using this link.
 

Introduction to probability

Here are links to probability books (pdf) and probability subjects






Topics and Problems

MATH-abundance home page - tutorial

MATH-tutorial Index

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