THE combinatorial analysis is a field of study in mathematics associated with counting rules. In the beginning of the 18th century, the study of games involving dice and cards made counting theories to have great development.
The work of combinatorics enables the realization of increasingly accurate counts.The fundamental principle of counting (PFC), the factorial and the types of grouping are examples of concepts studied in combinatorial analysis, which, in addition to providing bigger precision helps nothe development of other areas of mathematics, such as The probability and O Newton's binomial.
Read too: arrangement or çcombination?
What is combinatorial analysis for?
Combinatorial analysis is associated with the counting process, that is, the study of this area of mathematics allows us to develop tools that help us to perform counts more efficiently. Let's look at a typical counting problem, see:
Example 1
Consider three cities A, B and C connected by highways R1, R2, R3, R4 and R5. Determine how many ways we can get from city A to city C via city B.
Note that we need to leave city A and go to city B, and only then can we travel to city C, so let's analyze all the possibilities to carry out the event following the highways.
1st way: R1 → R3
2nd way: R1 → R4
3rd way: R1 → R5
4th way: R2 → R3
5th way: R2 → R4
6th way: R2 → R5
So we have six different ways to get from city A to city C via city B. However, note that the proposed problem is relatively simple and that the analysis performed was little laborious. So, from now on, we are going to study more sophisticated tools that make it possible to solve problems with much less work.
Fundamental principle of counting (PFC)
Consider an event E that can be performed in n independent and consecutive steps. Now, consider that the number of possibilities to perform the first step is equal to P1, also imagine that the number of possibilities to carry out the second stage is P.2, and so on, until we reach the last stage, which has Pno possibilities to be performed.
The fundamental principle of counting (PFC) states that the total possibilities of holding the event E is given by:
P1 ·P2 · … · Pno
Thus, the total is given by the product of the possibilities of each of the steps that constitute event E. Note that, in order to determine the total possibilities for holding event E, it is necessary to know the total possibilities for each of the stages.
Example 2
Let's redo example 1 using the fundamental principle of counting.
Consider the image in example 1.
Note that the event can be run in two stages, the first is going from city A to city B, and the second is going from city B to city C. To carry out the first step, we have two possibilities (roads R1 and R2), and to carry out the second stage, we have three possibilities (R3, R4 and R5).
1st step → two possibilities
2nd stage → three possibilities
By the fundamental principle of counting, we must multiply the total possibilities of each step.
2 · 3
6
Therefore, to go from city A to city C via city B, we have a total of six possibilities.
Example 3
How many ways can the three Olympic medals be distributed in a competition of mountain bike with five competitors?
Organizing the distribution of medals is an event that can be carried out in three stages. The first step is to analyze the total possibilities of who will get the gold medal, that is, five possibilities.
The second step is to analyze the possibilities of who will get the silver medal, that is, four, since the first place does not enter this choice. The third step is to analyze the total possibilities of who will get the bronze medal, that is, three, since the first two have already been chosen.
1st step → five possibilities
2nd stage → four possibilities
3rd stage → three possibilities
So, by the fundamental principle of counting, we have:
5 · 4 · 3
60 possibilities
See too: Additive counting principle - union of one or more sets
Factorial
O factorial is a way of decompose a natural number. To calculate the factorial of a number, just multiply it by all its predecessors up to the number 1. The factorial is represented by the exclamation mark — “!”.
See some examples of how to calculate the factorial of some numbers.
The) 2! (reads: two factorial)
For the calculation, just multiply the number that accompanies the factorial by all its predecessors up to the number 1, like this:
2! = 2 ·1 = 2
B) 4! = 4 · 3 · 2 ·1 = 24
ç) 5! = 5 · 4 · 3 · 2 · 1 = 120
d) 1! = 1
Formally we can write the factorial as follows:
Consider a natural number n > 2. The factorial of n is indicated by n! and is given by multiplying n by all of its positive integer predecessors.
no! = n (n – 1) · (n – 2) · (n – 3) · … · 1
Note the following factorials:
4! and 5!
Now carry out the development of both:
5! = 5 · 4 · 3 · 2 · 1
4! = 4 · 3 · 2 ·1
Note that in the development of 5! appears the development of 4!. So we can write the 5! thus:
5! = 5 · 4 · 3 · 2 · 1
5! = 5 · 4!
Example 4
Calculate the factorial sechowl:
See that the 15! was developed until the 13!. Also note that, in the numerator of the fraction, the elements are being multiplied, so we can “cut” the 13!, resulting in only 15 · 14.
Observation:0! = 1
Grouping Types
Some counting problems are more complex and more easily solved with new tools. These tools are called grouping because they group elements in different ways, making the counting process easier. These groupings are: simple arrangement, permutation, and simple combination.
simple arrangement
Consider a set with n distinct elements. let's call it arrangement from n the elements taken from p to p, any sequence ordered by p, and the distinct elements chosen among the elements.
Thus, the number of subsets formed by p elements will be the arrangement of n elements taken from p to p. The formula that allows us to calculate the number of arrangements is given by:
Example 5
Calculate the value of A4,2 + A5,2.
To calculate the value of the expression, let's determine each of the arrays and then add those values together. To determine the value of each array, we must substitute the values in the formula.
Note that n = 4 and p = 2, both have been substituted in the formula. Now, we must calculate the value of the array of five elements taken two by two.
So, we have to:
THE4,2 + A5,2
12 + 20
32
Example 6
How many distinct four-digit natural numbers can be formed using the numbers 2, 3, 4, 5, 6, 7, 8, and 9?
In this problem we can use the simple arrangement, since 2435 ≠ 4235. We will see that, in some cases, the order of the elements does not differentiate them, and thus we cannot use the arrangement.
Since we want to determine the total of numbers that can be formed, notice that the total of elements is equal to eight, and we want to group them four by four, so:
simple permutation
Consider a set with n elements. let's call it simple permutation of n elements every arrangement of n elements taken n to n. So we have to:
So that there is no confusion between the concepts, let us denote the simple permutation of n elements by Pno. So we have to:
Pno = n!
Example 7
Calculate P7 and P3.
To calculate these permutations, we must substitute the values in the formula. Look:
P7 = 7 · 6 · 5· 4 · 3 · 2 · 1
P7 = 5040
P3 = 3 · 2 · 1
P3 = 6
Example 8
Determine how many anagrams there can be in the word Brazil.
We understand as anagram all possible transpositions of the letters of the word, for example, "Lisarb" is a anagram of the word Brazil. To determine the number of anagrams, we must calculate the permutation of the letters in the word, so we have to:
P6 = 6!
P6 = 6 · 5 · 4 · 3 · 2 · 1
P6 = 720
Therefore, the word Brazil has 720 anagrams.
Also access: Permutation with repeated elements
simple combination
Consider a set A with n distinct elements. let's call it combination of the n elements taken p to p any subset of A formed by p elements. The formula for calculating the combination is given by:
Example 9
Calculate the combination of 10 elements taken from four to four.
Example 10
How many quadrilaterals distinct can we form with vertices at points A, B, C, D, E and F?
Note that the ABCD quadrilateral is the same as the CDBA quadrilateral in this context, so we should use the combination and not arrays. We have a total of six points and we want to combine them four by four, like this:
Therefore, we can form 15 distinct quadrilaterals.
Combinatorial Analysis and Probability
The study of probability is closely related to the study of combinatorial analysis.. In some probability problems, it is necessary to determine the sample space, which consists of a set formed by all the possible outcomes of a given event.
In some cases, the sample space E is written very directly, as in the flip of a fair coin, where the possible outcomes are heads or tails and are denoted as follows:
E = {heads, tails}
Now imagine the following situation: a die is thrown three consecutive times and we are interested in determining the sample space for this experiment. Note that writing down all the possibilities is no longer a simple task, we need to use the fundamental principle of counting (PFC). The event can be carried out in three stages, in each of them we have six possibilities, since a die has six faces, like this:
1st stage → six possibilities
2nd stage → six possibilities
3rd stage → six possibilities
By the PFC, we have that the total of possibilities is:
6 · 6 · 6
216
So we can say that the sample space of this event is 216.
See that for the study of probability it is a basic knowledge of combinatorial analysis is required., because, without determining the sample space of an experiment, it is impossible to solve the vast majority of probability exercises. For more details about this field of mathematics, read the text:Probability.
solved exercises
question 1 – Determine the number of anagrams of the word castle. Then determine the number of anagrams starting with the letter c.
Resolution
To determine the number of anagrams, we must calculate the permutation of the number of letters, like this:
P7 = 7!
P7 = 7 · 6 · 5 · 4 · 3 · 2 · 1
P7 = 5040
The word has 5040 anagrams. Now, to determine the number of anagrams that start with the letter c, we must fix the letter and calculate the anagram of the others, see:
Ç__ __ __ __ __ __
When we fix the letter c, note that there are six fields left to calculate the permutation, like this:
P6 = 6!
P6 = 6 · 5 · 4 · 3 · 2 · 1
P6 = 720
So we have 720 anagrams of the word castle that start with the letter c.
question 2 – In a classroom, there are five men and seven women. How many groups of three men and four women can be formed?
Resolution
First, see that the order in which we choose people doesn't matter, for example the group formed by João, Marcos and José is the same group formed by Marcos, João and José, therefore, we must use the combination for the calculation.
Let's calculate separately the number of groups that can be formed by men and women, and in Then let's multiply these results, because each group of men can mix with each group of women.
Men
Total → 5
Quantity in group → 3
Women
Total → 7
Quantity in group → 4
Therefore, the total number of groups that can be formed by three men and four women is:
Ç5,3 · Ç7,4
10 · 35
350
by Robson Luiz
Maths teacher
Source: Brazil School - https://brasilescola.uol.com.br/matematica/analise-combinatoria.htm