Presentation on the topic of combinatorics. Presentation on the topic: Elements of Combinatorics!!! Application of graph theory

1 slide

We don’t need to wield a blade, We don’t seek loud glory. He wins who is familiar with the art of thinking, subtle. English poet Wordsworth

2 slide

Introduction Purpose of the work Objectives of the work What is “Combinatorics”? History of origin Rules for solving combinatorial problems Sum rule Product rule Combinations With repetitions Without repetitions Thesaurus List of used literature and web resources Conclusion Author's page

3 slide

Create a reference guide for students in grades 10-11, studying at a basic level, in educational institutions. Prepare the first part of a large project “The theory of probability as the most common phenomenon in our lives.”

4 slide

1.1 Select literature and web resources on the topic “Combinatorics”. 1.2 Explore all possible methods for solving combinatorial problems based on real life. 1.3 Trace the history of the identification of an independent field of mathematics - combinatorics. 2.1 Justify the study of a combinatorics course in high school as a real necessity when implementing the course on the principle of continuity of education “School - University”. 2.2 Outline possible options for introducing a combinatorics course into the school educational space. 2.3 Select material for creating a reference book.

5 slide

A person often has to deal with problems in which he needs to count the number of all possible ways of placing some objects or the number of all possible ways of performing some action. The different paths or options that a person has to choose add up to a wide variety of combinations. Such problems have to be considered when determining the most advantageous communications within a city, when organizing an automatic control system, and therefore in probability theory and in mathematical statistics with all their numerous applications. And a whole branch of mathematics, called combinatorics, is busy searching for answers to the questions: how many combinations are there in a given case?

6 slide

Combinatorics is a branch of mathematics in which the problems of selecting elements from an initial set and arranging them in a certain combination according to given rules are studied and solved.

7 slide

Combinatorics as a science began to develop in the 13th century. parallel to the emergence of probability theory. The first scientific research on this topic belonged to the Italian scientists G. Cardano, N. Chartalier (1499-1557), G. Galileo (1564-1642) and the French scientists B. Piscamo (1623-1662) and P. Fermat. The German scientist G. Leibniz was the first to consider combinatorics as an independent branch of mathematics in his work “On the Art of Combinatorics,” published in 1666. He also coined the term "Combinatorics" for the first time.

8 slide

Slide 9

Task: There are 3 black and 5 red pencils on the table. In how many ways can you choose a pencil of any color? Solution: You can choose a pencil of any color in 5+3=8 ways. Sum rule in combinatorics: If element a can be chosen in m ways, and element b in n ways, and any choice of element a is different from any choice of elements in b, then the choice “a or b” can be made in m + n ways. Sample problems

10 slide

Task: In a class, 10 students play sports, the remaining 6 students attend a dance club. 1) How many pairs of students can be selected so that one of the pair is an athlete, the other a dancer? 2) How many choices does one student have? Solution: 1) The possibility of choosing 10 athletes, and for each of the 10 athletes there are 6 choices of dancer. This means that the possibility of choosing pairs of dancer and athlete is 10·6=60. 2) Possibility of choosing one student 10+6=16.

11 slide

Problem: There are 3 roads leading from city A to city B. And from city B to city C there are 4 roads. How many paths through B lead from A to C? Solution: You can reason this way: for each of the three paths from A to B, there are four ways to choose the road from B to C. The total number of different paths from A to C is equal to the product 3·4, i.e. 12. Product rule: Let you choose k elements. If the first element can be selected in n1 ways, the second in n2 ways, etc., then the number of ways k elements is equal to the product n1 · n2 ·... nк. Sample problems

12 slide

Problem: There are 2 first, 5 second and 4 third courses in the school canteen. In how many ways can a student choose a lunch consisting of first, second and third courses? Solution: The first dish can be selected in 2 ways. For each choice of first course, there are 5 second courses. The first two dishes can be chosen in 2·5=10 ways. And finally, for every 10 of these choices, there are four possibilities for choosing the third course, i.e. There are 2·5·4 ways of composing a three-course meal. So, lunch can be composed in 40 ways.

Slide 13

Slide 14

15 slide

An arrangement of n elements by k (k≤n) is any set consisting of any k elements taken in a certain order from the given n elements. The number of all placements of n elements by m is denoted by: Examples of problems n! – factorial of number n

16 slide

Problem: In how many ways can 4 boys invite four out of six girls to dance? Solution: Two boys cannot invite the same girl at the same time. And the options in which the same girls dance with different boys are considered different, therefore: 360 options are possible.

Slide 17

A permutation of n elements is each arrangement of these elements in a certain order. The number of all permutations of n elements is denoted by Pn Pn=n! Sample problems

18 slide

Quartet Naughty Monkey Donkey, Goat, Yes, clubfooted Bear They started playing a quartet... Stop, brothers, stop! - Monkey shouts, - wait! How should the music go? After all, you’re not sitting like that... And you changed seats this way and that – again the music doesn’t go well. Now they have more discussions and disputes than ever about who should sit and how... Decision

20 slide

A combination without repetition is an arrangement in which the order of the elements does not matter. Thus, the number of options when combined will be less than the number of placements. The number of combinations of n elements by m is denoted by: Examples of problems

21 slides

Problem: How many three-button combinations are there on a combination lock (all three buttons are pressed simultaneously) if there are only 10 digits on it. Solution: Since the buttons are pressed simultaneously, selecting these three buttons is a combination. From here it is possible:

22 slide

Often in combinatorics problems there are sets in which some components are repeated. For example: in number problems - numbers. For such problems, the following formulas are used: where n is the number of all elements, n1,n2,…,nr is the number of identical elements. Examples of tasks Examples of tasks Examples of tasks

Slide 23

Problem: How many three-digit numbers can be made from the numbers 1, 2, 3, 4, 5? Solution: Since the order of the numbers in a number is significant, the numbers can be repeated, then these will be placements with repetitions of five elements in threes, and their number is equal to:

24 slide

Task: A pastry shop sold 4 types of cakes: eclairs, shortbread, napoleons and puff pastries. In how many ways can you buy 7 cakes? Solution: The purchase does not depend on the order in which the purchased cakes are placed in the box. Purchases will be different if they differ in the number of purchased cakes of at least one type. Therefore, the number of different purchases is equal to the number of combinations of four types of cakes, seven each -

Slide 27

We believe that the work achieved its goals. We have compiled a reference textbook that aims to enliven school mathematics by introducing interesting problems that will raise theoretical questions for students. The work is intended for students of grades 10-11, studying at a basic level, educational institutions to deepen knowledge in mathematics. The distinctive features of this manual are: a theoretical part feasible for students of the third stage; selection and compilation of tasks based on life material and fairy tale plots. We hope that our work will interest students, help develop their horizons and thinking, and contribute to better preparation for passing the unified state exam.

28 slide

Student: Dmitry Zakharov Class: 10 Head: Toropova Nina Anatolyevna Municipal Educational Institution “Secondary educational school with in-depth study of individual subjects No. 5”, Krasnoyarsk

Combinatorics is a branch of mathematics that studies questions about how many different combinations, subject to certain conditions, can be made from given objects.
The word “combinatorics” comes from the Latin word “combinare”, which translated into Russian means “to combine”, “to connect”.
The term "combinatorics" was introduced by the famous Gottfried Wilhelm Leibniz, a world famous German scientist.

Combinatorics is an important branch of mathematics,
knowledge of which is necessary for representatives of a variety of specialties. Physicists, chemists, biologists, linguists, code specialists, etc. have to deal with combinatorial problems.
Combinatorial methods underlie the solution of many theoretical problems
probabilities and
its applications.

In Ancient Greece

counted the number of different combinations of long and short syllables in poetic meters, studied the theory of figured numbers, studied figures that can be made from parts, etc.

Over time, various games have appeared
(backgammon, cards, checkers, chess, etc.)

In each of these games, different combinations of figures had to be considered, and the winner was the one who studied them better, knew the winning combinations and knew how to avoid losing ones.

Gottfried Wilhelm Leibniz (07/1/1646 - 11/14/1716)

The German scientist G. Leibniz was the first to consider combinatorics as an independent branch of mathematics in his work “On the Art of Combinatorics,” published in 1666. He also coined the term "Combinatorics" for the first time.

Leonhard Euler(1707-1783)

considered problems about partitioning numbers, matching, cyclic arrangements, constructing magic and Latin squares, laid the foundation for a completely new field of research, which later grew into a large and important science of topology, which studies the general properties of space and figures.

If some object A can be chosen in m ways, and another object B can be chosen in n ways, then the choice “either A or B” can be made in (m+n) ways.

If some object A can be chosen in m ways, and another object B can be chosen in n ways, then the choice “either A or B” can be made in (m+n) ways.
When using the sum rule, you must ensure that none of the methods for selecting object A coincides with any method for selecting object B.
If there are such matches, the sum rule is no longer valid, and we get only (m + n - k) selection methods, where k is the number of matches.

There are 10 balls in the box: 3 white, 2 black, 1 blue and 4 red. In how many ways can you take a colored ball from the box?

There are 10 balls in the box: 3 white, 2 black, 1 blue and 4 red. In how many ways can you take a colored ball from the box?
Solution:
A colored ball is either blue or red, so we apply the sum rule:

If object A can be selected in m ways and if after each such choice object B can be selected in n ways, then the selection of the pair (A, B) in the specified order can be done in mn ways.

If object A can be selected in m ways and if after each such choice object B can be selected in n ways, then the selection of the pair (A, B) in the specified order can be done in mn ways.
In this case, the number of ways to select the second element does not depend on how exactly the first element is selected.

How many different combinations of coins can there be?

How many different combinations of coins can there be?
sides when throwing two dice?
Solution:
The first dice can have: 1,2,3,4,5 and 6 points, i.e. 6 options.
The second one has 6 options.
Total: 6*6=36 options.

The sum and product rules are true for any number of objects.

No. 1. There are 6 roads leading from city A to city B, and 3 roads from city B to city C. In how many ways can you travel from city A to city C?

No. 1. There are 6 roads leading from city A to city B, and 3 roads from city B to city C. In how many ways can you travel from city A to city C?
No. 2. On the bookshelf there are 3 books on algebra, 7 on geometry and 2 on literature. In how many ways can you take one math book from the shelf?
No. 3. The menu has 4 first courses, 3 main courses, and 2 desserts. How many different lunches can you make from them?

"En factorial" -n!.

Definition.
Product of consecutive first n
natural numbers are denoted by n! and call
“en factorial”: n!=1 2 3 … (n-1) n.

1 2 3=

1 2 3 4=

1 2 3 4 5=

1 2 3 4 5 6=

1 2 3 4 5 6 7=

n!=(n-1)! n

Convenient formula!!!

Combinations of n-elements that differ from each other only in the order in which the elements appear are called permutations.

Combinations of n-elements that differ from each other only in the order in which the elements appear are called permutations.
Designated by Pn

Rearrangements

Make a three-digit number from the numbers 1, 5, 9
a number without repeating digits.

2 combinations

2 combinations

2 combinations

Total 2 3=6 combinations.

Combinations of n-elements in k, differing from each other in composition and order, are called placements.

Combinations of n-elements in k, differing from each other in composition and order, are called placements.

Placements

Combinations of n-elements by To To.

Combinations of n-elements by To, differing only in the composition of the elements, are called combinations of n-elements according to To.

Combinations

Out of 20 students, you need to choose two duty officers.

Out of 20 students, you need to choose two duty officers.
In how many ways can this be done?

Solution:

You need to choose two people out of 20.
It is clear that nothing depends on the order of choice, that is,
Ivanov - Petrov or Petrov - Ivanov is one
and the same pair of attendants. Therefore, these will be combinations of 20 by 2.

1. How many words can be formed from the letters of the word fragment if the words must consist of: 8 letters; of 7 letters; of 3 letters?

1. How many words can be formed from the letters of the word fragment if the words must consist of: 8 letters; of 7 letters; of 3 letters?
2. The student must pass 4 exams within ten days. In how many ways can you schedule his exams?
3. In how many ways can a commission consisting of five members be elected from eight people?
4. How many different license plates are there that consist of 5 digits if the first one is not zero? What if the number consists of one letter followed by four non-zero digits?
5. The contractor needs 4 carpenters, and 10 have approached him with an offer of their services. In how many ways can he choose four of them?
6. In how many ways can seven books be arranged on a shelf?
7. How many 5-letter words can be formed using 10 different letters.
8. In how many ways can you select several fruits from seven apples, four lemons and nine oranges? (Fruits of the same type are considered indistinguishable.)

Petrov Vladimir, student of the 12th group of the State Budgetary Educational Institution SO NPO "Vocational School No. 22", Saratov

The presentation discusses examples of solving problems of finding permutations, placements, and combinations.

Download:

Preview:

To use presentation previews, create a Google account and log in to it: https://accounts.google.com

Slide captions:

Elements of combinatorics: permutations, combinations and placements The presentation was prepared by Vladimir Petrov, a student of group 12 of the State Budgetary Educational Institution SO NPO.

Combinatorics is a branch of mathematics that is busy searching for answers to questions: how many combinations are there in a given case, how to choose the best one from all these combinations. The word “combinatorics” comes from the Latin word “combinare”, which translated into Russian means “to combine”, “to connect”. The term "combinatorics" was introduced by the famous Gottfried Wilhelm Leibniz, a world famous German scientist.

Combinatorial problems are divided into several groups: Permutation problems Placement problems Combination problems

Rearrangement problems In how many ways can 3 different books be arranged on a bookshelf? This is a permutation problem

Write n! reads like this: “en factorial” Factorial is the product of all natural numbers from 1 to n For example, 4! = 1*2*3*4 = 24 n! = 1 · 2 · 3 · ... · n.

n 1 2 3 4 5 6 7 8 9 10 n! 1 4 6 24 120 720 5040 40320 362880 3628800 Factorials grow surprisingly quickly:

Task. In how many ways can the 8 participants in the final race be arranged on eight treadmills? P8 = 8!= 1 ∙2∙ 3 ∙4∙ 5 ∙6∙ 7 ∙8 = 40320

A permutation of n elements is each arrangement of these elements in a certain order. P n = 1 · 2 · 3 · ... · n. Pn=n!

Task. Quartet Naughty Monkey Donkey, Goat, Yes, clubfooted Bear They started playing a quartet... Stop, brothers, stop! - Monkey shouts, - wait! How should the music go? After all, you’re not sitting like that... And you changed seats this way and that – again the music doesn’t go well. Now they have more discussions and disputes than ever about who should sit and how... In how many ways can four musicians be seated? P = 4! = 1 * 2 * 3 * 4 = 24

Placement tasks

Problem: We have 5 books, that we have only one shelf, and that it can only hold 3 books. In how many ways can 3 books be arranged on a shelf? We choose one of 5 books and put it in first place on the shelf. We can do this in 5 ways. Now there are two places left on the shelf and we have 4 books left. We can choose the second book in 4 ways and place it next to one of the 5 possible first ones. There can be 5·4 such pairs. There are 3 books and one place left. One book out of 3 can be selected in 3 ways and placed next to one of the possible 5·4 pairs. You get 5·4·3 different triplets. This means that the total number of ways to place 3 books out of 5 is 5·4·3 = 60. This is a placement problem.

An arrangement of n elements by k (k≤n) is any set consisting of k elements taken in a certain order from the given n elements.

Task. Second grade students study 9 subjects. In how many ways can you create a schedule for one day so that it contains 4 different subjects? A 4 9 = = 6∙ 7∙ 8∙ 9 = 3024

Decide for yourself: There are 27 students in the class. You need to send one student to get chalk, the second to be on duty in the cafeteria, and the third to call to the blackboard. In how many ways can this be done?

Combination problems: Problem. In how many ways can 3 volumes be arranged on a bookshelf if you choose them from the 5 externally indistinguishable books available? The books are outwardly indistinguishable. But they differ, and significantly! These books are different in content. A situation arises when the composition of the sample elements is important, but the order of their arrangement is unimportant. 123 124 125 134 135 145 234 235 245 345 answer: 10 This is a combination problem

A combination of n elements by k is any set composed of k elements selected from the given n elements.

Task. There are 7 people in the class who are successfully doing mathematics. In how many ways can you choose two of them to participate in the Mathematical Olympiad? C 7 2 = = 21

Decide for yourself: In class 7 students are doing well in mathematics. In how many ways can two of them be selected to be sent to participate in the Mathematical Olympiad?

A special feature of combinatorial problems is a question that can be formulated so that it begins with the words “In how many ways...” or “How many options...”

Permutations Placements Combinations of n elements n cells n elements k cells n elements k cells Order matters Order matters Order does not matter Let's make a table:

Solve the problems yourself: 1. There are 10 white and 6 black balls in the box. In how many ways can one ball of any color be taken out of a box? 2. Olga remembers that her friend’s phone number ends with three numbers 5, 7, 8, but she forgot in what order these numbers are located. Indicate the largest number of options that she will have to go through to get through to her friend. 3. The Philately store sells 8 different sets of stamps dedicated to sports themes. In how many ways can you choose 3 sets from them?

Elements of combinatorics 9 -11 grades, MBOU Kochnevskaya secondary school teacher Gryaznova A.K. Main questions:

What is combinatorics?

What problems are considered combinatorial?

Rearrangements
Placements
Combinations

Let's not argue - let's calculate. G. Leibnitz

Combinatorics– a branch of mathematics that deals with problems of counting the number of combinations made according to certain rules.

II. What problems are considered combinatorial? Combinatorial problems Problems of counting the number of combinations from a finite number of elements

Combinatorics– from the Latin word combinare, which means “to connect, combine.”
Combinatorics methods are widely used in physics, chemistry, biology, economics and other fields of knowledge.
Combinatorics can be considered as part of set theory - any combinatorial problem can be reduced to a problem about finite sets and their mappings.

I. Levels of solving combinatorial problems 1. First level. The task of finding at least one solution, at least one arrangement of objects with given properties is to find such an arrangement of ten points on five segments, in which there are four points on each segment; - such an arrangement of eight queens on a chessboard in which they do not beat each other. Sometimes it is possible to prove that this problem has no solution (for example, it is impossible to arrange 10 balls in 9 urns so that each urn contains no more than one ball - at least one urn will contain at least two balls). 2. Second level. 2. Second level. If a combinatorial problem has several solutions, then the question arises of counting the number of such solutions and describing all solutions to this problem.

3. Third level.

optimal

For example:

A traveler wants to leave city A, visit cities B, C, and D, and then return to city A.

In Fig. shows a diagram of the routes connecting these cities. Different travel options differ from each other in the order in which they visit cities B, C, and D. There are six travel options. The table shows the options and lengths of each path:

Combinatorial optimization problems have to be solved by a foreman striving for the fastest completion of a task, an agronomist striving for the highest yield in given fields, etc.

We will only consider problems of counting the number of solutions to a combinatorial problem.

We will only consider problems of counting the number of solutions to a combinatorial problem.

enumeration theory

Sum and product rules

1. How many different cocktails can be made from four drinks, mixing them in equal quantities of two?
AB, AC, AD, BC, BD, CD – 6 cocktails in total

2. How many different two-digit numbers can be made from the digits 0, 1, 2, 3?

2. How many different two-digit numbers can be made from the digits 0, 1, 2, 3?
First digit second digit

Product rule:

If element A can be selected from a set of elements in n ways and for each such choice element B can be selected in t ways, then two elements (pair) A and B can be selected in n ways.

“Examples of solving combinatorial problems: enumeration of options, sum rule, multiplication rule.”

In how many ways can the 4 participants in the final race be placed on four treadmills?

R n = 4 3 2 1= 24 ways (permutations of 4 elements)

2 3 4 1 3 4 1 2 4 1 2 3

1 track

II. Permutations (1) K v a r t e t The naughty Monkey, the Donkey, the Goat, and the club-footed Bear They started playing a Quartet. ……………………………………………………. They hit the bows, they fight, but there’s no point. “Stop, brothers, stop! - Monkey shouts. - Wait! How should the music go? After all, you’re not sitting like that.”

4·3·2·1 = 4! ways

II. Permutations (2)

Permutation from P- elements are combinations that differ from each other only in the order of the elements
Pn - number of permutations (P is the first letter of the French word permutation - permutation)

Рп= n

Accommodations (1)

Four fellow travelers decided to exchange business cards. How many cards were used in total?

Combinations made from k elements taken from n elements, and differing from each other either in composition or in the order of arrangement of elements, are called placements from n elements by k(0< k ≤n ).

Accommodation from n elements by k elements. And the first letter

French word arrangement: "placement",

"putting things in order"

Accommodations (2)

There are 4 empty balls and 3 empty cells. Let's designate the balls with letters a, b, c, d. Three balls from this set can be placed in the empty cells in different ways.
By choosing the first, second and third balls differently, we will get different ordered three balls
Each ordered a triple that can be made up of four elements is called placement of four elements, three each

Accommodations (3)

How many placements can be made from 4 elements ( abcd) three?
abc abd acb acd adb adc
bac bad bca bcd bda bdc
cab cad cba cbd cda cdb
dab dac dba dbc dca dcb

It was decided to review the options

Accommodations (4)

You can solve this without writing out the placements themselves:
first an element can be selected in four ways, so it can be any element out of four;
for every first second can be selected in three ways;
for each first two there are two ways to choose third element from the remaining two.

We get

Solved using the multiplication rule

Combinations

A combination of P elements by k is any set made up of k elements selected from P elements

Unlike placements in combinations the order of the elements does not matter. Two combinations differ from each other in at least one element

Solving problems: 1. There are 5 points marked on the plane. How many segments will there be if you connect the points in pairs?

2. Marked on the circle P points. How many triangles are there with vertices at these points?

Information sources

V.F. Butuzov, Yu.M. Kolyagin, G.L. Lukankin, E.G. Poznyak and others. “Mathematics” textbook for 11th grade educational institutions / recommended by the Ministry of Education of the Russian Federation / M., Prosveshchenie, 1996.
E.A. Bunimovich, V.A. Bulychev: “Probability and Statistics”, a manual for general education institutions grades 5 – 9 / approved by the Ministry of Education of the Russian Federation // Bustard Moscow 2002
Yu.N. Makarychev, N.G. Mindyuk “Algebra: elements of statistics and probability theory, grades 7 – 9” Edited by S.A. Telyakovsky M: Prosveshchenie, 2006
Triangles http://works.doklad.ru/images/_E3ZV-_wFwU/md87b96f.gif

The rest of the drawings were created by A.K. Gryaznova.

Elements
combinatorics.
Electronic educational manual
for students in grades 9-11.
Author-compiler:
Katorova O.G.,
mathematic teacher
MBOU "Gymnasium No. 2"
Sarov

Combinatorics

Combinatorics is a section
mathematics, which studies
questions of choice or location
elements of the set in accordance
with given rules.
"Combinatorics" comes from the Latin
the words “combina”, which is translated into Russian
means “to combine”, “to connect”.

HISTORICAL REFERENCE
The term "combinatorics" was
introduced into mathematical use
worldwide
famous
German
scientist G.V. Leibniz, who in
1666 published Discourses
about combinatorial art."
G.W. Leibniz
In the 18th century, people turned to solving combinatorial problems
and other outstanding mathematicians. Yes, Leonhard Euler
considered problems about partitioning numbers, matching,
cyclic arrangements, about the construction of magical and
Latin squares.

Combinatorics deals
various types of compounds
(rearrangements, placements,
combinations) that can be
form from elements
some finite set.

Combinatorial connections

Rearrangements
1.
2.
Permutations without repetition
Permutations with repetitions
Placements
1.
2.
Placements without repetitions
Placements with repetitions
Combinations
1.
2.
Combinations without repetitions
Combinations with repetitions

Permutations - connections,
which can be composed of n
elements, changing all
possible ways to order them.
Formula:

Historical reference

In 1713 it was published
essay by J. Bernoulli "Art
assumptions" in which
were presented in sufficient detail
known by that time
combinatorial facts.
"Art
assumptions" was not completed
by the author and appeared after his death.
The essay consisted of 4 parts,
combinatorics was devoted
the second part, which contains
formula for the number of permutations out of n
elements.

Example

In how many ways can 8 people stand in
queue at the box office?
The solution of the problem:
There are 8 seats that must be occupied by 8 people.
Any of 8 people can take first place, i.e. ways
take first place - 8.
After one person is in first place, there are 7 left
seats and 7 people who can be accommodated on them, i.e.
ways to take second place - 7. Similarly for third,
fourth, etc. places.
Using the principle of multiplication, we obtain the product. This
the product is designated as 8! (read 8 factorial) and
is called the P8 permutation.
Answer: P8 = 8!

check yourself

1) In how many ways can you place
there are four different ones on the shelf next to each other
books?
SOLUTION

check yourself

2) In how many ways can you put
10 different cards in 10 available
envelopes (one postcard per envelope)?
SOLUTION

check yourself

3) In how many ways can you plant
eight children on eight chairs in the dining room
kindergarten?
SOLUTION

check yourself

4) How many different words can you make up?
rearranging letters in a word
“triangle” (including the word itself)?
SOLUTION

check yourself

5) How many ways can you install
duty of one person per day among seven
group students for 7 days (each
must be on duty once)?
SOLUTION

check yourself

Permutations with
repetitions
Any placement with repetitions, in
in which element a1 is repeated k1 times, element
a2 is repeated k2 times, etc. an element
repeated kn times, where k1, k2, ..., kn are data
number is called a permutation with
repetitions of the order
m = k1 + k2 + … + kn, in which the data
elements a1, a2, …, an are repeated
respectively k1, k2, .., kn times.

check yourself

Permutations with
repetitions
Theorem. Number of different permutations with
repetitions of elements (a1, ..., an), in
whose elements a1, …, an are repeated
respectively k1, ..., kn times, equals
(k1+k2+…+kn)!
m!
P
k1! k2! ...kn!
k1! k2! ...kn!

check yourself

Example
Words and phrases with letters rearranged
are called anagrams. How many anagrams can you
made from the word "macaque"?
Solution.
There are 6 letters in total in the word “MACACA” (m=6).
Let's determine how many times each letter is used in a word:
"M" - 1 time (k1=1)
“A” - 3 times (k2=3)
“K” - 2 times (k3=2)
m!
P=
k1! k2! …kn!
6!
4*5*6
Р1,3,2 =
= 2 = 60.
1! 3! 2!

check yourself

1) How many different words can you get,
rearranging the letters of the word "mathematics"?
SOLUTION

check yourself

2) In how many ways can you arrange the
first horizontal chessboard set
white pieces (king, queen, two rooks, two
elephant and two knights)?
SOLUTION

check yourself
3) Mom has 2 apples, 3 pears and 4 oranges.
Every day for nine days in a row she
gives his son one of the remaining fruits.
In how many ways can this be done?
SOLUTION

Historical reference
Combinatorial motives can be
notice also in the symbolism of the Chinese “Book
changes" (V century BC).
In the 12th century. Indian mathematician Bhaskara
his main work “Lilavati” in detail
studied problems with permutations and
combinations, including permutations with
repetitions.

Example

Placements
By placing n elements in k order
(k n) is any set
consisting of any k elements taken in
a certain order of n elements.
Two arrangements of n elements are considered
different if they differ themselves
elements or the order in which they are arranged.
A n(n 1)(n 2) ... (n (k 1))
k
n

check yourself

Example
In how many ways out of 40 students in a class
The asset can be identified as follows:
headman, physicist and wall newspaper editor?
Solution:
It is required to select ordered three-element
subsets of a set containing 40
elements, i.e. find the number of placements without
repetitions of 40 elements of 3.
40!
A=
=38*39*40=59280
37!
3
40

check yourself

1. Choose from seven different books
four. How many ways is this possible?
do?
SOLUTION

check yourself

2. They participate in the football championship
ten teams. How many exist
various opportunities to take
teams first three places?
SOLUTION

check yourself

3. 7 subjects are studied in the class. Wednesday 4
lessons, and each one is different. How many
ways you can create a schedule for
Wednesday?
SOLUTION

check yourself

Placements with
repetitions
Placements with repetitions –
compounds containing n elements,
selected from m different elements
species (n m) and differing one from
another either by composition or order
elements.
Their number is assumed
unlimited number of elements
each type is equal

check yourself

Usage example
To the library, which has many
ten identical textbooks
subjects, 5 schoolchildren came,
each of whom wants to take a textbook.
The librarian writes in a journal
order of names (without number) taken
textbooks without the names of the students who gave them
have taken. How many different lists are there in the magazine?
could it appear?

Historical reference

The solution of the problem
Since textbooks for each
subject are the same, and the librarian
records only the name (without
numbers), then the list is placement with
repetition, number of elements
the original set is 10, and
number of positions – 5.
Then the number of different lists is equal to
= 100000.
Answer: 100000

Placements

Check yourself!
1. The telephone number consists of 7 digits.
What is the largest number of calls
loser-Petya can commit
before guessing the correct number.
SOLUTION
SOLUTION

Example

Check yourself!
2. In how many ways can you
write a word made up of
four letters of the English alphabet?
SOLUTION

check yourself

Check yourself!
3. In a store where there are 4 types of balls,
We decided to put 8 balls in a row. How many
ways you can do this if they
Does location matter?
SOLUTION

check yourself

Check yourself!
4. In how many ways can you sew on
six button lined clown costume
one of four colors to get
pattern?
SOLUTION

check yourself

Combinations
Combinations – compounds containing each
m items out of n, different from each other
friend with at least one item.
Combinations are finite sets, in
the order of which does not matter.

check yourself

Combinations
Formula for finding quantity
combinations without repetition:

check yourself

Historical reference
In 1666, Leibniz published Discourses
about combinatorial art." In his essay
Leibniz, introducing special symbols, terms for
subsets and operations on them, finds all k combinations of n elements, displays properties
combinations:
,
,

check yourself

Usage example:
In how many ways can you choose two
duty officers from a class with 25 students?
Solution:
m = 2 (required number of duty personnel)
n = 25 (total students in the class)

Placements with repetitions

Check yourself!
1) In how many ways can you
delegate three students to
interuniversity conference of 9 members
scientific society?
SOLUTION

Usage example

Check yourself!
2) Ten conference participants
shook hands shaking hands
to each. How many handshakes were there?
made?
SOLUTION

The solution of the problem

Check yourself!
3) There are 6 girls and 4 boys in the school choir.
How many ways can you choose from
school choir composition: 2 girls and 1 boy
to participate in the performance of the district choir?
SOLUTION

Check yourself!

4) In how many ways can you choose 3
athletes from a group of 20 people for
participation in competitions?
SOLUTION

Check yourself!

5) There are 10 academic subjects and 5 different ones in the class
lessons per day. In how many ways can
be the lessons distributed on the same day?
SOLUTION

Check yourself!

Combinations with repetitions
Definition
Combinations with repetitions from m to
n are compounds consisting of n
elements selected from m elements
different types, and differing one from
another by at least one element.
Number of combinations from m to n
denote

Check yourself!

Combinations with repetitions
If from a set containing n elements one selects
alternately m elements, with the selected element
comes back every time, then the number of ways
make an unordered sample - the number of combinations with
repetitions – makes up

Check yourself!

Historical reference
Leading Indian mathematician
Bhaskara Akaria (1114–1185) also
studied various types of combinatorial
connections. He owns the treatise
"Sidhanta-Shiromani" ("Crown of Teaching"),
rewritten in the 13th century. on strips
palm leaves. In it the author gave
verbal rules for finding
And
, indicating their applications and placing
numerous examples

Check yourself!

Usage example
Task No. 1
How many sets of 7 cakes
can be compiled if available
Are there 4 types of cakes?
Solution:

Check yourself!

Usage example
Task No. 2
How many bones are there in a normal
game of dominoes?
Solution: Dominoes can be thought of as
combinations with repetitions of two out of seven digits
sets (0,1,2,3,4,5,6).
The number of all such
combinations are equal

Check yourself!

check yourself
Task 1.
The Gymnasium cafeteria sells 5 varieties
pies: with apples, with cabbage,
potatoes, meat and mushrooms. How many
number of ways you can make a purchase from
10 pies?
SOLUTION

Combinations

check yourself
Task 2.
The box contains balls of three colors -
red, blue and green. How many
ways you can create a set of two
balls?
SOLUTION

Combinations

check yourself
Task 3.
In how many ways can you choose 4
coins from four five-kopeck coins and from
four two-kopeck coins?
SOLUTION

check yourself
Task 4.
How many dominoes will there be?
if in their
education use all numbers?
SOLUTION

check yourself
Task 5.
The young impressionist's palette consists of 8
various colors. The artist takes a brush
randomly any of the colors and puts the color
stain on whatman paper. Then takes the next one
brush, dips it into any of the paints and makes
second spot next door. How many
different combinations exist for
six spots?
SOLUTION

Used Books
Algebra and the beginnings of mathematics
analysis. 11th grade / Yu.M. Kolyagin, M.V. Tkacheva,
N.E. Fedorova, M.I. Shabunin. –
M.: Education, 2011.
Vilenkin N.Ya. Combinatorics. – M., 1969
Vilenkin N.Ya. Combinatorics. – MCMNO,
2010
ru.wikipedia.org›wiki/History of combinatorics