April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.

69in b4410-ch01 page 1

by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

Chapter 1

Permutation and Combination

An Introduction to Probability Downloaded from www.worldscientific.com

1.1. Introduction
We start this journey through probability with an exploration of various
approaches to do counting. Why? To make a long story short, say we would
like to find the likelihood of the occurrence of a given event, call it event E,
of interest. Let m be the number of scenarios that are constituents of E and
n be the total number of possible scenarios in the experiment of interest.
Assume that all scenarios are equally likely to occur. Then it is reasonable
to assert that the probability E occurs is given by P (E) = m/n. For example,
we consider a simple experiment involving drawing a card from a standard
card deck. Let E denote the event of getting a spade. Then we see that
P (E) = 13/52 as there are 13 spades in a card deck of 52 cards. Probabilistic
problems at times can be involved and tricky. If we can master our expertise
in counting, then many times finding probability amounts to counting with
respect to figuring out the numerator m and the denominator n of P (E).

1.2. Permutations
Assume that there are n distinguishable items. We would like to line them
up. How many ways can this be done? So we do this methodically. For the
first spot, any one of the n items can occupy the spot. Once that is done, we
move to the second spot. There are n − 1 remaining items. Any one of the
n − 1 remaining items can occupy the second spot. We reiterate the process
till we reach the last spot. There is only one remaining item. Thus there is

1
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 2

2 An Introduction to Probability: With Mathematica

one possibility. To summarize, the total number of ways to line these n items
up is given by
n × (n − 1) × (n − 2) × · · · × 2 × 1 ≡ n!.
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

Example 1. Suppose there are five boys to be lined up on a stage. How

many ways such a lineup can be formed?

Solution. There are 5! = 120 possible lineups. 

Variant. Assume that there are n distinguishable items. We would like to
select k of them and line them up. There are
An Introduction to Probability Downloaded from www.worldscientific.com

n!
(n)k ≡ n × (n − 1) × · · · × (n − k + 1) =
(n − k)!
ways to do this. We see that the order of selection matters and each item can
be selected only once. The notation (n)k is sometimes called k−permutation.
Example 2. Suppose we want to use 26 alphabets to make license plates
that only display 6 alphabets Assume alphabets are not allowed to be
repeated. How many license plates are possible?

Solution. There are (26)6 =(26)(25)(24)(23)(22)(21)= 165 765 600 possible

26!
license plates. Another way to state the answer is (26−6)! = 26!
20! = 165 765 600.

Generalization. Assume that there are k experiments. We do these
experiments sequentially. In the first experiment, we have n1 distinct items
and would like to line them up. In the second experiment, we have n2 distinct
items and would like to line them up. We repeat the process till we reach the
kth experiment. Then the total number of possible permutations is given by
n1 ! × n2 ! × · · · × nk !.
Example 3. Suppose there are 3 distinct books in algebra, 4 distinct books
in calculus, and 6 distinct books in geometry. Books are to be lined up in
the order of algebra, calculus, and geometry. How many arrangements are
possible?

Solution. There are 3!4!6!= 103, 680 arrangements possible. 

When Some Items are Indistinguishable. Assume that there are n
items. We would like to line them up. However, there are k distinguishable
groups. Items in a given group are indistinguishable. Assume n1 + · · · + nk =
n. How many distinct arrangements are possible?
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 3

Permutation and Combination 3

Assume for the moment all n items were distinguishable. If so, there
would be n! ways to permute them. Since items in the same group are
not distinguishable, there are n1 ! × n2 ! × · · · × nk ! duplicates, i.e., being
counted n1 ! × n2 ! × · · · × nk ! times as duplicates. Thus, in actuality, the
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

distinguishable arrangements are

n!
.
n1 ! × n2 ! × · · · × nk !
The following example clearly demonstrates the use of above result.
Example 4. Suppose we use three alphabets and two numerals to form a
An Introduction to Probability Downloaded from www.worldscientific.com

plaque with five places. How many distinct arrangements are there: (a) If
alphabets are distinguishable and numerals are distinguishable, and (b) if
alphabets are indistinguishable and so are the numerals?

(a) If alphabets and numerals are all distinguishable. Then there are 5! =
120 ways to permute them.
(b) If the alphabets are indistinguishable and so are the numerals, we remove
the indistinguishable duplicates for both cases. Hence
5!
= 10. 
3!2!

Example 5. How many different 10-digit passcodes can be formed using

three *’s, four $’s, and three ˆ’s?

Solution. We can make a total of

10!
= 4200
3!4!3!
different passcodes. 
Example 6. How many different letter arrangements can be formed from
the letters P EP P ER?

Solution. Assuming for the moment the three P ’s and two E’s were
distinguishable. Then we would have 6! = 720 ways to permute them. Since
the three P ’s and two E’s are actually indistinguishable, we remove these
two sets of duplicates from the earlier permutations. Therefore, the number
of distinct letter arrangements is
6!
= 60.
2!3!
In Illustration 1, we use Mathematica to replicate the computation. 
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 4

4 An Introduction to Probability: With Mathematica

1.3. Combinations
Suppose we have n distinguishable items from which we will choose r of
them. How many ways can it be done? As an example, we have a class of 32
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

students and want to select 5 of them to form a basketball teams. How many
selections are there? We can come up with an answer by first approaching it
from a permutation perspective. We have r spots to be filled from a potential
of n candidates. Thus there are

n!
(n)r = n × (n − 1) × · · · × (n − r + 1) =
(n − r)!
An Introduction to Probability Downloaded from www.worldscientific.com

ways to fill the r spots. Since in actuality, the order with which a spot gets
filled with a candidate is irrelevant. Thus the above count contains r! of
duplicates. Hence, the number of distinguishable choices is given by
 
(n)r n! n
= ≡ .
r! (n − r)!r! r
n
The term r is commonly used as the notation for combinations.

Example 7. A mathematics department has 32 faculty members. A

promotion and tenure committee of size 7 is to be formed. How many possible
ways such a committee can be formed?

32 32!
Solution. There are 7 = 7!25! = 3, 365 , 856 ways to form such a
committee. 

Example 8. (Binomial Theorem). We want to expand (x + y)n .

The expansion involves the filling of the n spots with x’s and y’s. Thus,
a typical term involves xk y n−k , i.e., x shows up x times and y shows up n − x
times. For the term xk y n−k , out of the n spots, k of  which will be occupied
by x’s. Thus, for this particular terms, there are nk ways to make such a
selection. Since x can be selected from 0 to n times, we conclude that

n  
 n
(x + y) = n
xk y n−k .
k
k=0
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 5

Permutation and Combination 5

 n
The above also suggests the term k is sometimes called the binomial
coefficient. 
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

1.4. Basic Principles of Counting

There are some basic principles of counting in our tool box to assist
us in counting: by multiplications, by additions, by exclusion, and by
nesting.
Counting by Multiplication. When there are k independent experiments.
For i = 1, . . . , k, we assume experiment i has ni distinct outcomes. Then
An Introduction to Probability Downloaded from www.worldscientific.com

the total number of outcomes from the aggregate of k experiments is

given by

n1 × n2 × · · · × nk .

Here, we assume that the ordering of occurrences of outcomes is not our

concern. We call the above counting is by multiplications.

Example 9. Consider a group of 4 women and 6 men. If 2 women and

3 men are to be selected to form a jury, how many possible choices are
there?
46
Solution. There are 2 3 = 120 possible choices. 
There is another form of counting by multiplication. This occurs when
there is a dependency between successive experiments. Assume that there
are k experiments to be done sequentially. For i = 1, . . . , k, we assume
experiment i has ni distinct outcomes given that experiments 1, . . . , k −1 has
already been done. Then the total number of outcomes from the aggregate
of k experiments is given by

n1 × n2 × · · · × nk .

The notion of permutation follows precisely the above idea.

Example 10. Suppose we draw to cards in succession from a standard card

deck. How many ways two diamonds can be drawn?

Solution. There are (13) × (12) = 156 ways two diamonds can be
drawn. 
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 6

6 An Introduction to Probability: With Mathematica

Counting by Addition. We now address the second basic principle of

counting: by additions. If we can partition the outcomes of an experiment
into mutually exclusive and collectively exhaustive components. Them the
total number of possible outcomes will be the sum of the numbers of
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

outcomes from all its components.

Example 11. Suppose that there are 4 boys and 4 girls to be seated in
a row of chairs. Assume that boys and girls cannot sit next to each other.
What are the number of seating arrangements possible?

Solution. One way to start a seating plan is to have a boy occupying the
An Introduction to Probability Downloaded from www.worldscientific.com

leftmost position. Following this, there are 4! ways to seat the boys and then
4! to seat the girls. Similarly, another way is to have a girl occupying the
leftmost position. Again, there are 4! ways to seat the girls and then 4! to
seat the boys. These two components form a partition of all the possible
outcomes. Thus the total number of seating arrangements is

(4!)2 + (4!)2 = 1152. 

Example 12. There are 8 people playing in a neighborhood basketball

court. Five of them will be chosen to form a team to compete against another
team in a different neighborhood. How many choices are there if two of the
players are feuding and will not join the team together?

Solution. The possible outcomes can be partitioned into two components:

A = {none of the feuding players joins the team} and B = {exactly one of
the feuding player joins the team}.
6
26 A, there are 5 ways to form the team. For component
For component
B, there are 1 5 ways to form the teams. Thus the number of possible
ways a team can be formed is
    
6 2 6
+ = 18. 
5 1 5

Counting by Subtraction. Another principle of counting is by exclusion,

or by subtraction. Many times, we may be asked to count events involving
a statement that reads “at least some of the outcomes possess the indicated
attributes.” If the total number of possible outcomes and the number
pertaining none of the outcomes possessing the indicated attributes are easy
to compute, then the difference of the two is what we are looking for. Thus
a simple subtraction will yield the needed result.
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 7

Permutation and Combination 7

Example 13. How many 3 digit area codes can be formed while allowing
at most two of the digits assuming the same value?

Solution. We see that there are 103 possible outcomes without any
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

exclusion. Now there are 10 × 9 × 8 cases with all three digits being different.
Thus the difference yields the needed answer, i.e., 103 − 10 × 9 × 8 = 280. 

Example 14. Assume a person is either college educated or high school

educated. Also assume that a person is either a football fan, or a basketball
fan, or a soccer fan (not both). There are 15 people chosen for a study. (a)
Of the 15 chosen people, what is the number of possible outcomes? (b) What
An Introduction to Probability Downloaded from www.worldscientific.com

is the number of possible outcomes if at least one of the people chosen is

high school educated?

Solution. (a) We have 15 spots, each spot can assume 2×3 = 6 attributes.
Thus the total number of outcomes is 156 .
(b) The number of outcomes associated with “none is high school educated”
is 153 . Thus the number of possible outcomes if at least one of the chosen is
high school educated is 156 − 153 . 

Counting by Nesting. The last principle to assist us in counting is by

first considering several collections of elements with each collection sharing
a common feature. We consider the counting at the collection level. We then
return to the counting within each collection. We multiply results obtained
from all these collections to arrive at the needed result. We call this approach
as counting by nesting, or grouping. This approach is illustrated in the
following example.

Example 15. Suppose there are 4 distinct chemistry books, 5 distinct

biology books, and 8 distinct physics books. These books are to be line up on
the bookshelf with books dealing with the same subject staying contiguous.
How many different arrangements are possible?

Solution. We first consider books dealing with the same subject a collection.
There are three collections — hence 3! ways to arrange them. Within the
three collections, there are 4!, 5!, and 8! ways to permute them, respectively.
Therefore the total number ways to arrange the books is

3! × (4! × 5! × 8!) = 696 , 729, 600. 

April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 8

8 An Introduction to Probability: With Mathematica

1.5. Binomial and Multinomial Coefficients

We first explore more about the properties of the binomial coefficient.
Many identities involving the binomial coefficient can be established by a
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

combinatorial argument. To illustrate, we have

           
n+1 1 n 1 n n n
= + = + .
r 1 r−1 0 r r−1 r

The left side is about the number of ways to select r items from n + 1 items.
To establish the equivalent right side, we argue
 n that
 a specific item is either
An Introduction to Probability Downloaded from www.worldscientific.com

being included in the selection,

n resulting in r−1 , or not being included by
the selection, resulting in r . These eventualities form a partition hence we
use counting by addition.
To establish another identity using the combinatorial argument, we
consider
          
n+m n m n m n m
= + + ··· + .
r 0 r 1 r−1 r 0

Assume that an urn contains n white and m black balls. When we remove
r balls from the urn, a part of which, say i, will be white balls and the
remaining r − i balls will be black balls where i = 0, . . . , r. The left side of the
last equality gives the number of possible such selections when considered in
aggregate. The right side of it gives the result when we sum over all possible
scenarios leading to the same objective. Other identities can be obtained in
similar manner without resorting to a brute-force work involving the factorial
notation.
We now introduce the multinomial coefficient. Let n1 + · · · + nk = n. We
define
 
n n!
= .
n1 , . . . , nk n1 !n2 ! · · · nk !

The above is called the multinomial coefficient. It gives the number of

possible outcomes obtainable from choosing n items, for which n1 of them are
indistinguishable, n2 are indistinguishable, . . . , and nk are indistinguishable,
i.e., there are k distinct groups.
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 9

Permutation and Combination 9

By direct expansion, we obtain the following identity:

      
n n n − n1 n − (n1 + · · · + nk−1 )
= ··· .
n1 , . . . , nk n1 n2 nk
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

The above amounts to making the needed selections sequentially and

applying the multiplication principle of counting.
Example 16. A high school class has 15 students. (a) If three teams are to
be formed with 5 members per team, how many ways the three teams can be
formed. (b) Assume for the three teams, each has a name, say Team Alpha,
or Beta, or Gamma. How many formations are possible?
An Introduction to Probability Downloaded from www.worldscientific.com

 15  15!
Solution. (a) There are 5,5,5 = 5!5!5! = 756, 756 possible selections.
(b) We can first form a group of three teams using the result obtained in
part (a). We then assign a team name to each one of the three teams so
chosen. There are 3! ways to do so. In conclusion, there are 756, 756 × 6 =
4, 540 , 536 possible arrangements. We also use of the “Multinomial” function
of Mathematica in Illustration 2 to do part (a). 
Example 17 (Multinomial Expansion). We want to expand (x1 + x2 +
· · · + xk )n .
The expansion involves the filling of the n spots with x1 ’s, x2 ’s, . . . ,
and xk ’s. Thus a typical term involves xn1 1 xn2 2 · · · xnk k , i.e., x1 shows up n1
times, x2 shows up n2 times, . . . , and xk shows up nk times. For the term
xn1 1 xn2 2 · · · xnk k , out of the n spots, n1 of which will be occupied by x1 ’s, n2 of
which will be occupied by x2 ’s, and so on. We use the multinomial coefficients
to account for the multiplier associated with each product term. This gives
the needed expansion:
 n  
n
(x1 + x2 + · · · + xk ) = n
xn1 xn2 · · · xnk k . (1.1)
n1 , n2 , ..., nk 1 2
(n1 ,...,nk ):
n1 +···+nk =n 
ni =0,1,2,...,n

1.6. Occupancy Problems

One objective of presenting this problem is to fine-tune our combinatorial
analysis skill. A version of the occupancy problem can be described as follows:
There are n indistinguishable balls to be placed in r urns. How many ways
could that be done provided that each urn must contain at least one balls.
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 10

10 An Introduction to Probability: With Mathematica

Following Polya: look at an easily solvable problem, solve it, and develop
some insights for solving the original problem.
We start with a small example. Consider n = 5 and r = 3. In this case,
we can enumerate the solution:
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

1,1,3 0#0#000
1,2,2 0#00#00
1,3,1 0#000#0
2,1,2 00#0#00
2,2,1 00#00#0
3,1,1 000#0#0
An Introduction to Probability Downloaded from www.worldscientific.com

In the above table, we place our enumerated results in the first column. Thus
we know the answer is 6, namely, there are 6 ways the 5 balls can be put
into the three urns. Now we look for hints that would lead us to the solution.
Assume that the 5 balls, each marked as “0”, are lined up. There are four
“gaps” between to five “0”. We choose any two such gaps and fill each one of
them with a marker “#”. By doing so, the five “0” are being split into three
groups. The numbers of 0’s in the three demarcated groups corresponds to
the numbers of balls in the respective urns. This is clearly illustrated in the
second column of the above tally. Thus there is one-to-one correspondence
between the placements of markers and the resulting solution. The number
of ways this can be done is given by
     
n−1 5−1 4
= = =6
r−1 3−1 2

We have just solve the following general problem: Let xi = the number
of balls in urn i. Assume x1 + · · · + xr . = n and we require xi ≥ 1 for each i.
Then the number of vectors (x1 , . . . , xr ) that satisfies the stated conditions is
 
n−1
.
r−1

Variant. Consider a variant that reads

y1 + · · · + yr = n,
yi ≥ 0.

We are interested in finding the number of vectors (y1 , . . . , yr ) that satisfies

the above conditions.
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 11

Permutation and Combination 11

We let xi = yi + 1. Hence yi = xi − 1. We make the substitution in the

above equation:

(x1 − 1) + · · · + (xr − 1) = n,
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

xi − 1 ≥ 0

or equivalently

x1 + · · · + xr = n + r,
xi ≥ 1 for each i.
An Introduction to Probability Downloaded from www.worldscientific.com

n+r−1
But the answer for this version is r−1 . Hence the problem is solved. 

Example 18. A person plan to leave 10 million dollars to her four children.
Her favorite child should receive at lease 3 million dollars. How many ways
the inheritance can be divided among the four children. Assume that each
child should receive at least 1 million dollars.

Using one million as an unit. Let yi = the amount of inheritance to be

received by child i. Then, we have

y1 + · · · + y4 = 10,
y1 = 3, 4, . . . ,
y2 , y3 , y4 = 1, 2, . . . .

We set x1 = y1 − 2 and xi = yi , i = 2, 3, and 4. Thus, an equivalent problem

becomes

(x1 + 2) + x2 + x3 + x4 = 10,
xi ≥ 1 for each i

or

x1 + · · · + x4 = 8
x1 ≥ 1 for each i.
8+4−1
Thus, the number of ways the inheritance can be allocated is 4−1 =
11
3 = 165. 
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 12

12 An Introduction to Probability: With Mathematica

1.7. Combinatorial Generating Functions

In this section, we explore the use of polynomials to assist us in doing
counting involving permutations and combinations. Stated simply, we would
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

like to make use of the coefficients in a multinomial expansion of a polynomial

to generate results for a certain class combinatorial problems. It is in
this context, we call a polynomial expansion, accompanied by relevant
interpretations of its coefficients, a combinatorial generating function.
Consider a multinomial expansion of (x1 + x2 + x3 )4 , we try to give
interpretations to its resulting coefficients. Using (1.1), we obtain

(x1 + x2 + x3 )4 = x41 + 4x31 x2 + 4x31 x3 + 6x21 x22 + 12x21 x2 x3

An Introduction to Probability Downloaded from www.worldscientific.com

 
(∗)

+ 6x21 x23 + 4x1 x32 + 12x1 x22 x3 + 12x1 x2 x23

+ 4x1 x33 + x42 + 4x32 x3 + 6x22 x23 + 4x2 x33 + x43 . (1.2)

Consider the term marked by (*), x21 x2 x3 . Assume that we have 4 “1’s” to
be placed in three slots indexed by 1, 2, and 3, where 4 is the exponent
shown at the left hand side of (1.2). We envision that two “1’s” are placed
in slot 1, one “1” in slot 2, and one “1” in slot 3, For the each “1” we assign
a value of one to the corresponding xi . For this specific term, we end up in
(1.2) having x21 = 1 · 1 = 1, x12 = 1, and x13 = 1. We notice that for the
three exponents of the term x21 x2 x3 can be represented by an ordered triplet
(n1 , n2 , n3 ) = (2, 1, 1). Now its coefficient in associated with this term in
(1.2) represents the number of ways the 4 “1’s” can be distributed to form
4 
the pattern (2, 1, 1), namely, 2,1,1 = 12.
Following the above line of argument, we consider the case where we have
4 indistinguishable balls to be randomly distributed to three urns. If we are
interested in the number of cases where we observe the ordered pattern (2, 2,
0), then the coefficient associated with the term x21 x22 gives the answer. It is
6. On the other hand, if we are interested in the number of cases of unordered
pattern (2, 2, 0), the sum of the coefficients associated with the terms x21 x22 ,
x21 x23 , and x22 x23 yields 18. Extracting these coefficients from a polynomial
can easily be done using Mathematica. This is shown in Illustration 3.
In this example, when we set all {xi } to 1, then it give
  
4
= 81.
n1 , n2 , n3
(n1 ,n2 ,n3 )
n1 +n2 +n3 =4
ni =0,1,... ∀i
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 13

Permutation and Combination 13

This is equal to (1 + 1 + 1)4 = 34 = 81 — the number of ways the four “1’s”

can land in each one of the three slots. From the result of the occupancy
problem, the number vectors (n1 , n2 , n3 ) such that the conditions under the
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

summation sign is met is given by

     
n+r−1 4+3−1 6
= = = 15.
r−1 3−1 2
This is the number of terms on the right side of (1.2). For example, the
first three terms on the right side of (1.2) correspond to the ordered triplets
(4, 0, 0), (3, 0, 1), and (3, 2, 0). The coefficient in front of each triplet gives
the numbers of ways the “1’s” can be randomly distributed to the respective
An Introduction to Probability Downloaded from www.worldscientific.com

slots. Having given the aforementioned interpretations to the multinomial

expansion of a polynomial, we are ready to give examples to demonstrate
the applications of combinatorial generating function.
Example 19. Consider there are four identical balls are randomly thrown
into three numbered urns. How many ways in which two balls land in one
urn and another two land in a different urn.

Solution. We set the polynomial as it has just been suggested (x1 +x2 +x3 )4 .
We sum over the coefficients associated with the terms x21 x22 , x21 x23 , and x22 x23
in the expansion. In Illustration 3, we find that it is 18 — as expected. 
Example 20. An elevator starts from the basement of a four-story condo
with 7 seven passengers on board. Assume that passengers will leave for the
four floors randomly and there are no one enters the elevator for this ride
towards the top floor. (a) What is the number ways, denote it by n(E), that
all passengers get discharged from the elevator and there are four passengers
leave for the third floor? (b) What is the number ways, denote it by n(S),
that all passengers get discharged from the elevator?

Solution. We set up the polynomial as

(x1 + x2 + t x3 + x4 )7 .
We note that a tag “t” has been placed along with x3 . The specific event of
leaving from floor 3 is being duly acknowledged. Then we can determine n by
summing all the coefficients in the above expansion whose terms involving t4 .
From Illustration 4, we see that n(E) = 945 and n(S) = 16384. 
Example 21. Consider the roll of a fair die 6 times. Let E be the event of
getting a sum of 20. Find the number of ways this can occur. Denote this
number by n.
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 14

14 An Introduction to Probability: With Mathematica

Solution. Define the polynomial by

(x1 + x2 + x3 + x4 + x5 + x6 ).
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

We envision that in each roll of the die, if it lands a number “i,” then an “1”
is tosses into slot i whose exponent is i. The exponent counts the number
resulting from the roll. If we sum up all coefficients associated with the
above polynomial expansion with their exponents being 20. It gives the value
of n. 
An Introduction to Probability Downloaded from www.worldscientific.com

1.8. Exploring with Mathematica

Illustration 1. This following results are related to Example 6:

Illustration 2. Recall Example 16, we have 15 students and want to form

three teams with five members per team. The number of ways the three
teams cab be formed is given by the multinomial coefficient:

Illustration 3. The number of terms involving x21 x22 , x21 x23 , x22 x23 in a
polynomial expansion of (x1 + x2 + x3 )4 as stated in Example 19.

Illustration 4. The counting of the number of cases, n(E), where four

passengers leaving at floor 3 in Example 20. The total number of discharge
scenarios is given by n(S).
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 15

Permutation and Combination 15

by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.


An Introduction to Probability Downloaded from www.worldscientific.com

Illustration 5. Example 21 about the number of cases, nE, in rolling a fair

die 6 times and getting a total of 20.

Problems
1. In how many ways can 5 boys and 5 girls be seated around a round
table so that no two boys sit next to each other?
2. In how many ways can a lady having 10 dresses, 5 pairs of shoes, and 2
hats be dressed?
3. In how many ways can we place in a bookcases with two works each of
three volumes and two works each of four volumes, so that the volume
of the same work are not separated?
4. In how many ways can r indistinguishable objects be distributed to n
persons if there is no restriction on the number of objects that a person
may receives?
5. In how many ways can r distinguishable objects be distributed to n
persons if there is no restriction on the number of objects that a person
may receive?
6. Eight points are chosen on the circumference of a circle. (a) How many
chords can be drawn by joining these point in all possible ways? If the
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 16

16 An Introduction to Probability: With Mathematica

8 points are considered vertices of a polygons, how many (b) triangles,

and how many (c) hexagons can be formed?
7. (a) In how many ways can 20 recruits be distributed into four groups
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

each consisting of 5 recruits? (b) In how many ways can they be

distributed into 4 camps, each camp receiving 5 recruits?
8. Using 7 consonants and 5 vowels, how many words consisting of 4
consonants and 3 vowels can we form?
9. A house has 12 rooms. We want to paint 4 yellow, 3 purple, and 5 red.
In how many ways can this be done?
An Introduction to Probability Downloaded from www.worldscientific.com

10. How many ways can 5 history books, 3 math books, and 4 novels be
arranged on a shelf if books of each type must be together?
11. Twelve different toys are to be divided among 3 children so that each
one gets 4 toys. How many ways can this be done?
12. How many ways can 4 men and 4 woman can sit in a row if no two men
or two women sit next to each others?
13. (a) In how many ways can 4 boys and 4 girls sit in a row? (b) In how
many ways can 4 boys and 4 girls sit in a row if boys and girls are each
to sit together? (c) In how many ways if only boys must sit together?
(d) In how many ways if no two people of the same gender are allowed
to sit together?
14. How many 3 digit numbers xyz with x, y, z all ranging from 0 to 9 have
at least 2 of their digits equal? (b) How many have exactly 2 equal
digits?
15. We have $20,000 that must be invested among 4 possible opportunities.
Each investment must be integral in units of $1,000. If an investment is
to be made in a given opportunity at all, then the minimal amounts
to be invested in the each one of the four investments are $2,000,
$2,000, $3,000, and $4,000, respectively. How many different investment
strategies are available if
(a) An investment must be made in each opportunity?
(b) Investments must be made in at least 3 of the four
opportunities?
16. An elevator starts at the basement with 8 people (not including the
elevator operator) and discharges them all by the time it reaches the
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 17

Permutation and Combination 17

top floor, the 6th floor. In how many ways could the operator have
observed the 8 people leaving the elevator (e.g., all leave from the 1st
floor)? What if the 8 people consist of 5 men and 3 women (e.g., 2 men
leave from the 2nd floor, 1 man leaves from 3rd floor, 1 man leaves from
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

the 5th floor, and all 3 women leave from the 6th floor)?
17. Delegates from 12 countries, including Russia, Australia, New Zealand,
and the United States, are to be seated in a row. How many different
seating arrangements are possible if the Australian and New Zealand
delegates are to be next to each other and the Russian and U.S. delegates
are not to be next to each other?
An Introduction to Probability Downloaded from www.worldscientific.com

18. A dance class consists of 22 students, of which 10 are women and 12 are
men. If 5 men and 5 women are to be chosen and then paired off, how
many results are possible?
19. A person has 8 friends, of whom 5 will be invited to a party. (a) How
many choices are there if 2 of the friends are feuding and will not attend
together? (b) How many choices are there if 2 of the friends will only
attend together?
20. If 8 identical blackboards are to be divided among 4 schools, how many
divisions are possible? How many if each school must receive at least 1
blackboard?
21. (a) In how many ways can n indistinguishable balls be put into n
numbered boxes so that exactly one box is empty? (b) In how many
ways can n distinguishable balls be put into n numbered boxes so that
exactly one box is empty?
22. A girl decides to choose either a shirt or a tie for a birthday present.
There are 3 shirts and 2 ties to choose from. (a) How many choices does
she have if she will get only one of them? (b) If she may get both a shirt
and a tie?
23. There are 3 kinds of shirts on sale. (a) If two men buy one shirt each
how many possibilities are there? (b) If two shirts are sold, how many
possibilities are there?
24. How many different initials can be formed with 2 or 3 letters of the
alphabet? How large must the alphabet be in order that one million
people can be identified by 3-letter initials?
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 18

18 An Introduction to Probability: With Mathematica

25. (a) In how many ways can 4 boys and 4 girls be paired off? (b) In how
many ways can they stand in a row in alternating gender?
26. (a) In how many ways can a committee of three be chosen from 20
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

people? (b) In how many ways can a president, a secretary and a

treasurer be chosen?
27. You walk into a party without knowing anyone there. There are 6 women
and 4 men and you know there are 4 married couples. (a) In how many
ways can you guess who the couples are? (b) What if you know there
are exactly 3 couples?
An Introduction to Probability Downloaded from www.worldscientific.com

28. A child has 5 blocks with the letter A, 3 blocks with the letter B and
1 block with the letter C. Assuming these 9 blocks are to be randomly
lined up to form letters. How many distinct words can be formed?
29. There are 10 indistinguishable balls and 5 numbered urns. These balls
are randomly thrown into the urns. (a) How many different distributions
of balls into the urns. (b) How many different distributions of balls into
the urns provided that each urn must contain at least one ball.
30. Letters in the Morse code are formed by sending a succession of dashes
and dots with repetitions allowed. How many letters can be formed using
ten symbols or less?
31. Consider an experiment consists of determining the type of job — either
blue collar or white collar, and the political affiliation — Republican,
Democrat, or Independent — of the 15 members of an adult soccer
team (a) How many elements are in the sample space? (b) How many
elements are there when at least one of the team members is a blue-
collar worker? (c) How many elements are there when none of the team
members consider himself or herself an independent?

Remarks and References

Example 6 is based on Example 3d in Chapter 1 of Ross [4]. G. Polya [3] gives a clear
road map for solving intricate combinatorial problems. The book by Graham, Knuth,
and Patashnik [1], has a whole chapter on binomial coefficients. The exposition on
combinatorial generating functions stems from Mood and Graybill [2, pp. 27–31]. A related
work of interest on generating functions is the book by Wilf [5].
April 10, 2022 16:16 An Introduction to Probability: With Mathematica 9.61in x 6.69in b4410-ch01 page 19

Permutation and Combination 19

[1] Graham, R. L., Knuth, D. E. and Patashnik, O. Concrete Mathematics: A Foundation

for Computer Science, Addison-Wesley, 1999.
[2] Mood, A. M. and Graybill, F. A., Introduction to the Theory of Statistics, 2nd edn.,
McGraw-Hill, 1963.
by 2401:4900:5959:71f2:ace8:7eff:febd:ff on 10/06/24. Re-use and distribution is strictly not permitted, except for Open Access articles.

[3] Polya, G., How to Solve It, A Doubleday Anchor Book, 1957. (Originally published by
Princeton University Press in 1945.)
[4] Ross, S. M., A First Course in Probability, 10th edn., Pearson, 2019.
[5] Wilf, H. S., Generating functionology, Academic Press, 1990.
An Introduction to Probability Downloaded from www.worldscientific.com