Combinatorial analysis

Introduction

To calculate the probability of an event, one can count the number of different ways an even can occur. The mathematical theory of counting is formally known as combinatorial analysis.

The Basic Principle of Counting

Suppose that two experiments are to be performed one after the other. If the first experiment results in any of \(n\) possible outcomes, and for each outcome of the first experiment, the are \(m\) possible outcomes of the second experiment, then together there are \(nm\) possible outcomes of the two experiments.

The basic principle can be generalized: If there are \(r\) experiments to be performed one after the other, then the total of possible outcomes \(n\) is the product of possible outcomes of each single experiment: \(n = n_1 \cdot n_2 \cdot n_3 \cdots n_r\)

Problem How many different 7-place licence plates are possible if the first 3 places are to be occupied by letters and the final 4 by numbers?
Solution By the generalized version of the basic principle, the answer is \(26^3 \cdot 10^4 = 175,760,000.\)

Problem How many licence plates would be possible if the repetition among letters or numbers were prohibited?
Solution In this case, there is one less choice for the next number or letter to choose from: \(26 \cdot 25 \cdot 24 \cdot 10 \cdot 9 \cdot 8 \cdot 7 = 78,624,000.\)

Permutations

A permutation is a rearrangement of elements of an ordered set. The order in which the elements are rearranged is important. We can use enumeration to calculate the number of possible permutations. Suppose we need to calculate the number of possible permutations of letters A, B, and C. From the basic principle of counting we have three choices of letters in the first position, two remaining letters in the second position, and one remaining letter in the third position. Thus, there are \(3 \cdot 2 \cdot 1 = 6\) possible permutations. If there are n elements in the set, the number of permutations is defined as

$$ n(n - 1)(n - 2) \cdots 3 \cdot 2 \cdot 1 = n! $$

Problem How many different batting orders are possible for a baseball team consisting of 9 players?
Solution There are \(9! = 362,880\) possible batting orders.

The following is a Python function that generates all permutations for a given list:

def permutations(L):
"""Input (L) is a list of elements.
Returns a list of all possible permutations of the given list (L)."""

# If (L) is an empty list, no permutations are possible
if len(L) == 0:
    return []
# If (L) has only one element, a single permutation is returned
if len(L) == 1:
    return [L]

permutation = [] # Empty list that will store current permutation
for i in range(len(L)):
    # Make a new list w/o L[i] element
    remList = L[:i] + L[i+1:]

    # Generate all permutations where L[i] is the first element
    for p in permutations(remList):
        permutation.append([L[i]] + p)
return permutation

Problem How many different letter arrangements can be formed from the letters PEPPER?
Solution First we notice that there are \(6!\) permutations of the letters \(P_1 E_1 P_2 P_3 E_2 R\) when P's and E's are distiguished from one another. However, since three P's and two E's are identical within themselves, we need to exclude their permutations from the resulting set. If we permutate P's and E's among themselves, we get \(3! \, 2!\) permutations. Therefore, there are \(6!/(3! \, 2!)\) possible letter arrangements of letters PEPPER.

In general, to calculate the number of permutations of \(n\) objects, of which \(n_1\) are alike, \(n_2\) are alike, \(\ldots , n_r\) are alike, we use the following formula:

$$ \frac{n!}{n_1! \, n_2! \, \cdots \, n_r!} $$

With a slightly modified code, we can now handle indistinguishable elements in the list:

def permutationsAlike(L):
    """Input (L) is a list of elements.
    Returns a list of all possible permutations of the given list (L)
    where alike elements are permuted only once."""

    # If (L) is an empty list, no permutations are possible
    if len(L) == 0:
        return []
    # If (L) has only one element, a single permutation is returned
    if len(L) == 1:
        return [L]

    permutation = [] # Empty list that will store current permutation
    for i in range(len(L)):
        # Make a new list w/o L[i] element
        remList = L[:i] + L[i+1:]

        # Generate all permutations where L[i] is the first element
        for p in permutationsAlike(remList):
            if [L[i]] + p not in permutation: # Add only unique permutation
                permutation.append([L[i]] + p)

    return permutation

Combinations

A combination is a set of different groups of r objects that could be formed from a total of n objects. For example, if we were to calculate the number of different groups of 3 from the set of 5 items A, B, C, D, and E, and the order was important, than to calculate the number of objects we would use the basic principle of counting: there are 5 ways to select the first item, 4 ways to select the second item, and 3 ways to select the third item. On the other hand, since every group of 3 would be counted 6 times because the number of permutations of a group of 3 is 3!=6, then if the order is not important, we need to devide this number of permutations from our set. In general, if the order is relevant, the number of different ways that a group of r items could be selected from the set of n items is defined as

$$ n(n -1) \cdots (n - r + 1) $$