Multiplicative principle or fundamental counting principle“If an event can be divided into two stages, where the 1st stage can occur in m different ways and, for each of these m ways, the 2nd stage can occur in n distinct ways, then the number of ways the event can occur is m × n.”- Fundamental counting principleThe principle works for any number of stages: just multiply the number of possibilities of each one.ExamplesIn how many different ways can a person enter and then leave a hall that has 10 doors?1st STAGE: Enter —————— 10 ways2nd STAGE: Leave ——————— 10 waysEntering and leaving the hall: 10 × 10 = 100 ways.There are four roads connecting cities A and B and three roads connecting cities B and C. In how many distinct ways can one go from A to C, passing through B?The trip from A to C can be seen as an action made up of two successive stages:1st - go from A to B: we have four possibilities.2nd - go from B to C: for each of the previous possibilities, there are three ways to reach C from B.So, by the fundamental counting principle (FCP), the answer is 4 × 3 = 12.With the digits 1, 2, 3, 4, 5 and 6, how many three-digit numbers with distinct digits can we form?Forming a three-digit number can be seen as an action made up of three successive stages:1st - choosing the hundreds digit: we have six possibilities.2nd - choosing the tens digit: since there can be no repetition, the digit must differ from the one chosen for the hundreds. So there are five possibilities.3rd - choosing the units digit: the digit must differ from the previous two (hundreds and tens). So there are only four possibilities.By the FCP, the answer is 6 × 5 × 4 = 120 numbers.A snack bar offers 3 types of bread, 4 fillings and 2 sauces. How many different sandwiches can be made with one bread, one filling and one sauce?Answer: 24 — there are three independent stages, so we multiply: 3 × 4 × 2 = 24. Adding (3 + 4 + 2 = 9) is the most common mistake: the sum counts how many options there are, not how many combinations.Simple permutation [1]In a permutation, all the elements of a set are used, and what changes from one arrangement to another is the order, that is, the position of the elements.The number of possible permutations of \(n\) distinct elements is given by:\[ P_n = n! \]\[ P_n = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 \]This is the multiplicative principle itself: for the first position there are \(n\) choices; for the second, one fewer, because one element has already been used; and so on, until a single element is left for the last position. That is why the number of possibilities drops by 1 each time and the result is a factorial.ExamplesIn an election for class representative with 3 candidates (V, C and F), there are 6 possible results for the ranking (1st, 2nd and 3rd place), since 3! = 6. See the possible results of this election below.Result 1Result 2Result 3Result 4Result 5Result 6VCFVFCCVFCFVFCVFVCIn how many distinct ways can we line up the models Ana, Carla, Maria, Paula and Silvia for a promotional photo?\[ P_5 = 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 \]In how many distinct ways can we put six men and six women in single file, starting with a man and ending with a woman?If the line starts with a man and ends with a woman, we have:six possible men for the first position;six possible women for the last position;the remaining 10 people permuted in the 10 middle positions: \(10!\).\[ 6 \cdot 10! \cdot 6 = 6 \cdot 3{,}628{,}800 \cdot 6 = 130{,}636{,}800 \]Permutation with repetitionWhen some elements repeat, swapping two identical elements does not create a new arrangement. That is why we divide the simple permutation by the permutations of each group of repeated elements:\[ P_n^{n_1, n_2, \ldots} = \frac{n!}{n_1! \cdot n_2! \cdot n_3! \cdot \ldots} \]\(n\): total number of elements;\(n_1, n_2, \ldots\): how many times each element repeats.ExamplesHow many anagrams can be formed with the word CASA (Portuguese for house)?The word CASA has 4 letters (\(n = 4\)), and the letter A appears twice (\(n_1 = 2\)).\[ P_4^{2} = \frac{4!}{2!} = \frac{4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1} = \frac{24}{2} = 12 \]CASAACSAASCAASACSCAACSAAAASCAACSCAASSAACSACAACASHow many anagrams can be formed with the word COPACABANA?The word COPACABANA has 10 letters, with four letters A and two letters C.\[ P_{10}^{4,2} = \frac{10!}{4! \cdot 2!} = \frac{3{,}628{,}800}{24 \cdot 2} = 75{,}600 \]How many anagrams does the word BANANA have?Answer: 60 — there are 6 letters, with A repeated 3 times and N repeated 2 times: 6!/(3! · 2!) = 720/12 = 60. 720 would be the answer if all the letters were different.Simple arrangement [2]In a simple arrangement (also called a partial permutation), we choose \(p\) elements out of \(n\) distinct elements, and the order in which they appear matters: moving the elements to different positions creates a different arrangement.“In arrangements, order matters!”- Rule to rememberTo find the number of arrangements of \(n\) elements taken \(p\) at a time, we use the formula:\[ A_{n,p} = \frac{n!}{(n-p)!} \]\(n\): number of available elements;\(p\): number of elements in each arrangement.Note that \((n-p)\) is the number of elements left out of the arrangement. In \(n!\), each arrangement appears repeated once for every possible order of the elements left out; that is why we divide by their \((n-p)!\) permutations. In practice, it is the multiplicative principle stopped after \(p\) stages: \(A_{n,p} = n \cdot (n-1) \cdot \ldots \cdot (n-p+1)\).ExamplesHow many two-digit numbers with distinct digits can be formed from the digits 2, 4, 6, 8 and 9?We have a set of 5 elements, from which we choose 2. Order matters here, because 24 is different from 42.\[ A_{5,2} = \frac{5!}{(5-2)!} = \frac{5!}{3!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1} = 20 \]Flávia, Maria, Gustavo and Pedro are taking part in a competition with prizes for the top three places (1st, 2nd and 3rd). How many possible prize outcomes are there?Number of participants in the competition: \(n = 4\)Number of people in each arrangement (prize places): \(p = 3\)\[ A_{4,3} = \frac{4!}{(4-3)!} = \frac{4!}{1!} = \frac{4 \cdot 3 \cdot 2 \cdot 1}{1} = 24 \]Simple combinationIn a simple combination, we choose \(p\) elements out of \(n\) distinct elements, but the order of the chosen elements does not matter: changing the order does not create a new group, only replacing an element does.“In combinations, the order of the elements is irrelevant!”- Rule to rememberThe formula is:\[ C_{n,p} = \frac{n!}{p!\,(n-p)!} \]\(n\): number of available elements;\(p\): number of elements in each group.As in the arrangement, we divide by \((n-p)!\) because of the elements left out. In addition, since the order of the \(p\) chosen elements is irrelevant, each group would appear repeated \(p!\) times (once for each order), so we also divide by \(p!\). In other words:\[ C_{n,p} = \frac{A_{n,p}}{p!} \]ExamplesIn how many different ways can I choose 2 marbles, out of 10 marbles of different colors, to put in a small bag?\(n = 10\)\(p = 2\)The order in which the marbles go into the bag does not matter.\[ C_{10,2} = \frac{10!}{2!\,(10-2)!} = \frac{10 \cdot 9 \cdot 8!}{2! \cdot 8!} = \frac{10 \cdot 9}{2} = 45 \]João is packing for a trip and will take two pairs of shorts. Knowing that he has five (blue, black, white, brown and striped), in how many different ways can he choose the shorts?We have a set of 5 elements (shorts), from which we choose 2, and it does not matter which pair he picks first: what matters is which two go in the suitcase.Taking the blue and the black is the same as taking the black and the blue. So it is a combination:\[ C_{5,2} = \frac{5!}{2!\,(5-2)!} = \frac{5 \cdot 4 \cdot 3!}{2! \cdot 3!} = \frac{5 \cdot 4}{2} = 10 \]In a class of 10 students, how many different committees of 3 students can be formed?Answer: 120 — a committee has no positions, so order does not matter: C(10,3) = 10!/(3! · 7!) = 720/6 = 120. 720 is the arrangement A(10,3), which would be the answer if the three chosen students held different positions (president, vice-president and secretary).Which of these situations should be solved with a combination rather than an arrangement?Answer: Picking 6 numbers in a Mega-Sena ticket (Brazil's main lottery) — the ticket 05-12-23-34-41-58 is the same in whatever order the numbers are marked. In the other three situations, changing the order produces a different result (another password, another podium, another ticket of candidates).ExercisesTo go to the club, Júnior wants to wear a T-shirt, a pair of shorts and a pair of sneakers. Knowing that he has six T-shirts, four pairs of shorts and three pairs of sneakers, in how many distinct ways can he get dressed?A travel agency offers plane tickets for the São Paulo – Miami route on two airlines. The passenger can also choose between first class, business class and economy class. In how many ways can a passenger make this choice?A dinner will have three parts: starter, main course and dessert. In how many distinct ways can it be put together if there are eight starters, five main courses and four desserts to choose from?A train car has six doors. In how many distinct ways can a passenger enter the train and leave it through a door other than the one he entered?A test has ten multiple-choice questions. In how many distinct ways can the test be answered if each question has five distinct options?With the digits 1, 2, 4, 6, 8 and 9:How many four-digit numbers can we form?How many four-digit numbers with distinct digits can we form?With the digits 2, 3, 4, 5, 6 and 7:How many four-digit numbers with distinct digits start with 3?How many even four-digit numbers with distinct digits can we form?How many three-digit numbers with distinct digits are there?With the digits 0, 1, 2, 3, 4, 5 and 6, how many odd four-digit numbers can we form (digits may repeat)?We want to form numbers divisible by 5 made up of four distinct digits. How many possibilities are there using the digits 0, 1, 2, 3, 4, 5 and 6? (Hint: consider two cases: when the number ends in zero and when it ends in 5.)A thief knows that the combination of a safe is a sequence of three distinct digits. He also knows that the hundreds digit is 4. If the thief takes, on average, 3 minutes to test a possible sequence, what is the maximum time it will take him to open the safe?In a certain city, license plates consist of a sequence of two distinct letters and three digits. How many plates can be made? (Consider an alphabet of 26 letters.)To cope with the growing number of vehicles, it was decided to add one digit to the plates. If the rules for making plates remain the same as in the previous item, what is the new total number of plates?A student is looking for integer solutions of the equation 2x = a + b. Knowing that a ∈ {1, 2, 3, 4, 5} and b ∈ {1, 2, 3, 4, 5}, in how many ways can the student choose a and b to get integer solutions?How many sets of initials can be formed if everyone has only one surname and:exactly one first name?exactly two first names?Brazil's old-style license plates (before the Mercosur standard) had seven symbols: three letters, out of the 26 in the alphabet, followed by four digits.How many distinct plates can we have without the digit zero in the 1st position reserved for digits?Among all possible distinct plates, what percentage have the first two letters equal?Braille is a writing system for the blind in which each character is formed by a matrix of six dots, of which at least one is raised relative to the others. What is the maximum number of distinct characters that can be represented in this writing system?Find how many three-digit numbers, multiples of 5, have a hundreds digit in {1, 2, 3, 4} and the other digits in {0, 5, 6, 7, 8, 9}.Find the number of anagrams that can be formed with the letters of the word ALEMANHA (Portuguese for Germany).When filling in a lottery card with 13 columns, André chose the following marks: in 4 columns he marked the number 1, in 6 columns the number 2 and in 3 columns the number 3. In how many distinct ways can André mark the cards?In a futsal tournament, a team got 8 wins, 5 draws and 2 losses in the 15 matches played. In how many distinct ways could these results have occurred?In a test with 20 true-or-false questions, in how many distinct ways can we have twelve T answers and eight F answers?At a company, fifteen employees applied for the positions of financial director and deputy financial director. They will be chosen by individual vote of the members of the company's board. Find in how many distinct ways this choice can be made.A phone number has 8 digits. Find how many phone numbers with all digits different can be formed that start with 2 and end with 8.A prize-draw urn holds ten balls numbered from 0 to 9. Find the number of possible outcomes of a draw, without replacing the balls, in which the prize is a sequence of 6 digits.A classroom has 12 female students, one of them named Carla, and 8 male students, one of them named Luiz. We want to form committees of 5 female and 4 male students. Find the number of committees in which Carla and Luiz both take part.A soccer team has 11 players: 1 goalkeeper, 4 defenders, 4 midfielders and 2 forwards. Given that the coach has 3 goalkeepers, 8 defenders, 10 midfielders and 6 forwards available, find the number of possible ways to form this team.A scientific researcher needs to choose three guinea pigs from a group of eight. Find the number of ways in which he can make the choice.In basketball, each team takes the court with five players. A team has 12 players, 2 of whom are guaranteed starters. Find the number of lineups the coach can form with the other players to complete the five, given that they can play any position.Answer key [3]726160305¹⁰ = 9,765,625a) 1,296; b) 360a) 60; b) 180648882220216 min, or 3 h 36 mina) 650,000; b) 6,500,00013a) 676; b) 17,576a) 158,184,000; b) 3.85%63486,72060,060135,135125,97021020,160151,20011,550661,50056120References[1] https://www.infoescola.com/matematica/analise-combinatoria/[2] http://sabermatematica.com.br/a-diferenca-entre-arranjo-e-combinacao.html[3] http://exercicios.brasilescola.uol.com.br/exercicios-matematica/exercicios-sobre-permutacao-com-elementos-repetidos.htm
ردود الفعل
0
0 تعليقات
كن أول من يعلق
لا شيء هنا بعد.