Counting problems
If a finite set A contains n elements, then we write #A = n.
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).
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! .
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)!
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)
The number C(n,p) is called a binomial coefficient and this is written as
n
( )
p
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.
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
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.
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)
You can find solved problems about counting
here
Topics and Problems
MATH-abundance home page - tutorial
MATH-tutorial Index
The tutorial address is http://home.scarlet.be/~ping1339/
Copying Conditions
Send all suggestions and remarks to Johan.Claeys@ping.be