COMBINATORICS
Lesson objectives:
- Find out what combinatorics studies
- Find out how combinatorics arose
- Study combinatorics formulas and learn how to apply them when solving problems
The birth of combinatorics as a branch of mathematics is associated with the works of Blaise Pascal and Pierre Fermat on the theory of gambling.
Blaise Pascal
Pierre Fermat
A great contribution to the development of combinatorial methods was made by G.V. Leibniz, J. Bernoulli and L. Euler.
G.V. Leibniz
L. Euler.
J. Bernoulli
Lemma. Let the set A have m elements, and the set B have n elements. Then the number of all distinct pairs (a,b), where a\in A,b\in B will be equal to mn. Proof. Indeed, with one element from the set A we can make n such different pairs, and in total there are m elements in the set A.
Placements, permutations, combinations Let us have a set of three elements a,b,c. In what ways can we choose two of these elements? ab,ac,bc,ba,ca,cb.
Rearrangements We will rearrange them in all possible ways (the number of objects remains unchanged, only their order changes). The resulting combinations are called permutations, and their number is equal to Pn = n! =1 · 2 · 3 · ... · ( n-1) n
The symbol n! is called factorial and denotes the product of all integers from 1 to n. By definition, it is believed that 0!=1 1!=1 An example of all permutations of n=3 objects (different figures) is in the picture. According to the formula, there should be exactly P3=3!=1⋅2⋅3=6 , and this is what happens.
As the number of objects increases, the number of permutations grows very quickly and it becomes difficult to depict them clearly. For example, the number of permutations of 10 objects is already 3628800 (more than 3 million!).
Placements Let there be n different objects. We will select m objects from them and rearrange them in all possible ways (that is, both the composition of the selected objects and their order change). The resulting combinations are called placements of n objects by m, and their number is Aⁿm =n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)
Definition. By placing a set of n different elements into m elements (m ≤ n) are called combinations , which are composed of given n elements by m elements and differ either in the elements themselves or in the order of the elements.
Combinations Let there be n different objects. We will select m objects from them in every possible way (that is, the composition of the selected objects changes, but the order is not important). The resulting combinations are called combinations of n objects by m, and their number is Cmn=n!(n−m)!⋅m!
An example of all combinations of n=3 objects (different figures) by m=2 is in the picture below. According to the formula, there should be exactly C23=3!(3−2)!⋅2!:3!=3. It is clear that there are always fewer combinations than placements (since the order is important for placements, but not for combinations), and specifically in m! times, that is, the connection formula is correct: Amn=Cmn⋅Pm.
Method 1. There are 2 people participating in one game, therefore, you need to calculate how many ways you can select 2 people out of 15, and the order in such pairs is not important. Let's use the formula to find the number of combinations (samples that differ only in composition) of n different elements of m elements each
n!= 1⋅ 2 ⋅3⋅...⋅ n , with n=2, m=13.
Method 2. The first player played 14 games (2nd, 3rd, 4th, and so on until 15th), the 2nd player played 13 games (3rd, 4th, etc. until 15th). well, we exclude the fact that there was already a game with the first), 3rd player - 12 games, 4th - 11 games, 5 - 10 games, 6 - 9 games, 7 - 8 games, 8 - 7 games,
and the 15th one has already played with everyone.
Total: 14+13+12+11+10+9+8+7+6+5+4+3+2+1=105 games
ANSWER. 105 games.
Mathematics teacher Svetlana Valerievna Aksenova
Bugrovskaya secondary school, Vsevolozhsk district, Leningrad region
Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
The presentation on the topic "Discrete analysis. Combinatorics. Permutations" can be downloaded absolutely free of charge on our website. Project subject: Computer science. Colorful slides and illustrations will help you engage your classmates or audience. To view the content, use the player, or if you want to download the report, click on the corresponding text under the player. The presentation contains 24 slide(s).
Presentation slides
Slide 1
Discrete Analysis
Lecture 3 Combinatorics. Rearrangements
Slide 2
Rearrangements
Let a set of n elements be given. The ordering of these elements is called permutation. Sometimes they add “of n elements”. Usually one basic or natural ordering is distinguished, which is called a trivial permutation. The elements of set A themselves do not interest us. Often the elements are integers from 1 to n or from 0 to n-1. Let us denote the set of permutations of n elements by Pn and its cardinality by Pn. Let's ask the same three questions: what is Pn equal, how to iterate through the elements of Pn, how to renumber them.
Slide 3
Theorem on the number of permutations
The number of permutations of n elements is n! - the product of numbers from 1 to n. (n! read n-factorial) Proof. By induction. For n=1 the formula is obviously correct. Let it be true for n-1, let us prove that it is also true for n. The first element of the ordering can be selected in n ways, and the rest can be assigned to the selected first element in ways. Therefore, the formula Pn= Pn-1n is correct. If Pn-1=(n-1)!, then Pn=n!
Slide 4
Numbering of permutations
To number permutations, we map the set Pn one-to-one into another set Tn, on which it will be much easier to introduce numbering, and then for any element pPn we take the number of its image in Tn as its number. The set Tn is a direct product of several numerical segments Tn =(0:(n-1))(0:(n-2) … (0). That is, each element of Tn is a set of non-negative numbers i1, i2, …, in-1, in, and ikn-k.
Slide 5
Display
Let's take a permutation and write the trivial permutation next to it. As the first index, we take the place of the first element (counting from zero) in the trivial permutation. Instead of a trivial permutation, let's write down the string of remaining characters. As the second index we take the place of the second element of the permutation in this row. Let's repeat the process until the end. Obviously, the kth index will be less than the length of the kth string, and the last index will be equal to zero. Let's look at this process with an example.
Slide 6
Display example
0 1 2 3 4 5 6 Index c a d f g b e a b c d e f g 2 2 a d f g b e a b d e f g 0 2 0 d f g b e b d e f g 1 2 0 1 f g b e b e f g 2 2 0 1 2 g b e b e g 2 2 0 1 2 2 b e b e 0 2 0 1 2 2 e e 0 2 0 1 2 2 0 0 Obviously, this process is reversible and the inverse mapping will construct the original permutation from a set of indices.
Slide 7
Numbering of the set Tn
Any direct product of ordered sets can be considered as a number system with a variable base. Recall the seconds example from the first lecture, or consider some old size scale: 1 yard = 3 feet, 1 foot = 12 inches, 1 inch = 12 lines, 1 line = 6 points. (2, 0, 4, 2, 3) = 2 yards 0 feet 4 inches 2 lines 3 points, how many points is that? You need to count (this is called the Horner scheme) (((2 3+0) 12+4) 12+2) 6+3
Slide 8
Numbering of the set Tn - 2
We prefer to write the formula # that finds the number for a set of indices i1, i2, …, in-1, in in the form of recurrent expressions #(i1, i2, …, in) = a(i1, i2, …, in-1, n-1); a(i1, i2, …, ik,k) = a(i1, i2, …, ik-1,k-1)(n-k+1)+ ik; a(empty,0) = 0; According to this formula #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). We have a(2,1)=2; a(2,0,2) = 26+0=12; a(2,0,1,3)=125+1=61; a(2,0,1,2,4) =614+2=246; a(2,0,1,2,2,5) =2463+2=740; a(2,0,1,2,2,0,6) =7402+0=1480;
Slide 9
Iterating over index sets
Based on the above, it is simple to enumerate permutations: you need to enumerate all sets of indices from and for each set build a corresponding permutation. To enumerate sets of indices, note that in fact each set is a record of a number in a special number system with a variable base (the system is called factorial). The rules for adding 1 in this system are almost as simple as in the binary system: moving from the last digit, try to add 1 to the current digit. If this is possible, then stop adding 1. If this is not possible, write a zero to the bit and move on to the next bit.
Slide 10
Enumerating sets of indexes - 2
Let's look at an example: 7 6 5 4 3 2 1 These are variable bases 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Note that in 3 4 4 2 2 1 0 each line the beginning is 3 4 4 3 0 0 0 same as in the previous one, 3 4 4 3 0 1 0 then comes the element, strictly 3 4 4 3 1 0 0 larger, . . . , and 3 4 4 3 1 1 0 what follows is not significant. 3 4 4 3 2 0 0 This means that each line 3 4 4 3 2 1 0 is lexicographically greater than 3 5 0 0 0 0 0 the previous one. 3 5 0 0 0 1 0
Slide 11
Theorem on lexicographic enumeration of permutations
The described algorithm iterates through permutations in lexicographic increasing order. Proof. It is enough for us to show that if we have two sets of indices I1 and I2, and I1 is lexicographically prior to I2, then the permutation (I1) is lexicographically prior to (I2). These permutations are formed sequentially, and as long as I1 and I2 coincide, their permutations also coincide. And a larger index value corresponds to a larger element.
Slide 12
Direct algorithm for lexicographic enumeration of permutations
Let's take any permutation p and directly find the next one lexicographically. Let's take the beginning - the first k elements. Among its extensions, there is a minimal one, in which all elements are arranged in ascending order, and a maximum, in which all elements are arranged in descending order. For example, in the permutation p =(4, 2, 1, 7, 3, 6, 5) all continuations for (4, 2, 1) lie between (3, 5, 6, 7) and (7, 6, 5, 3). The existing continuation is less than the maximum, and the 3rd element still does not need to be changed. And the 4th too. And the 5th one needs to be changed. To do this, from the remaining elements you need to take the next one in order, put it 5th and assign a minimal continuation. You get (4, 2, 1, 7, 5, 3, 6).
Slide 13
Direct algorithm for lexicographic enumeration of permutations - 2
Let us write down the following several permutations. (4, 2, 1, 7, 5, 3, 6) (4, 2, 1, 7, 5, 6, 3) (4, 2, 1, 7, 6, 5, 3) (4, 2, 3, 1, 5, 6, 7) (4, 2, 3, 1, 5, 7, 6) (4, 2, 3, 1, 6, 5, 7) (4, 2, 3, 1, 6 , 7, 5) (4, 2, 3, 1, 7, 5, 6) (4, 2, 3, 1, 7, 6, 5) (4, 2, 3, 5, 1, 6, 7)
Slide 14
Formal description of the algorithm
Operating state: Permutation p and Boolean attribute isActive. Initial state: A trivial permutation is written in and isActive = True. Standard step: If isActive, return the permutation as the result. Moving from the end, find the largest monotonically decreasing suffix in the permutation. Let k be the position before the suffix. Put isActive:= (k > 0). If isActive, then find the smallest element in the suffix that is greater than pk, swap it with pk, and then “flip” the suffix.
Slide 15
Another algorithm for enumerating permutations
Let us now try to sort out the permutations so that two successive permutations differ little from each other. How little? One elementary transposition in which two adjacent elements are swapped. Is it possible? Let's show a schematic diagram of such an algorithm; we will be interested in it. Imagine n-1 elementary “mechanisms”, each of which moves its element within the set. At each step, the mechanism makes a shift to the left or right. The direction changes when the element reaches the edge. Changing direction takes one step, during which the next mechanism takes a step, which, however, can also change direction.
Slide 16
Another algorithm for enumerating permutations -2
Let's see an example. 1 2 3 4 5 Whose move a b c d e a c d a b e a b a c d e a c d b a e a b c a d e a c d b e a b b c d a e a c d e b a a b c d e a b c d e a b a c b d e a a c d a e b a c b d a e a c a d e b a c b a d e a a c d e b c a b d e a a d c e b a a c b d e b d a c e b a a c d b e a d c a e b a c a d b e a d c e a b a
Slide 17
Enumeration of permutations. 1
function ExistsNextPerm(var kCh: integer): Boolean; var iV,iP,iVC,iPC: integer; begin result:= False; for iV:= nV downto 2 do if count
Slide 18
Minimum sum of pairwise products problem
Let two sets of n numbers each be given, say, (ak|k1:n) and (bk|k1:n) . These numbers are divided into pairs (ak,bk) and the sum of their pairwise products k1:n akbk is calculated. You can change the numbering (ak) and (bk). You need to choose a numbering that minimizes the amount. In this problem, you can fix some numberings (ak) and (bk) and look for a permutation for which the minimum sum k1:n akb(k) is achieved. We will choose numberings when (ak) are in ascending order and (bk) are in descending order.
Slide 19
Theorem on the minimum sum of pairwise products
The minimum sum of pairwise products is achieved on a trivial permutation. Proof. Let us assume that there are two indices k and r such that ak 0, i.e. ar br + ak bk > ar bk + ak br . In our numbering (ak) are arranged in ascending order. If (bk) are not arranged in ascending order, then there is a pair k and r, as stated above. By rearranging bk and br for this pair, we will reduce the value of the sum. This means that in the optimal solution (bk) are in ascending order. We will encounter this simple theorem several times later.
Slide 20
Maximum Increasing Subsequence Problem
Given a sequence (ak|k1:n) of numbers of length n. It is required to find its sequence of the greatest length in which the numbers (ak) would appear in ascending order. For example, in the sequence 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9, the maximum subsequence will be 2, 11, 14, 16, 17, 25, 37, 41 This problem is related to permutations in that the original sequence can be a permutation. We will limit ourselves to showing how this problem is solved, and we will provide the formalization and justification of the algorithm to the listeners.
Slide 21
Finding the maximum increasing subsequence
We will, as economically as possible, divide ours into descending sequences (the example has been changed) 9 12 11 14 18 16 6 17 15 13 37 19 21 8 7 5 9 6 5 12 11 8 7 14 13 18 16 15 17 37 19 21 Each subsequent number is written in the very top of the lines, where it will not disturb the order. Let's take the number from the bottom line, 21. Why is it in the 8th line? He is hindered by 19. And the number 19 is hindered by 17. And he is 16. Etc. The sequence 9, 11, 14, 16, 17, 19, 21 is increasing and has a length of 7. Any sequence of greater length contains two numbers from the same line ( Dirichlet principle) and cannot be increasing.
Slide 22
Minimum number of inversions problem
Given a sequence (ak|k1:n) of numbers of length n. Let us call an inversion an in-place mirror image of any of its substrings—a continuous subsequence. It is required to arrange the elements of the sequence in ascending order in a minimum number of inversions. For example, the permutation “solid” can be transformed as follows (the red letters have been rearranged, the big ones are already in place)
Slide 23
Exam questions
Rearrangements. Their enumeration and numbering. The problem of minimizing the scalar product. The greatest increasing subsequence problem.
Slide 24
1. Two-way transition permutation number 2. Find a permutation distant from the given one by a given number of steps. 3. Enumeration of permutations by elementary transpositions. 4. Run an example for the problem of minimizing the scalar product.
Tips for making a good presentation or project report
- Try to involve the audience in the story, set up interaction with the audience using leading questions, a game part, do not be afraid to joke and smile sincerely (where appropriate).
- Try to explain the slide in your own words, add additional interesting facts; you don’t just need to read the information from the slides, the audience can read it themselves.
- There is no need to overload the slides of your project with text blocks; more illustrations and a minimum of text will better convey information and attract attention. The slide should contain only key information; the rest is best told to the audience orally.
- The text must be well readable, otherwise the audience will not be able to see the information being presented, will be greatly distracted from the story, trying to at least make out something, or will completely lose all interest. To do this, you need to choose the right font, taking into account where and how the presentation will be broadcast, and also choose the right combination of background and text.
- It is important to rehearse your report, think about how you will greet the audience, what you will say first, and how you will end the presentation. All comes with experience.
- Choose the right outfit, because... The speaker's clothing also plays a big role in the perception of his speech.
- Try to speak confidently, smoothly and coherently.
- Try to enjoy the performance, then you will be more at ease and less nervous.
The presentation “Permutations” presents educational material for a school lesson on this topic. The presentation contains a definition of permutations, visual examples for understanding the meaning of this operation, a description of the mathematical apparatus for solving problems with permutations, and examples of problem solving. The purpose of the presentation is to convey educational material to students in a convenient, understandable form, to promote better understanding and memorization.
The presentation uses special techniques to help the teacher explain a new topic. The learning materials are pre-structured. Using animation effects, they present examples and problems, emphasizing the important features of the examples and problems during the demonstration. Important concepts are highlighted in color, making them easier to remember.
After introducing the topic of the lesson, students are shown the definition of permutations as the simplest combinations that can be made from a certain set of elements. The text is highlighted with an exclamation mark as important to remember.
The following shows an example of permutations of colored pencils that can be placed in different orders. To do this, pencils are signed with the first letter of their color name: S, K, Zh. Using an animated representation, options for placing these pencils in order are clearly demonstrated. On one slide, blue pencils are placed first, and next to them there are two placement options - red and yellow, yellow and red. The next slide shows options for placing pencils after red - blue and yellow, yellow and blue. The last possible options are, after yellow, red and blue, blue and red. After a visual demonstration, the performed operations are signed as permutations of three elements. A more precise definition of a permutation of three elements is given on a separate slide 7. In the frame for memorization, the text is highlighted that each arrangement of these elements in a certain order will be called a permutation of three elements.
Slide 8 shows the designation for permutations of n elements - P n. It is indicated that permutations of three elements were examined in detail using the example of pencils, and it is obvious that there will be 6 such permutations. The mathematical notation of the number of permutations is marked on the slide: P 3 = 6. The screen further notes that there is a combinatorial multiplication rule to find the number of permutations of three elements.
The next slide breaks down the permutation procedure into steps to arrive at a rule for finding the number of permutations. It is indicated that for calculation it is necessary to put any of the three elements in first place. There are two possibilities for him to select the second element. The only option left is to select the third element. This means that the number of permutations of 3 elements will be found by multiplying 3.2.1=6. We get the total number of possible permutations. Similar to the process of searching for permutation options, variability for n elements is considered.
Let there be some set of n elements. For it, one of n-1 elements is placed in second place, one of n-2 elements is placed in third place, etc. Thus, we can derive a general rule for finding the number of permutations of n elements: P n =n(n-1)(n-2)....3.2.1.
On slide 11 the formula P n is displayed on the screen in the form P n =1.2.3.….(n-2)(n-1)n. Thus, the concept of factorial is introduced, the designation of which is demonstrated below the formula: n!. Examples of finding the factorial of a certain number are considered: 3!=1.2.3=6, and also 6!=1.2.3.4.5.6=720. It is also stated that 1!=1. The text of the general rule for finding the number of permutations as n factorial is located at the bottom of the slide.
Next, we propose to consider several problems to find the number of permutations. On slide 12, a problem is proposed to be solved: finding the number of ways to decompose seven balls into seven cells. It is indicated that the solution is to calculate the number of permutations of 7 elements: P 7 =7!=5040.
Slide 13 discusses the solution to the problem of finding the number of four-digit numbers that are made up of 0,1,2,3, while the numbers are not repeated in the same number. The solution is provided in two stages - first, the number of all permutations of 4 elements is found, and then the number of permutations in which numbers with 0 in front is subtracted, so numbers starting with zero will not be four-digit. Thus, the solution comes down to calculating P 4 -P 3 =4!-3!=18. That is, there are 18 options for the formation of such numbers.
The last slide examines the solution to a problem in which it is proposed to find the number of ways in which 9 plates can be arranged, 4 of which are red, so that the red ones are located next to each other. The main difficulty in solving this problem is to understand that the red plates in these permutations must be taken as one. Thus, the solution comes down to finding the product P 6 .P 4 =6!.4!=17280.
The presentation “Permutations” is intended to visually accompany the teacher’s explanation on the topic “Permutations”. A detailed, understandable presentation of educational material can also be useful during distance learning, and the tasks considered will help the student figure out the solution on their own.
Fundamentals of combinatorics.
Placements, rearrangements,
combinations.
Naughty Monkey
Donkey,
Goat,
Yes, clubfooted Mishka
We started playing a quartet
Stop, brothers, stop! –
Monkey shouts, - wait!
How should the music go?
After all, you’re not sitting like that...
And this way and that they changed seats - again the music is not going well.
Now they're getting even more intense than ever
And disputes
Who and how to sit...
know:
- definitions of the three most important concepts of combinatorics:
- placement of n elements by m;
- combinations of n elements, m each;
- permutations of n elements;
- basic combinatorial formulas
- distinguish tasks of “permutations”, “combinations”, “placements” from each other;
- apply basic combinatorial formulas when solving simple combinatorial problems.
be able to:
a bunch of
A set is characterized by the union of some homogeneous objects into one whole.
The objects that form a set are called set elements.
We will write a set by arranging its elements in curly brackets ( a, b, c, … , e, f}.
In a set, the order of the elements does not matter, so ( a, b} = {b, a}.
A set that does not contain a single element is called empty set and is indicated by the symbol ø.
a bunch of
If each element of the set A is an element of set B, then we say that the set A is a subset of the set IN.
A bunch of ( a, b) is a subset of the set ( a, b, c, … , e, f}.
Designated
List possible options for a subset of the set ( 3 , 4 , 5 , 7, 9 }.
Combinatorics is a branch of mathematics that studies questions about how many different combinations, subject to certain conditions, can be made from elements belonging to a given set.
Combinatorics is an important branch of mathematics that studies the patterns of arrangement, ordering, selection and distribution of elements from a fixed set.
SUMMATION RULE
If two mutually exclusive actions can be performed according k And m ways, then one of these actions can be performed k+m ways.
Example No. 1
You can get from city A to city B by 12 trains, 3 planes, 23 buses. In how many ways can you get from city A to city B?
Solution
Example No. 2
There are n different colored balls in a box. We randomly take out one ball. In how many ways can this be done?
Solution. Certainly, n ways.
Now these n balls are distributed over two boxes: In the first m balls, in the second k. We randomly take one ball out of some box. How many different ways can this be done?
Solution.
You can pull a ball out of the first box m in various ways, from the second k in various ways, in total N = m + k ways.
PRODUCT RULE
Let two actions performed one after the other be carried out in accordance k And m ways Then both of them can be done k∙m ways.
Example No. 3
8 hockey teams take part in the tournament. How many ways are there to distribute first, second and third places?
Solution
Example No. 4
How many two-digit numbers can you write in the decimal number system?
Solution. Since the number is two-digit, then the number of tens ( m) can take one of nine values: 1,2,3,4,5,6,7,8,9. Number of units ( k) can take the same values and can, in addition, be equal to zero. It follows that m= 9, a k= 10. In total we get two-digit numbers
N= m · k= 9·10 =90.
Example No. 5
There are 14 girls and 6 boys in the student group. In how many ways can two students of the same sex be selected to complete different tasks?
Solution. According to the multiplication rule, two girls can be chosen in 14 · 13 = 182 ways, and two boys can be chosen in 6 · 5 = 30 ways. You should choose two students of the same gender: two male or female students. According to the rule of addition of such selection methods, there will be
N =182 + 30 = 212.
Connection types
Sets of elements are called connections.
There are three types of connections:
- permutations from n elements;
- accommodation from n elements by m;
- combinations of n elements by m (m < n).
Definition: Permutation of n elements is any ordered set of n elements.
In other words, this is a set for which it is indicated which element is in the first place, which is in the second, which is in the third, ..., which is in the nth place.
PERmutations
Rearrangements- these are connections according to n elements from given elements that differ from one another in the order of the elements.
The number of permutations of n elements is denoted by Pn.
Рn = n · ( n- 1) · ( n– 2) · … · 2 · 1 = n!
Definition:
Let n- natural number. Through n! (read "en factorial") denotes a number equal to the product of all natural numbers 1 from to n:
n! = 1 · 2 · 3 · ... · n.
If n= 0, by definition it is assumed: 0! = 1.
FACTORIAL
Example No. 6
Let's find the values of the following expressions: 1! 2! 3!
Example No. 7
What is equal to
A) R 5 ;
b) R 3.
Example No. 8
Simplify
b) 12! · 13 · 14
V) κ ! · ( κ + 1)
Example No. 9
In how many ways can the 8 participants in the final race be arranged on eight treadmills?
Solution.
R 8=8! = 8 7 6 5 4 3 2 1 =40320
ACCOMMODATIONS
Definition. Accommodation from n elements of m is any ordered set of m elements, consisting of elements n element set.
Number of placements from m elements by n stand for:
calculated by the formula:
Example No. 9
11th grade students study 9 academic subjects. You can put 4 different subjects in your class schedule for one day. How many different ways are there to schedule one day?
Solution.
We have a 9-element set, the elements of which are educational subjects. When creating a schedule, we will select a 4-element subset (of lessons) and set the order in it. The number of such methods is equal to the number of placements from nine to four ( m=9, n=4) that is A 94:
Example No. 10
In how many ways can a prefect and an assistant prefect be selected from a class of 24 students?
Solution.
We have a 24-element set, the elements of which are students of the class. When electing a prefect and an assistant prefect, we will select a 2-element subset (student) and set the order in it. The number of such methods is equal to the number of placements from nine to four ( m=24, n=2), that is A 242:
COMBINATIONS
Definition. A combination without repetition of n elements by m- called any m elemental subset n-element set
The number of combinations of n elements by m is denoted by
and calculated using the formula:
Example No. 11
In how many ways can two attendants be selected from a class of 24 students?
Solution.
n =24, m=2
COMBINATIONS
ACCOMMODATIONS
PERmutations
Рn = n!
Determine what type of connections the task belongs to.
1. In how many ways can you schedule one school day with 5 different lessons?
2. There are 12 students in class 9B. In how many ways can you form a team of 4 people to participate in the Mathematical Olympiad?
Is the order of elements in a connection taken into account?
Are all elements included in the connection?
Conclusion: permutation
Is the order of elements in a connection taken into account?
Are all elements included in the connection?
(no answer needed for this question)
Conclusion: combinations
3. How many different two-digit numbers are there in which the numbers 1, 2, 3, 4, 5, 6 can be used if the numbers in the number must be different?
Is the order of elements in a connection taken into account?
Are all elements included in the connection?
Conclusion: placement
Naughty Monkey
Yes, clubfooted Mishka
We started playing a quartet
Stop, brothers, stop! –
Monkey shouts, - wait!
How should the music go?
After all, you’re not sitting like that...
And this way and that they changed seats - again the music is not going well.
Now they're getting even more intense than ever
Who and how to sit...
How many different arrangements of musicians are possible?
Solution.
Is the order of elements in a connection taken into account?
Are all elements included in the connection?
Conclusion: permutation
Рn = n! =n · ( n- 1) · ( n– 2) · … · 2 · 1
P4 = 4! = 4 3 2 1=24
“Sooner or later, every correct mathematical idea finds application in one thing or another”?
permutations
accommodation
combination
Results of problem solving
HOMEWORK
Learn notes and formulas.
S. 321 No. 1062
Permutations are combinations made up of the same elements and differing in the order in which they appear. The number of all possible permutations of elements is denoted by P n, and can be calculated using the formula: Permutation formula: P n =n! When permuting, the number of objects remains unchanged, only their order changes. As the number of objects increases, the number of permutations grows very quickly and it becomes difficult to depict them clearly.
Problem 1. Seven teams participate in the tournament. How many options for distributing seats between them are possible? P 7 =7!=1*2*3*4*5*6*7=5040 Answer: 5040 Problem 2. In how many ways can 10 people sit at a round table? R 10 =10! = = 1*2*3*4*5*6*7*8*9*10 = Answer:
Let there be n different objects. We will select m objects from them and rearrange them in all possible ways among themselves. The resulting combinations are called placements of n objects by m, and their number is equal to: During placements, both the composition of the selected objects and their order change. Placement formula:
Problem: In how many ways can three vouchers to one sanatorium be distributed among five people? Since the vouchers are provided to one sanatorium, the distribution options differ from each other by at least one person. Therefore, the number of distribution methods Answer: 10 methods.
Task: There are 12 people working in the workshop: 5 women and 7 men. In how many ways can a team of 7 people be formed so that there are 3 women in it? Out of five women, three must be selected, hence the number of selection methods. Since it is required to select four men out of seven, then the number of ways to select men Answer: 350
