COMBINATORIAL ALGEBRA; COUNTING TECHNIQUES
 

Objectives:
To learn how to count objects from a certain given set. For example:
* How many ways are there for four people to sit at a round table;
* How many 3-digit numbers can be formed using only 1,2,3 and 4;
* How may ways are there for 30 students to be seated in a classroom?
 

Recall 1:  A permutation is an arrangement of a group of objects in a particular order.
For example, the three numbers 1,2 and 3 can be arranged in six different ways:
123  132
213  231
312  321.
Each of these arrangements is a different permutation.To determine the total number of permutations that can be made from three digits using each one only once we can indicate a position (first, second, third) for each digit. Any of the three digits may be placed in the first position.. Any one of the two remaining may occupy the second place. There is only one choice left for the third space. The product of the number for each space is the total number of permutations that can be made. In this case, the answer is 3*2*1=3!=6.

1.1 The total number of permutations of a set that can be formed from n objects using all of them without repetition is n! .
"n!" is read as "n factorial".

1.2 If n>0, n!=1*2*…*n.

1.3 n!=n*(n-1)!

1.4 0!=1     1!=1

Example 1 How many different ways are there that five books can be arranged on a shelf? The answer is the number of permutations that can be formed from 5 books, which is 5!=1*2*3*4*5=120.

Recall 2:  For counting the number of ordered subsets of k elements taken from a set of n elements we use arrangements (or permutations of n elements taken k).

2.1   A(n,k)=n(n-1)...(n-k+1)
2.2   A(n,k)= n!/(n-k)! for any n and k natural numbers, with k<=n .

Example 2. Using only the digits 1,2,3, and 4 one can form the following two digit numbers with no repetition allowed:
12 21 31 41
13 23 32 42
14 24 34 43
So, the number of ways one can arrange a 4 elements set, namely {1,2,3,4} into subsets of two elements is  .4x3=12

Example 3 Using only the digits 1,2,3, and 4 and with no repetition allowed one can form the following three digit numbers:
 123 213 312 412
 124 214 314 413
 132 231 321 421
 134 234 324 423
 142 241 341 431
 143 243 342 432

So the number of three elements subsets of the four elements set ({1,2,3,4} is  4x3x2=24.

Recall 3:  A combination is a group of objects in which the order of the objects is disregarded.

Example 4  From the numbers 1,2 and 3, six different permutations can be formed. They are 123, 132, 231, 213, 312, 321. When the order of the digits is not considered, all six permutations make up one combination. The number of combinations of three objects, taken three at a time is one.

3.1  In general, the number of combinations of n objects taken k at a time is denoted by C(n,k). 

3.2   C(n,k) is given by 

3.3  Two combinations of n elements, taken k at a time, differ by the nature of their elements and not by their order. Hence, the order of elements in sets is not important.

Example 5. The number of ways that 40 students can sit in pairs is  C(40,2)= ways.

3.4 The number of combinations of n things taken r at a time, is equal to the number of combinations of n things, taken n-r at a time, that is,C(n,r)=C(n,n-r).

For example, C(40, 2)=C(40, 38)=40!/[2!*38!]=780

3.5  Pascal's formula : C(n,k)=C(n-1,k)+C(n-1,k-1).

3.6  The numbers C(n,k)  are called binomial coefficients. A two-term expression is called a binomial and an expansion for an expression such as (a+b)^n is called a binomial expansion.

3.7 Pascal’s triangle gives a way to compute the numbers C(n,k) . The method consists in a certain disposal of those numbers and a recursive application of Pascal's formula.

3.8  We construct the Pascal Triangle as follows. We tabulate the coefficients of (a+b)^n for n=0, 1, 2, 3, 4, …..in a triangular array:
 

n                        Coefficients of (a + b)^n

0                                   1

1                                 1   1

2                               1   2   1

3                             1   3   3   1

4                           1   4   6   4   1

5                         1  5  10   10   5   1

...                        .  .   .   .   .   .

One may observe that the array is bordered with 1's and that each number inside the border is the sum of the two closest numbers on the previous line. This observation simplifies the generation of additional lines of the array. For example, the coefficients for n = 5 are 1, 1 + 4 = 5, 4 + 6 = 10, 6 + 4 = 10, 4 + 1 = 5, and 1.
Note that  C(n,k) denotes the coefficient of a^(n-k)*b^k or of a^k*b^(n-k).
The number n in  C(n,k) is the row number and k+1 is the place number on that row, if the convention of labeling the rows and places is from 0, 1, 2, ….
For example,  C(3,1) is the number in second place in the third row, i.e. 3.

3.9.    Newton’s Binomial Theorem. Let n be a positive integer. Then for all x and y,

where the sum is taken from k=0 to k=n and  is another notation for the binomial coeficient.

Example 6 Expand  (2x+3y)^3.

Solution: The expansion (a+b)^3=a^3 +3a^2b + 3ab^2 + b^3  is an identity which remains true when one substitutes a=2x and b=3y and thus obtains

 (2x+3y)^3 = (2x)^3 + 3(2x)^2(3y) + 3(2x)(3y)^2 + (3y)^3
                 = 8x^3 +18x^2y+54xy^2+27y^3

Example 7 Show that  .

Using the fact that C(4,0)=C(5,0) and Pascal’s formula we see that

EXERCISES