CountBio

In the previous section, we defined the probability of event to be the ratio of the number of favourable outcomes to the total number of possible outcomes of the experiment. In this section, we will learn the methods of counting the possible outcomes of an experiment under various conditions.

The multiplication principle

Suppose we have an experiment \(\small{ E_1 }\) with \(\small{n_1}\) possible outcomes, and another experiment \( \small{E_2}\) with \( \small{n_2}\) possible outcomes.

We define a composite experiment \(\small{E_1 E_2} \) as "performing \(\small{ E_1} \) first followed by \( \small{E_2}\) and noting down the results". Thus, if \(\small{ E_1 }\) and \(\small{ E_2 }\) are single coin tosses, then toss coin 1 followed by coin 2 and note down the composite result, like \(\small{ \{HT\}}\)or \(\small{\{TT\} }\).

The miltiplication principle states that if the experiment \(\small{ E_1 }\) has \(\small{n_1}\) possible outcomes and experiment \(\small{ E_2 }\) has \( \small{n_2}\) possible outcomes, then the composite experiment \( \small{E_1 E_2 }\) has \( \small{n_1 n_2}\) possible outcomes.

Thus the composite experiment of a two coin toss, in which each experiment has two outcomes of H and T, will have \(\small{ 2 \times 2 = 4 }\) possible outcomes namely \( \small{\{HH, HT, TH, TT \} } \)

Permutation of n objects

Given three objects labelled \(\small{ A_1} \), \(\small{ A_2 }\) and \(\small{ A_3 }\), in how many ways we can arrange them next to each other?.
After considering various possible shuffles, we come up with the following six arrangements:

        \(\small{A_1 A_2 A_3 }\), \( \small{A_1 A_3 A_2} \), \( \small{A_2 A_1 A_3 }\), \( \small{A_2 A_3 A_1} \), \( \small{A_3 A_1 A_2} \), \( \small{A_3 A_2 A_1 }\)

In order to calculate the number of ways in which n objects can be arranged, we proceed as follows:

For first position, an object can be chosen in n ways.
For the second position, we can select an obeject in (n-1) ways.
For the third position, we have (n-2) choices and so on.

The composite experiment consists of choosing object for all positions.

Therefore, by multiplication principle, we write,

The number of ways of arranging n objects among themselves is called the permutation of n objects . We remember,

Permutation of n objects taken r at a time

Sometimes we have to pick up a subset of r objects out of n objects. How many ways this can be done?

In this case, we have to fill r positions by picking from n objects.

The first position can be filled in n ways.
Once the first position is filled, the second can be filled up in (n-1) ways.
Once the secon is filled, the third position has (n-2) choices.
When this is continued, finally the \(\small{r^{th}}\) position has (n-r+1) choices.

Therefore,

Number of ways of filling r positions by selcting out of n objects is given by,
                  \(\small{_nP_r } \) = \( \small{n(n-1)(n-2)(n-3)....(n-r+1) } \)
Here, the symbol \( \small{_nP_r} \) stands for the permutation of n objects taken r at a time.

We can re-write the above expression as,
\(\small{_nP_r } \) = \( \small{n(n-1)(n-2)(n-3)....(n-r+1) \times \dfrac{(n-r)(n-r-1)(n-r-2)....3.2.1}{(n-r)(n-r-1)(n-r-2)....3.2.1} } \)
realizing that the numerator of the above expression is \( \small{n!}\) and the denominator is \( \small{(n-r)!} \), we get

Therefore,

Combination (indistinguishable permutation)

In the case of permutation of n objects taken r at a time, it was understood that each one of the object had an identity. ie., they are distingushable . We know that we can arrange r objects in \( r! \) ways. If they are distinguishable, each one of these \( r! \) arrangments will be different.

Next, we will deal with the case of n objects which are indistinguishable (ie., identical). They can either be really identical or we don not bother to differentiate between them. We can choose r objects out of these n in \( _nP_r \) permutations. For each of these group of r objects each,the \( r! \) arrangements among them will be identical or redundant. They all look same. Therefore, effectively, there are only \(\dfrac{_nP_r}{r!} \) ways in which we can choose r out of n indistinguishable objects .

Thus the number of ways we can select r objects out of n objects in an unordered fashion is denoted by the symbol \(\small{_nC_r}\) which is defined by,

Each one of the \(\small{_nC_r}\) unordered subsets is a combination of n objects taken r at a time . Thus the combination \(\small{_nC_r}\) is an indistinguishable permutation.

Distinguishable permutations

We take a three letter word MOM and consider all the permutations of the letters in it : MOM, OMM, MOM, MMO, OMM, MMO. Of these 6 permutations, only three are distinguishable (unique): MOM, OMM and MMO.

In general, if N is the total number of objects which are divided into k groups with identical members, with frequencies \(\small{n_1, \ n_2\,..., n_k }\) within each group, then the distinguishable permutations can be determined by dividing the total number of permutations by the product of factorials of frequencies:

R Scripts

R has many library functions for sampling and permuting the given set of objects.

Given a set of n objects(can be numbers, strings or characters), we can find various permutations and combinations of them taken r at a time.

Random sampling from a set of objects

The sample() can be called to sample r elements from a given vector x of n elements. We can actually get the permuted elements. In addition to n,r and x, this function takes one more parameter to decide whether we allow repeat of elements in the permutations. See below:

###### Randoml sampling from a set of objects

# Create a vector integers from 1 to 100
 x = c(1:100)

# we can randomly sample 20 of them with equal probability
 s = sample(x,20)
 print(s)

The above code prints the following 20 random samples from given set.

[1] 33 16 73 48 34 17 20 95 67 59 83 39 22  2 49 79 26 74 45 25

Permutation and combination of objects

We can generate the possible permutations of \(\small{n}\) elements of a set taken \(\small{r}\) at a time. We use the functions called permutations() in the library gtools . The boolean parameter repeats.allowed allows one to create a list of combinations which are having unique elements:

#####  To get the permutation of n objects

library(gtools)

## create a list of n objects

x = c('A','B','C','D') ## unique elements of x should be >= r

## get and print permuted list of n objects in x taken r at a time
## This function returns a matrix with permuted elements along rows.

permlist = permutations(n=length(x), r=3, v=x, repeats.allowed=FALSE)

print(permlist)

Running the above script creates this output on the screen:

      [,1] [,2] [,3]
 [1,] "A"  "B"  "C" 
 [2,] "A"  "B"  "D" 
 [3,] "A"  "C"  "B" 
 [4,] "A"  "C"  "D" 
 [5,] "A"  "D"  "B" 
 [6,] "A"  "D"  "C" 
 [7,] "B"  "A"  "C" 
 [8,] "B"  "A"  "D" 
 [9,] "B"  "C"  "A" 
[10,] "B"  "C"  "D" 
[11,] "B"  "D"  "A" 
[12,] "B"  "D"  "C" 
[13,] "C"  "A"  "B" 
[14,] "C"  "A"  "D" 
[15,] "C"  "B"  "A" 
[16,] "C"  "B"  "D" 
[17,] "C"  "D"  "A" 
[18,] "C"  "D"  "B" 
[19,] "D"  "A"  "B" 
[20,] "D"  "A"  "C" 
[21,] "D"  "B"  "A" 
[22,] "D"  "B"  "C" 
[23,] "D"  "C"  "A" 
[24,] "D"  "C"  "B" 

The function combinations () from the sample library generates possible combinations of n objects taken r at a time. This is demonstrated here with the output:

#####  To get the permutation and combination of n objects

library(gtools)

## create a list of n objects

x = c('A','B','C','D') ## unique elements of x should be >= r

# To get a combination of above list
## This function returns a matrix with permuted elements along rows.

y = combinations(n=length(x), r=3, v=x)

print(y)

     [,1] [,2] [,3]
[1,] "A"  "B"  "C" 
[2,] "A"  "B"  "D" 
[3,] "A"  "C"  "D" 
[4,] "B"  "C"  "D" 

Number of Permutation and combination

In order to get the number of permutations and combinations of n objects taken r at a time, we write R functions to translate the corresponding formulas \(\small{ ~~_nP_r = \dfrac{n!}{(n-r)!}~~ }\) and \(\small{_nC_r = \dfrac{n!}{r!(n-r)!} }\). In the script below, we have written the two functions and called them:

## Function to compute permutation of n items taken r at a time

npermute = function(n,r) {

 nPr = factorial(n)/factorial(n-r)

 return(nPr)
} 


## Function to compute the combination of n items taken r at a time

ncomb = function(n,r) {

nCr = factorial(n)/(factorial(r)*factorial(n-r))

return(nCr)
}


### We use the functions

n = 10
r = 6

np = npermute(n,r)

nc = ncomb(n,r)

print(paste("Permutation of ", n, " things taken ",r," at a time = ", np))

print(paste("Combination of ", n, " things taken ",r," at a time = ", nc))

here is the output:

[1] "Permutation of  10  things taken  6  at a time =  151200"
[1] "Combination of  10  things taken  6  at a time =  210"