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)

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.

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

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

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

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

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

negation – отрицание

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

69381. | Особливості архітектури типового мікроконтролера родини МК-51 | 2.36 MB | |

Структура типового МК (мікроконтролера) родини МК-51 (рисунок 1) містить: арифметико-логічний пристрій (АЛП); регістри тимчасового збереження операндів (програмно недоступні, на структурі МК позначені Т1, Т2); один з основних регістрів – акумулятор, на структурі МК позначений А... | |||

69382. | Особливості розробки робочої керуючої програми та програмна модель мікроконтролера | 302 KB | |

РПД являє собою 128 восьмирозрядних регістрів які призначені для прийому збереження та видачі різноманітної інформації. Шістнадцять із цих регістрів допускають побітову адресацію. В області молодших адрес РПД знаходяться 4 банки регістрів загального призначення РЗП кожен... | |||

69383. | ХАРАКТЕРИСТИКА КОМАНД МІКРОКОНТРОЛЕРА | 208 KB | |

Мнемоніка команди представлення коду операції у вигляді сполучення латинських літер що мають визначений зміст використовуються англійські слова або скорочення наприклад MOV PUSH POP JMP CLR NOP. Мнемокод включає в себе мнемоніку команди та опис операндів які беруть участь в операції. | |||