Combinatorics and its basic principles
Very often you have to solve problems in which you need to count the number of possible options for a given situation. For example, how many positions can appear on the chessboard after the first move of both players? How many different passwords of ten characters can be written if no character is used twice? How many different number combinations can you get when playing the 6 out of 49 lottery? A special branch of mathematics called combinatorics helps answer all these questions. Almost always, a combinatorial problem can be formulated so that its question begins with the words “in how many ways...”.
Obviously, if a finite set contains n elements, then there are exactly n ways to choose one of them.
Example. There are 15 people in the class. In how many ways can the teacher assign one of them to be responsible for keeping the board clean?
Answer. There are exactly 15 such methods.
There are two basic rules in combinatorics. The first of these is called the addition rule.
Despite the wording, in essence this is a very simple rule.
Example. The store sells 14 Panasonic TVs and 17 Sony TVs. Petya wants to buy one TV. How many purchasing options does it have?
Solution. According to the addition rule, Petya can choose one of 14 + 17 = 31 televisions.
Answer: 31 TVs.
Of particular importance is the second rule, which is called the multiplication rule.
Let's illustrate this rule.
Example. There are 15 boys and 20 girls in the badminton section. The coach must send a mixed pair to the competition. How many options does he have?
Solution. A coach can make 15•20= 300 opposite-sex pairs from his students.
Answer: 300
Example. Petya needs to buy equipment for a computer. The store sells 20 different keyboards, 25 models of gamepads and 30 computer mice. You need to buy one copy of each of these devices. How many purchasing options does he have?
Solution. First, let's count the number of possible keyboard-gamepad pairs. Their number is 20•25 = 500. Now let’s make a “three” from one of 500 pairs and one of 30 mice. The number of triplets is 500•30 = 15000.
Answer: 15000
Addition and multiplication rules can be combined.
Example. How many words of no more than three letters can be formed using an alphabet containing exactly 30 letters?
Solution. Obviously, exactly 30 words can be made from one letter. The number of two-letter words is equal to the number of pairs that can be made from these letters, that is, 30•30 = 900. Three-letter words can be made 30•30•30 = 27,000. In total, words of length there will be no more than 3 letters
30 + 900 + 27000 = 27930
Answer: 27930
Next, we will study the basic concepts of combinatorics - permutations, placements, combinations.
Lesson summary “Elements of combinatorics. Combinatorial sum and product rules"
Grade 11
Subject. Elements of combinatorics. Combinatorial sum and product rules.
“Number, place and combination are three mutually overlapping but distinct spheres of thought into which all mathematical ideas can be classified.” J. Sylvester
Purpose of the lesson: to introduce
students with the subject of studying combinatorics and combinatorial rules of sum and product;
develop the ability to solve combinatorial problems using sum and product rules; develop
logical thinking, memory, attention;
cultivate
mathematical literacy, perseverance, accuracy.
Expected results: students should know what combinatorics is studying; understand how to apply the sum and product rules.
Equipment: textbook, projector.
Lesson type: learning new knowledge.
During the classes
I. _ Organizing time
II . Checking homework; updating of background knowledge
A frontal conversation is held with the class on questions 1-7 p. 134 §17
1. Give an example of a set.
(Many planets, states, songs, parties, equations, functions, points, numbers, figures, etc.)
2. How are sets and their elements designated?
An object belonging to a set is called its element
.
Sets denoted
in capital letters of the Latin alphabet, and its
elements
in lowercase.
braces are
sometimes
to denote a set .
3. What types of sets are there?
There are many
finite and infinite (according to the number of elements). Many figures, numbers - finite; set of natural, integer, rational, real numbers; the set of points on a line or segment, the set of real numbers on intervals [2; 3], (-6; +∞) – infinite.
Which set is called empty?
A set that does not contain a single element is called
empty
and is denoted by the symbol
.
4. Which sets are called equal?
If sets consist of the same elements, then such sets are called
equal
.
5. What is a subset?
If A is part of set B, then it is called
a subset of
set B and written AB.
6. What is the union of two sets?
A set containing each element of each of the sets a and B and only them is called the union of the sets A and B. If K is the union of the sets A and B, then write: AB = K.
7. What is the intersection of two sets?
If the set P contains all the common elements of the sets A and B and only them, then the set P is called the intersection of the sets A and B. It is written like this: AB = P.
8. What is called the difference of sets A and B?
The difference of sets A and B is a set consisting of all elements of set A that do not belong to set B. It is denoted by: AB.
A bunch of
– the concept is primary, it is not given a definition. For example, many students in a class; many letters of the alphabet; set of natural numbers, etc. In mathematics, any collection is called in one word: set.
Exercises:
1.
What is the name: 1) many flowers in a vase?; 2) many musicians performing together; 3) the set of points in space equidistant from a given point?
2.
Give examples of sets that have: 1) 3 elements; 2) 7 elements; 3) 10 elements.
Answer:
1) many colors of traffic lights; 2) many days of the week; many colors of the rainbow; many notes; 3) many numbers.
3.
Given sets A = {1; 2; 3; 4; 5} and B = {3; 4; 5; 6; 7}.
Find: 1) 2) 3)
Answer:
1) 2) 3)
4.
What can be said about the sets A={▲, ■, ●} and B={●, ▲, ■}?
5.
Write down all subsets of the set A={▲, ■, ●}.
Answer:
{▲}, {■}, {●}, {▲, ■}, {▲, ●}, {■, ●}, {▲, ■, ●}, ∅.
Individually:
K-1
- Write down the set, listing its elements: A={x | x Є N, -3≤x<7}.
- Write down all subsets of the set M={a; b; c}.
- Given: A={3; a; b; c; 5}; B={5; d; 7; b}. Find: 1)
- Given: A={x | x2-5x+6=0}; B={x2-3x+2=0}. Find: 1)
- Find the intersection and union of sets A and B if
K-2
- Write down the set, listing its elements: A={x | x Є Z, -4≤x<5}.
- Write down all subsets of the set N={3; 5; 7}.
- Given: A={k; m; c; 7; 5}; B={7; d; 6; m}. Find: 1)
- Given: A={x | x2-3x+2=0}; B={x2-7x+10=0}. Find: 1)
- Find the intersection and union of sets A and B if
III . Formulating the topic, purpose and objectives of the lesson; motivation of educational activities
In everyday life, you often have to choose from a large number of options. For example, in how many ways can 10 football teams be ranked in the standings if no two of them have equal points?
In how many ways can you create a daily schedule of six different subjects for one class if 12 subjects are studied?
It turns out that similar problems have common solution methods, which you will become familiar with when studying combinatorics.
IV . Perception and awareness of new material
Saying "set", "subset",
they are not interested in the order of arrangement of their elements.
They say they are not ordered. ordered sets
are often considered - sets with a fixed order of elements.
They are denoted
by parentheses.
We often have to consider ordered sets
, i.e.
sets in which each element occupies its own, well-defined place. To order a set
means to put some element of the set in first place, some other element in second place, etc.
For example, from the elements of the set {a, b, c} we can form 6
three-element ordered sets:
(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a).
As sets they are all equal, as ordered sets they are different.
There are problems in which you need to determine how many different subsets or ordered subsets can be formed from the elements of a given set.
They are called combinatorial problems. And the branch of mathematics about solving combinatorial problems is called combinatorics .
Combinatorics
– one of the branches of mathematics that plays an important role in solving some modern problems in probability theory, cybernetics, mathematical logic, and number theory. Knowledge of combinatorics is necessary for representatives of a variety of specialties. Physicists, chemists, biologists, linguists, and code theorists have to deal with combinatorial problems. Here we will get acquainted with the basic concepts and methods of combinatorics.
Many combinatorics problems are solved using two basic rules - the sum rule and the product rule.
Sum Rule
If an element of a certain set A can be chosen in m ways, and an element of a set B in n ways, then an element from the set A or from B can be chosen in m + n ways.
The sum rule also applies to more sets.
For example,
There are 5 apples and 9 pears on a plate. One fruit can be selected in 5 + 9 = 14 ways.
Product rule
If the first component of a pair can be chosen m ways, and the second in n ways, then such a pair can be chosen in ways.
For example ,
from 6 types of envelopes without stamps and 5 types of stamps, one envelope and one stamp can be selected 65=30 (in ways).
The product rule also applies to ordered triples, quadruples, and any other ordered finite sets.
In particular, if the first element of an ordered triple can be chosen in m ways, the second in n ways, and the third in k ways, then such a triple can be chosen in mnk ways.
V. _ Understanding new material
Collective problem solving under the guidance of a teacher
1.
There are 15 boys and 12 girls in the class. In how many ways can you choose: a) a boy; b) a girl; c) one student of this class; d) two students - a boy and a girl?
(Answer:
a) 15 ways; 6) 12 ways; c) 27 ways; d) 180 ways
2.
The box contains 12 white and 16 black balls.
In how many ways can you take out: a) one ball of any color; b) two different colored balls? Solution.
a) According to the sum rule, one ball of any color can be removed in 12+16=28 (ways); b) according to the product rule, two different-colored balls can be removed in 1612 = 192 (ways).
Answer:
a) 28 ways; 6) 192 ways.
3.
There are 15 boys and 12 girls in the class.
One student has already been selected. In how many ways can you then choose a girl and a boy? Solution.
One student has already been selected. Then: a) if a boy was chosen, then there are 14 boys left and there are 14 options to choose from, and for girls there are 12 options, then a boy and a girl can be chosen in 1412=168 (ways); b) if a girl was chosen, then there are 11 of them left and then there are 1115 = 165 choices. So, according to the sum rule: 168 +165 = 333 (in ways).
Answer:
333 ways.
4.
There are fabrics in five different colors.
How many ways can you sew a tricolor flag? Solution.
The first color can be selected in five ways.
The second - four, the third - three. According to the product rule, a tricolor flag can be sewn in 543=60 (ways). Answer:
60 ways.
5.
How many four-digit numbers divisible by five can be made from the digits 0, 1,
2,
3, 5 if none of the digits are repeated in each number?
Solution.
The last digit of the composed number must be 0 or 5 (divisibility by 5). Then there are two options for selecting the last digit.
The first digit can be selected in four ways, the second in three, and the third in two.
This means there will be 2432 =48 four-digit numbers,
but it is necessary to exclude those that begin with zero and therefore end with 5.
The second digit in them can be selected in three ways, the third - in two.
That is, there will be 23 = 6. This means that the numbers that satisfy the condition will be 48–6 = 42.
Answer:
42 numbers.
( II method)
The last digit of the composed number must be 0 or 5 (divisibility by 5).
According to the multiplication rule, numbers ending in 0 will be 4·3·2·1=24.
There cannot be a 0 in the first place, which means that numbers ending with 5 are 3·3·2·1=18.
According to the addition rule, the total number of ways to combine the numbers 0, 1, 2,
3, 5 a four-digit number divisible by 5 is 24+18=42.
Answer:
42 numbers.
VI . Summing up the lesson
Frontal conversation
1. What does combinatorics study? 2. Formulate the sum rule and the product rule that underlie the solution of combinatorial problems. Give examples. 3. Which set is considered ordered? Give an example of an ordered finite set.
Individually
In how many ways can four algebra books and three geometry books be arranged so that all the geometry books are in a row?
(Answer:
720.)
VII . Homework
§ 17 repeat, §18 read, answer questions (p. 140), learn definitions; complete No. 607, 610, 623 (according to the textbook Bevz G.P. Mathematics 11th grade (standard level))
Permutations with repetitions
Previously, we considered cases where all the objects being rearranged were different. However, sometimes some of them are no different from each other. Suppose there are 3 books to be placed on a shelf, but two of them are identical. How many permutations are there then? The total number of permutations of 3 books is 3! = 6:
Here the same books are marked as A and A1. Obviously, the 1st and 2nd options (A1AB) and (AA1B) are actually no different from each other. The only difference in them is the order of identical books A and A1. In the first case, A1 is followed by A, and in the second, on the contrary, A is followed by A1. The same can be said about options 3 and 4, 5 and 6. It turns out that all possible permutations can be divided into groups containing “duplicate permutations”:
A1AB and AA1B
A1BA and ABA1
BA1A and BAA1
Each group contains exactly two “duplicates”. Why exactly two? This number is equal to the number of permutations of identical books. Since there are 2 identical volumes, and P2 = 2, then there are 2 “duplicates” in each group. Indeed, if we “removed” all the books from the shelf, except for the repetitive ones, then there would only be 2 identical volumes left, which can be rearranged in two ways.
In order to find the number of “original” permutations, their total number must be divided by the number of duplicates in each group.
6:2 = 3
Suppose now we need to arrange 4 books, 3 of which are identical. Let's designate the volumes as A, A1, A2 and B. You can write 4 in total! = 24 permutations. However, every 6 of them will duplicate each other. That is, they can be divided into groups, each of which will have 6 identical “duplicates”:
1st group: BAA1A2, BAA2A1, BA1AA2, BA1A2A, BA2AA1, BA2A1A
2nd group: ABA1A2, ABA2A1, A1BAA2, A1BA2A, A2BAA1, A2BA1A
3rd group: AA1BA2, AA2BA1, A1ABA2, A1A2BA, A2ABA1, A2A1BA
4th group: AA1A2B, AA2A1B, A1AA2B, A1A2AB, A2AA1B, A2A1AB
And again, to calculate the number of original permutations, divide the total number of permutations by the number of duplicates in each group:
P4/P3 = 4!/3! = 24/6 = 4
To denote permutations with repetitions, the notation is used
Рn(n1, n2, n3,… nk)
where n is the total number of objects, and n1, n2, n3,... nk is the number of identical elements. For example, in a problem with 4 books, we were looking for the value P4(3, 1), because there were 4 books in total, but they were divided into two groups, one of which contained 3 identical volumes (letters A, A1, A2), and another book (B) made up the second group. We noticed that to calculate the number of permutations with repetitions, we need to divide the total number of permutations by the number of duplicate permutations. The formula in general looks like this:
Example. Vasya decided that he should study only two foreign languages. He decided to spend 4 days a week on English and the remaining three days on Spanish. How many class schedules can he create for himself?
Solution. Vasya must arrange 3 Spanish lessons and 4 English lessons, then n1 = 3, and n2 = 4. The total number of lessons is 3 + 4 = 7. Then
Answer: 35
Please note that for convenience, when dividing factorials, we did not calculate them immediately, but tried to reduce the factors. Since the answer to any combinatorial problem is an integer, the entire denominator of the fraction will necessarily cancel with some factors in the numerator.
Example. Mom has 3 apples, 2 bananas and 1 orange. She distributes these fruits among 6 children. In how many ways can she do this if everyone has to get a piece of fruit?
Solution. There are three groups of fruits in total. The first group has 3 apples, so n1 = 3. The second group has 2 bananas, so n2 = 2. The third group has only 1 orange, so nk = 1. The total number of fruits is 6. We use the formula:
Answer: 60
In the denominator of the formula for permutations with repetitions, we write the number of objects in each group of identical objects. So, if 3 apples, 2 bananas and 1 orange are rearranged, then in the denominator we write 3!•2!•1!. But what happens if each group contains exactly one unique object? Then we write the product of units in the denominator:
As a result, we received the same formula as for permutations without repetitions. In other words, permutations without repetition can be considered simply as a special case of permutations with repetitions.
Placements
Let 6 teams participate in a football tournament. We are asked to guess the teams that will take prizes (that is, the first three places). How many variants of such triplets are there?
First, let's write down the team that will win the tournament. There are six options, depending on the number of participating teams. Let's write down these options:
Next, we will select one of the options and indicate the silver medalist of the competition for it. There are only 5 options here, because 1 of the 6 teams is already recorded in 1st place:
Such a five can be written down for each of the six options for who will become the champion. It turns out that there are 6•5 = 30 pairs “champion - silver medalist”. Finally, for one such pair, you can write 4 options for who will be third (you cannot write two commands, since they are already written on the first two lines):
For each pair you can record 4 top threes. Since the number of pairs “champion - vice-champion” is 6•5 = 30, then the number of triplets will be 6•5•4 = 120.
In this case, from a certain set of commands, we selected several and arranged them in some order. That is, we have chosen an ordered set. In combinatorics this is called placement.
If the total number of commands is denoted as n (in this example n = 6), and the number of commands being ordered is k , then the number of such placements in combinatorics is denoted as
In the example with teams, the number of placements was 120:
This entry reads as “the number of placements from 6 to 3 is 120.”
To find this number, we multiplied k (3) factors. The first one was equal to n (6), since each of the n teams could take first place. The second multiplier was equal to (n– 1), since after determining the champion we could put one of (n– 1) teams in second position. The third factor was equal to (n– 2). According to this logic, each subsequent factor will be less than the previous one by one. For example, to calculate the number of placements from 7 to 4, you need to multiply 4 factors, the first of which is equal to 7, and each next one is less than 1:
However, it is mathematically more convenient to represent this product as the ratio of two factorials. To do this, multiply the number of placements by the fraction 3!/3!, equal to one. Naturally, the number of placements does not change due to multiplication by one:
The number 3 in this case can be obtained by subtracting 4 from 7. In the general case, the number k must be subtracted from the number n . Then the formula for calculating the number of placements will take the form:
Example. There are 12 different subjects in the 8 “A” class program. On Monday there are 5 classes in a row. How many scheduling options are there for a class if two of the same lessons cannot be taught on a Monday?
Solution. To create a schedule, you need to select 5 subjects and put them in order. Therefore, we need to find placement from 12 to 5:
Answer: 95040
Example. There are 10 free seats in the carriage. 6 passengers boarded it. In how many ways can they arrange themselves in the carriage?
Solution. Out of ten seats, you need to select six and indicate for each which passenger it corresponds. That is, each passenger seating option is an arrangement of 10 to 6. Let’s find their number:
Answer: 151200
Note that permutation is a special case of placement when k = n. Indeed, if we need to indicate the top three winners of a tournament in which 6 teams participate, then we indicate a placement of 6 to 3. But if we indicate for each of the 6 teams what place it will take in the championship, then this is a placement of 6 to 6. On the other hand, this arrangement is also a permutation of 6 teams. Let us make sure that in this particular case the formula for calculating the number of placements will show the same result as the formula for permutations
For an example with 6 commands it would look like this:
Here we used the fact that the factorial of zero is taken to be equal to one. This reasoning can, on the contrary, be used to prove that the factorial of zero is one.
Basic concepts of probability theory
The basic concepts of probability theory are the concepts of an event and the probability of an event.
Finished works on a similar topic
- Course work Elements of combinatorics and probability theory 420 rub.
- Abstract Elements of combinatorics and probability theory 230 rub.
- Test work Elements of combinatorics and probability theory 190 rub.
Receive completed work or specialist advice on your educational project Find out the cost
Definition 4
an event any statement that may or may not happen.
Usually events are indicated in capital English letters.
Example: $A$ – the number $6$ is rolled on the dice.
Due to the fact that an event can have two variations of outcome (“happened” and “did not happen”), we are faced with the concept of the probability of such an event. This concept has $4$ basic definitions.
Classic definition.
The classical definition is associated with such undefined concepts as equal possibility and elementaryness of an event. They can be understood intuitively using the following examples:
Equal Opportunity: When tossing a coin, it can land on either the obverse or the reverse, regardless of external conditions. That is, we can say that the probability of getting one or the other side is essentially the same.
The elementary nature of the event: If the number $4$ appears on the dice, this means that the numbers $1, 2, 3, 5$ and $6$ have not fallen out.
Too lazy to read?
Ask a question to the experts and get an answer within 15 minutes!
Ask a Question
Definition 5
The probability of an event is the ratio of the number $n$ of equally possible elementary events of the initial event $B$ to all elementary events $N$.
Mathematically it looks like this:
$P(B)=\frac{n}{N}$
Geometric definition.
The geometric definition is applied to the case when the number of equally possible events is infinite. Here, to introduce the geometric definition, consider the following example. To play darts, take a circle with area $S$ and divide it into several circles. What is the probability that the dart will hit the center circle? (We will exclude here cases of complete failure to hit the field). It is obvious that there will be an infinite number of equally possible events here (as well as general events) since the circle contains an infinite number of points.
Let the area of the central circle be $s$. Then we are faced with a geometric definition of the probability of such an event:
$P(B)=\frac{s}{S}$
Statistical (frequency) definition.
The classical definition quite often does not take into account all possibilities. Considering even the classic example of throwing a dice, we neglect the possibility that none of the six numbers will come up (the die will simply “stop” on the corner). Therefore, the following definition of probability is introduced, taking into account all possibilities. Consider $N$ observations. Let the event we need occur $n$ times. Then
$P(B)=lim_{N→∞}\frac{n}{N}$
Axiomatic definition.
This definition is given using Kolmogorov’s axiomatics.
Let $X$ be the space of all elementary events. Then
Definition 6
We will call the probability of an event $B$ such a function $P(B)$ that satisfies the following conditions:
- This function is always non-negative,
- The probability that at least one of the pairwise incompatible events will occur is equal to the sum of their probabilities.
- The function is always less than or equal to $1$, and $P(X)=1$.
