67866

Basic formulas of combinatorial analysis

Лекция

Математика и математический анализ

A reliable (universal) event is an event that necessarily will happen if a certain set of conditions S holds. For example, if a vessel contains water with a normal atmospheric pressure and temperature 20 degrees, the event «water in a vessel is in a liquid state» is reliable.

Английский

2014-09-15

50.91 KB

3 чел.

INTRODUCTION

       Events (phenomena) observed by us can be subdivided on the following three kinds: reliable, impossible and random.

       A reliable (universal) event is an event that necessarily will happen if a certain set of conditions S holds. For example, if a vessel contains water with a normal atmospheric pressure and temperature 20 degrees, the event «water in a vessel is in a liquid state» is reliable. In this example the given atmospheric pressure and temperature of water make the set of conditions S.

      An impossible (null) event is an event that certainly will not happen if the set of conditions S holds. For example, the event «water in a vessel is in a rigid state» certainly will not happen if the set of conditions of the previous example holds.

      A random event is an event that can either take place, or not to take place for holding the set of conditions S. For example, if a coin is tossed it can land on one of two sides: heads or tails. Therefore, the event «the coin lands on heads» is random. Each random event, in particular an appearance of heads, is the consequence of a functioning very many random reasons (in our example: the force with which the coin is tossed, the form of the coin and many others). It is impossible to take into account an influence on result of all these reasons as their number is very great and laws of their functioning are unknown. Therefore probability theory does not pose the problem to predict that a single event whether or not will happen – it simply is unable to solve this problem.

      We have another picture if we consider random events that can multiply be observed for holding the same conditions S, i.e. if the speech goes on mass homogeneous random events. It appears that a rather large number of homogeneous random events independently from their concrete nature are subordinated to definite regularities, namely probability regularities. Probability theory studies these regularities. Thus, the subject of probability theory is studying probability regularities of mass homogeneous random events.

      Methods of probability theory are widely applied in various branches of natural sciences and techniques: theory of reliability, theory of mass service,  theoretical physics, geodesy, astronomy, theory of shooting, theory of mistakes of observation, theory of automatic control, general theory of communication and many others theoretical and applied sciences. Probability theory serves also for a substantiation of mathematical statistics which is in turn used at planning and organizing a manufacture, at analysis of technological processes, and for many other purposes.

      All life a person has to make decisions: in personal sphere (in which university or college to enter, with whom to communicate; how to study); in public (to attend evenings, theatres, meetings, assemblies, elections); in industrial (determining factors essentially influencing on productivity, quality of materials and etc.); in scientific (promotion and checking scientific hypotheses).

      Decision-making usually pursues one of the following purposes: forecasting of a future state of a process (an object); control (i.e. how should to change certain parameters of an object in order that other parameters have taken on a desirable value); an explanation of internal structure of an object.

      Usually decision-making is preceded with an analysis of known data (on the basis of previous experience, common sense, intuition, and etc.). Aspiring to see and prove regularities in uncertain processes, the mankind has developed the whole arsenal of methods which refer to as mathematical statistics (applied statistics or data analysis).

      Mathematical statistics is a section of mathematics in which mathematical methods of ordering, processing and using statistical data for scientific and practical conclusions are studied.

      Abraham Wald (1902-1950) spoke that «mathematical statistics is theory of decision-making in conditions of uncertainty».

      In essence mathematical statistics gives a unique, mathematically proved apparatus for solving problems of control and forecasting at absence of obvious regularities (presence of randomness) in investigated processes.

     It is wonderful that the science begun with consideration of gambles was fated to become the major object of human knowledge …

Pierre-Simon Laplace (1749-1827)

L E C T U R E   1

Basic formulas of combinatorial analysis  

Here is a typical problem of interest involving probability. A communication system is to consist of n seemingly identical antennas that are to be lined up in a linear order. The resulting system will then be able to receive all incoming signals – and will be called functional – as long as no two consecutive antennas are defective. If it turns out that exactly m of the n antennas are defective, what is the probability that the resulting system will be functional? For instance, in the special case where n = 4 and m = 2 there are 6 possible system configurations – namely,

0110, 0101, 1010, 0011, 1001, 1100

where 1 means that the antenna is working and 0 that it is defective. As the resulting system will be functional in the first 3 arrangements and not functional in the remaining 3, it seems reasonable to take 3/6 = 1/2 as the desired probability. In the case of general n and m, we could compute the probability that the system is functional in a similar fashion. That is, we could count the number of configurations that result in the system being functional and then divide by the total number of all possible configurations.

From the preceding we see that it would be useful to have an effective method for counting the number of ways that things can occur. In fact, many problems in probability theory can be solved simply by counting the number of different ways that a determinate event can occur. The mathematical theory of counting is formally known as combinatorial analysis.

Combinatorial analysis studies quantities of ordered sets subordinate to determinate conditions, which can be made of elements, indifferent of a nature, of a given finite set.

Permutations are ordered sets consisting of the same n different elements and distinguishing only by the order of their disposition (location).

The number of all possible permutations     Pn = n!  

where                                        

  

Observe that it is convenient to consider 0!, assuming by definition that

0! = 1

Example. How many three-place numbers can be made of the digits 1, 2, 3 if each digit is included into the image of a number only once?

Solution: P3 = 3! = 1  2  3 = 6.

Allocations are ordered sets composed of n different elements on m elements, which are differed by either structure of elements or their order.

The number of all possible allocations

, i.e.

                                                

Example. How many signals is it possible to make of 6 flags of different colour taken on 2?

Solution:

Combinations are ordered sets composed of n different elements on m elements that are differed by at least one element.

The number of all possible combinations   

Example. How many ways are there to choose two details from a box containing 10 details?

Solution: The required number of ways   

Observe that the numbers of allocations, permutations and combinations are connected by the equality

Remark. It was above supposed that all n elements are different. If some elements are repeated then in this case ordered sets with repetitions are calculated by other formulas. For example, if there are n1 elements of one kind, n2 elements of other kind and et cetera among n elements then the number of permutations with repetitions 

                                                      

where  n1 + n2 + … = n.

Example. How many seven-place numbers consisting of the digits 4, 5 and 6 are there in which the digit 4 is repeated 3 times, and the digits 5 and 6 – 2 times?

Solution: Each seven-place number differs from other by the order of consecution of the digits (so that n1 = 3, n2 = 2, n3 = 2, and their sum is equal to 7), i.e. is the permutation with repetitions of 7 elements:

If in allocations (combinations) of n elements on m some of elements (or all) can appear identical, such allocations (combinations) are said to be allocations (combinations) with repetitions of n elements on m. For example, allocations with repetitions of 5 elements a, b, c, d, e on 3 are abc, cba, bcd, cdb, bbe, ebb, beb, ddd and et cetera; combinations with repetitions – abc, bcd, bbe, ddd and et cetera.

The number of allocations with repetitions of n elements on m is

 

The number of combinations with repetitions of n elements on m is

Example. 10 films participate in a competition on 5 nominations. How many variants of distribution of prizes are there, if on each nomination are established:

a) different prizes; b) identical prizes?

Solution: a) Each of variants of distribution of prizes represents a combination of 5 films from 10 that differs from other combinations by both the structure of elements and their order on nominations so that the same films can be repeated some times (a film can receive prizes on both one nomination and some nominations), i.e. it represents the allocations with repetitions of 10 elements on 5:

b) If identical prizes are established on each nomination then the order of following the films in a combination of 5 prizewinners doesn’t have any significance. Therefore, the number of variants of distribution of prizes represents the number of combinations with repetitions of 10 elements on 5:

The following rules are used for solving problems of combinatorial analysis:

Sum rule. If some object A can be chosen from the set of objects by m ways, and another object B can be chosen by n ways, then we can choose either A or B by m + n ways.

Example. There are 300 details in a box. It is known that 150 of them are details of the first kind, 120 – the second kind, and the rest – the third kind. How many ways of extracting a detail of the first or the second kind from the box are there?

Solution: A detail of the first kind can be extracted by n1 = 150 ways, of the second kind – by n2 = 120 ways. By the sum rule there are n1 + n2 = 150 + 120 = 270 ways of extracting a detail of the first or the second kind.

Product rule. If an object A can be chosen from the set of objects by m ways and after every such choice an object B can be chosen by n ways then the pair of the objects (A, B) in this order can be chosen by mn ways.

Example. There are 30 students in a group. It is necessary to choose a leader, its deputy and head of professional committee. How many ways of choosing them are there?

Solution: A leader can be chosen from any of 30 students, its deputy – from any of the rest 29 students, and head of professional committee – from any of the rest 28 students, i.e. n1 = 30, n2 = 29, n3 = 28. By the product rule the total number of ways is n1  n2  n3 = 30  29  28 = 24360.

Operations over events

We enter operations over events: sum, product and negation.

The sum of two events A and B is such third event A + B which consists in appearance of at least one of these events, i.e. A or B. If A and B are compatible events then their sum A + B means appearance of either the event A, or the event B, or both A and B. If A and B are incompatible events then their sum A + B means appearance of either the event A, or the event B. For example, if two shots are made by a gun and A is hit at the first shot, B is hit at the second shot then A + B is either hit at the first shot or hit at the second shot, or two hits. The event A + B + C consists of appearance of one of the following events: A; B; C; both A and B; both A and C; both B and C; all the events A, B and C.

The product of two events A and B is such third event AB which consists in simultaneous appearance of the events A and B. If A and B are incompatible events then their product AB is an impossible event.  

The negation of an event A is the event (not A) which consists in non-appearance of the event A. Observe that A + is a reliable event, and A is an impossible event.

Example. A winner of a competition is rewarded: by a prize (the event А), a money premium (the event В), a medal (the event С).

What do the following events represent: a) A + B; b) ABC; c) ?

Solution: a) The event A + B consists in rewarding the winner by a prize, or a money premium, or simultaneously both a prize and a money premium.

b) The event ABC consists in rewarding the winner by a prize, a money premium and a medal simultaneously.

c) The event consists in rewarding the winner by both a prize and a medal simultaneously without giving a money premium. 

Glossary

seemingly –  на вид, по-видимому;  arrangementрасположение

allocation – размещение;  combination – сочетание

permutation – перестановка;  three-place number – трехзначное число

consecution – следование;  repetition – повторение

to extract – извлекать;  simultaneous –  одновременный

negationотрицание


 

А также другие работы, которые могут Вас заинтересовать

76477. Осуществление супругами правомочий по владению, пользованию и распоряжению общим имуществом 14.94 KB
  Особенностью совместной собственности супругов является то что владение пользование и распоряжение общим имуществом супругов осуществляется по обоюдному согласию супругов п. В настоящее же время в отсутствие специальных правил единственным выходом для супругов которые не могут самостоятельно договориться по вопросу осуществления правомочий владения и пользования общим имуществом является раздел имущества который предполагает прекращение совместной собственности и возникновение общей долевой собственности. Определив свою долю в общем...
76478. Раздел общего имущества супругов: Соглашение о разделе имущества супругов 17.81 KB
  256 ГК РФ имущество нажитое во время брака супругами является их совместной собственностью а имущество которое принадлежало супругам до брака является имуществом каждого из супругов и разделу не подлежит за исключением случаев когда имущество одного из супругов признано судом общим имуществом супругов. 38 СК РФ устанавливает что общее имущество супругов может быть разделено как в течение брака так и после расторжения брака по требованию любого из супругов. Также общее имущество супругов может быть разделено по требованию кредиторов...
76479. Определение долей супругов при разделе имущества в судебном порядке 15.66 KB
  В соответствие с этим совершенно логично звучит принцип равенства долей супругов при разделе общего имущества закрепленный в п. Если договором между супругами не установлено иное то по закону по умолчанию каждый из супругов является собственником доли общего имущества в размере 1 2 части. Как уже упоминалось выше тот факт что один из супругов по уважительной причине не имел источника постоянного дохода или по совместному согласию занимался домашним хозяйством и воспитанием детей не дает никаких оснований уменьшать долю при разделе...
76480. Вопросы, разрешаемые судом при расторжении брака. Момент прекращения брака при разводе 16.15 KB
  24 СК РФ разрешить и другие вопросы: а с кем из родителей будут проживать несовершеннолетние дети после развода; б о взыскании с родителей средств на содержание детей; в о взыскании средств на содержание нетрудоспособного нуждающегося супруга; г о разделе имущества находящегося в общей совместной собственности супругов. Не вызывает сомнения что все перечисленные вопросы являются весьма важными для разводящихся супругов. 24 СК РФ требования об учете интересов детей и каждого из супругов например размер алиментов на несовершеннолетних...
76481. Брачный договор: понятие, форма, стороны 15.48 KB
  Брачный договор соглашение лиц вступающих в брак или соглашение супругов определяющее имущественные права и обязанности супругов в браке и или в случае его расторжения ст. По правовой природе брачный договор гражданскоправовой договор имеет особенности касающиеся субъектного состава предмета времени заключения и содержания договора; к нему могут применяться общие положения ГК о договорах; изменение расторжение и признание брачного договора недействительным происходят по основаниям и в порядке установленными нормами...
76482. Содержание брачного договора 15.8 KB
  Так брачным договором супруги вправе изменить установленный законом режим совместной собственности установить режим совместной долевой или раздельной собственности на все имущество супругов на его отдельные виды или на имущество каждого из супругов. Брачный договор может быть заключен как в отношении имеющегося так и в отношении будущего имущества супругов. Так условия брачного договора могут содержать: права и обязанности по взаимному содержанию; способы участия в доходах друг друга; порядок несения каждым из них семейных расходов;...
76483. Прекращение и изменение брачного договора 15.33 KB
  Соглашение об изменении или о расторжении брачного договора совершается в той же форме что и сам брачный договор т. Односторонний отказ от исполнения брачного договора не допускается. Может возникнуть ситуация когда супруги не пришли к обоюдному соглашению о расторжении брачного договора.
76484. Признание брачного договора недействительным 18.76 KB
  Брачный договор может быть признан судом недействительным в случае: признания брака недействительным; если условия договора ставят одного из супругов в крайне неблагоприятное положение; по основаниям предусмотренным ст. На признание брачного договора действительным или недействительным распространяются соответствующие нормы ГК РФ о действительности и недействительности сделок. Брачный договор может быть признан недействительным по иску супруга чьи права и законные интересы были нарушены в результате заключения договора: в состоянии...
76485. Обращение взыскание на имущество супругов. Гарантии прав кредиторов при заключении брачного договора 18.08 KB
  Таким имуществом в частности являются движимые и недвижимые вещи ценные бумаги паи доли в капитале внесенные в кредитные или иные коммерческие организации и любое другое нажитое в период брака имущество независимо от того на имя кого из супругов оно приобретено. 256 ГК РФ по обязательствам одного из супругов взыскание может быть обращено на его долю в общем имуществе супругов которая причиталась бы этому супругу при разделе имущества. 39 СК РФ доли супругов при разделе общего имущества признаются равными если иное не предусмотрено...