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



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

67859. Методы проектирования авиационных геоинформационных комплексов на основе информационно-структурного подхода 203 KB
  Системный подход В.М.Глушкова является достаточно хорошей основой для создания компонентов ИГК РВ, работающих в статике. Однако основной чертой таких комплексов, какими являются ИГК РВ, является их работа в динамике. Они должны успевать отображать в реальном времени быстротечные процессы...
  Современные радиотехнические системы часто включают в себя комплекс достаточно сложных электрических цепей среди которых разнообразные линейные цепи. Поэтому необходимо иметь ясное представление о таких процессах и уметь рассчитывать их для определенной цепи при заданном воздействии.
67861. Релігія як феномен духовної культури 73.5 KB
  Деномінація (лат. denominatio – наділення спеціальним ім’ям) – релігійне об’єднання, що перебуває в стадії організаційного оформлення; перехідний тип організації, яка має характеристики церкви( централізація, ієрархічні принципи управління, відмова від ізоляціонізму) та секти (визнання своєї виключності...
67862. Первісні вірування, ранні та пізні національні релігії 68.5 KB
  Особливості ранніх національних релігій об’єктами поклоніння були вже не духи, а боги, які, мали антропоморфний і деколи зооморфний характер; послідовний політеїзм (poly-багато, teoc – Бог), виникають ієрархії богів, на їх чолі стоять, як правило, боги Сонця чи Неба, або ж боги-деміурги...
67863. Буддизм. Організаційна структура буддизму 48.5 KB
  Буддизм є особливою світовою релігією: не знає Богатворця не визнає існування Бога у вигляді персоніфікованої могутньої особи; стверджує що матеріальний світ ілюзорний постійне коливання ідеальних частинок дхарм із яких комбінуються існуючі речі; вважає що людина позбавлена душі; тісно повязаний...
67864. Християнство: витоки, еволюція і сучасний стан 90.5 KB
  Засновник: ІCУС ХРИСТОС. Священні книги: Біблія, Священний переказ. Географічне поширення: країни Європи, Північно-Східної Євразії, Північної та Південної Америки, Австралії, Африки на південь від Сахари. Виникнення християнства звичайно пов’язується із початком нашої ери.
67865. Іслам – наймолодша світова релігія 45 KB
  Особливості релігійно – культурних традицій ісламу: злиття духовного і світського початків, політичної адміністрації і релігійної влади; в жодній мусульманській державі не існувало організованої церкви, яка б до того ж протистояла державі; це сприяло абсолютизації релігійного...