You can find solved problems about counting using this link.
Example:
D = the set of the diagonals of a regular pentagon. #D = 5.
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.
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.
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.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
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.
(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
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 = . . . = 24x2Find 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 = 24Find 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
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
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!
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.
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. |
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).