Themes > Science > Mathematics > Algebra > Foci of a conic section > Topics and Problems > Counting problems

..Counting without repetition
..Number of elements in a set
 ..Variations
 ..Permutations
 ..Combinations
..Properties of combinations
 ..Binomial coefficient
 ..Binomial theorem
..Counting with repetition
..Variations with repetition
 ..Permutations with repetition
 ..Combinations with repetition


Counting without repetition

Number of elements in a set

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

Variations

Take a set A of n different elements. Choose p elements in a specific order.
Each such choice is called a variation of n elements choose p. 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-p+1 possibilities to choose the last element.
So, the total number of variations is n.(n-1).(n-2). ... .(n-p+1).
We write V(n,p) = n.(n-1).(n-2). ... .(n-p+1).

Permutations

Take a set A of n different elements. Choose the n elements in a specific order.
Each such choice is called a permutation of n elements.
How many permutations are there?
From above we know that such permutation is a variation of n elements, taking all the elements in a specific order.
So, the total number of permutations = V(n,n) = n.(n-1).(n-2). ... .1 .
We write P(n) = n.(n-1).(n-2). ... .1 = n! .

Combinations

Take a set A of n different elements. Choose a subset of p elements.
Such choice is called a combination of n elements choose p.
We write the number of such combinations as C(n,p).
Each of the V(n,p) variations of n elements choose p, can be constructed as follows.
a) Take a subset ( a combination) of p elements from the n elements. This can be done in C(n,p) ways.
b) Take that subset and choose a particular order of the p elements.
This can be done in p! ways.
From this 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)!

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 called a binomial coefficient and this 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.

Counting with repetition

Variations with repetition

Take a set A of n different elements. Point p elements in a specific order.
Each such choice is called a variation with repetition of n elements choose p. Well, there are n possibilities to point each element. 
 

The total number of variations with repetition of n elements choose p is (np ).
We write

                V'(n,p) = np

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 marbles. Now, we'll calculate the number of such permutations.
Take 10 numbered compartments. First place the three red marbles in a compartment. This gives C(10,3) possibilities. Then place the 2 blue marbles. Now there are C(10-3,2) possibilities. At last, we place the 5 yellow marbles. Now there are C(10-3-2,5) possibilities. 
 
        The total number of possibilities are

        C(10,3).C(10-3,2).C(10-3-2,5)

            10!      7!      5!
        = -------.-------. ------
          3!.7!    2!.5!    5!.0!

               10!
        = --------------
           3! . 2! . 5!
This method can easily be generalized.

Combinations with repetition

Take n different and ordered elements.
Point p elements one after another and order these elements in the same order as the given elements.
The result is called a combination with repetition of n elements choose p.
We write the number of all combinations with repetition of n elements choose p as C'(n,p).

Example: 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 such combination by means of a symbol with points and slashes. 

 
(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 such combination there is just one symbol and with each symbol corresponds just one such 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 you can prove that C'(n,p) = C(n+p-1,p)


Information Provided by Johan.Claeys@ping.be