59
 
 Combinatorial analysis or combinatorics
 Permutations

  Given a set of n different elements or objects. Any distinct ordered arrangement of the n elements is called permutation. The total number of permutations for n elements is
P(n) = n!.

 Example:  Given is the sequence of four digits 1, 2, 3, 4. Write all possible ordered arrangements or permutations of the 4 digits.

 Solution:  The number of permutations of the given 4 digits,  P(4) = 4! = 4 · 3 · 2 · 1 = 24.
The permutations are,    1, 2, 3, 4         2, 1, 3, 4         3, 1, 2, 4         4, 1, 2, 3
                                    1, 2, 4, 3         2, 1, 4, 3         3, 1, 4, 2         4, 1, 3, 2
                                    1, 3, 2, 4         2, 3, 1, 4         3, 2, 1, 4         4, 2, 1, 3
                                    1, 3, 4, 2         2, 3, 4, 1         3, 2, 4, 1         4, 2, 3, 1
                                    1, 4, 2, 3         2, 4, 1, 3         3, 4, 1, 2         4, 3, 1, 2
                                    1, 4, 3, 2         2, 4, 3, 1         3, 4, 2, 1         4, 3, 2, 1.
 Permutations of n objects some of which are the same

The number of permutations of n elements some groups of which are the same

where, k1, k2, ... , km denotes each group with identical elements.

 Example:  How many different 7-letter words can be formed from the word GREETER?

 Solution:  
since the letter R repeats twice and E repeats 3 times.
 Combinations

Given a set of n different elements or objects. Select a subset of r elements out of n. Such selection is called the combination.

A combination is an unordered arrangement of r objects selected from n different objects taken r at a time. The number of distinct combinations selecting r elements out of n is

Therefore, combinations must differ from each other at least in one element.

 Example:  Find the number of combinations of size 3 that can be made from digits 1, 2, 3, 4, 5 and write them out.

 Solution:  Since, n = 5 and r = 3 then
The combinations are,    1 2 3         2 3 4         3 4 5.
                                    1 2 4         2 3 5
                                    1 2 5         2 4 5
                                    1 3 4
                                    1 3 5
                                    1 4 5
 Combinations with repetition

The number of ways to choose r objects from a set of n different objects, so that an object can be chosen more than once
Remember that combinations must differ from each other at least in one element.
 Example:  Find the number of combinations of size 3 that can be made from digits 1, 2, 3, 4 if repetition is allowed, and write them out.
 Solution:  Since, n = 4 and r = 3 then
The combinations are,     1 1 1          2 2 2          3 3 3          4 4 4          1 2 3
                                     1 1 2          2 2 1          3 3 1          4 4 1          1 2 4
                                     1 1 3          2 2 3          3 3 2          4 4 2          1 3 4
                                     1 1 4          2 2 4          3 3 4          4 4 3          2 3 4
 Variations or permuted combinations (permutations without repetition)

The variations of size r chosen from a set of n different objects are the permutations of combinations of r.

The number of variations of size r chosen from n objects equals the number of combinations of size r multiplied by the r! permutations,

 Example:  Find the number of variations of size 3 that can be made from digits 1, 2, 3, 4 and write them out.

 Solution:  Since, n = 4 and r = 3 then

Notice that there are 4 combinations of size 3 chosen from the given 4 digits, each of which gives six permutations as is shown below.
The variations are,          1 2 3           1 2 4           1 3 4           2 3 4
                                    1 3 2           1 4 2           1 4 3           2 4 3
                                    2 1 3           2 1 4           3 1 4           3 2 4
                                    2 3 1           2 4 1           3 4 1           3 4 2
                                    3 1 2           4 1 2           4 1 3           4 2 3
                                    3 2 1           4 2 1           4 3 1           4 3 2.
 Variations with repetition (or permuted combinations with repetition)

The number of ways to choose r objects from a set of n different objects when order is important and one object can be chosen more than once
V (n, r) = n r.

 Example:  Find the number of variations with repetition of size 8 that can be made from the binary digits  0, 1.

  Solution:  Since, n = 2 and r = 8 then the total number of the variations with repetition is
V(n, r) = nr      =>        V(2, 8) = 28 = 256.
First we should select the combinations of size 8 that can be made from the 2 binary digits, then examine the number of ways each combination can be rearranged or permuted to prove the total number of variations. So, the number of the combinations is
The 9 combinations are,
1)
0 0 0 0 0 0 0 0
this combination can not be rearranged or permuted
2)
1 1 1 1 1 1 1 1
this combination can not be rearranged or permuted
3)
0 0 0 0 0 0 0 1
4)
0 0 0 0 0 0 1 1
5)
0 0 0 0 0 1 1 1
6)
0 0 0 0 1 1 1 1
7)
0 0 0 1 1 1 1 1
8)
0 0 1 1 1 1 1 1
9)
0 1 1 1 1 1 1 1
Therefore, the total number of the variations of size 8 with repetition chosen from the given 2 digits are,
V(2, 8) = 2 + 2 ´ 8 + 2 ´ 28 + 2 ´ 56 + 70 = 2 · (1 + 8 + 28 + 56 + 35) = 2 · 128 = 2 · 27 = 28
V(2, 8) = 28 = 256.
Both numerical and non numerical data can be processed by the computer as all letters digits and special characters are coded (represented as a unique sequence of binary digits 0 and 1) using binary variations.
 
 
 
 
 
 
 
Contents F
 
 
 
 
Copyright © 2004 - 2020, Nabla Ltd.  All rights reserved.