1. The schedule of one day contains 5 lessons. Determine the number of such schedules when choosing from eleven disciplines.
2. The commission consists of a chairman, his deputy and five other people. In how many ways can members of the commission distribute duties among themselves.
3. In how many ways can three attendants be chosen from a group of 20 people?
4. How many different sound combinations can be taken on ten selected piano keys, if each sound combination can contain from three to ten sounds.
5. There are 10 red and 5 pink carnations in a vase. In how many ways can five carnations of the same color be selected from a vase?
6. Tram route numbers are sometimes indicated by two colored lights. How many different routes can be marked using lanterns of eight colors.
7. From a group of 15 people, four participants in the relay race 800 + 400 + 200 + 100 are selected. In how many ways can the athletes be placed in the stages of the relay.
8. A team of five competes in a swimming competition with 20 other athletes. In how many ways can the places occupied by the members of this team be distributed.
9. From a group of 12 people, two attendants are selected daily for 6 days. Determine the number of different duty lists if each person is on duty once.
Questions for discussion on the forum
1. Solving problems of combinatorics.
List of additional literature:
1. Gorbatov V.A. Fundamentals of discrete mathematics. M.: Higher school, 2000. - 544 p.
2. V. A. Kofman, Introduction to applied combinatorics. M.: Radio and communication, 1982. 431s.
Seminar №7. Graph theory
The purpose of the workshop:
Consider issues related to the practical application of graph theory in decision making.
Lesson plan:
Semina is devoted to graph theory. The first topic is the basic concepts and operations on graphs, then the topic is dedicated to routes and trees. The workshop is 2 hours.
Task 1. Figure 7.1 shows graphs - with four vertices in each. Compare graphs.
Rice. 7.1. Counts -
Decision.
The results of the graph comparison are as follows:
unoriented;
Oriented;
Complete, and = ;
It is not complete, since although each pair of vertices is connected by an edge, there is a loop. Sometimes a complete graph is a graph with loops at all vertices, each pair of which is connected by an edge. The graph does not meet this definition.
All vertices of this graph are isolated (a graph with an empty set of edges, i.e. 0);
And they complement each other: = and = ;
Multigraph because it contains multiple edges a and b, as well as e and f;
Directed, canonically corresponding to an undirected graph;
And is not equal, since they have different edges (4,1) - and (1,4) in ;
Directed Multigraph: Edges a and b are multiples, while it is not a multigraph, since the edges in it a and b differently oriented.
Task 2. What are the degrees of the vertices of the graphs in Fig. 7.2.
Rice. 7.2. Counts and
Decision.
Both graphs have four vertices: . Degrees of vertices of an undirected graph: , , , , if we agree to consider the contribution of the loop to the degree of the vertex. The sum of the degrees of all vertices of the graph is 14, i.e. twice the number of edges in the graph:
Where m=7 is the number of graph edges.
Degrees of vertices of a directed graph:
The sums of degrees of vertices of the first and second type of graph coincide and are equal to the number m graph edges: .
Task 3. On fig. 7.3 shows a network graph (network model) for performing a set of operations (works) of a certain program. In it, arrows indicate operations, vertices - events that characterize the end of some work and the beginning of others. The direction of the arrows reflects the sequence of these events. Define a network graph in various ways.
Rice. 7.3. network graph
Decision.
The depicted network model is a directed graph that can be fully defined in various ways:
1) graphically (see figure above);
2) by specifying two sets: and ;
3) the incidence matrix (Table 7.1). A feature of the network model is that arrows exit from the initial event 1, and only enter the final event 6. Therefore, in the first row of the incidence matrix there are units only with a minus sign, and in the last row only with a plus sign;
Table 7.1. Incidence matrix
4) adjacency matrix (Table 7.2). For the reason indicated in paragraph 3, only zeros are placed in the last row of the adjacency matrix;
Table 7.2. Adjacency matrix
5) the list of edges defines a network graph in an obvious way, since the edges of the graph are denoted by their end vertices. In this case, the numbers of the vertices indicated in the "edges" column will be repeated in the "vertices" column of the list, and in the sequence in which the arrows - edges are indicated in this case.
Task 4. Do the graphs in Fig. 7.4 below are Hamiltonian cycles, chains.
Rice. 7.4. Counts and
Decision.
A Hamiltonian cycle as a simple cycle passing through all the vertices of the graph exists on the graph - it goes along the edges ( a, b, c, d, e, f, g, q, n, m, l, h, a). There is also a Hamiltonian chain in B, for which it suffices to remove any edge in the Hamiltonian cycle.
There is no Hamiltonian cycle in a graph: to go through the vertices a, b, c the outer triangle of the graph must contain all the edges lying on these sides, but then it does not pass through the vertex located in the center of the triangle d.However, there exists a Hamiltonian chain in the graph, for example, with the beginning at the vertex a, the end d and a sequence of edges connecting the vertices a, f, b, g, c, e, d.
Task 5. Shortest Path Problem. What is the shortest way to get from one graph vertex to another. In terms of production management: how to get from point A to point B in the shortest way (and, therefore, with the least fuel and time consumption). start vertex to end vertex. Consider the graph shown in Fig. 7.5.
Rice. 7.5. Graph
The situation can be described not only by a directed graph with weights assigned to the arcs, but also by a table (see table below). In this table, two vertices - the beginning of the path and the end of the path - are associated with the travel time. In table. 7.3 considers paths without intermediate stops. More complex routes are made up of elementary segments listed in the table.
Table 7.3. Initial data for the shortest path problem.
The question is asked in the problem: how to get from vertex 1 to vertex 4 in the shortest way.
Decision. Let's introduce the notation: With(T) - length of the shortest path from vertex 1 to vertex T. (Since any path to be considered consists of arcs, and there are a finite number of arcs, and each enters at most once, there are finitely many contenders for the shortest path, and the minimum of a finite number of elements is always reached.) The problem under consideration is to calculate With(4) and an indication of the path on which this minimum is reached.
For the initial data presented in fig. above and in table. above, only one arrow enters vertex 3, just from vertex 1, and near this arrow there is its length equal to 1, therefore With(3) = 1. Moreover, it is obvious that With(1) = 0.
You can get to vertex 4 either from vertex 2, having traveled a path equal to 4, or from vertex 5, having traveled a path equal to 5. Therefore, the relation
With(4) = min(С(2) + 4; With(5) + 5}.
Thus, the restructuring (simplification) of the problem has been carried out - finding С(4) has been reduced to finding С(2) and With(5).
You can get to vertex 5 either from vertex 3, having traveled a path equal to 2, or from vertex 6, having traveled a path equal to 3. Therefore, the relation
With(5) = min ( With(3) + 2; With(6) + 3}.
We know that With(3) = 1. Therefore
With(5) = min(3; With(6) + 3}.
Since it is obvious that With(6) is a positive number, then it follows from the last relation that With(5) = 3.
You can get to vertex 2 either from vertex 1, having traveled a path equal to 7, or from vertex 3, having traveled a path equal to 5, or from vertex 5, having traveled a path equal to 2. Therefore, the relation
With(2) = min (С(1) + 7; С(3) + 5; With(5) + 2}.
We know that With(1) = 0, With(3) = 1, With(5) = 3. Therefore
With(2) = min(0 + 7; 1 + 5; 3 + 2) = 5.
Now we can find With(4):
With(4) = min ( With(2) + 4; With(5) + 5) = min(5 + 4; 3 + 5) = 8.
Thus, the length of the shortest path is 8. It is clear from the last relation that one must go to vertex 4 through vertex 5. Returning to the calculation With(5), we see that we must go to vertex 5 through vertex 3. And we can get to vertex 3 only from vertex 1. So, the shortest path is as follows:
1 → 3 → 5 → 4 .
Task 6. The problem of the maximum flow. How (ie, on what routes) to send the maximum possible amount of goods from the starting point to the final point, if the capacity of the paths between the points is limited.
To solve this problem, each arc of the directed graph corresponding to the transport system must be associated with a number - the capacity of this arc. Consider the graph in Fig. 7.6.
Rice. 7.6. Graph
The initial data on the transport system, for example, in-plant, shown in fig. 7.6., You can also set the table in Table 7.4.
Table 7.4. Initial data for the shortest path problem.
Decision.
The solution of the maximum flow problem can be obtained from the following considerations.
Obviously, the maximum capacity of the transport system does not exceed 6, since no more than 6 units of cargo can be sent from the starting point 0, namely, 2 units to point 1, 3 units to point 2 and 1 unit to point 3.
Next, it is necessary to ensure that all 6 units of cargo leaving point 0 reach the final point 4. Obviously, 2 units of cargo that arrived at point 1 can be directly sent to point 4. The goods that arrived at point 2 will have to be divided: 2 units immediately sent to the point 4, and 1 unit - to the intermediate point 3 (due to the limited capacity of the section between points 2 and 4). The following cargoes were delivered to point 3: 1 unit from point 0 and 1 unit from point 2. We send them to point 4.
So, the maximum capacity of the transport system under consideration is 6 units of cargo. At the same time, internal sections (branches) between points 1 and 2, as well as between points 1 and 3 are not used. The branch between points 1 and 4 is not fully loaded - 2 units of cargo are sent along it with a throughput of 3 units.
The solution can be presented in the form of a table. 7.5.
Table 7.5. Solving the maximum flow problem
Omnibus N 9-10 2007.
Sea soul of route lights.
The mysterious thing is tradition. At first, they carefully observe it, trying to withstand all the nuances, bring it to superstition, then they suddenly discover that it does not live up to the expectations placed on it, does not meet logic, has no scientific justification - and they break with tradition, and subsequently notice with sadness that with her Lost something beautiful and necessary. . .
More recently, there was a tradition to give tram routes not only a digital, but also a color designation - route lights were lit on both sides of the route number, in front and behind the car. Streets with tram traffic were distinguished by a special, festive elegance, drivers, passengers, track workers, dispatchers and switchmen were guided by route lights in the tram flow, many could not imagine a tram without colored lights. The Moscow route lights system was built on a one-to-one correspondence between numbers and colors. "1" is always red, "2" is green, "5" is olive, "7" is blue, and so on. But in Leningrad, the lights "spoke" in a different language, and their reading "in Moscow" most often led to nonsense, since there were not 10 lights, as in Moscow, but only five. They differed well, and their combinations always looked very beautiful. However, out of five lights, 25 different combinations of two are possible, while the routes in St. Petersburg-Leningrad eventually became about 70, so the signs of the routes could be repeated. For example, two whites - 9, 43; red and yellow - 1, 51, 64; blue and red - 33, 52, 54; two red ones - 5, 36, 39, 45, 47. And only route N 20 was designated in the same way according to the Moscow and St. Petersburg systems: green and white.
It happened that the route lights in St. Petersburg changed. If it happened that after changing one of the routes it worked on a sufficiently long section with another route having the same colors, then one of these routes had to change the composition of the lights.
Route N 4 used to go from the island of the Decembrists to the Volkov cemetery and was indicated by two yellow (orange) lights. Then the route was closed and under the same number it was opened in another place with different lights: blue + blue, since it had a common section with the 35th tram (two yellow ones).
Route N 43 originally had lights: red + white. When extended to the port in 1985, the lights changed: white + white, as the route began to share a section with tram N 28 (red + white). Route 3 was marked with green and white colors. When the lights were restored in 2007, the combination was changed to yellow + green. At the same time, the combinations on a number of other routes also changed: 48 (was: white + white, now: blue + blue); 61 (was: white + white, now: white + yellow), etc.
The St. Petersburg system of route lights, so simple in appearance and so intricate, is connected with the tradition, first of all, of European tram cities. So, already in 1907, a letter to the Novoye Vremya newspaper contained a request from the "inhabitants of Vasilevsky Island" to introduce colored lights on trams, "as they do abroad, in particular in Frankfurt am Main." Currently, the remnants of the former systems have been preserved in the form of colored diagonal illumination on the route signs of trams in Amsterdam. This tradition, in turn, probably goes back to the navigational lights. Why exactly to the sea, and not, say, to the railway? Yes, because route lights, like sea lights, do not prohibit anything, do not force anyone, but simply help to orient themselves in the dark.
The lights of maritime navigation are deciphered in special maritime books - sailing directions of the seas. Route lights are also described in city guidebooks. The first of these was the "Mobile guide of St. Petersburg trams", published by the publishing house E.I. Marcus (1910).
The composition of the colors used in St. Petersburg route lights (white, red, orange or yellow, green, blue) differs little from the colors of sea lights (white, red, orange, green, blue, purple).
Looking closely, you can find other similarities, but it is much more important to understand why such a non-strict system of route lights has taken root in prudent Petersburg, requiring constant adjustment. The answer is simple: after all, St. Petersburg is a seaside city, and the severity of architectural forms and the frivolity of the carnival are equally characteristic of it, which means that the cheerful colors of the route lights are also characteristic.
In 2007, the tradition took a new turn. Now the cars are equipped with LED lamps for route lights. They will shine not only in the evening twilight, but also in the light of day.
Task number 3. Table 26 Option No. Job
Table 26
c) The subway train makes 16 stops where all passengers get off. In how many ways can 100 passengers board the train at the final stop be distributed between these stops?
ELEMENTS OF COMBINATORICS.
Sum and product rules.
Combinatorics (or compound theory) is a branch of mathematics that studies questions about how many different combinations that satisfy certain conditions can be made from given objects.
In the case when the intersection of sets A and B is not empty, the following equality holds: n(AÈB) = n(A) + n(B) – n(AÇB).
The number of elements in the union of three sets can be found by the formula
n(AÈBÈC) = n(A) + n(B) + n(C) - n(AÇB) -n(AÇC) - n(BÇC) - - n(AÇBÇC)
Example. Of the 40 students in the group, 35 successfully passed the exam in mathematics, and 37 in the Russian language. Two students received unsatisfactory grades in both subjects. How many students have academic debt?
Decision. Let A be the set of students who received an unsatisfactory grade in mathematics, then n(A) = 40 - 35 = 5; and B is the set of students who received an unsatisfactory mark in the Russian language, then n(B) = 40 - 37 = 3. Then the number of students with academic debt is n(AÈB). Hence, n(AÈB) = n(A) + n(B) - n(AÇB) = 5 + 3 – 2 = 6.
If AÇB = Æ, then n(AÈB) = n(A) + n(B)
sum rule and is formulated as follows: if element x can be chosen in k ways, and element y in m ways and, and no way of choosing element x is the same as any way of choosing element y, then the choice of "x or y" can be made k + m ways.
For sets, we also have n(А´В) = n(А) × n(В)
In combinatorics, this rule is called product rule and is formulated as follows: if the element x can be chosen in k ways, and if after each such choice the element y can be chosen in m ways, then the choice of the ordered pair m ways.
Example. There are 3 roads from city A to city B, and 2 roads from B to C. How many ways are there to travel from A to C via B?
Decision. If we denote the numbers 1, 2, 3, and the roads from B to C - the letters x and y, then each option of the path from A to C is given by an ordered pair of numbers and letters. But we can choose a number in three ways, and a letter in two ways, so the number of such ordered pairs is 3 × 2 = 6.
Accommodations.
Let n(A) = m. A tuple of length k (k £ m), whose components are elements of the set A, and all components are pairwise distinct, is called placement without repetition
For any set A such that n(A) = m, the number of possible arrangements of m elements by k is denoted
And it is calculated according to the formula
Example. 5 schoolchildren and 15 students participate in the chess tournament. In how many ways can the places occupied by schoolchildren in the tournament be distributed if it is known that no two participants have scored the same number of points?
Decision. In total there are 20 participants in the tournament. Consequently, out of 20 places, schoolchildren belong to 5. Therefore, the solution of the problem is associated with the formation of all possible tuples of length 5 from the elements of the set, in which there are 20 elements, that is, we are talking about placements without repetitions of 20 elements of 5 elements.
Let n(A) = m. A tuple of length k, whose components are elements of the set A, is called placement with repetitions from m elements to k elements.
For any set A such that n(A) = m, the number of possible arrangements with repetitions of m elements by k is denoted and calculated by the formula .
Example. There are 5 different chairs and 7 rolls of upholstery in different colors. In how many ways can chairs be upholstered?
Decision. Since the chairs are different, each upholstery is a tuple of length 5, made up of elements of a given set of fabric colors, containing 7 elements. This means that there are as many ways of upholstery of chairs as there are such tuples, that is, placements with repetitions of 7 elements by 5. We get .
Permutations.
Let n(A) = m. Permutation without repetition from m elements any ordered m-element set is called.
The number of different permutations of m elements is equal to the product of consecutive natural numbers from 1 to m inclusive, i.e.
Example. How many different five-digit numbers can be written using the digits 0, 1, 2, 3, 4 if no digit in the number is repeated twice?
Decision. The number of all possible permutations of five digits is P 5 = 5!. And since the number zero cannot take the first place, the desired number is:
P 5 - P 4 \u003d 5! - 4! = 120 - 24 = 96.
permutation with repetitions from the elements a, b,…,l, in which these elements are repeated m 1 , m 2 , ..., m k times, respectively, is called a tuple of length m = m 1 + m 2 + ... + m k , among the components of which a occurs m 1 times, b- m 2 times and so on l- mk times.
The number of permutations with repetitions is denoted by the symbol
Number of different permutations with repetitions of elements a, b,…,l, in which these elements are repeated m 1 , m 2 , ..., m k times, respectively, is determined by the formula
Example. How many eight-digit numbers can be written using the numbers 1, 3, 5, provided that the number 1 is repeated four times in each number, the numbers 3 and 5 - 2 times each?
Decision. The desired number is the number of different permutations with repetitions of the numbers 1, 3, 5, in which the number 1 is repeated four times, and the numbers 3 and 5 are repeated twice. Therefore, according to the formula, we have: 
.
Combinations.
Any k-element subset of an m-element set (k £ m) is called combination without repetition from m elements by k.
The number of different combinations of m elements by k is denoted by the symbol
Example. In how many ways can you choose three attendants out of 30 students?
Decision. Since the order of choosing the attendants does not play a role, the problem is about selecting from a set in which there are 30 elements of subsets containing three elements each, that is, combinations without repetitions of thirty elements of three.
Hence, 
.
Combination with repetitions from given m different types of elements by k elements, any collection containing k elements is called, each of which is one of the elements of the specified types.
The number of different combinations with repetitions of m elements by k elements will be denoted by the symbol .
The number of different combinations with repetitions of m types of elements for k elements is determined by the formula
Example. The post office sells four types of postcards. In how many ways can 9 postcards be bought here?
Decision. The number of ways to buy postcards is equal to the number of different combinations with repetitions of 4 elements by 9, that is, equal to 
.
The number of subsets of a finite set.
Let n(A) = m.
The number of all subsets of set A is 2 n .
Exercise 6
1. There are 30 people in the class attending optional classes in physics and mathematics. It is known that 10 people study both subjects in depth, and 25 people study mathematics. How many people attend optional classes only in physics?
2. Out of 50 students, 20 speak German and 15 speak English. What could be the number of students who know both languages; knowing at least one language?
3. Out of 100 people, 28 study English, 30 – German, 10 – French, 5 – German and French, 15 – German and English, 6 – English and French. All three languages are studied by 3 students. How many students study only one language? How many students do not study any language?
Tasks for independent work on the topic "Combinatorics" .
1. The schedule of one day contains 5 lessons in different subjects. Determine the number of such schedules when choosing from 11 items.
2. The commission consists of a chairman, his deputy and five more people. In how many ways can members of the commission distribute the duties of the chairman and deputy among themselves?
3. In how many ways can three attendants be chosen from a group of 20 people?
4. How many different sound combinations can be taken on ten selected piano keys, if each sound combination can contain from three to ten sounds?
5. There are 10 red and 5 pink carnations in a vase. In how many ways can five carnations of the same color be selected from a vase?
6. Tram route numbers are sometimes indicated by two colored lights. How many different routes can be marked using lanterns of eight colors?
7. The championship, in which 16 teams participate, is held in two rounds (ie each team meets every other twice). Determine the number of meetings to be held.
8. The lock only opens if a certain three-digit number is dialed. The attempt consists in typing three digits at random from the given five digits. It was possible to guess the number only on the last of all possible attempts. How many attempts were there before a successful one?
9. From a group of 15 people, four relay participants are selected 800 + 400 + 200 + 100. In how many ways can the athletes be placed in the stages of the relay?
10. A team of five competes in a swimming competition with 20 other athletes. In how many ways can the places occupied by the members of this team be distributed?
11. In how many ways can two rooks be placed on a chessboard so that one cannot capture the other? (One rook can capture another if it is on the same rank or file on the chessboard with it.)
12. Two rooks of different colors are placed on a chessboard so that each can capture the other. How many such locations exist?
13. The order of performance of eight participants in the competition is determined by lot. How many different outcomes of the draw are possible?
14. Thirty people are divided into three groups I, II and III of ten people each. How many different group compositions can there be?
15. How many four-digit numbers divisible by 5 can be made from the numbers 0, 1, 3, 5, 7, if each number must not contain the same digits?
16. How many different luminous rings can be made by placing 10 multi-colored light bulbs around a circle (the rings are considered the same if the colors are in the same order)?
17. There are 30 volumes on a bookshelf. In how many ways can they be arranged so that the first and second volumes do not stand side by side?
18. Four shooters must hit eight targets (two each). In how many ways can they distribute the targets among themselves?
19. From a group of 12 people, two duty officers are selected daily for 6 days. Determine the number of different duty lists if each person is on duty once.
20. How many four-digit numbers made up of the numbers 0, 1, 2, 3, 4, 5 contain the number 3 (the numbers in the numbers are not repeated)?
21. Ten groups are engaged in ten consecutive classrooms. How many scheduling options are there in which groups 1 and 2 would be in adjacent classrooms?
22. 16 chess players participate in the tournament. Determine the number of different schedules for the first round (schedules are considered different if they differ in the participants of at least one game; the color of the pieces and the number of the board are not taken into account).
23. Six boxes of various materials are delivered to five floors of the construction site. In how many ways can materials be determined by floors? In how many variants is any one material delivered to the fifth floor?
24. Two postmen must deliver 10 letters to 10 addresses. In how many ways can they distribute work?
©2015-2019 site
All rights belong to their authors. This site does not claim authorship, but provides free use.
Page creation date: 2016-08-20
Previously, tram numbers were marked with two colored lanterns. How many different routes can be marked using eight different colors of lights?
Answers:
the formula will be: 8²=64 64 different routes.
Similar questions
- Remember the architectural buildings and sculptures of the Renaissance, which have something similar to the Cathedral of the Renaissance, and the statue of Verrocchio. Write down their names.
- Insert instead of gaps the serial numbers of the corresponding words from the proposed list. The words are given in the list in the singular, in the nominative case. PLEASE NOTE: there are more words in the list than gaps in the text! A classification that, depending on the grounds and conditions for acquiring ____ membership, is widely used in ____, distinguishes personnel in ____ parties. The former are distinguished by the fact that they are formed around a group of political ___, and the basis of their structure is a committee of activists. Personnel parties are usually formed "from above" on the basis of various ___ factions, associations of the party bureaucracy. Such parties usually intensify their activities only for the time ___. Other parties are centralized, well-disciplined organizations. They attach great importance to the unity of party members. Such parties are most often formed "from below", on the basis of trade union and other ___ movements, reflecting various social interests. groups 1) Sociology 10) elections 2) public 11) norm 3 factor 12) party 4) electoral 13) parliamentary 5) national 14) consensus 6) society 15) idiological 7) mass 16) system 8) impeachment 17) leader 9) political science
- No. 1 Solve: 28/5 * 4 No. 2 The number a is marked on the coordinate line _______o____|___|___|___________> a -1 0 1 1) a; a -1;\frac(1)(a) 2) a;\frac(1)(a);a-1 3) a-1;\frac(1)(a);a 4)a-1; a;\frac(1)(a)
- is the number 2008*2011*2012*2014+1 an exact square
- There are 300 apartments in the newly built building. On the first day, 120 apartments were occupied, on the second day - a third of the rest. How many apartments are left to be occupied?
- Tolik multiplied a five-digit number by the sum of its digits. Then Tolik multiplied the result by the sum of his (result) digits. Surprisingly, it turned out to be a five-digit number again. What number did Tolik multiply for the first time? (Find all possible answers.)
