Essentials of Data Science – Probability and Statistical Inference - Basic Principles of Counting

In the previous note on the axiomatic definition of Probability, we have seen the intuitive notion of Probability, its limitation, axiomatic definition of Probability, and various rules to compute probabilities of the events. This note, we will read and understand basic principles of counting which includes, combination and permutation.

Whenever we are trying to compute the probability of an event, the essential ingredient is to count how many ways that event can happen. In other words, find a total number of ways an event can take place. So, once we have that value, we can find the probability by dividing by the total number of outcomes, which gives the likelihood of an event.

For any event A,

$P(A)$ = $\frac{\text{Number of points in A}}{N}$

In other words, if we assume that each outcome of an experiment is equally likely to occur, then the probability of any event A = the proportion of points or outcomes in the sample space that are contained in A.

Thus, to compute probabilities it is necessary to know the number of different ways to count given events.

Table of Contents hide

1 Basic Principle of Counting

1.1 Ordered and Unordered Sets

1.1.1 Ordered samples

1.1.2 Unordered samples

1.2 Factorial Function

1.3 Permutation

1.3.1 Permutation without replacement

1.3.2 Permutation with replacement

1.4 Combination

1.4.1 Combinations without replacement and order does not matter

1.4.2 Combinations without replacement and order matters

1.4.3 Combinations with replacement and order does not matter

1.4.4 Combination with replacement and order matters

Basic Principle of Counting

Suppose that two experiments are to be performed. The first experiment can result in any one of m possible ways and if, for each outcome of first experiment, there are n possible outcomes of second experiment. Then together there are m*n possible outcomes of the two experiments.

Ordered and Unordered Sets

We will understand ordered and unordered sets with an example, suppose there are three balls of different colours, black, grey, and white, are drawn. Now there are two options:

The first option is to take into account the order in which the balls are drawn. In such a situation, multiple possible sets of balls can be possible, such as (black, grey, and white) (white, black, and grey) and many others. In this type of construction, we can have different sets, and each set can be treated differently, and such set is called an ordered set.

In the second option, we do not take into account the order in which the balls are drawn. In such a situation, the two possible sets of balls such as (black, grey, and white) and (white, black, and grey) are the same sets and constitute an unordered set of balls.

A group of elements is said to be ordered if the order in which these elements are drawn is of relevance, otherwise it is called unordered.

Ordered samples

The first three places in a 100m race are determined by the order in which the athletes arrive at the finishing line. Suppose if 8 athletes are competing with each other, the number of possible results for the three places is of interest.
In a lottery with two prizes, the first drawn lottery ticket gets the first prize, and the second lottery ticket gets the second prize.

Unordered samples

The selected members for a football team. The order in which the selected names are announced is irrelevant.
Fishing 20 fish from a lake.
A bunch of 10 flowers made from 21 flowers of 4 different colours.

Factorial Function

The factorial function $n!$ is defined as:

n! = $1 \times 2 \times 3 \times \cdots \times n$ for n > 0 and 0! = 1.

Permutation

Consider a set of n elements. Each ordered composition of these n elements is called a permutation. We distinguish between two cases are as follows:

Permutation without replacement

If all the elements are distinguishable, then we speak of permutation without replacement. Suppose, if all the n elements are distinguishable, then there are n! different compositions of these elements.

Example 1

There are three students who will get three ranks, first (F), Second (S), and Third (T). It means there are 3! = 6 possible ways in which they can be ranked. These are, (F,S,T), (F,T,S), (S,T,F), (S,F,T), (T,F,S), and (T,S,F).

Example 2

A person has 10 books that he is gonig to put on his bookshelf. of these, 4 are mathematics books, 3 are chemistry books, 2 are history books, and 1 is a language book. He wants to arrange his books so that all the books dealing with the same subject are together on the shelf. So we want to know the total number of possible different arrangements.

Solution:

There are 4! 3! 2! 1! arrangements such that the mathematics books are first in line, then the chemistry books, then the history books and then the language book. Similarly, for each possible ordering of the subjects, there are 4! ways we can do it. Hence, as there are 4! possible orderings of the subjects, the desired answer is : 4! x 4! x 3! x 2! x 1! = 6,912.

Permutation with replacement

If some or all of the elements are not distinguishable, then we speak of permutation with replacement. Consider a set of n elements, assume that not all n elements are distinguishable. The elements are divided into groups, and these groups are distinguishable. Suppose, there are s groups of sizes $n_1, n_2, \cdots, n_s$ . The total number of different ways to arrange the n elements is s groups is:

$\frac{n!}{n_1! x n_2! x \cdots x n_s!}$

Example 1

There were 10 students and there are 3 types of chocolates C1, C2, and C3. The total number of ways in which two C1, three C2, and five C3 chocolates can be given to the 10 students is obtained as follows: $n_1 = 2, n_2 = 3, n_3 = 5, n = 10$ .

The total number of different ways to arrange the n = 10 elements in 3 groups is:

$\frac{10!}{2!3!5!}$

The meaning of replacement is just a convention and does not directly refer to the drawings.

Combination

The binomial coefficient for any integers m and n with $n \ge m \ge 0$ is denoted and defined as:

$n \choose m = \frac{n!}{m!(n-m)!}$

It is read as “n choose m” and can be calculated in R using following command, choose(n,m)

It answers the following type of questions, such as how many different possibilities exist to draw m out of n elements, i.e. for example, suppose there are n balls in a box and we want to choose m out of n balls from the box, what are the different ways we can choose the balls.

Combinations without replacement and order does not matter

When there is no repleacement and the order of the elements is also not relevant, then the total number of distinguishable combinations is drawing m out of n elements is

$n \choose m = \frac{n!}{m!(n-m)!}$

The result can be obtained in R by using the command, choose(n,m)

Example 1:

Suppose a company elects a new board of directors. The board consists of 6 members and 10 people are eligible to be elected. How many combinations for the board of directors exist?

Solution:

Since a person cannot be elected twice, we have a situation where there is no replacement. The order is also of no importance: either one is elected or not.

$10 \choose 6 = \frac{10!}{6! x 4!}$ = 210 possible combinations.

Combinations without replacement and order matters

The total number of different combinations for the setting without replacement and with consideration of the order is:

$\frac{n!}{(n-m)!} = m! \times n \choose m$

This can be calculated in R as follows: factorial(m) * choose(n,m)

Example 2:

Consider a race with 10 students. A possible bet is to forecast the winner of the race, the second student of the race, and the third student of the race.

Solution:

The total number of different combinations for the students in the first three places is $\frac{10!}{(10-3)!}$ . This result can be explained intutively.

For the first place, there is a choice of 10 different students.
For the second place, there is a choice of 9 different student (10 students minus the winner)
For the third place, there is a choice of 8 different students ( 10 students minus the first and second students).
The total number of combinations is 10 x 9 x 8 = 720.

Combinations with replacement and order does not matter

The total number of different combinations with replacement and without consideration of the order is as follows:

${n+m-1} \choose m = \frac{(n+m -1)!}{m! (n-1)!}$

This can be calculated in R as follows: choose(n+m-1, m)

Example 3:

A farmer has 2 fields and aspires to cultivate one out of 4 different organic products per field. Then, the total number of choices he has is ${4+2-1} \choose 2$ = 10. The explaination is as follows:

If 4 different organic products are denoted as a,b,c, and d, then the following combinations are possible: (a,a), (a,b), (a,c), (a,d), (b,b), (b,c), (b,d), (c,c), (c,d), (d,d). Here order does not matter, so (a,b) = (b,a), as the order in which the products a and b are cultivated on the first or second field is not important in this example.

Combination with replacement and order matters

The total number of different combinations for the intergers m and n with replacement and when the order is of relevance is:

$n^m$

This can be calculated in R as follows: n^m

Example 4:

Consider a credit card with a four-digit ATM personal identification number (PIN) code. The total number of possible combiations for the PIN is $n^m = 10^4$ = 10000. For every digit in the first, second, third, and fourth places (m =4) can be chosen out of ten digits from 0 to 9 (n = 10).

Example 5:

A committee of 5 is to be selected from a group of 6 men and 9 women. If the selection is made randomly, what is the probability that the committee consists of 3 men and 2 women?

Solution:

Let us assume that randomly selected means that each of the $15 \choose 5$ possible combinations is equally likely to be selected. Hence the probability that committee consists of 3 men and 2 women.

$\dfrac{ \binom{6}{3} \times \binom{9}{2}}{\binom{15}{5}} = \dfrac{240}{1001}$

Example 6:

An urn contains n balls, of which one is special. If k of these balls are withdrawn one at a time, with each selection being equally likely to be any of the balls that remain at the time, what is the probability that the special ball is choosen?

Solution:

Since all the balls are treated in an identical manner, it follows that the set of k balls selected is equally likely to be any of the $n \choose k$ sets of k balls. Therefore,

$P(\text{special ball is selected})$ = $\dfrac{ \binom{1}{1} \times \binom{n-1}{k-1}}{ \binom{n}{k}}$ = $\dfrac{k}{n}$

Q&A

From this note, we can get answers to the following questions.

What is the difference between an ordered set and an unordered set in Probability?
What is the difference between permutation and combination?

References

Essentials of Data Science With R Software – 1: Probability and Statistical Inference, By Prof. Shalabh, Dept. of Mathematics and Statistics, IIT Kanpur.

115 total views, 1 views today

Essentials of Data Science – Probability and Statistical Inference – Basic Principles of Counting