I.1 The basic principle of counting

(1)

Faculty of Mathematics

“Alexandru Ioan Cuza” University Tuesday, July 16^th2019

Applications of Probability Theory:

Combinatorial Identities

The Jassy Summer School, 7 – 21 July 2019

“A Journey Through Hard Sciences, Economics, Social Sciences and the Tourism Industry”

Module: Hard Sciences unveiled – an Interdisciplinary Tour

I Combinatorial Identities

In many situation it is useful to have an effective method for counting the number of ways that some things can occur. In fact, there exists a lot of examples that can be solved simply by counting the number of different ways that a certain event can occur. The mathematical theory of counting is formally known ascombinatorial analysis.

I.1 The basic principle of counting

This principle is fundamental in our work.

• The basic principle of counting (the multiplication principle)

Suppose that two experiments are to be performed. Then if the first experiment can result in any one ofm possible outcomes and if, for each outcome of the first experiment, there arenpossible outcomes of the second experiment, then together there arem·npossible outcomes of the two experiments.

Proof of the Basic Principle.The basic principle may be proven by enumerating all the possible outcomes of the two experiments:

(1,1) (1,2) . . . (1, n) (2,1) (2,2) . . . (2, n)

...

(m,1) (m,2) . . . (m, n)

where the outcome is(i, j)if the first experiment results in itsi^thpossible outcome and the second experiment then results in itsj^thpossible outcome. Hence, the set of possible outcomes consists ofmrows, each containing nelements. This proves the result.

Example 1 A small community consists of10women, each of whom has3children. If one woman and one of her children are to be chosen as mother and child of the month, how many different choices are possible?

By regarding the choice of the woman as the outcome of the first experiment and the subsequent choice of one of her children as the outcome of the second experiment, we see from the basic principle that there are10×3 = 30possible choices.

(2)

When there are more than two experiments to be performed, the basic principle can be generalized.

• The generalized basic principle of counting

Ifrexperiments that are to be performed are such that the first one may result in any ofn₁possible outcomes;

and if, for each of thesen1possible outcomes, there aren2possible outcomes of the second experiment; and if, for each of the possible outcomes of the first two experiments, there aren3possible outcomes of the third experiment and so on. Then there is a total ofn1·n2·. . .·nrpossible outcomes of therexperiments.

Example 2 A college planning committee consists of3freshmen,4sophomores,5juniors, and2seniors. A subcommittee of 4, consisting of one person from each class, is to be chosen. How many different subcommittees are possible?

We may regard the choice of a subcommittee as the combined outcome of the four separate experiments of choosing a single representative from each of the classes. It then follows from the generalized version of the basic principle that there are 3×4×5×2 = 120possible subcommittees.

I.2 Permutations

How many different ordered arrangements of the lettersa,b, andcare possible? By direct enumeration we see that there are6, namely,

abc, acb, bac, bca, cab, cba.

Each arrangement is known as apermutation. Thus, there are6possible permutations of a set of3objects.

This result could also have been obtained from the basic principle, since the first object in the permutation can be any of the3, the second object in the permutation can then be chosen from any of the remaining2, and the third object in the permutation is then the remaining1. Thus, there are3×2×1 = 6possible permutations.

• Suppose now that we havenobjects. Reasoning similar to that we have just used for the3letters, i.e. using the basic principle of counting, we see that there are

n! =n·(n−1)·(n−2)·. . .·3·2·1 differentpermutationsof thenobjects.

Example 3 How many different batting orders are possible for a baseball team consisting of9players?

There are9! = 362,880possible batting orders.

Example 4 A class in Probability Theory consists of6 men and4 women. An examination is given, and the students are ranked according to their performance. Assume that no two students obtain the same score.

(a)How many different rankings are possible?

Because each ranking corresponds to a particular ordered arrangement of the10people, the answer to this part is10! = 3,628,800.

(b)If the men are ranked just among themselves and the women just among themselves, how many different rankings are possible?

Since there are6!possible rankings of the men among themselves and4!possible rankings of the women among themselves, it follows from the basic principle that there are6!×4! = 720×24 = 17,280possible rankings in this case.

Example 5 How many different letter arrangements can be formed from the letters of the wordP EP P ER?

We first note that there are6!permutations of the lettersP1E1P2P3E2R, when the3P’s and the2E’s are distinguished from each other.

However, let us consider any one of these permutations, for instance,P₁P₂E₁P₃RE₂.

(3)

If we now permute theP’s among themselves and theE’s among themselves, then the resultant arrangement would still be of the formP P EP RE. That is, all3!·2!permutations:

P1P2E1P3RE2 P1P2E2P3RE1

P₃P₁E₁P₂RE₂ P₃P₁E₂P₂RE₁ P3P2E1P1RE2 P3P2E2P1RE1

are of the formP P EP RE. Hence, there are6!/(3!·2!) = 60possible letter arrangements of the letters of the wordP EP P ER.

Example 6 In general, the same reasoning as that used in the previous example shows that there are n!

n1!·n2!·. . .·nr!

different permutations ofnobjects, of whichn1are alike,n2are alike, . . . ,nrare alike.

• We also use the termpermutationswhen we do not consider arrangements of allnelements, but of onlyr≤n elements. The number of permutations ofrobjects drawn from a set ofndistinct objects can be derived in a similar manner, i.e. using the basic principle of counting, and is equal to

n·(n−1)·(n−2)·. . .·(n−r+ 1) which can be written as well as

nPr:=n·(n−1)·(n−2)·. . .·(n−r+ 1) = n!

(n−r)!.

Example 7 The number of permutations when drawing without replacement3 balls from a box with10numbered balls is

10P3:= 10·9·8 = ^10!_7! = 720.

I.3 Combinations

We are often interested in determining the number of different groups ofrobjects that could be formed from a total ofnobjects. For instance, how many different groups of3could be selected from the5itemsA, B, C, D, andE?

To answer this question, reason as follows: since there are5ways to select the initial item,4ways to then select the next item, and3ways to select the final item, there are thus5·4·3ways of selecting the group of3when the order in which the items are selected is relevant.

However, since every group of3,let’s say, the group consisting of itemsA, B,andC, will be counted6times (that is, all of the permutationsABC, ACB, BAC, BCA, CAB,andCBAwill be counted when the order of selection is relevant), it follows that the total number of groups that can be formed is

5·4·3 3·2·1 = 5!

3! 2!.

• Suppose now that we havenobjects. Reasonin similar to that we have just used above, i.e. using the basic principle of counting, we see that there are

n r

,forr≤n,where n

r

:= n!

r! (n−r)!, number of possiblecombinationsofnobjects takenrat a time¹.

1By convention,0!is taken1.Therefore,n 0

=n n

= 1.We also taken i

to be0wheneveri <0ori > n.

(4)

Thus, n

r

represents the number of different groups of sizerthat could be selected from a set ofnobjects when the order of selection is not considered relevant.

We also denote n

r

by nCr or by C_n^r.

Example 8 A committee of3is to be formed from a group of20people. How many different committees are possible?

There are 20

3

= 20·19·18 3·2·1 = 20!

3! 17! = 1140possible committees.

• The values n

r

are often referred to asbinomial coefficients because of their prominence in the binomial theorem.

The binomial theorem

(x+y)ⁿ =Xⁿ

k=0

n k

x^ky^n−k, x, y∈R. (1)

Equality (1) may be proved analytically or by the following combinatorial argument.

Let us consider the product

(x1+y1) (x2+y2). . .(xn+yn).

Its expansion consists of the sum of2ⁿterms, each term being the product ofnfactors. Furthermore, each of the2ⁿterms in the sum will contain as a factor eitherxioryi,for eachi= 1, n .For example,

(x1+y1) (x2+y2) =x1x2+x1y2+y1x2+y1y2.

Now, how many of the2ⁿ terms in the sum will havekof thexi’s and(n−k)of theyi’s as factors? As each term consisting ofkof thexi’s and(n−k)of theyi’s corresponds to a choice of a group ofkfrom thenvalues x1, x2, . . . , xn,there are ⁿ_k

such terms.

Thus, lettingx_i=xandy_i=y,we obtain equality (1).

Example 9 How many subsets are there of a set consisting ofnelements?

Since there are ⁿ_k

subsets of sizek,the desired answer isPn k=0

n k

which is

Xⁿ

k=0

n k

= (1 + 1)ⁿ= 2ⁿ. (2)

Remark 10 The results on the number of samples of sizek(i.e. k−tuples) from a urn withnbals are presented in the next table:

PP PP

PP PPP Sample

Type of

tuple Ordered Unordered

With replacement n^k C_n+k−1^k Without replacement A^k_n C_n^k

For instance, the possible results on the number of samples of size2(i.e.2−tuples) from a urn with3bals are presented in

(5)

the next table:

PP PP

PP PPP Sample

Type of

tuple Ordered Unordered

With replacement

(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)

(1,1) (1,2) (1,3) (2,2) (2,3)

(3,3) Without replacement

(1,2) (1,3) (2,1) (2,3) (3,1) (3,2)

(1,2) (1,3) (2,3)

I.4 Multinomial Coefficients

In this section, we consider the following problem: a set ofndistinct items is to be divided intordistinct groups of respective sizesn1, n2, . . . , nr,wherePr

i=1ni=n.How many different divisions are possible?

To answer this question, we note that there are n

n1

possible choices for the first group; for each choice of the first group, there are

n−n1

n₂

possible choices for the second group; for each choice of the first two groups, there are

n−n₁−n₂ n3

possible choices for the third group and so on. It then follows from the generalized version of the basic counting principle that there are

n n₁

·

n−n1

n₂

·. . .·

n−n1−n2−. . .−n_r−1 n_r

= n!

n1! (n−n1)!· (n−n₁)!

n2! (n−n1−n2)!·. . .·(n−n₁−n₂−. . .−n_r−1)!

nr! 0!

= n!

n₁!n₂!. . . n_r! possible divisions.

• As above, letPr

i=1ni=n.We define

n n₁, n₂, . . . , n_r

by n

n1, n2, . . . , nr

:= n!

n1!n2!. . . nr! and we say that

n n1, n2, . . . , nr

represents the number of possible divisions ofndistinct objects intordistinct groups of respective sizesn₁, n₂, . . . , n_r.

Example 11 A police department in a small city consists of10officers. If the department policy is to have5of the officers patrolling the streets,2of the officers working full time at the station, and3of the officers on reserve at the station, how many different divisions of the10officers into the3groups are possible?

There are_{5! 2! 3!}^10! = 2520possible divisions.

• The values

n n₁, n₂, . . . , n_r

are often referred to asmultinomial coefficientsbecause of their prominence in the multinomial theorem.

(6)

The multinomial theorem

(x₁+x₂+. . .+x_r)ⁿ=X

n1,n2,...,nr=0,n n1+n2+...+nr=n

n n₁, n₂, . . . , n_r

xⁿ₁¹xⁿ₂² . . . xⁿ_r^r, x₁, x, . . . , x_r∈R. (3)

Equality (3) may be proved analytically or by the following combinatorial argument.

I.5 Solved Exercises

1. Prove, using a combinatorial argument, that the number of all the ordered sequence of r objects taken with replacement from a set ofndistinct objects that can be constructed isn^r.

2. Prove, using a combinatorial argument, that the number of all the ordered sequence ofrobjects taken without replacement from a set ofndistinct objects (which is called apermutationof sizerof thenobjects) that can be constructed isnPr= n!

(n−r)!.

3. Prove, using a combinatorial argument, that the number of all the unordered subset ofrobjects taken without replacement from a set ofndistinct objects (which is called acombinationof sizerof thenobjects) that can be constructed isC_n^r = n!

r! (n−r)!. Solution.

Sincen·(n−1)·. . .·(n−r+ 1)represents the number of different ways that a group ofritems could be selected fromnitems when the order of selection is relevant, and as each group ofritems will be countedr!times in this count, it follows that the number of different groups ofritems that could be formed from a set ofnitems is

n·(n−1)·. . .·(n−r+ 1)

r! = n!

r! (n−r)!.

4. Prove, using a combinatorial argument, the following combinatorial identity²:

C_n^r=C_n^n−r. (4)

Solution.

We should obtain in two different manner the number of all the unordered subset ofr objects taken without replacement from a set ofndistinct objects.

5. From a group ofnpeople suppose that we want to choose a committee ofrpersons. Count the total number of committee of sizer,and, after that, the total number of committee of sizerwhich contain and which doesn’t contain a particular element.

Prove the following combinatorial identity³:

C_n^r=C_n−1^r−1+C_n−1^r , 1≤r≤n (Pascal triangle rule) (5) Solution.

2All the next combinatorial identities may be proved analytically also.

3The numbers from the Pascal triangle are the binomial coefficients and the representation is:

1 1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

(7)

Of course, there is a total ofC_n^rgroups of sizer.On the other hand, let’s fix attention on some particular one of these objects, and call it object1.Now, there areC_n−1^r−1groups of sizerthat contain object1(since each such group is formed by selectingr−1from the remainingn−1objects). Also, there areC_n−1^r groups of sizerthat do not contain object1. Hence equality (5) follows.

6. From a group of(n+m)people, wherenare men andmare women, suppose that we want to choose a committee ofrpersons (with0≤r≤n∧m). Find in two ways the total number of these committees.

Prove⁴the following combinatorial identity⁵:

C_n^r·C_m⁰ +C_n^r−1·C_m¹ +C_n^r−2·C_m² +. . .+C_n⁰·C_m^r =C_n+m^r (Vandermonde binomial convolution) (6) In particular, deduce that

C_n⁰²

+ C_n¹²

+ C_n²²

+. . .+ C_nⁿ⁻¹²

+ (C_nⁿ)²=C_2nⁿ . (7) Solution.⁶

Obviously, there areC_n+m^r numbers of groups ofrpersons from(n+m)persons. On the other hand, a group of rpersons can be made in this manner: let us takek= 0, r and, for eachk,let us considerkpersons from then men and the other(r−k)persons from themwomen. Therefore, using the the multiplication principle, we have C_n^k·C_m^k−rnumbers of groups.

Hence the total number of groups ofrpersons isC_n^r·C_m⁰ +C_n^r−1·C_m¹ +C_n^r−2·C_m² +. . .+C_n⁰·C_m^r ,whereris such that0≤r≤n∧m.

Hence equality (6) follows.

7. For a game we have5girls and3boys. They should form a team of4persons. How many teams can be made?

Solution.

A team can be made inC₅⁴·C₃⁰+C₅³·C₃¹+C₅²·C₃²+C₅¹·C₃³= 70ways or, directly, inC₈⁴ways, since the order is not important.

We therefore obtain the combinatorial identity:

C₅⁴·C₃⁰+C₅³·C₃¹+C₅²·C₃²+C₅¹·C₃³=C₈⁴.

8. Let us take the group{1,2, . . . , n}andksuch thatk≤nandisuch thatk≤i≤n.Find the total number of the subsets ofknumbers we can made such that the numberiis the highest-numbered member of the respectively subset.

Prove the following combinatorial identity:

C_k−1^k−1+C_k^k−1+C_k+1^k−1+. . .+C_n−1^k−1=C_n^k (Fermat combinatorial identity) (8) Solution.

Obviously, there areC_n^k numbers of subsets ofknumbers from the initial set. On the other hand, if in the subset iis the greater number, then the other(k−1)are randomly chosen from the other(i−1)remaining numbers.

Therefore there areC_i−1^k−1ways to have a subset of(k−1)numbers from the(i−1)numbers.

And the total number of the subsets ofknumbers that can be made such that the numberi=k, nis the greatest number of the respective subset isPn

i=kC_i−1^k−1.Hence equality (8) follows.

4Let us remark that the identity can be deduce directly, by identification of the coefficients ofx^rfrom the equality(a+b)ⁿ(a+b)^m = (a+b)^n+m.

5See also the convention from the page3and afterthat equalities (14-17).

6See also Exercise14.

(8)

9. From a group ofnpeople, suppose that we want to choose a committee of any size. Find in two ways the total number of these kind of committees.

C_n⁰+C_n¹+C_n²+. . .+C_nⁿ = 2ⁿ. (9) Solution.

The npersons may be or not in the committee. Hence the total number of committees with any number of members is, using the multiplication principle,2·2·. . .·2 = 2ⁿ.Note that we have included the set consisting of 0elements (that is, the null set) as a subset of the original set. Hence, the number of subsets that contain at least one element is2ⁿ−1.

On the other hand, the total number of committees withk members (with0 ≤ k ≤ n) isC_n^k,hence the total number of committees withk= 0, nmembers isPn

k=0C_n^k. Hence equality (9) follows.

10. From a group of npeople, suppose that we want to choose a committee of any size, one of whom is to be designated as chairperson. Find in two ways the total number of these kind of committees.

1·C_n¹+ 2·C_n²+. . .+n·C_nⁿ =n·2ⁿ⁻¹. (10) Solution.

The chairperson can be any person from thenpeople and the other(n−1)people may be or not in the committee.

But the number of possible selections of a committee of any size (minimum0and maximum(n−1)) is2ⁿ⁻¹. Hence, using the multiplication principle, the number of possible selections of a committee of any size and a chairperson for the committee isn·2ⁿ⁻¹.

On the other hand, the number of possible selections of a committee withkmembers (whit1 ≤ k ≤ n) from thenpersons isC_n^kand the chairperson may be any of thekpersons from the committee. Hence the number of possible selections of a committee withkmembers and of a chairperson of this committee isk·C_n^k.

Therefore, the total number of possible selections of a committee withk= 1, nmembers and of a chairperson of this committee isPn

k=1k·C_n^k. Hence equality (10) follows.

11. From a group of npeople, suppose that we want to choose a committee of any size, one of whom is to be designated as chairperson and another as secretary (the chairperson can be the secretary). Find in two ways the total number of these kind of committees.

1²·C_n¹+ 2²·C_n²+. . .+n²·C_nⁿ=n(n+ 1)·2ⁿ⁻². (11) Solution.

The number of possible selections of a committee withkmembers (whit1 ≤k ≤n) from thenpersons isC_n^k and the chairperson may be any of thek persons from the committee and the secretary may be any of thek persons from the committee. Hence the number of possible selections of a committee withkmembers and of a chairperson and of a secretary of this committee isk·k·C_n^k.

Therefore, the total number of possible selections of a committee withk = 1, nmembers and of a chairperson and of a secretary of this committee isPn

k=1k²·C_n^k.

On the other hand, if the chairperson is the same with the secretary, then we havenways and the other(n−1) persons may be or not in the committee. Hence the number of possible selections of a committee of any size and a chairperson (which is also the secretary) is, by the multiplication principle,n·2ⁿ⁻¹.

(9)

If we want that the chairperson to be different from the secretary, then we havenpossibilities in choosing the chairperson, hence the are(n−1)ways to chose the secretary and the other(n−2)persons may be or not in the committee. Hence the number of possible selections of a committee of any size and a chairperson and a different secretary is, by the multiplication principle,n·(n−1)·2ⁿ⁻².

Therefore, the number of possible selections of a committee of any size and a chairperson and a secretary (possibly the same as the chairperson) for the committee is

n·2ⁿ⁻¹+n·(n−1)·2ⁿ⁻². Hence equality (10) follows:

Xⁿ

k=1k²·C_n^k =n·2ⁿ⁻¹+n·(n−1)·2ⁿ⁻²=n(n+ 1)·2ⁿ⁻².

12. Suppose that a sample of sizenis to be chosen randomly (without replacement) from an urn containing2nballs, of whichnare white andnare black. If we letXdenote the number of white balls selected⁷, then prove that⁸

P(X=k) = C_n^k²

C_2nⁿ , withk= 0, n . Prove the following combinatorial identity:

C_n⁰²

+ C_n¹²

+ C_n²²

+. . .+ C_nⁿ⁻¹²

+ (C_nⁿ)²=C_2nⁿ . (12) Solution.

We can count, using the notion of combinations, the multiplication principle and the definition of the probability⁹, and we obtain

P(X =k) =C_n^k·C_n^n−k

C_n+nⁿ = C_n^k² C_2nⁿ .

On the other hand, the events{X =k}_k=0,nrepresent a partition of the entire spaceΩ,therefore 1 =P(Ω) =P[ⁿ

k=0{X =k}

=Xⁿ

k=0P(X=k)

⇔ Xⁿ

k=0

C_n^k²

C_2nⁿ = 1 ⇔ Xⁿ

k=0 C_n^k²

=C_2nⁿ . 13. Prove that

n! =Xⁿ

i=0(−1)ⁱC_nⁱ(n−i)ⁿ. Solution.

Dac˘aD, C sunt dou˘a mult,imi cu un num˘ar finit de elementecard (D) =|D|=niarcard (C) =|C|=m, atunci num˘arul tuturor funct,iilorf :D→Ceste

mⁿ =|D|^|C|.

Într-adev˘ar, fiec˘arui element al mult,imiiDi se pot asociamvalori, deci, folosind principiul multiplic˘arii, num˘arul tuturorn−uplurilor ordonate(a₁, a₂, . . . , a_n)care se pot scrie estem·m·. . .·m

| {z }

den-ori

=mⁿ.

7See Definition29

8For the definition of a random variable see page15

9In the particular case whenΩhas a finite number of elements,Fmay be taken a subset (which should be aσ–algebra) of all the parts of Ω,denoted byP(Ω)(possibleF =P(Ω)) and the probability measure is takenP(A) = ^|A|_|Ω|,for anyA∈ F,where|A|is the cardinal of the setA.More precisely, the probability of an event is the number of the outcomes in that event divided by the total number of possible outcomes, provided that all the outcomes are “equally likely”. We denote the total number of outcomes by|Ω|and the total number of those that are within eventAby|A|.

(10)

Evident, dac˘a|D|= n > m= |C|,atunci nu exist˘a nici o funct,ie injectiv˘a întreDs,iC.Dac˘an≤ m,num˘arul tuturor funct,iilor injectivef :D→Ceste

Aⁿ_m=A^|D|_|C|.

Într-adev˘ar, dac˘an ≤m, atunci elementuluia1i se pot asociamvalori, elementuluia2 i se pot asocia(m−1) valori (deoarece asocierea este injectiv˘a s,i deci o valoare dinCnu se mai poate asocia nici unui alt element din D) s,.a.m.d. În final, elementuluian i se pot asocia(m−(n−1))valori. Deci, folosind principiul multiplic˘arii, num˘arul tuturorn−uplurilor ordonate(a1, a2, . . . , an)care se pot scrie este

m·(m−1)·. . .·(m−(n−1)) = m!

(m−n)! =Aⁿ_m. Evident,num˘arul tuturor funct,iilor bijectivef :D→Ceste

n! =A^|C|_|C|

deoarece trebuie s˘a avem|C|=|D|.

În ceea ce prives,te num˘arul de funct,ii surjective s˘a observ˘am c˘a dac˘a|D| =n < m=|C|,atunci nu exist˘a nici o funct,ie surjectiv˘a întreD s,iC. Dac˘an ≥ m,atunci se poate ar˘ata c˘anum˘arul tuturor funct,iilor surjective f :D→Ceste

X^m

i=0(−1)ⁱC_mⁱ (m−i)ⁿ.

Într-adev˘ar, s˘a num˘ar˘am, mai întâi, funct,iile care nu sunt surjective; în acest sens, s˘a not˘am cuAk num˘arul de funct,iif : D →Ccare nu iau valoareak= 1, m(adic˘af(x)6=k,pentru oricex∈ {1, . . . , n}). Astfel num˘arul tuturor funct,iilor care nu sunt surjective este dat de|A1∪A2∪. . .∪Am|.Conform formulei (??), avem

[

1≤k≤mAk

=X^m

`=1(−1)^`+1X

1≤i1<...<i`≤m|Ai₁∩. . .∩Ai_`|.

Pe de alt˘a parte, dac˘a f ∈ Ai₁ ∩. . .∩Ai_`, atunci f nu poate lua ` din cele m valori dinC, deci sunt doar (m−`)variante posibile de valori; adic˘a ne intereseaz˘a num˘arul de funt,ii posibilef :D→C^`,unde|D|=niar C^`

=m−`.Deci

|Ai₁∩. . .∩Ai_`|= (m−`)ⁿ. În plus, observ˘am c˘a sumaP

1≤i₁<...<i_`≤mareC_m^` termeni, deci

[

1≤k≤mA_k

=X^m

`=1(−1)^`+1X

1≤i1<...<i`≤m(m−`)ⁿ

=X^m

`=1(−1)^`+1C_m^` (m−`)ⁿ.

Având în vedere c˘a num˘arul tuturor funct,iilor estemⁿ,deducem c˘a num˘arul tuturor funct,iilor surjective este mⁿ−X^m

`=1(−1)^`+1C_m^` (m−`)ⁿ=mⁿ+X^m

`=1(−1)^`C_m^` (m−`)ⁿ

=X^m

`=0(−1)^`C_m^` (m−`)ⁿ.

Prin urmare, în cazul particular al funct,iilor bijective, num˘arul tuturor funct,iilor este obt,inut luândn=m;astfel obt,inem identitatea

n! =Xⁿ

i=0(−1)ⁱC_nⁱ(n−i)ⁿ.

14. Suppose that a sample of sizekis to be chosen randomly (without replacement) from an urn containing(n+m) balls, of whichnare white andmare black. If we letX denote the number of white balls selected, then prove that¹⁰

P(X=r) = C_n^r·C_m^k−r

C_n+m^k , withr= 0, n .

10We say thatXis a Hypergeometric random variable.

(11)

C_n^(k−m)∨0·C_m^{k−(k−m)∨0}+C_n^{(k−m)∨0+1}·Ck−(k−m)∨0−1

m +. . .+C_n^k∧n·C_m⁰ =C_n+m^k ,

wheren, m, k∈N^∗, k≤n+m. (13) Solution¹¹.

Letr ∈ Nbe the number of white balls, hence0 ≤r ≤ k,0 ≤k−r ≤ kandr ≤n,(k−r) ≤ m.We deduce k−(k∧m)≤r≤k∧n.

We can count, using the notion of combinations, the multiplication principle and the definition of the probability, and we obtain

P(X=r) = C_n^r·C_m^k−r

C_n+m^k , r=k−(k∧m), k∧n .

On the other hand, the events{X =r}r=k−(k∧m),k∧nrepresent a partition of the entire spaceΩ,therefore 1 =P(Ω) =P

[^k∧n

r=k−(k∧m){X =r}

=X^k∧n

r=k−(k∧m)P(X =r)

⇔ X^k∧n

r=k−(k∧m)

C_n^r·C_m^k−r

C_n+m^k = 1 ⇔ X^k∧n

r=k−(k∧m)C_n^r·C_m^k−r=C_n+m^k . In particular, ifn=m=k,

Xⁿ

k=0 C_n^k²

=C_2nⁿ . Identity (13) becomes in the casek≤n∧m:

C_n⁰·C_m^k +C_n¹·C_m^k−1+. . .+C_n^k·C_m⁰ =C_n+m^k , (14) in the casen < k≤m:

C_n⁰·C_m^k +C_n¹·C_m^k−1+. . .+C_nⁿ·C_m^k−n=C_n+m^k , (15) in the casem < k≤n:

C_n^k−m·C_m^m+C_n^k−m+1·C_m^m−1+. . .+C_n^k·C_m⁰ =C_n+m^k , (16) and in the casen∨m < k≤n+m:

C_n^k−m·C_m^m+C_n^k−m+1·C_m^m−1+C_n^k−m+2·C_m^m−2+. . .+C_nⁿ·C_m^k−n=C_n+m^k . (17)

I.6 Proposed Exercises

1. Give a combinatorial explanation of the next identities¹²: (i) C_n^k=C_n−2^k + 2C_n−2^k−1+C_n−2^k−2 (ii) Xⁿ

k=02^kC_n^k= 3ⁿ (iii) X^k

j=0C_n+j^j =C_n+k+1^k (iv) Xⁿ

k=0(−1)^n−kC_m^k =C_m−1ⁿ , m≥n+ 1 (v) C_n−k^k +C_n−k−1^k−1 = n

n−kC_n−k^k (vi) Xⁿ

k=0k(k−1)C_n^k=n(n−1) 2ⁿ⁻², n≥2 (vii) Xⁿ

k=0(−1)^n−k2^kC_n^k= 1 (viii) C_n^kC_k^l =C_n^lC_n−l^k−l, l≤k≤n (ix) X^m

k=0(−1)^kC_n^k= (−1)^mC_n−1^m (x) X^k

j=0C_n^j =X^k

j=02^jC_n^j, k≤n−1 (xi) Xⁿ

k=0(−1)^k C_2m^k ²

= (−1)^mC_2m^m (xii) Xⁿ

k=0(−1)^k C_2m^k ²

= 0, n6= 2m.

(18)

11See also Exercise6.

12See [26, Section 1.2].

(12)

2. Give a combinatorial explanation of the next identity which involves the multinomial coefficients:

n r

= n

r, n−r

. (19)

3. Give a combinatorial explanation of the next identity which involves the multinomial coefficients:

n n1, n2, . . . , nr

=

n−1 n1−1, n2, . . . , nr

+

n−1 n1, n2−1, . . . , nr

+. . .+

n−1 n1, n2, . . . , nr−1

. (20)

Hint.Use an argument similar to the one used to prove the Pascal triangle rule, i.e. the equality (5).

4. From a group of npeople, suppose that we want to choose a committee of k ≤ n, one of whom is to be designated as chairperson.

(a)By focusing first on the choice of the committee and then on the choice of the chair, argue that there are C_n^k·kpossible choices.

(b)By focusing first on the choice of the nonchair committee members and then on the choice of the chair, argue that there areC_n^k−1·(n−k+ 1)possible choices.

(c)By focusing first on the choice of the chair and then on the choice of the other committee members, argue that there aren·C_n−1^k−1possible choices.

(d)Conclude from(a),(b)and(c)that

k C_n^k= (n−k+ 1)C_n^k−1=n C_n−1^k−1. (21) 5. From a group ofnpeople, suppose that we want to choose a committee with2members. Find in two ways

the total number of these kind of committees.

C_n² =C_k²+C_n−k² +k(n−k), with1≤k≤n. (22) 6. From a group ofnpeople, suppose that we want to choose a committee of any size, one of whom is to be designated as chairperson and another as secretary and another as censor (the chairperson can be the secretary and also the censor).

(a)By focusing first on the choice of the committee of sizek≤nand then on the choice of the chair, secretary and censor (the chairperson can be the secretary and also the censor), argue that there arek³·C_n^k possible choices.

(b)By focusing first on the choice of the committee of any size and then on the choice of the chair and secretary and of the censor (all three are the same), argue that there aren·2ⁿ⁻¹possible choices.

(c)By focusing first on the choice of the committee of any size and then on the choice of the chair and secretary and of the censor (two of these are different), argue that there are3n(n−1)·2ⁿ⁻²possible choices.

(d)By focusing first on the choice of the committee of any size and then on the choice of the chair and secretary and of the censor (all three are different), argue that there aren(n−1) (n−2)·2ⁿ⁻³possible choices.

(e)Conclude from(a),(b),(c)and(d)that:

1³·C_n¹+ 2³·C_n²+. . .+n³·C_nⁿ=n²(n+ 3)·2ⁿ⁻³. (23) 7. From a set ofnpeople, a committee of sizejis to be chosen, and from this committee, a subcommittee of size

i≤jis also to be chosen.

(a)Derive a combinatorial identity by computing, in two ways, the number of possible choices of the committee and subcommittee, first by supposing that the committee is chosen first and then the subcommittee is

(13)

chosen, and second by supposing that the subcommittee is chosen first and then the remaining members of the committee are chosen.

(b)Use(a)to prove the following combinatorial identity:

C_n¹·C₁ⁱ+C_n²·C₂ⁱ+. . .+C_nⁿ·C_nⁱ =C_nⁱ ·2ⁿ⁻ⁱ, with1≤i≤n. (24) (c)Use(a)and the identity

Xⁿ

k=0(−1)^k·C_n^k= 0 to show that

Xⁿ

j=i(−1)^n−j·C_n^j·C_jⁱ = 0, with1≤i < n. (25)

8. We know that in100lottery tickets3are winning tickets. A player buy40tickets. What is the probability to buy a winning ticket? What is the probability to buy at least one winning ticket?

Hint.

See the solution of Exercise14. Ifris the number of the winning tickets, then r= 40−(40∧96),40∧3 = 0,3. We deduceP(X = 1) = C₃¹·C₉₇³⁹

C₁₀₀⁴⁰ and

P({X = 1} ∪ {X = 2} ∪ {X = 3}) =P(X = 1) +P(X = 2) +P(X = 3)

= C₃¹·C₉₇³⁹

C₁₀₀⁴⁰ +C₃²·C₉₇³⁸

C₁₀₀⁴⁰ +C₃³·C₉₇³⁷ C₁₀₀⁴⁰ .

We deduce the identityP3 r=0

C^r₃·C₉₇^40−r

C₁₀₀⁴⁰ = 1and therefore

C₃⁰·C₉₇⁴⁰+C₃¹·C₉₇⁴⁰⁻¹+C₃²·C₉₇⁴⁰⁻²+C₃³·C₉₇⁴⁰⁻³=C₁₀₀⁴⁰ , (26) which is identity (15) in the case3 =n < k= 40≤m= 97.

9. We know that in12lottery tickets8are winning tickets. A player buy5tickets. Deduce formula (16) Hint.

See the solution of Exercise14. Ifris the number of the winning tickets, then r= 5−(5∧4),5∧8 = 1,5.

We deduce the identityP5 r=1

C^r₈·C₄^5−r

C₁₂⁵ = 1and therefore

C₈¹·C₄⁴+C₈²·C₄³+C₈³·C₄²+C₈⁴·C₄¹+C₈⁵·C₄⁰=C₁₂⁵ . (27) which is identity (16) in the case4 =m < k= 5≤n= 8.

10. The Banach match problem.

At all times, a pipe-smoking mathematician carries2matchboxes, one in his left-hand pocket and one in his right-hand pocket. Each time he needs a match, he is equally likely to take it from either pocket. Consider the moment when the mathematician first discovers that one of his matchboxes is empty. If it is assumed that

(14)

both matchboxes initially containednmatches, what is the probability that there are exactlyk ∈ {0, . . . , n}

matches in the other box?

Using the previous result, deduce the combinatorial identity¹³:

C_2nⁿ + 2C_2n−1ⁿ + 2²C_2n−2ⁿ +. . .+ 2ⁿ⁻¹C_n+1ⁿ + 2ⁿC_nⁿ = 2²ⁿ. (28) 11. A game involvesnplaces andkballs. Each ofkball is randomly associated to a place. Which is the probability

to have in each place at least one ball?

Using the previous result, deduce the combinatorial identity¹⁴:

1^kC_n¹−2^kC_n²+ 3^kC_n³+. . .+ (−1)ⁿ⁻¹n^kC_nⁿ=

( 0, 0≤k≤n−1,

(−1)ⁿ⁻¹ n!, k=n. (29)

13For the solution see [14, Page 166] or [8, Problem 14, page 17].

14For the solution see [8, Problem 31, page 29].

(15)

II Some Limits obtained using Probability Theory

II.1 Random variables

Throughout this section we will work on a probability space(Ω,F,P).

In order to introduce this, first we should consider ameasurable spacewhich is a couple(Ω,F),whereΩis a non-empty set andFis aσ−algebra. Theprobability measureis a measure defined on the events in theσ−algebra F, taking values in the unit interval[0,1].This setup can be applied to any random phenomena, from simple ones, for example, rolling a dice or tossing a coin, to complex ones. The probability measures the size of the events.

Any probability measure is defined by two properties: the probability of must equal to1and the measure must be countably additive.

More precisely, given a measurable space(Ω,F),a probability measure is any functionP:F →[0,1]such that:

(i)P(Ω) = 1, (ii)P(S∞

n=1An) =P∞

n=1P(An),for any sequence{An}_n∈_N∗of disjoint events fromF.

The triple(Ω,F,P)will be called a probability space.

Definition 12 The function

X : Ω→R is calledrandom variable(r.v.for short) if

for anyx∈R, {ω∈Ω :X(ω)≤x} ∈ F. (30)

Remark 13 For the sake of simplicity we denote{X≤x}:={ω:X(ω)≤x}.

• Adiscreter.v. is an r.v. whose possible values constitute either a finite set or a countably infinite set (i.e., if the valued setX(Ω)⊆Ris at most countable).

• A r.v. iscontinuousif both of the following apply:

(a)its possible values comprise either a single interval on the number line (for somea < b,any numberx betweenaandbis a possible value) (possibly infinite in extent) or a union of disjoint intervals, and

(b)no possible value of the variable has positive probability, that is,P(X =c) = 0,for any possible valuecof the r.v.X(i.e., for anyc∈X(Ω)).

Definition 14 Thecumulative distribution function(cdffor short) associated to a r.v.X is the function FX :R→[0,1],

given by

FX(x) :=P(X ≤x) =P({ω∈Ω :X(ω)≤x}), x∈R. II.1.1 Discrete random variables

A discrete r.v.X is well defined if we know its values, i.e.X(Ω), and their respective probabilities.

More precisely, we should know the setX(Ω) = {xi}_i∈I ,where I ⊆ N is at most countable set and pi :=

P(X =xi),for anyxi∈X(Ω).Of course, we should have pi≥0, i∈I and X

i∈Ipi= 1.

Definition 15 The valuesp_i=P(X =x_i),wherex_i∈X(Ω),are calledprobability mass functionofX.

In this case the cdf is a increasing step function:

F(x) =P(X ≤x) =X

x_i∈X(Ω) xi≤x

P(X=xi), x∈R

(16)

or

F(x) =











0, x < x1, p1, x1≤x < x2, p1+p2, x2≤x < x3,

· · ·

p₁+· · ·+p_n, x_n ≤x < x_n+1,

· · · ·

(31)

The pointsx_i∈X(Ω)are the jump points forF_X.

Definition 16 We call theexpectation(or theexpected value) of the r.v.Xthe value E(X) =X

i∈Ix_ip_i (whenever this sum exists).

Proposition 17 (Properties of the expectation) IfX, Y are two r.v. (discrete or continuos) anda∈R,then (i) E(a) =a,

(ii) E(a+X) =a+E(X), (iii) E(aX) =aE(X),

(iv) E(X+Y) =E(X) +E(Y). The expectation of a function of a r.v. is given by the next result.

Teorema 18 (Transfer formula) Letf :R→Rbe a measurable function. Thenf(X) : Ω→Ris a r.v. and its expectation exists if and only if

X

i∈I|f(x_i)| p_i<+∞.

In this case the expectationE(f(X))is given by the formula:

E(f(X)) =X

i∈If(xi) pi. Definition 19 We call thevarianceof the r.v.X the value

Var (X) :=E(X−E(X))²=X

i∈Ipi(xi−E(X))² . Remark 20 The variance can be computed using the formula

Var (X) =E X²

−(E(X))².

Proposition 21 (Properties of the variance) IfX, Y are two r.v. (discrete or continuos) anda, b∈R,then (i) Var (a) = 0 (=E a²

−(E(a))²=a²−a²), (ii) Var (aX) =a²Var (X),

(iii) Var (a+bX) =b²Var (X),

(iv) Var (X+Y) = Var (X) + Var (Y), ifX, Y are independent.

Definition 22 We say that the r.v.X is abinomialr.v., and we wroteX ∼ B(n, p), if

X(Ω) ={0,1,2, . . . , n} and P(X =k) =C_n^kp^kq^n−k, k= 0, n .

(17)

Remark 23 Of course,P(X =k) =C_n^kp^kq^n−k≥0and, using binomial theorem (1), Xⁿ

k=0p_k=Xⁿ

k=0C_n^kp^kq^n−k = (p+q)ⁿ= 1.

Remark 24 In the particular casen= 1we obtain theBernoulli distribution typeandX ∼ B(1, p)if X(Ω) ={0,1} and P(X= 1) =p, P(X = 0) = 1−p .

Remark 25 Suppose that a trial, or an experiment, whose outcome can be classified as either asuccessor afailure, is performed. We consider that the probability that the trial is asuccessisp∈(0,1)(and, of course, the probability that the trial is afailureis1−p). We letXbeing1when the outcome is asuccessandXbeing0when it is afailure. The probability mass function ofXisP(X = 1) =pandP(X = 0) = 1−p .ThenXis a Bernoulli r.v.

Suppose now thatnindependent trials, each of which results in asuccesswith probabilitypand in afailurewith proba- bility1−p, are to be performed. IfXrepresents the number ofsuccessesthat occur in thentrials, thenX is a binomial r.v.

with parameters(n, p).

Proposition 26 IfX ∼ B(n, p),then

E(X) =np and Var (X) =npq. (32)

Proposition 27 IfX ∼ B(n, p)andY ∼ B(m, p)are two independent binomial r.v., then the sum is also a binomial r.v. and X+Y ∼ B(n+m, p).

Remark 28 As a consequence, ifXi∼ B(1, p)arenindependent r.v., then the r.v.Sn:=Pn

i=1Xi∼ B(n, p). SinceE(Xi) =p,Var (Xi) =pq,

E(X) =E

X^k

i=1Xi

=X^k

i=1E(Xi) =np and

Var (X) = Var

X^k

i=1X_i

=X^k

i=1Var (X_i) =npq.

Definition 29 We say that the r.v.X is ahypergeometricr.v. if

X(Ω) ={0,1,2, . . . , n} and P(X=k) = C_a^kC_b^n−k

C_a+bⁿ , k= 0, n . Remark 30 Of course,P(X =k)≥0and, using relation (6) or (13),

Xⁿ

k=0pk=Xⁿ

k=0

C_a^kC_b^n−k C_a+bⁿ =

Pn

k=0C_a^kC_b^n−k C_a+bⁿ = 1.

Remark 31 Suppose that a sample of sizenis to be chosen randomly (without replacement) from an urn containing(a+b) balls, of whichaare white andbare black. If we letXdenote the number of white balls selected, thenX is a hypergeometric r.v..

Definition 32 We say that the r.v.X is aPoissonr.v. with the parameterλ >0,and we wroteX∼ P(λ),if X(Ω) =N and P(X =k) =λ^k

k! e^−λ, k∈N. Remark 33 Of course,P(X =k)≥0and, using the Taylor expansion of theexp,

X

k∈Npk =X

k∈N

λ^k

k! e^−λ=e^−λX

k∈N

λ^k k! = 1.

(18)

Proposition 34 The expectation and the variance are

E(X) =λ and Var (X) =λ. (33)

Remark 35 The Poisson distribution often shows up in situations where we are dealing with the number of events occurring in a fixed time or space interval, if these events occur with a certain average rate and independently of the time (or space) since the last event occurred. Examples:

(a)the number of traffic accidents along a specific road section per year;

(b)the number of lightning strikes in Amsterdam in August;

(c)the number of people deaths from tetanus in the Netherlands per year;

(d)the number of flaws per square metre of clothing.

The only parameter of this distribution is the expected number of times that the event will occur in the chosen interval, notated byλ.

Proposition 36 If X ∼ P(λ)and Y ∼ P(µ)are two independent Poisson r.v., then the sum is also a Poisson r.v. and X+Y ∼ P(λ+µ).

II.1.2 Continuous random variables

Definition 37 We say that the functionf :R→Ris aprobability density function(pdffor short) if:

(i)f(x)≥0, for anyx∈R. (ii)R+∞

−∞ f(t)dt= 1.

We can take as definition of a continuous r.v. the next one.

Definition 38 We say thatXis a continuos r.v. if there exists a pdff such that P(a≤X≤b) =

Z b a

f(t)dt, for anya, b∈R. (34)

In this casef is the pdf associated toX.

In this case the cdf is the increasing continuous function:

F(x) =P(X≤x) = Z x

−∞

f(t)dt, x∈R. Hence, of course,

P(X =a) = Z a

a

f(t)dt= 0 and

P(a≤X ≤b) =F(b)−F(a) = Z b

a

f(t)dt.

Definition 39 We call theexpectation(or theexpected value) of the r.v.Xthe value E(X) =

Z +∞

−∞

xf(x)dx (whenever this integral exists).

The expectation of a function of a r.v. is given by the next result.