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 P_n = 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: P₃ = 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 n₁ elements of one kind, n₂ elements of other kind and et cetera among n elements then the number of permutations with repetitions

where n₁ + n₂ + … = 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 n ₁ = 3, n ₂ = 2, n ₃ = 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 n ₁ = 150 ways, of the second kind – by n ₂ = 120 ways. By the sum rule there are n₁ + n₂ = 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. n ₁ = 30, n ₂ = 29, n ₃ = 28. By the product rule the total number of ways is n ₁ × n ₂ × n ₃ = 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 – отрицание

Exercises for Seminar 2

2.1. A college planning committee consists of 3 freshmen, 4 sophomores, 5 juniors, and 2 seniors. A subcommittee of 4, consisting of 1 person from each class, is to be chosen (a freshman – первокурсник; a sophomore – второкурсник). How many different subcommittees are possible?

 

2.2. How many outcome sequences are possible when a die is rolled four times, where we say, for instance, that the outcome is 3, 4, 3, 1 if the first roll landed on 3, the second on 4, the third on 3, and the fourth on 1?

 

2.3. There are five disks on the general axis of a lock. Each disk is subdivided into six sectors on which different letters are written. The lock opens only in the event that each disk occupies one certain position regarding the case of the lock. Find the probability that the lock can be opened at any installation of disks (the case of a lock – корпус замка).

The answer: 0,0001286.

 

2.4. The order of performance of 7 participants of a competition is determined by a toss-up. How many different variants of the toss-up are possible?

 

2.5. There are 10 cards each of which contains one letter: 3 cards with letter A, 2 cards with letter S and 5 cards with letters D, R, O, M, B. A child takes cards in a random order and puts one to another. Find the probability that the word «AMBASSADOR» will be turned out (to turn out – оказываться).

 

2.6. By the conditions of the lottery «Sportloto 6 of 45» a participant of the lottery who have guessed 4, 5 or 6 numbers from 6 randomly selected numbers of 45 receives a monetary prize. Find the probability that the participant will guess: a) all 6 numbers; b) 4 numbers.

 

2.7. 10 of 30 students have sport categories. What is the probability that 3 randomly chosen students have sport categories?

The answer: 0,03.

 

2.8. A group consists of 12 students, and 8 of them are pupils with honor. 9 students are randomly selected. Find the probability that 5 pupils with honor will be among the selected.

The answer: 0,255.

 

2.9. Eight different books are randomly placed on one shelf. Find the probability that two certain books will be put beside (a shelf – полка, beside – рядом).

The answer: 0,25.

 

2.10. A box contains 5 red, 3 green and 2 blue pencils. 3 pencils are randomly extracted from the box. Find the probabilities of the following events:

A – all the extracted pencils are different color;

B – all the extracted pencils are the same color;

C – one blue pencil among the extracted;

D – exactly two pencils of the same color among the extracted.

The answer: P(A) = 0,25; P(B) = 0,092; P(C) = 0,467; P(D) = 0,658.

 

2.11. It has been sold 21 of 25 refrigerators of three marks available in quantities of 5, 7 and 13 units in a shop. Assuming that the probability to be sold for a refrigerator of each mark is the same, find the probability of the following events:

a) refrigerators of one mark have been unsold;

b) refrigerators of three different marks have been unsold.

The answer: a) 0,06; b) 0,396.

 

2.12. A shooter has made three shots in a target. Let A_i be the event «hit by the shooter at the i- th shot» (i = 1, 2, 3). Express by A ₁, A ₂, A ₃ and their negations the following events: A – «only one hit»; B – «three misses»; C – «three hits»; D – «at least one miss»; E – «no less than two hits»; F – «no more than one hit».

 

Exercises for Homework 2

2.13. How many different 7-place codes for license plates are possible if the first 3 places are to be occupied by letters of Latin alphabet and the final 4 by numbers?

The answer: 175760000.

 

2.14. In Ex. 2.13, how many codes for license plates would be possible if repetition among letters or numbers were prohibited?

 

2.15. 10 persons participate in competitions, and three of them will take the first, second and third places. How many different variants are possible?

The answer: 720.

 

2.16. How many ways of choosing 3 persons of 10 are possible?

The answer: 120.

 

2.17. A randomly taken phone number consists of 5 digits. What is the probability that all digits of the phone number are:

a) identical;

b) odd?

It is known that any phone number does not begin with the digit zero.

The answer: a) 0,0001; b) 0,0347.

 

2.18. There are 3 cards with letter S, 3 cards with letter T, 2 cards with letter I, 1 card with letter A and 1 card with letter C. Cards are mixed and randomly taken out without replacement by one. Find the probability that cards with letters are taken out by the way of consecution of letters of the word «STATISTICS».

The answer: 0,0000198.

 

2.19. A box contains 15 details, and 10 of them are painted. A collector chooses at random 3 details. Find the probability that the chosen details are painted (collector – сборщик).

The answer: 0,264.

 

2.20. Find the probability that from 10 books located in a random order, 3 certain books will be beside.

The answer: 0,0667.

 

2.21. Four tickets are distributed among 25 students (15 of them are girls). Everyone can take only one ticket. What is the probability that owners of these tickets will be:

a) four girls;

b) four young men;

c) three young men and one girl?

The answer: a) 0,108; b) 0,017; c) 0,142.

 

2.22. There are 100 products (including 4 defective) in a batch. The batch is arbitrarily divided into two equal parts which are sent to two consumers. What is the probability that all defective products will be got:

a) by one consumer;

b) by both consumers fifty-fifty?

The answer: a) 0,117; b) 0,383.

 

2.23. A library consists of ten different books, and five books cost on 4 thousands of tenghe each, three books – on one thousand of tenghe and two books – on 3 thousands of tenghe. Find the probability that two randomly taken books cost 5 thousands of tenghe.

The answer: 1/3.

 

2.24. A coin is tossed three times. Let A_i be the event «an appearance of heads at the i- th tossing» (i = 1, 2, 3). Express by A ₁, A ₂, A ₃ and their negations the following events: A – «three heads»; B – «three tails»; C – «at least one heads»; D – «at least one tails»; E – «only one heads»; F – «only one tails».

 

L E C T U R E 3