Content
Combinatorial
The combinatorial is a branch of mathematics belonging to the area of discrete mathematics that studies the enumeration, construction and existence of configuration properties that satisfy certain established conditions
In addition, it studies the sorts or groupings of a certain number of elements. It is used in statistics to perform probabilistic calculations
Variations
Suppose we want to count the total number of possible injective applications that can be built from an X set, from k elements, into another set Y, of n elements (which will have to be k \le n)
An application f| X \rightarrow Y with injective f, it is completely determined whether we know each of the images of the k elements of X
If we consider the f application as a word of k letters of the Y alphabet, it will not have repeated letters. The f app will be f(x_1)f(x_2)\cdots f(x_n) then:
f(x_1) \in Y
f(x_2) \in Y \text{\ }\{f(x_1)\} = \{y \in Y | y \not= f(x_1)\}
f(x_3) \in Y \text{\ }\{f(x_1), f(x_2)\} = \{y \in Y | y \not= f(x_1), y \not= f(x_2)\}
\vdots
f(x_n) \in Y \text{\ }\{f(x_1), \cdots, f(x_{k - 1})\} = \{y \in Y | y \not= f(x_1), \cdots, y \not= f(x_{k - 1})\}
If we denote by V(n, k) to the total injective applications of X in Y and we call it variations of n elements taken from k to k, then we have by the principle of the product that:
V(n, k) = n \cdot (n - 1) \cdot (n -2)\cdots (n - k + 1) = \frac{n!}{(n-k)!}
Where n! = n \cdot (n - 1) \cdot (n -2) \cdot \cdots \cdot 2 \cdot 1 which is the product of all natural numbers from 1 to n (this amount is called factorial of n)
Example of variations
What is the probability that in a group of n people there will be 2 who celebrate the birthday on the same day?
Calculating the probability of the n sets is very tedious, we have to calculate the probability that they met it 0, 1, \cdots, (n -1) on the same day
That's why it's best to calculate the probability of the opposite event. That is, the probability that n people will celebrate their birthday on different days, it becomes the same as giving an orderly list of n days other than between 365 days of the year. Therefore we have to:
\text{Favorable cases = }V(365, n) = \frac{365!}{(365 - n)!}
Possible cases are all sorted lists of n days, so repetitions are allowed (they are variations with repetition). Therefore we have to:
\text{Possible cases = }VR(365, n) = 365^n
So the solution to our problem will be given by:
p = 1 - \frac{\text{favorable cases}}{\text{possible cases}} = 1 - \frac{V(365, n)}{VR(365, n)} = 1 - \frac{365!}{365^n \cdot (365 - n)!}
The following table shows the p probability that in a group of n people there are at least two who celebrate their birthday on the same day:
| n | p | n | p |
| 5 | 0.027136 | 35 | 0.814383 |
| 10 | 0.116948 | 40 | 0.891223 |
| 15 | 0.252901 | 45 | 0.940976 |
| 20 | 0.411438 | 50 | 0.970374 |
| 21 | 0.443688 | 55 | 0.986262 |
| 22 | 0.475695 | 60 | 0.994123 |
| 23 | 0.507297 | 65 | 0.997683 |
| 24 | 0.538344 | 70 | 0.999160 |
| 25 | 0.568700 | 75 | 0.999720 |
| 26 | 0.598241 | 80 | 0.999914 |
| 27 | 0.626859 | 85 | 0.999976 |
| 28 | 0.654461 | 90 | 0.999994 |
| 29 | 0.680969 | 95 | 0.99999856 |
| 30 | 0.706316 | 100 | 0.99999969 |
Variations with repetition
Let's say we want to count the total number of possible applications that can be built from an X set, from k elements, into another set Y, of n elements
An application f| X \rightarrow Y is completely determined if we know every one of the images of the k elements of X
I mean, we need to know f(x_i) with 1 \le i \le k. This is equivalent to giving a k-tuple (f(x_1), f(x_2), \cdots, f(x_k)) set Y^k = \overbrace{Y x \cdots x Y}^{k\;\rm times}
It is also equivalent to a word of k letters of the alphabet Y (f(x_1), f(x_2), \cdots, f(x_k)) or give an ordered selection of k elements among Y's (Y elements can be repeated, i.e. it may happen that f(x_i) = f(x_i)\text{ con }i \not= j)
The only condition is that f(x_i) \in Y. Therefore, the total applications of X in Y, or the total variations with repetition of n elements taken from k to k, is equal to the cardinal of Y^k which, by the beginning of the product, is n^k. If we denote this number by VR(n, k), then:
VR(n, k) = n^kExample of variations with repetition
What is the probability of hitting the plenary to fifteen in a quiniela?
Filling a quiniela is equivalent to giving a list of 15 symbols by choosing between 1, X and 2, that is, a word of length 15 constructed with alphabet 1, X and 2
So we have that the number of possible quinielas will be:
VR(3, 15) = 3^{15}
However, this is not the solution to our problem, which will be given by:
Permutations
We will call permutations of m elements, the number of variations without repetition of m elements that can be formed
P_m = m!Example of Permutations
We have a bookshelf that fits three books and we want to sort them without any repeat. Each book has the cover of a different color: red, blue, and green. To distinguish them we will use the L set of books and their elements are the first letter of the color of their cover:
L=\{R, A, V\}| Management | Number of permutation |
| L=\{R, A, V\} | 1 |
| L=\{R, V, A\} | 2 |
| L=\{V, R, A\} | 3 |
| L=\{V, A, R\} | 4 |
| L=\{A, V, R\} | 5 |
| L=\{A, R, V\} | 6 |
To calculate the number of permutations we can see that they have been grouped together until we get all the possible variations. The first pass all 3 items have been used. The second is discarded 1 and only 2 are used. The third and final, 1 is discarded and the only remaining element is used
Therefore, to calculate the permutations we have to multiply the number of elements other than the 3 passes:
3\cdot 2 \cdot 1 = 6
Or what's the same:
Permutations with repetition
We will call permutations with repetition of m elements, the number of variations of m elements that can form when some elements are repeated a finite number of times
PR_{m}^{n_{1}, n_{2}, \cdots, n_k} = \frac{m!}{n_{1}! \times n_{2}! \times \cdots \times n_k!}Example of permutations with repetition
The result of a football match was 5-4
How many different ways could this result be achieved?
Any goal scored by the local team what we denote by L and any goal scored by the visiting team with V
The number of L or V-total has to be of length 5 + 4 = 9, so we look for any sorted list containing 5 L and 4 V in any order, representing the possible order of goals in the match
With what we have that the number of different ways to reach that result is:
PR_{9}^{5, 4} = \frac{9!}{5! \cdot 4!} = 126Combinations
We call combinations of m elements taken from n in n the number of subsets that can be formed with n of these m elements without repeating any
C_{m, n} = {m \choose n} = \frac{m!}{n! \cdot (m - n)!}Example of combinations
What is the probability of hitting the primitive lottery?
In the primitive lottery, there are 49 possible numbers to play and 6 of them can be chosen, regardless of the order in which they appear
To know how many possible combinations there are in this game, just calculate the number of subsets that can be formed with 6 of those 49 elements
With what we have that the number of possible lottery tickets will be:
C_{49, 6} = {49 \choose 6} = \frac{49!}{6! \cdot (49 - 6)!}=\frac{49!}{6! \cdot 43!}
However, this is not the solution to our problem, which will be given by:
Combinations with repetition
We will call combinations with repetition of m elements taken from n in n the number of subsets that can be formed with n of these m elements may repeat any
CR_{m, n} = {m + n - 1\choose n} = \frac{(m + n - 1)!}{n! \cdot (m - n)!}Example of combinations with repetition
How many tiles does the domino have?
A domino is a rectangle divided into two equal pairs, and that each part contains a number of points chosen within the set \{0, 1, 2, 3, 4, 5, 6\}, where 0 is represented with the absence of points
The total number of dominoes matches the number of unordered selections of two elements, repeated or not, chosen from the set \{0, 1, 2, 3, 4, 5, 6\}
With what we have that the total number of dominoes will be:
CR_{7, 2} = {7 + 2 - 1\choose 2} = \frac{(7 + 2 - 1)!}{2! \cdot (7 + 2 - 1 - 2)!} = \frac{8!}{2! \cdot 6!} =28