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.



50.91 KB

3 чел.


       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!  



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?


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 –  одновременный



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

22698. Національний банк України 24.5 KB
  2 Забезпечити високий рівень довіри в суспільстві до банків завдяки створенню дієвої системи нагляду за банківською діяльністю системи захисту інтересів вкладників та інвесторів системи оперативного кредитування комерційних банків з метою підвищення їх ліквідності. 3 Забезпечити високий ступінь незалежності і самостійності НБУ в проведенні монетарної політики з питань що стосуються сталості грошей чітко розмежувати кредитну діяльність банківської системи і фінансову діяльність уряду виключити пряме кредитування НБУ бюджетних витрат...
22699. Залучення іноземних інвестицій в Україну 27 KB
  На приплив іноземних інвестицій можна впливати лише побічно а саме: шляхом приведення інституційних та правових норм в Україні відповідно до міжнародних вимог. Для залучення іноземних інвестицій в Україну та їх ефективного використання необхідно: 1. На державному рівні відмовитися від мети залучення іноземних інвестицій будьякою ціною тобто не ставити іноземні компанії в більш привілейоване положення ніж національні.
22700. Ситсема держорганів, щ о регулюють ЗЕД 34 KB
  ситсема держорганів щ о регулюють ЗЕД Державне регулювання зовнішньоекономічної діяльності здійснюється для того щоб забезпечити: 1 захист економічних інтересів України та законних інтересів суб’єктів зовнішньоекономічної діяльності; 2 створення рівних можливостей для суб’єктів зовнішньоекономічної діяльності розвивати всі види підприємницької діяльності незалежно від форм власності та всі напрями використання доходів і здійснення інвестицій; 3 заохочення конкуренції та ліквідацію монополізму в сфері зовнішньоекономічної діяльності....
22701. Експорт та імпорт України 26.5 KB
  Існує заборона експорту або імпорту того чи іншого товару для захисту національних інтересів економічна безпека захист культурних цінностей фінансові положення тощо. Сьогодні ні розміри експорту ні його структура не можуть задовольнити Україну. Розміри експорту поки що недостатні: в 1995 р. У його структурі найбільшу частку мають сировина матеріали і товари народного споживання 876; машини і устаткування 103 інші товари у тому числі послуги 21 що вказує на дуже неефективну структуру експорту оскільки майже 90 його...
22702. Структурна політика розвитку 35.5 KB
  сукупних економічних проблем які виникають внаслідок структурних зрушень всередині галузей народного господарства та між ними регіонами і між групами підприємств структурна політика розвитку.Структурна політика розвитку використовується там і тоді де і коли виникає потреба у скороченні періоду адаптації галузей і регіонів до необхідних змін макроекономічної структури та коли структурні зрушення мають стати соціально вигідними для економічних суб'єктів. Заходи держави орієнтовані на галузі народного господарства визначаються як галузева...
22703. Зовнішньоекономічна діяльність 26 KB
  ЗЕЗ – це комплексна система різних форм міжнародного співробітництва. ЗЕЗ – категорія історична: продукт цивілізації виникає з появою держави та розвивається разом з нею. ЗЕЗ виступають елементом зростання та прискорення. В залежності від ефективності ЗЕЗ розглядають класифікацію.
22704. Українська класифікація товарів ЗЕД 19 KB
  Вона розроблена на базі гармонізованої системи опису та кодування товарів яка існує в світі з 1983 р. Цифрові коди товарів уніфіковано з гармонізованою системою в світі.
22705. Географічна і галузева структура прямих іноземних інвестицій 27 KB
  Географічна і галузева структура прямих іноземних інвестицій Державний комітет статистики зафіксував у 2002 році рекордний для України показник залучення прямих іноземних інвестицій у 107 млрд. Галузева структура іноземних інвестицій визначається значною диференціацією. Більше 60 іноземних інвестицій зосереджено у п'яти галузях харчовій промисловості внутрішній торгівлі машинобудуванні фінансах та паливній промисловості. Безпосередньо в 2000 році до галузей промисловості надійшло лише близько 42 прямих іноземних інвестицій тоді як...
22706. Основні системні наслідки економічного спаду 1992-1999 рр 44.5 KB
  Об'єкт економічної стратегії в Україні на початку періоду трансформації характеризувався складною і недосконалою структурою великою кількістю неузгоджених чинників розвитку що мають різну природу. Надмірний негативний вплив цих чинників став можливим через значну розбалансованість економічної стратегії неузгодженість її елементів. Ефективність економічної стратегії на цьому етапі може бути оцінена як вкрай низька. В основі його виникнення і поширення лежить відсутність економічної свободи і надмірно високі податки.