7 Sets and Elements of Combinatorial Analysis in Python
In this chapter, we intend to present the basic concepts of combinatorial analysis and sets in a very simple way. We will build some simple functions for computing probabilities computationally in a few particular cases. We saw in chapter 1 the Python set objects. The set() operator is used to create a set. The argument of the set() function is a list or a tuple. They are immutable, unordered, and have no duplicate elements.
Several functions can be used for this type of object in Python, such as membership (in), union (union or |), intersection (intersection or &), and symmetric difference (symmetric_difference or ^), as illustrated in chapter 1. It is also possible to obtain differences, such as A-B, between two sets A and B.
Combinatorial analysis allows us to solve countless probability problems. Problems that commonly occur are listed below:
- selecting \(x\) elements among \(n\) elements, \(0\le x\le n\), without repeating any element (sampling without replacement) where order does not matter: combination;
- selecting \(x\) elements among \(n\) elements, \(0\le x\le n\), allowing repetition of the selected elements (sampling without replacement) where order matters: arrangements;
- distributing \(n\) elements into \(x\), \(x= n\), positions in different ways: permutations;
- different possible paths to follow with \(n_1\) possibilities at the first stage, \(n_2\) possibilities at the second stage, and so on up to \(n_k\) possibilities at the \(k\)-th stage: counting.
Thus, we want to obtain all possible combinations, permutations, arrangements, or paths (countings) possible in solving some probability problem or another situation in general.
7.1 Introduction to Combinatorial Analysis in Python
Combinatorial analysis and counting methods are essential to understanding probability. In Python we can compute the number of combinations given by \[\begin{align*}
\binom{n}{x} =& \dfrac{n!}{x!(n-x)!}, \textrm{ for } 0\le x \le n,
\end{align*}\] by math.comb(n, x). The listing of the combinations of \(n\) taken \(x\) at a time is obtained by the command combinations(range(1,n+1), x) from the itertools package, which must be imported. The first argument of the combinations function is a list, which in this case was a list ranging from \(1\) to \(n\), where we used the range function to obtain this list. We can, instead, use any other list. We can also use the comb function from scipy.special to obtain the number of combinations in an alternative way.
The command combinations(n, x) from the itertools package returns an object that must be converted to a list with \(\binom{n}{x}\) elements, where each element of the list corresponds to a tuple of \(x\) elements (the combination).
The following script illustrates a particular case of these commands:
7.2 Permutations and Arrangements
The total number of permutations of \(n\) objects is given by \(n!\), and with the itertools package we can list them in a list of size \(n!\), where each element is a tuple of size \(n\), using the permutations() function;
We can also take the arrangements of \(n\) taken \(x\) at a time with the same command, whose number of arrangements is given by \[\begin{align*}
A_{n,x}=& \dfrac{n!}{(n-x)!},
\end{align*}\] where in Python this value is obtained through the function math.perm(n, x).
The following script illustrates these commands:
To randomly draw permutations or arrangements, the command random.sample(range(1,n+1),n) returns a permutation of \(n\) taken \(n\) at a time. If we want a draw of \(n\) taken \(x\) at a time, random.sample(range(1,n+1),x), that is, an arrangement resulting in \(x\) elements without repetition (sample without replacement). It is not about the case in question (permutations and arrangements), but if we want sampling with replacement, as required in the bootstrap methods, we use the function random.choices(range(1,n+1),x), where \(x\) is a value between 1 and n. Both commands require us to import the Python random library. The following script illustrates these commands:
7.3 Counting
The fundamental counting principle, known as the multiplicative principle, is used to find the number of possibilities for an event consisting of \(k\) stages. The stages must be successive and independent. If an event has two \((k=2)\) stages, where the first has \(n_1\) possibilities and the second has \(n_2\) possibilities, then there are \(n_1\times n_2\) possibilities.
The fundamental counting principle is the multiplication of the options of each stage to determine the total number of possibilities. This concept is important for combinatorial analysis, which is an area of mathematics that brings together methods for solving problems including counting, and is therefore very useful in scientific research to determine the probabilities of natural phenomena.
To obtain all possibilities in \(k\) stages, each with the same number \(n\) of possibilities \((n^k)\), we created a Python class with some functions. The function contag(n, k) returns all \((n^k)\) countings from \(n\) possibilities in \(k\) stages, such as, for example, with \(n=2\) sexes of animals in \(k=3\) births, or \(n=2\) doors of a building in \(k=2\) possibilities (entrances and exits), corresponding to the entrances and exits of the building. We also did the same when we have a list (any iterator) of size \(k\) corresponding to the \(k\) stages in which each element refers to the number of possibilities of that stage. If \(x\) is the iterator, the total countings (possibilities) are \(\prod_{i=0}^{k-1} x[i]\).
The question, for example, of in how many different ways a person can enter and leave a building with \(2\) entrances and two exits, is what we intend to list (enumerate). The proposed function uses an iterative process controlled by the while, which at each iteration updates the particular count. The permuta or permutav functions are called for the case of \(n\) quantities in \(k\) stages and for the case of a list \(x\) of stages, respectively.
In the current script we have several novelties. For the first time in the course, we created a Python class. In this class we implemented four functions. The first two are intended to perform the listings of all countings in an iterative process. The next two have the same name and represent versions of the same function with different arguments, denoted by contag. For this we used the overloading technique.
The overload was implemented manually, without external dependencies. Instead of decorators, the contag function receives a variable number of arguments (*args) and checks, at the beginning of the body, how many and of what type these arguments are. If it receives two integers, it executes the permuta method (countings of n taken k at a time); if it receives a list (or tuple/array), it executes the permutav method (countings of the levels of a vector x); otherwise, it raises an explanatory TypeError. Thus, the same calling interface is maintained — contag(n, k) and contag(x) — and the interpreter chooses the appropriate option at runtime.
To illustrate, we created an object of the Cont class, the object res, through which we call the contag method twice with different arguments — first with two integers and then with a list — which causes, when executed, the interpreter to select the appropriate version and produce the corresponding outputs.
To illustrate, we created an object of the Cont class, the object res, through which we call the contag method twice with different arguments — first with two integers and then with a list — which causes, when executed, the interpreter to select the appropriate version and produce the corresponding outputs.
If, for example, we wanted to obtain all possible sex-of-birth possibilities for families with up to \(4\) children, we would have the following sample space for our experiment with \(2^4\) \(=\) \(16\) elements. The subtraction of \(1\) from all elements of the result of the call to the contag method is because the sexo vector has two levels, and in Python lists start at zero rather than one. The elements of the contag result are in this case composed of numbers \(1\) and \(2\) (female and male), whose positions in the sexo vector are \(0\) and \(1\), respectively.
Python already has these resources implemented for counting. The itertools library has the product function, which plays the same role as our functions implemented in the cont class.
7.4 Sets in Python
Let us recall the main functions of the set objects, sets in Python, so that we can perform some simple operations. Sets in Python are a collection of elements with no occurrence of values with multiplicities. Sets are created by the set method or by using braces. Thus, x = set([1,2,3]) or x={1,2,3} is a set, but y= [1,2,3,3] is not, because it has repeated elements. If we consider the command y= set([1,2,3,3]), this object would be a set, since Python automatically eliminates the repeated elements when creating the set.
The arguments of the set function are the lists or the tuples. We can efficiently use sets to remove duplicate elements from a list or tuple. First, we apply the set() operator with the argument being a list or a tuple and then apply the list() or tuple() argument to the result. Another advantage of sets is that they can have elements of different types. Sets are immutable, because their elements cannot be exchanged, but we can add and remove elements from a set in Python. Furthermore, sets are unordered. Let us see an example of how to create a set.
We can add or remove elements from a set. The elements that are arguments of the set.add() or set.update() functions must be immutable, such as tuples or strings, for the first method, and any iterator object, such as lists, for the second. If the argument is a list, an error will occur in the add method. To remove an element from a set, we can use methods such as set.remove(), set.discard(), or set.pop(). The first command removes a specific element from the set and returns an error if the element does not exist. The second removes the element but does not raise an error if the element does not exist, leaving the set as it was before its application. The third removes an element randomly from the set and has no argument. The pop method returns the removed element and updates (modifies) the set to which it was applied. The add and update methods differ in that the first does not support adding a list to the set. The set.clear() method removes all elements from the set. See the script with some examples:
Python includes some set operations, some of which are:
set.union(x, y): union of sets \(x\) and \(y\), which corresponds to the set of all elements present in \(x\) and in \(y\), considering only once those elements with multiplicity greater than \(1\);set.intersect(x,y): intersection of sets \(x\) and \(y\), which corresponds to the set of elements present simultaneously in \(x\) and \(y\);set.difference(x,y): set of the difference between sets \(x\) and \(y\), consisting of the set of all elements of \(x\) that are not in \(y\);x == yorx != y: tests whether two sets \(x\) and \(y\) are equal or different, respectively;c in y: membership, that is, tests whether \(c\) is an element of set \(y\);set.symmetric_difference(x, y): the set of elements that are either in \(x\) or in \(y\), but not in both simultaneously.
Other basic set operations are the following:
y.issubset(x): returnsTrueif \(y\) is contained in or equal to set \(x\);x.issuperset(y): returnsTrueif \(x\) contains or is equal to set \(y\);x.isdisjoint(y): returnsTrueif \(x\) and \(y\) have no elements in common, that is, if the intersection is an empty set.
7.5 Some Probability Problems
We will present some particular cases, such as the birthday coincidence case. For birthday coincidence, let us consider the coincidence of births of a group of \(n\) people on the same date and that the year has \(365\) days. We also assume that the distribution of births over the birthdays’ years is uniformly random, which is a strong assumption. The probability that no two people have the same birth date (event \(A\)) in a group of \(n\) people is: \[\begin{align*} P(A) =& \dfrac{A_{365,n}}{365^n}=\dfrac{365!}{(365-n)!365^n}. \end{align*}\]
We want the probability of the complementary event, which is given by \(P(A^c)=1-P(A)\). Hence, \[\begin{align*} P(A^c) =& 1-\dfrac{A_{365,n}}{365^n}=1-\dfrac{365!}{(365-n)!365^n}, \end{align*}\]
which is the probability of there being at least one birthday coincidence on the same date.
We implemented two ways. In the first, we use the complete formula. We take the logarithm (we use the gammaln function from scipy.special) and at the end recover it by taking the exp of the result. In the second alternative, we use the math library, where the total number of arrangements \(A_{365,n}\) is obtained by the command math.perm(365, n).
The program for the first alternative in Python is:
Our second implementation is:
In the second example, let us consider the probability that a committee of size \(m\), when drawn randomly from a group of size \(n\), does not contain representatives of a specific existing group of size \(k\) among the \(n\) elements of the whole group. This probability is: \[\begin{align*} P(\textrm{Not represented}) =& \frac{\binom{n-k}{m}}{\binom{n}{m}}. \end{align*}\]
The Python program was implemented and illustrated with the example of Brazilian senators, who have representatives from the different Brazilian federal units. In Brazil we have \(n = 27\times 3\) senators, that is, \(81\) senators in total, with \(3\) from each state or from the Federal District. If we are to form a random committee of \(m=10\) senators, what is the probability that any given federal unit containing \(k=3\) senators is not represented? We saw through the analysis of the previous formula that we have \(\binom{n}{m}\) different ways of drawing committees of size \(m\) from \(n\) elements of the whole group. If we remove from the total \(n\) the \(k\) that will be excluded from the committee composition, \(n-k\) remain, which can be sampled \(m\) at a time. Thus, the number of committees without the \(k\) of the considered group is \(\binom{n-k}{m}\). The ratio between these two quantities gives us the desired probability. The script with the senators example is presented below.
Our next example refers to the probabilities in a poker hand, building the possibilities and probabilities. In this game we can have a hand with nothing (no pairs, no two pairs, no three of a kind, etc.), one with a pair, one with two pairs, one with three of a kind, one with a straight (any suit), one with a flush (different values that are not in sequence of the same suit), one with a full house (three of a kind and a pair), one with a four (four of a kind), one with a straight of the same suit, and a royal straight of the same suit (royal flush — from 10 to Ace).
The total number of possibilities of distributing \(52\) in a draw of \(5\) cards (one hand) is: \[\begin{align*} \binom{52}{5}=& \dfrac{52!}{5!(52-5)!}=2,598,960. \end{align*}\]
- To obtain a hand with nothing, we must understand that the deck is made of \(52\) cards, with \(13\) card values (Ace, \(1\), \(2\), \(\cdots\), \(10\), Jack, Queen, and King) and \(4\) suits for each value (spades, clubs, diamonds, and hearts). The number of possibilities of a five-card hand (draw of \(5\) cards without replacement) containing a hand with nothing, that is, with no pairs, no three of a kind, no four of a kind, no straights of different suits or no straights of the same suit, is:
\[\begin{align*} \binom{13}{5}\left(\binom{4}{1}\right)^5-10\left(\binom{4}{1}\right)^5 - 4\binom{13}{5} +4\times 10=&=1,302,540, \end{align*}\]
that is, it is the number of cards of different values with any of the \(4\) suits \(\binom{13}{5}4^5\), subtracted from all possibilities of straights of different suits \(10\times 4^5\) and from the possibilities of having cards of different values with the same suit \(4\binom{13}{5}\). This value must be added to the ten possible straights for each of the suits \(4\times 10\). This addition occurs because we removed the possibilities of having cards of different values with the same suit, which includes the \(10\) possible straights of the same suit, and again it was removed when we eliminated the possibilities of having \(5\) cards of different values with the same suit, which includes the \(10\) possible straights of the same suit. Hence we need to add them, since they were removed twice.
- For the single-pair hand we have:
\[\begin{align*} \binom{13}{1}\binom{4}{2}\binom{12}{3}4^3, \end{align*}\]
where \(\binom{13}{1}\) chooses the value of the pair, \(\binom{4}{2}\) chooses the suits for the pair, \(\binom{12}{3}\) chooses among the \(12\) remaining values (not chosen for the pair), and \(4^3\) chooses the suits of the \(3\) values different from the pair.
- For two pairs we have:
\[\begin{align*} \binom{13}{1}\binom{4}{2}\binom{12}{1}\binom{4}{2}\binom{11}{1}4, \end{align*}\]
where \(\binom{13}{1}\) chooses the value of the first pair, \(\binom{4}{2}\) chooses the suits for the first pair, \(\binom{12}{1}\) chooses the second pair among the \(12\) remaining values, \(\binom{4}{2}\) chooses the suits for the second pair, and \(\binom{11}{1}\) chooses the values among the \(11\) remaining values (not chosen for the \(2\) pairs), and \(4\) chooses the suits of the value different from the two pairs.
- For three of a kind we have:
\[\begin{align*} \binom{13}{1}\binom{4}{3}\binom{12}{2}4^2, \end{align*}\]
where \(\binom{13}{1}\) chooses the value of the three of a kind, \(\binom{4}{3}\) chooses the suits for the three of a kind, \(\binom{12}{2}\) chooses the \(2\) values among the \(12\) remaining values, and \(4^2\) chooses the suits for these values.
- For the straight:
\[\begin{align*} 10\times 4^5 - 10\times 4, \end{align*}\]
where \(10\) chooses among the \(10\) possible straights (from Ace to \(5\), from \(2\) to \(6\), up to from \(10\) to Ace), and \(4^5\) chooses the suits of each value. The result includes straights of the same suit, which must be removed, corresponding to \(10\times 4\) (straights of the same suit including the royals).
- For the flush (cards of the same suit):
\[\begin{align*} \binom{13}{5}\times 4 - 10\times 4, \end{align*}\]
where \(\binom{13}{5}\) chooses the \(5\) different values among the \(13\), and \(4\) chooses one of the suits for the \(5\) values. The result includes straights of the same suit, which must be removed, corresponding to \(10\times 4\) (straights of the same suit including the royals).
- For the full house (three of a kind and a pair):
\[\begin{align*} \binom{13}{1}\binom{4}{3}\binom{12}{1}\binom{4}{2} \end{align*}\]
where \(\binom{13}{1}\) chooses the value for the three of a kind, \(\binom{4}{3}\) chooses the suits of the three of a kind, \(\binom{12}{1}\) chooses the value of the pair among the \(12\) remaining values, and \(\binom{4}{2}\) chooses the suits of the pair.
- For the four of a kind (four):
\[\begin{align*} \binom{13}{1}\binom{12}{1}4 \end{align*}\]
where \(\binom{13}{1}\) chooses the value for the four of a kind, which will necessarily have one of each suit, \(\binom{12}{1}\) chooses a value for the remaining card among the \(12\) remaining values, and \(4\) chooses one of the suits of the remaining card, which is not the one of the four of a kind.
- For straights of the same suit (straight flush):
\[\begin{align*} 10\times 4 - 4, \end{align*}\]
since there are \(10\) straights for one of the \(4\) suits, minus the \(4\) royal straights among them, from \(10\) to Ace of each of the four possible suits.
- The royal straight (royal straight flush): there is a single possible straight from \(10\) to Ace for each of the four suits, totaling \(4\) possible royal straights.
The following program creates a dataframe with all these countings and computes the probabilities by dividing them by the total number of combinations:
Our next example refers to the probability of the maximum difference in an ordered enumerated list. Obtain the largest gap (jump) (maximum difference) between two consecutive numbers in the draw without replacement of \(m\) numbers among the first \(n\) integers from \(1\) to \(n\), for \(m<n\). In Python, the command np.diff(x) returns the differences between consecutive numbers of the list x.
The following program uses the checkgap function to return the maximum difference of any iterator. The maxgap function receives \(n\), \(m\), and \(k\) and computes the probabilities for each case. To do this, it traverses all combinations generated by combinations, returning the maximum of each combination obtained in y, and with the command mean(y == k) the exact probability of \(P(X=k)\) is obtained, where \(X\) is the variable representing the largest difference between consecutive integers of a sample without replacement of size \(m\) obtained among \(n\) integers, for \(m\) from \(1\) to \(n\), and \(k\) the value of the largest difference (value of the random variable) for which we want to compute the probability of occurrence. If \(m=2\), then the maximum difference will be considered the consecutive difference, because the difference in each outcome of the sample space is unique, since we have samples of size \(2\).
Our last example is for the probability of the sums of faces in the throw of \(n\) dice and of the difference in absolute value of the faces in the throw of \(2\) dice. For this case, we can use a similar version, either by applying the previously presented contag function or by applying the product function from the intertools library. We chose to use the contag function from the cont class.
With the use of some small additional details, we obtained the results for both cases. The second case, of the difference, for obvious reasons, results from the throw of only \(2\) dice. In both cases we also present the probability results by obtaining all possibilities that correspond to the sample space of the random experiment. We have a function to obtain a probability for a specific value of the random variable and another for all probability values relative to the support of the random variable, in both cases, that of the sum of \(n\) dice and that of the difference of two dice. The results are presented in the following script:
7.6 Exercises
Obtain a function to compute, by Monte Carlo simulation, the probabilities of the throws of \(n\) dice and the sums obtained, as well as the absolute differences between faces in the independent throws of \(2\) dice. To do this, choose a large number of replications \(N\) and in each one simulate the outcomes of the dice throws. Obtain the results of the random variables and, at the end, compute the proportions of each occurrence, as we did exactly before. These proportions are empirical estimates of the desired probabilities.
Also obtain, by Monte Carlo, the empirical probabilities of a poker hand, simulating a large number of hands. For this you need to create a deck, which can be done with a dictionary, and then sample five-card hands and compute the empirical probabilities of each possible outcome. Compare with the exact probabilities obtained in this chapter. What do you expect to happen in this comparison when the number of simulations increases?