In combinatorics, they study questions about how many combinations of a certain type can be made from given objects (elements).
The birth of combinatorics as a branch is associated with the works of B. Pascal and P. Fermat on the theory gambling. A great contribution to the development of combinatorial methods was made by G.V. Leibniz, J. Bernoulli and L. Euler.
The French philosopher, writer, mathematician and physicist Blaise Pascal (1623–1662) showed his outstanding math skills. Pascal's range of mathematical interests was very diverse. Pascal proved one thing
from the basic theorems of projective geometry (Pascal's theorem), designed a summing machine (Pascal's adding machine), gave a method for calculating binomial coefficients (Pascal's triangle), was the first to precisely define and apply the method for proof mathematical induction, made a significant step in the development of infinitesimal analysis, played important role in the origins of probability theory. In hydrostatics, Pascal established its fundamental law (Pascal's law). Pascal's “Letters to a Provincial” was a masterpiece of French classical prose.
Gottfried Wilhelm Leibniz (1646–1716) was a German philosopher, mathematician, physicist and inventor, lawyer, historian, and linguist. In mathematics, along with I. Newton, he developed differential and integral calculus. Important Contribution contributed to combinatorics. His name, in particular, is associated with number-theoretic problems.
Gottfried Wilhelm Leibniz had little impressive appearance and therefore gave the impression of a rather plain-looking person. One day in Paris he went into bookstore in the hope of purchasing a book by a philosopher friend of his. When a visitor asked about this book, the bookseller, having examined him from head to toe, mockingly said: “Why do you need it? Are you really capable of reading such books?” Before the scientist had time to answer, the author of the book himself entered the shop with the words: “Greetings and respect to the Great Leibniz!” The seller could not understand that this was really the famous Leibniz, whose books were in great demand among scientists.
In the future, the following will play an important role
Lemma. Let in a set of elements, and in a set - elements. Then the number of all distinct pairs where will be equal to .
Proof. Indeed, with one element from a set we can make such different pairs, and in total in a set of elements.
Placements, permutations, combinations
Let us have a set of three elements. In what ways can we select two of these elements? .
Definition. Placements of many of various elements By elements are combinations that are made up of given elements by > elements and differ either in the elements themselves or in the order of the elements.
The number of all placements of a set of elements by elements is denoted by (from initial letter French word“arrangement”, which means placement), where and .
Theorem. The number of placements of a set of elements by elements is equal to
Proof. Let's say we have elements. Let be possible placements. We will build these placements sequentially. First, let's define the first placement element. From a given set of elements it can be selected different ways. After selecting the first element, there are still ways to select the second element, etc. Since each such choice gives a new placement, all these choices can be freely combined with each other. Therefore we have:
Example. In how many ways can a flag be composed of three horizontal stripes? various colors, if there is material of five colors?
Solution. The required number of three-band flags:
Definition. A permutation of a set of elements is the arrangement of elements in in a certain order.
Thus, all different permutations of a set of three elements are
The number of all permutations of elements is indicated (from the initial letter of the French word “permutation”, which means “permutation”, “movement”). Therefore, the number of all various permutations calculated by the formula
Example. In how many ways can the rooks be placed on the chessboard so that they do not attack each other?
Solution. The required number of rooks
A-priory!
Definition. Combinations of different elements by elements are combinations that are made up of given elements by elements and differ in at least one element (in other words, -element subsets of a given set of elements).
As you can see, in combinations, unlike placements, the order of elements is not taken into account. The number of all combinations of elements, elements in each, is indicated (from the initial letter of the French word “combinasion”, which means “combination”).
Numbers
All combinations from a set of two are .
Properties of numbers (\sf C)_n^k
Indeed, each -element subset of a given -element set corresponds to one and only one -element subset of the same set.
Indeed, we can select subsets of the elements in the following way: fix one element; the number of -element subsets containing this element is equal to ; the number of -element subsets not containing this element is equal to .
Pascal's triangle
In this triangle, the extreme numbers in each row are equal to 1, and each non-extreme number is equal to the sum of the two numbers above it from the previous row. Thus, this triangle allows you to calculate numbers.
Theorem.
Proof. Let's consider a set of elements and solve the following problem in two ways: how many sequences can be made from the elements of a given
sets in each of which no element occurs twice?
1 way. We select the first member of the sequence, then the second, third, etc. member
Method 2. Let's first select elements from a given set, and then arrange them in some order
Multiply the numerator and denominator of this fraction by:
Example. In how many ways can you choose 5 numbers out of 36 in the game “Sportloto”?
Required number of ways
Tasks.
1.
Car license plates consist of 3 letters of the Russian alphabet (33 letters) and 4 numbers. How many different license plate numbers are there?
2.
There are 88 keys on the piano. In how many ways can you produce 6 sounds in succession?
3.
How many six-digit numbers are there that are divisible by 5?
4.
In how many ways can 7 different coins be placed in three pockets?
5.
How many five-digit numbers can you make in decimal notation which number 5 appears at least once?
6.
In how many ways can 20 people be seated? round table, considering the methods the same if they can be obtained one from the other by moving in a circle?
7.
How many five-digit numbers are there divisible by 5 that are not written down? identical numbers?
8.
On checkered paper with a cell side of 1 cm, a circle of radius 100 cm is drawn, which does not pass through the tops of the cells and does not touch the sides of the cells. How many cells can this circle intersect?
9.
In how many ways can numbers be arranged in a row so that the numbers are adjacent and in ascending order?
10.
How many five-digit numbers can be made from digits if each digit can only be used once?
11.
From the word ROT, by rearranging the letters, you can get the following words: TOP, ORT, OTR, TRO, RTO. They are called anagrams. How many anagrams can you make from the word LOGARITHM?
12.
Let's call splitting natural number representation as a sum natural numbers. Here, for example, are all the partitions of a number:
Partitions are considered different if they differ either in numbers or in the order of their terms.
How many different partitions of a number into terms are there?
13.
How many exist three-digit numbers with non-increasing order of digits?
14.
How many four-digit numbers are there with non-increasing digit order?
15.
In how many ways can 17 people be seated in a row so that they end up side by side?
16.
girls and boys are seated randomly in a row of seats. In how many ways can they be seated so that no two girls sit next to each other?
17.
girls and boys are seated randomly in a row of seats. In how many ways can they be seated so that all the girls sit next to each other?
Example. k, o, n are they standing next to each other?
Example. How many permutations of the letters of the word “cone” are there in which the letters k, o, n are they standing next to each other?
Solution.
Given 5 letters, three of which must be next to each other.
Three letters k, o, n can stand next to one of = 3! = 6 ways.
For each method of “gluing” letters k, o, n we get = 3! = 6 ways
Rearrangement of letters, "gluing" u, s.
The total number of different permutations of the letters of the word "cone", in which the letters
k, o, n stand next to each other equals 6 · 6 = 36 permutations - anagrams.
Answer: 36 anagrams.
Example.
Example. Count how many of the images of the letters A, B, C, D, D, E, F, Z, I, K there are letters that have: 1) a vertical axis of symmetry; 2) horizontal axis of symmetry.
Solution.
1) Letters with a vertical axis of symmetry: A, D, F – 3 letters (we do not take into account the thickening of some elements of the letters A, D on the right).
2) Letters with a horizontal axis of symmetry: V, E, ZH, Z, K – 5 letters.
Answer: 1) 3 letters, 2) 5 letters.
Example.
Example. The inhabitants of the planet XO have three letters in their alphabet: A, O, X. Words in the language consist of no more than three letters (a letter in a word can be repeated). What is the largest number of words that can be in the vocabulary of the inhabitants of this planet?
Solution. Words can be one-letter, two-letter or three-letter.
Single letter words: A, O, X – 3 words.
Two-letter words: AO, AH, AA, OO, OA, OX, XX, HA, XO – 9 words (3·3=9, choice of two letters with repetitions).
Three-letter words: 3·9=27 words (choice of three out of three with repetitions, choice of the first letter - three ways; add each of the 9 possible two-letter words to each first letter).
Thus, in the dictionary of the inhabitants of the planet XO there can be a maximum of 3 + 9 + +27 = 39 words.
Answer: 39 words.
Example No. 1.
Example No. 1. All tickets for the literature exam are written on cards with two-digit numbers. Petya randomly chose one card. Describe the following events as certain, impossible or random:
Event A - there is a prime number on the selected card;
Event B – there is a composite number on the card;
Event C – there is a number on the card that is neither prime nor composite;
Event D – there is an even or odd number on the card.
Solution.
Events A and B are random because they may or may not happen.
Event C is impossible: remember the definition of prime and composite numbers.
Event D is reliable, since any two-digit number is either even or odd.
You opened the book to any page and read the first noun you came across. It turned out that: a) the spelling of the selected word contains a vowel; b) the spelling of the selected word contains the letter “o”; c) there are no vowels in the spelling of the selected word; d) there is a soft sign in the spelling of the selected word.
Solution.
a) The event is reliable, since in the Russian language there are no nouns consisting only of consonants.
b) The event is random.
c) An impossible event (see point a)).
d) The event is random.
Example.
Example. Describe the sum of the following incompatible events.
“The queen gave birth in the night, either a son (event A), or a daughter (event B) ...”
Solution.
The queen gave birth to a son or daughter (A B).
Answer: 4 complex events, which are the sum of two incompatible events.
Example. o, t, k, r.
Example. Letters are written on four cards o, t, k, r. The cards were turned over and shuffled. Then they opened these cards at random, one after another, and put them in a row. What is the probability that the word "mole" will come out?
Solution. Outcomes are all possible permutations of four elements ( o, t, k, r); the total number of outcomes is n = = 4! = 24.
Event A – “after opening the cards, the word “mole” will be obtained”; = 1 (only one option for the arrangement of letters - “mole”; = .
Answer:
Example O, On the second T, on third With, on the fourth P.
Example. We took four cards. They wrote a letter on the first one O, On the second T, on third With, on the fourth P. The cards were turned over and shuffled. Then they opened one card after another at random and placed it next to it. What is the probability that the result was the word "stop" or the word "post"?
Solution. Outcomes – all possible permutations of 4 letters; total number of outcomes
n = = 4! = 24.
Event A – “the word “stop” or “post” came out; number of favorable outcomes = 1 (“stop”) + 1 (“post”) = 2 (according to the rule of the sum of mutually exclusive outcomes).
Probability = .
Answer: 1/12.
Example No. 1. We measured the lengths of words (number of letters) in the excerpt below from A.S. Pushkin’s poem “The Bronze Horseman”. It is necessary to construct histograms of the distribution of multiplicities and frequencies, selecting intervals 1-3, 4-6, 7-9 for the sampling option.
“...He is terrible in the surrounding darkness! 6, 2, 1, 9, 4
What a thought on the brow! 5, 4, 2, 4
What power is hidden in him, And what fire is in this horse! 5, 4, 1, 3, 7
Where are you riding, proud horse, 1, 1, 3, 4, 5, 5
And where will you put your hooves?..." 1, 3, 8, 2, 6
To the right of the text, instead of words, their lengths are written down line by line. After the calculations we make a table.
Example.
Example. When checking 70 works on the Russian language, the number of spelling errors made by students was noted. The resulting data series was presented in the form of a frequency table:
What is the largest difference in the number of errors made? What number of errors is typical for this group of students? Indicate what statistical characteristics were used to answer the questions posed.
Solution.
The largest difference in the number of errors: 6 – 0 = 6.
Typical number of errors: 3 (occurs 26 times out of 70).
Scale and fashion are used.
Answer: 6; 3.
Statistical research frequency tables language.
Statistical research over a large number of literary texts, they showed that the frequencies of appearance of a particular letter (or space between words) tend to certain certain constants as the volume of the text increases. Tables that contain the letters of a particular language and the corresponding constants are called frequency tables language.
Each author has his own frequency table of the use of letters, words, specific literary expressions, etc. Using this frequency table, you can determine the author about as accurately as using fingerprints.
For example, before today Disputes about authorship continue " Quiet Don" Quite a few people believe that at 23 years old M.A. Sholokhov is so profound and truly great book I just couldn’t write. Various arguments and different candidate authors have been put forward. The debates were especially heated at the time of awarding M.A. Sholokhov Nobel Prize in literature (1965). Statistical analysis the novel and its comparison with texts, the authorship of which was beyond doubt by M.A. Sholokhov, nevertheless confirmed the hypothesis about M.A. Sholokhov as the true author of “The Quiet Don”.
Example No. 1.
Example No. 1. The sample consists of all letters included in the couplet
“...This tree is a pine,
And the fate of the pine is clear..."
Write down a series of sample data.
Find the sample size.
Determine the multiplicity and frequency of the “o” options.
What is the highest percentage frequency of the sample option?
Solution
1). Sample data series (values option):
a, b, c, d, f, i, n, o, p, s, t, y, b, s, e, i.
2). The sample size is the total number of letters in the couplet: n = 30.
3). The multiplicity of options “o” is 4, the frequency of options is equal.
4). Option “c” has the highest percentage frequency: its multiplicity is 6, frequency
, percentage frequency 20%.
Answer: 1). 16 letters; 2). thirty; 3). 4 and 0.133; 4). 20%.
Example No. 1 (continued). The sample consists of all letters included in the couplet
Example No. 1 (continued). The sample consists of all letters included in the couplet
“...This tree is a pine,
And the fate of the pine is clear..."
The alphabet is divided in order into three identical sections: No. 1 from “a” to “th”, No. 2 from “k” to “u”, No. 3 from “f” to “z”.
1).Find the multiplicity and (percentage) frequency of section No. 3.
2).Make a table of the frequency distribution of sections.
3).Indicate the area of the highest frequency.
4).Construct a frequency histogram with the selected distribution into sections.
Solution. First of all, we note that if the Russian alphabet has 33 letters, then three identical sections are sections of 11 letters. Number of letters in a couplet: n = 30.
Frequency and multiplicity distribution table:
Example.
Example. 60 ninth-graders were tested for reading speed (number of words per minute of reading). The obtained data were grouped into five areas: No. 1- (91;100); No. 2 (101;110); No. 3 (111;120); No. 4 (121;130); No. 5 (131;140). The result is a histogram of multiplicities (see figure). Approximately estimate: range, mode, arithmetic mean of the sample, explain why the answers are only approximate.
Range A = 140-91 = 49
Range A = 140-91 = 49
Fashion.
Average value.
The obtained values are only approximate because instead of actual values, the calculations used conditional values - the boundaries and midpoints of partial intervals, that is, values that were not observed experimentally, but were accepted by us for the convenience of presenting data.
Answer: 49; 125,5; 117,17.
A.G. Mordkovich, P.V. Semenov. Events. Probabilities. Statistical data processing: Additional. Paragraphs for the algebra course 7 – 9 grades. general education institutions / A.G. Mordkovich, P.V. Semenov. 4th ed. – M.: Mnemosyne, 2006.-112 p.
Makarychev Yu.N. Algebra: elements of statistics and combinatorics and probability theory: textbook. A manual for students of grades 7-9. general education institutions / Yu.N. Makarychev, N.G. Mindyuk; edited by S. A. Telyakovsky. - 2nd ed. – M.: Education, 2004.-78 p.
M.V. Tkacheva, N.E. Fedorova. Elements of statistics and probability: A textbook for general education grades 7-9. institutions. – M.: Education, 2004.-112 p.
Rearrangements. Formula for the number of permutations
Permutations from n elements
Let the set X comprises n elements.
Definition. Placement without repetition fromn elements of the setX By n called permutation from n elements.
Note that any permutation includes all elements of the setX , and exactly once. That is, permutations differ from one another only in the order of the elements and can be obtained from one another by permutation of elements (hence the name).
Number of all permutations fromn elements are indicated by the symbol .
Since permutations are special case placements without repetitions at , then the formula for finding the number we obtain from formula (2), substituting into it :
Thus,
(3)
Example. In how many ways can 5 books be placed on a shelf?
Solution. There are as many ways to place books on a shelf as there are different permutations of the five elements: ways.
Comment. Formulas (1)-(3) do not need to be memorized: problems involving their application can always be solved using the product rule. If students have problems creating combinatorial models of problems, then it is better to narrow the set of formulas and rules used (so that there is less opportunity for mistakes). True, problems that use permutations and formula (3) are usually solved without any problems.
Tasks
1. F. In how many ways can they queue up at the ticket office: 1) 3 people; 2) 5 people?
Solution.
Various options The arrangements of n people in a queue differ from one another only in the order in which the people are arranged, i.e., they are different permutations of n elements.
Three people can queue P3 = 3! = 6 different ways.
Answer: 1) 6 ways; 2) 120 ways.
2. T. In how many ways can 4 people fit on a four-seater bench?
Solution.
The number of people is equal to the number of seats on the bench, so the number of placement options is equal to the number of permutations of 4 elements: P4 = 4! = 24.
You can reason according to the product rule: for the first person you can choose any of the 4 places, for the second - any of the 3 remaining, for the third - any of the 2 remaining, the last one will take 1 remaining place; there is everything = 24 different ways to seat 4 people on a four-seater bench.
Answer: 24 ways.
3. M. At Vova’s for lunch - first, second, third courses and cake. He will definitely start with the cake and eat the rest in random order. Find the number possible options lunch.
M-problems from the textbook. manuals by A.G. Mordkovich
T - ed. S.A.Telyakovsky
F- M.V. Tkacheva
Solution.
After the cake, Vova can choose any of three dishes, then two, and finish with the rest. Total number of possible lunch options: =6.
Answer: 6.
4. F. How many different correct (from the point of view of the Russian language) phrases can be made by changing the order of words in a sentence: 1) “I went for a walk”; 2) “A cat is walking in the yard”?
Solution.
In the second sentence, the preposition “in” must always appear before the noun “yard” to which it refers. Therefore, counting the pair “in the yard” as one word, you can find the number of different permutations of the three conditional words: P3 = 3! = 6. Thus, in this case, you can make 6 correct sentences.
Answer: 1) 6; 2) 6.
5. In how many ways can you use the letters K, L, M, H to designate the vertices of a quadrilateral?
Solution.
We will assume that the vertices of the quadrilateral are numbered, each with a constant number. Then the problem comes down to counting the number of different ways of arranging 4 letters on 4 places (vertices), i.e., counting the number of different permutations: P4 = 4! =24 ways.
Answer: 24 ways.
6. F. Four friends bought cinema tickets: for 1st and 2nd seats in the first row and for 1st and 2nd seats in the second row. In how many ways can friends take these 4 seats in the cinema?
Solution.
Four friends can take 4 different places P4 = 4! = 24 different ways.
Answer: 24 ways.
7. T. The courier must deliver packages to 7 different institutions. How many routes can he choose?
Solution.
The route should be understood as the order in which the courier visits institutions. Let's number the institutions from 1 to 7, then the route will be represented as a sequence of 7 numbers, the order of which may change. The number of routes is equal to the number of permutations of 7 elements: P7= 7! = 5,040.
Answer: 5,040 routes.
8. T. How many expressions exist are identical equal to the product abcde, which are obtained from it by rearranging the factors?
Solution.
Given is the product of five different factors abcde, the order of which can change (when the factors are rearranged, the product does not change).
There is a total of P5 = 5! = 120 different ways to arrange the five multipliers; We consider one of them (abcde) to be the original one, the remaining 119 expressions are identically equal to this one.
Answer: 119 expressions.
9. T. Olga remembers that her friend’s phone number ends with the numbers 5, 7, 8, but she forgot in what order these numbers appear. Indicate the largest number of options that she will have to go through to get through to her friend.
Solution.
Last three digits phone number can be located in one of P3 =3! =6 possible orders, of which only one is correct. Olga can immediately type the correct option, she can type it third, etc. Largest number options she will have to dial if correct option will be the last, i.e. sixth.
Answer: 6 options.
10. T. How many six-digit numbers (without repeating numbers) can be made from the numbers: a) 1,2, 5, 6, 7, 8; b) 0, 2, 5, 6, 7, 8? Solution.
a) Given 6 digits: 1, 2, 5, 6, 7, 8, from them you can form different six-digit numbers only by rearranging these digits. The number of different six-digit numbers is equal to P6 = 6! = 720.
b) Given 6 digits: 0, 2, 5, 6, 7, 8, from them you need to make up various six-digit numbers. In contrast of previous task is that zero cannot come first.
You can directly apply the product rule: you can choose any of the 5 digits (except zero) for the first place; in second place - any of the 5 remaining digits (4 are “non-zero” and now we count zero); to third place - any of the 4 digits remaining after the first two choices, etc. The total number of options is: = 600.
You can use the method of eliminating unnecessary options. 6 digits can be rearranged P6 = 6! = 720 different ways. Among these methods there will be those in which the first place is zero, which is unacceptable. Let's count the number of these invalid options. If there is a zero in the first place (it is fixed), then the next five places can contain “non-zero” numbers 2, 5, 6, 7, 8 in any order. The number of different ways in which 5 numbers can be placed in 5 places is equal to P5 = 5! = 120, i.e. the number of permutations of numbers starting from zero is 120. The required number of different six-digit numbers in this case is equal to: P6 - P5 = 720 - 120 = 600.
Answer: a) 720; b) 600 numbers.
11. T. How many of the four-digit numbers (without repeating numbers) made up of the numbers 3, 5, 7, 9 are those that: a) begin with the number 3;
b) are multiples of 15?
Solution.
a) From the numbers 3, 5, 7, 9 we make four-digit numbers starting with the number 3.
We fix the number 3 in first place; then on the remaining threenumbers 5, 7 9 can be placed in any order in any order. The total number of options for their location is equal to P 3 = 3!=6. There will be so many different four-digit numbers made up ofgiven numbers and starting with the number 3.
b) Note that the sum of these digits 3 + 5 + 7 + 9 = 24 is divisible by 3, therefore, any four-digit number made up of these digits is divisible by 3. In order for some of these numbers to be divisible by 15, it is necessary so that they end with the number 5.
We fix the number 5 on last place; the remaining 3 digits can be placed in three places in front of 5 Рз = 3! = 6 different ways. There will be so many different four-digit numbers made up of these numbers that are divisible by 15.
Answer: a) 6 numbers; b) 6 numbers.
12. T. Find the sum of the digits of all four-digit numbers that can be made from the numbers 1, 3, 5, 7 (without repeating them).
Solution.
Each four-digit number made up of the digits 1, 3, 5, 7 (without repetition) has a sum of digits equal to 1 + 3 + 5 + 7 = 16.
From these numbers you can make P4 = 4! = 24 different numbers, differing only in the order of the digits. The sum of the digits of all these numbers will be equal to
16 = 384.
Answer: 384.
13. T. Seven boys, which include Oleg and Igor, stand in a row. Find the number possible combinations, If:
a) Oleg should be at the end of the row;
b) Oleg should be at the beginning of the row, and Igor should be at the end of the row;
c) Oleg and Igor should stand next to each other.
Solution.
a) There are only 7 boys in 7 places, but one element is fixed and cannot be rearranged (Oleg is at the end of the row). The number of possible combinations is equal to the number of permutations of the 6 boys standing in front of Oleg: P6=6!=720.
a couple like single element, rearranged with the other five elements. The number of possible combinations will then be P6 = 6! = 720.
Let Oleg and Igor now stand side by side in IO order. Then we get another P6 = 6! = 720 other combinations.
The total number of combinations in which Oleg and Igor are next to each other (in any order) is 720 + 720 = 1,440.
Answer: a) 720; b) 120; c) 1,440 combinations.
14. M. Eleven football players line up before the start of the match. The first is the captain, the second is the goalkeeper, and the rest are randomly. How many construction methods are there?
Solution.
After the captain and goalkeeper, the third player can choose any of the 9 remaining places, the next one from 8, etc. The total number of construction methods using the product rule is equal to:
1 =362,880, or P 9 = 9! = 362,880.
Answer: 362,880.
15. M. In how many ways can the vertices of a cube be designated by the letters A, B, C, D, E, F, G, K?
Solution.
For the first vertex you can choose any of the 8 letters, for the second - any of the remaining 7, etc. The total number of ways according to the product rule is=40 320, or P8 = 8!
Answer: 40,320.
16. T. The schedule for Monday has six lessons: algebra, geometry, biology, history, physical education, chemistry. In how many ways can you create a lesson schedule for this day so that two mathematics lessons are next to each other?
Solution.
There are 6 lessons in total, of which two mathematics lessons should be next to each other.
We “glue” two elements (algebra and geometry) first in the order AG, then in the order GA. For each “gluing” option we get P5 = 5! = 120 schedule options. The total number of ways to create a schedule is 120 (AG) +120 (GA) = 240.
Answer: 240 ways.
17. T. How many permutations of the letters of the word “cone” are there in which the letters K, O, N are next to each other?
Solution.
Given 5 letters, three of which must be next to each other. Three letters K, O, N can stand next to one of P3 = 3! = 6 ways. For each method of “gluing” the letters K, O, N, we get P3 = 3! = 6 ways of permuting letters, “gluing”, U, S. The total number of different permutations of letters of the word “cone”, in which the letters K, O, N are next to each other, is 6 6 = 36 permutations - anagrams.
Answer: 36 anagrams.
18. T. In how many ways can 5 boys and 5 girls occupy seats from 1 to 10 in the same row in the theater? In how many ways can they do this if the boys sit in odd-numbered seats and girls in even-numbered seats?
Solution.
Each arrangement of boys can be combined with each of the arrangements of girls, therefore, according to the product rule total number There are 120 ways to seat children in this case. 20= 14400.
Answer: 3,628,800 ways; 14,400 ways.
19. T. Five boys and four girls want to sit on a nine-seater bench so that each girl sits between two boys. In how many ways can they do this?
Solution.
According to the conditions of the task, boys and girls must alternate, that is, girls can only sit in even-numbered places, and boys can only sit in odd-numbered ones. Therefore, girls can only change places with girls, and boys can only change places with boys. Four girls can be seated in four even places P4 = 4! = 24 ways, and five boys in five odd places P5 = 5! = 120 ways.
Each way of placing girls can be combined with each way of placing boys, therefore, according to the product rule, the total number of ways is equal to: P4
20 = 2,880 ways.
Answer: 2,880 ways.
20. F. Factor the numbers 30 and 210 into prime factors. In how many ways can the number be written as a product of simple factors: 1) 30; 2) 210?
Solution.
Let's factor these numbers into prime factors:
30 = 2 ; 210 = 2 .
The number 30 can be written as a product of prime factors
R 3 = 3! = 6 different ways(rearranging the factors).
The number 210 can be written as a product of primes
multipliersR
4
= 4!
= 24 different ways.
Answer: 1) 6 ways; 2) 24 ways.
21. F. How many different even four-digit numbers with non-repeating digits can be written using the numbers 1, 2, 3, 5?
Solution.
For a number to be even, it must end with an even digit, i.e. 2. Let's fix the two in the last place, the remaining three digits must appear in front of it in any order. The number of different permutations of 3 digits is P3 = 3! = 6; therefore, there will also be 6 different even four-digit numbers (the number 2 is added to each permutation of three digits).
Answer: 6 numbers.
22. F. How many different odd five-digit numbers that do not have identical digits can be written using Digits 1,2, 4, 6, 8?
Solution.
For a composed number to be odd, it must end in an odd digit, i.e. one. The remaining 4 digits can be rearranged, placing each rearrangement before the unit.
The total number of odd five-digit numbers is equal to the number of permutations: P4 = 4! =24.
23. F. How many different six-digit numbers with non-repeating digits can be written using the digits 1; 2 3, 4, 5, 6, if: 1) the number must start with 56; 2) should the numbers 5 and 6 be next to each other?
Solution.
We fix two digits 5 and 6 at the beginning of the number and add to them various permutations from the 4 remaining digits; the number of different six-digit numbers is equal to: P4 = 4! = 24.
The total number of different six-digit numbers in which the numbers 5 and 6 are next to each other (in any order) is 120 + 120 = 240 numbers. (Options 56 and 65 are incompatible and cannot be realized simultaneously; we apply the combinatorial sum rule.)
Answer: 1) 24th; 2) 240 numbers.
24. F. How many different even four-digit numbers that do not have identical digits can be made from the numbers 1,2,3,4?
Solution.
Even number must end with an even number. We fix the number 2 in the last place, then the 3 previous digits can be rearranged P3 = 3! = 6 different ways; we get 6 numbers with a two at the end. We fix the number 4 in the last place, we get P3 = 3! = 6 different permutations of the three preceding digits and 6 numbers ending in 4.
The total number of even four-digit numbers will be 6 + 6 = 12 different numbers.
Answer: 12 numbers.
Comment. We find the total number of options using the combinatorial sum rule (6 options for numbers ending in two, 6 options for numbers ending in four; the methods for constructing numbers with a two and with a four at the end are mutually exclusive, incompatible, therefore the total number of options is equal to the sum of the number of options with a two at the end and the number of options with 4 at the end). The entry 6 + 6 = 12 better reflects the reasons for our actions than the entry P.
25. F. In how many ways can the number 1) 12 be written as a product of prime factors? 2) 24; 3) 120?
Solution.
The peculiarity of this problem is that in the expansion of each of these numbers there are identical, repeating factors. When forming different permutations from factors, we will not get a new permutation if we swap any two identical factors.
1) The number 12 is decomposed into three prime factors, two of which are the same: 12 = .
If all the factors were different, then they could be rearranged in the product P3 = 3! = 6 different ways. To list these methods, we will conditionally “distinguish” two twos and emphasize one of them: 12 = 2.
Then the following 6 variants of decomposition into inhabitants are possible:
But in fact, underlining numbers has no meaning in mathematics, so the resulting 6 permutations in ordinary notation look like:
i.e., in fact, we got not 6, but 3 different permutations. The number of permutations was halved due to the fact that we do not have to take into account the permutations of two twos with each other.
Let's denote P x the required number of permutations of three elements, including two identical ones; then the result we obtained can be written as follows: Рз = Р X But 2 is the number of different permutations of two elements, i.e. 2 == 2! = P 2, therefore P3, = P x P 2, hence P x = 
. (this is the formula for the number of permutations with repetitions).
One can reason differently, based only on the combinatorial product rule.
To create a product of three factors, first choose a place for factor 3; this can be done in one of three ways. After this, we fill both remaining spaces with twos; this can be done in 1 way. According to the product rule, the total number of ways is: 3-1 =3., Р x =20.
Second way. When composing a product of five factors, we first choose a place for the five (5 ways), then for the three (4 ways), and fill the remaining 3 places with twos (1 way); according to the product rule 5 4 1 = 20.
Answer: 1) 3; 2) 4; 3) 20.
26. F. In how many ways can 6 cells be colored so that 3 cells are red, and the remaining 3 are painted (each with its own color) white, black or green?
Solution.
Permutations of 6 elements, among which three are identical:
Otherwise: to paint with white, you can choose one of 6 cells, black - from 5, green - from 4; The three remaining cells are painted red. Total number of ways: 6 5 4 1 = 120.
Answer: 120 ways.
27.T. A pedestrian must walk one block north and three blocks west. Write down all possible pedestrian routes.= 4.
Answer: 4 routes.
28. M. a) On the doors of four identical offices it is necessary to hang signs with the names of four deputy directors. In how many ways can this be done?
b) In 9 “A” class on Wednesday there are 5 lessons: algebra, geometry, physical education, Russian language, English language. How many schedule options can you create for this day?
c) In how many ways can four thieves scatter, one at a time, in all four directions?
d) The adjutant must deliver five copies of the general's order to five regiments. In how many ways can he choose the delivery route for copies of the order?
Solution.
a) For the first plate, you can choose any of 4 cabinets,
For the second - any of the three remaining, for the third - any of the two remaining, for the fourth - one remaining; according to the rule
product, the total number of ways is: 4 3 2 1 = 24, or P4 = 4! = 24.= 120, or P5 = 5! = 120.
Answer: a) 24; b) 120; c) 24; d) 120.
Literature
Afanasyev V.V. Probability theory in examples and problems, Yaroslavl: Yaroslavl State Pedagogical University, 1994.
Bavrin I. I. Higher mathematics: Textbook for students of chemical and mathematical specialties of pedagogical universities - 2nd edition, revised. - M.: Education, 1993.
Bunimovich E. A., Bulychev V. A. Probability and statistics. Grades 5-9: Manual for general education educational institutions, - M.: Bustard, 2005.
Vilenkin N. Ya. and others. Algebra and mathematical analysis for 10th grade: Tutorial for students of schools and classes with in-depth study mathematics. - M.: Education, 1992.
Vilenkin N. Ya. and others. Algebra and mathematical analysis for grade 11: A textbook for students of schools and classes with in-depth study of mathematics - M.: Prosveshchenie, 1990.
Glazer G.I. History of mathematics at school: grades 9-10. Manual for teachers. - M.: Education 1983.
Dorofeev G.V., Suvorova S.B., Bunimovich E.A. Math 9: Algebra. Functions. Data analysis - M.: Bustard, 2000.
Kolyagin and others. Algebra and beginning of analysis grade 11. Mathematics at school - 2002 - No. 4 - pp. 43,44,46.
Lyupshkas V.S. Elective courses in mathematics: probability theory: Textbook for grades 9-11. - M., 1991.
Makarychev Yu.N., Mindyuk N.G. Elements of statistics and probability theory: A textbook for students in grades 7-9. - M.: Prosveshchenie, 2005.
Mordkovich A.G., Semenov P.V. Algebra and beginning of analysis grade 10: Textbook for educational institutions (profile level) – M.: Mnemosyne, 2005.
Tkacheva M.V., Fedorova N.E. Elements of statistics and probability: A textbook for students in grades 7-9. - M.: Prosveshchenie, 2005.