Combinatorial analysis: concepts, formulas, examples

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.

What is combinatorial analysis for?
What is combinatorial analysis for?

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: R1R3

2nd way: R1R4

3rd way: R1R5

4th way: R2R3

5th way: R2R4

6th way: R2R5

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.

What is combinatorial analysis for?
What is combinatorial analysis for?

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.

Combinatorial analysis is also associated with the study of binomials.
Combinatorial analysis is also associated with the study of binomials.

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

Titan submarine: three aquatic expeditions that almost met the same end

In recent days, there has been no talk of anything other than the implosion of the Titan submarin...

read more

Letter from Steve Jobs sold at auction has curious content; understand

Regardless of the area of ​​expertise, there are people who inspire you and are admired, as they ...

read more

Online auction brings together Corolla, Hilux and the classic Beetle; learn how to participate!

Milan Auctions will promote an online auction of vehicles, this Wednesday, February 1st. Starting...

read more