You can find solved problems about counting using this link.
Example : From a class of 20 students you must choose 5 students in a particular order.
Such a choice is called 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-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).
Example 2
From box with 7 different cakes you must choose three cakes.The first choice is a cake for your brother.
The second is for your sister, the third is for yourself. You have made a variation of 7 elements choose 3.
There are V(7,3)=7.6.5 possibilities to make the choice.
Example: Take a class of 20 students. Place the students in a row.Such a choice is called a permutation of 20 elements. Forming such a row is actually a special variation. It is the variation of 20 elements choose 20.
How many possibilities of forming such 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! .
Example:
Order 5 different marbles in a row. There are 5! = 120 different possibilities.
Example
Take a class of 20 students. Choose a group of 3 students to do a job. We see that the order of selected elements is not important. Such a choice is called a combination of 20 elements choose 3. The number of possibilities is C(20,3). We can make 3!=6 variations with just one such combination. So, there are six times more variations than combinations. We found: C(20,3). 3! = V(20,3).
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)!
p n
C or as ( )
n p
(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.
(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
= 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.
Example
In a bakery, one can choose between three types of cakes.We will buy 7 cakes. Obviously, some cakes will belong to the same type. Each possibility is called a variations with repetition of 3 elements choose 7. One can choose each cake in 3 different ways. In total we have 37 possibilities.
In general
One can choose each element in n different ways. The total number of variations with repetition of n elements choose p is (np ). We write
V'(n,p) = np
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 a elements of the first kind, b elements of the second kind and c elements of the third kind.
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 a other number of species.
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.
Generalizing you can prove that C'(n,p) = C(n+p-1,p)
Example:
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.
Take 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).