UMAP Module 771

Modules in
Undergraduate The Probability
Mathematics
and Its
That a Queen Sits
Applications Beside a King:
Juxtapositions and Runs
Published in
cooperation with
in a Random Permutation
The Society for John M. Holte
Industrial and Mark M. Holte
Applied Mathematics, Kenneth A. Suman
The Mathematical
Association of America,

The National Council

of Teachers of
Mathematics,

The American
Mathematical
Association of
Two-Year Colleges,

The Institute for

Operations Research
and the Management
Sciences, and

The American
Statistical Association.

Applications of Combinatorics
and Probability to Statistics,
Applied Probability and
Recreational Mathematics

COMAP, Inc., Suite 210, 57 Bedford Street, Lexington, MA 02420 (781) 862–7878
110 Tools for Teaching 1998

INTERMODULAR DESCRIPTION SHEET: UMAP Unit 771

TITLE: The Probability That a Queen Sits Beside a King:

Juxtapositions and Runs in a Random Permutationa
a 1991 AMS subject classifications: 60–01, 05A15,

60C05

AUTHORS: John M. Holte

Department of Mathematics and Computer Science
Gustavus Adolphus College
St. Peter, MN 56082
[email protected]

Mark M. Holte
1410 Krause Pl.
Mt. Vernon, WA 98274

Kenneth A. Suman
Department of Mathematics and Statistics
Winona State University
Winona, MN 55987
[email protected]
MATHEMATICAL FIELD: Combinatorics, probability

APPLICATION FIELD: Statistics, applied probability, recreational mathematics

TARGET AUDIENCE: Students in a combinatorics course or in a mathematical

statistics course
ABSTRACT: This Module deals with random permutations, focus-
ing on probabilities, means, and variances of the num-
bers of juxtapositions and runs of items of different
types. It illustrates the ideas via questions regarding a
shuffled deck of standard playing cards, such as: What
is the probability that a Queen is next to a King? What
is the average number of juxtapositions? What is the
variance? Tough problems are tamed. In a statistics
course, this Module provides a natural extension of the
usual distribution theory of runs.

PREREQUISITES: From combinatorics: the addition and multiplication

principles, permutations, combinations, and distribu-
tions of balls into urns. From probability: probability
as the number of successful cases divided by the num-
ber of possible cases, discrete means and variances and
their properties. From statistics: the notion of statistical
hypothesis testing (used in some exercises). Access to
mathematical software would be helpful.

Tools for Teaching 1998, 109–130. Reprinted from The UMAP Journal 19 (4) (1998): 373–394.
°Copyright
c 1998, 1999 by COMAP, Inc. All rights reserved.

Permission to make digital or hard copies of part or all of this work for personal or classroom use
is granted without fee provided that copies are not made or distributed for profit or commercial
advantage and that copies bear this notice. Abstracting with credit is permitted, but copyrights
for components of this work owned by others than COMAP must be honored. To copy otherwise,
to republish, to post on servers, or to redistribute to lists requires prior permission from COMAP.

COMAP, Inc., Suite 210, 57 Bedford Street, Lexington, MA 02420

(800) 77-COMAP = (800) 772-6627, or (781) 862-7878; http://www.comap.com
 The Probability That a Queen Sits Beside a King 111

The Probability That a Queen Sits

Beside a King: Juxtapositions and
Runs in a Random Permutation
John M. Holte
Department of Mathematics and Computer Science
Gustavus Adolphus College
St. Peter, MN 56082
[email protected]
Mark M. Holte
1410 Krause Pl.
Mt. Vernon, WA 98274
Kenneth A. Suman
Department of Mathematics and Statistics
Winona State University
Winona, MN 55987
[email protected]

Table of Contents
1. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. THE PROBABILITY THAT A QUEEN IS NEXT TO A KING . . . . . . . . 1
3. JUXTAPOSITIONS AND RUNS . . . . . . . . . . . . . . . . . . . . . . . 4

4. ORDERED JUXTAPOSITIONS . . . . . . . . . . . . . . . . . . . . . . . 7
5. MEAN AND VARIANCE . . . . . . . . . . . . . . . . . . . . . . . . . 8
6. RELATED PROBLEMS . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

7. RANDOM CIRCULAR PERMUTATIONS . . . . . . . . . . . . . . . . . . 12

8. SOLUTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

ABOUT THE AUTHORS . . . . . . . . . . . . . . . . . . . . . . . . . . 18

112 Tools for Teaching 1998

MODULES AND MONOGRAPHS IN UNDERGRADUATE

MATHEMATICS AND ITS APPLICATIONS (UMAP) PROJECT

The goal of UMAP is to develop, through a community of users and devel-

opers, a system of instructional modules in undergraduate mathematics and
its applications, to be used to supplement existing courses and from which
complete courses may eventually be built.
The Project was guided by a National Advisory Board of mathematicians,
scientists, and educators. UMAP was funded by a grant from the National
Science Foundation and now is supported by the Consortium for Mathemat-
ics and Its Applications (COMAP), Inc., a nonprofit corporation engaged in
research and development in mathematics education.

Paul J. Campbell Editor

Solomon Garfunkel Executive Director, COMAP
 The Probability That a Queen Sits Beside a King 113

1. Introduction
Suppose that you thoroughly shuffle a deck of ordinary playing cards and
then deal them out in one long row. What is the probability that somewhere
in the row you will find a Queen next to a King? Or a club next to a diamond?
Or a face card next to an Ace? More generally, in a random permutation of n
objects of various kinds, what is the probability of finding j instances where an
object of a given kind is adjacent to one of another given kind?
At first glance, you may conclude that an explicit solution would be quite
difficult. Indeed, an earlier published solution [Singmaster 1991] for the special
case of no Queen–King juxtapositions relied entirely on a recurrence-relation
calculation. But in fact, explicit solutions to such problems turn out to be
elementary and accessible to undergraduate students who have studied com-
binatorics or discrete probability. Furthermore, the juxtaposition problem turns
out to be closely related to the problem of determining the distribution of runs,
which is studied in many undergraduate mathematical statistics courses and
whose solution has been known at least since 1886 (Whitworth [1886, Exercises
193, 194]; Barton and David [1957, 168]). In fact, the solution of the juxtaposi-
tion problem to be given here provides a natural follow-up to the solution of
the runs problem.
In the special case of Ace-King juxtapositions, an explicit solution for j
juxtapositions was given by Holte and Holte [1993]. An explicit solution for
the general problem of no adjacencies between any objects of k different kinds
was given by Suman [1993]. In this Module, we extend the techniques of these
papers to find the probability of exactly j juxtapositions occurring between
objects of two different kinds in a random permutation of any number of objects
of two or more kinds.
In addition, we find the mean and variance of the number of juxtapositions.
Doing this provides a nice illustration of techniques for dealing with moments
of sums of dependent random variables.

2. The Probability That a Queen Is Next to

a King
Let us begin by finding the probability that there are exactly j places where
a Queen is adjacent to a King in the order specified in a shuffled deck. For now,
assume that all four Queens (Qs) are identical, all four Kings (Ks) are identical,
and all 44 cards that are neither (Ns) are identical. Clearly, if we can find the
number of all permissible permutations under this assumption, then we can
multiply this answer by 4!4!44! to adjust for the fact that the cards are all distinct.
Now, a permutation of the deck might look like this:
NNNNNNQNNNNNQKNNNNQNNNNNNNNKNNNNNNNNNKNNNNQNNNKNNNNN.

1
114 Tools for Teaching 1998

Suppressing the Ns, we see

Q QK Q K K Q K.
Without the Ns there are three potential QK juxtapositions, but with the Ns
inserted as above, there was just one such actual juxtaposition.
Let’s count the number of arrangements of the four Qs and four Ks that
by themselves have m (potential) QK juxtapositions. We first consider the Qs
alone and mark the m places where Ks will follow a Q; in our example with
m = 3, we’d write
QQ|Q|Q|.
¡4¢
There are m ways to choose these places. Second, we consider the Ks alone
and mark the m places where a K is to be preceded by Qs; for our example, we
write

|K|KK|K.
¡4¢
There are m ways to choose these places. With these choices, the string of Qs
and Ks is determined; it would be QQKQKKQK in our example. There are
µ ¶2
4
m

possible arrangements.
Next, let’s count the number of ways that we can insert the Ns so as to
achieve j actual juxtapositions. Think of the nine spaces before, between, and
after the four Qs and four Ks as urns. To achieve j actual
¡m¢juxtapositions, choose
j of the m QK urns to be empty; this can be done in j ways. To make sure
that there are no more than j juxtapositions, place one N in each of the other
(m − j) QK urns. Then distribute the remaining 44 − (m − j) Ns into the (9 − j)
urns that do not have to be empty.
We need to know here and later that
the number of ways to place r identical balls into u urns without restriction is
µ ¶
r+u−1
.
u−1

This formula can be established by a “stars-and-bars” argument: Write ∗

for each ball, and divide the balls into u groups by (u − 1) vertical bars. For
example, ∗ ∗ ∗| ∗ ∗||∗ represents 3 balls in the first urn, 2 in the second, none in
the third, and 1 in the fourth. The number of ways to choose u − 1 places from
r + u − 1 for the |s is µ ¶
r+u−1
.
u−1
For us, the number of ways that we can distribute the Ns is

2
 The Probability That a Queen Sits Beside a King 115

µ ¶ µ ¶
(44 − (m − j)) + (9 − j) − 1 52 − m
= .
(9 − j) − 1 8−j

Thus, there are µ ¶2 µ ¶µ ¶

4 m 52 − m
m j 8−j
arrangements of Qs, Ks, and Ns having m potential QK juxtapositions and j
actual QK juxtapositions. Multiplying by 4!4!44!, summing over all possible
values of m (j ≤ m ≤ 4), and dividing by the number of permutations of 52
cards, we get the probability qj of j QK juxtapositions:
4 µ ¶2 µ ¶µ
X ¶
4 m 52 − m 4!4!44!
qj = .
m=j
m j 8−j 52!

Approximate values of qj are given in the following table.

j 0 1 2 3 4
qj 0.7187 0.2556 0.0250 0.0007 4 × 10−6

The probability of j Queen–King juxtapositions in either order (QK or KQ)

is computed in the next section.

Exercises
¡ ¢2
1. List the 43 possible sequences of four Qs and four Ks having exactly 3 QK
juxtapositions.

2. Suppose that the deck is reduced to two Qs, two Ks, and one Ace. Adapt
the analysis in the text to complete the following table. Find the probability
qj of j QK juxtapositions for each j.

m Qs Ks K–Q # ways to insert A to get

to follow to precede sequence j=0 j=1 j=2
m=0 QQ KK KKQQ
m=1 Q|Q |KK 1 4 0
m=1 Q|Q K|K KQKQ
m=1 QQ| |KK 1
m=1 QQ| K|K KQQK
m=2 Q|Q| |K|K QKQK

3
116 Tools for Teaching 1998

3. Juxtapositions and Runs

Now consider a set of n distinguishable objects of various kinds: a of one
kind (As), b of a second kind (Bs), and c = n − a − b of other kinds (collectively
Cs). What is the probability that a random permutation of the n objects contains
exactly j instances where an object of the first kind is adjacent (on either side)
to an object of the second kind?
Temporarily regard the As (respectively, Bs) as indistinguishable. Let A+
denote a generic string of one or more consecutive As; define B + similarly.
When our a As and b Bs are laid out in a line, the A+ s and B + s alternate, so
the numbers of A+ s and B + s must either be the same or differ by one; let i be
the common or smaller number, as the case may be. Then the following table
summarizes all the possibilities.

Pattern #A+ s #B + s #ABs #BAs #juxtapositions

A B A ···A B
+ + + + +
i i i i−1 2i − 1
A+ B + A+ · · · B + A+ i+1 i i i 2i
B + A+ B + · · · A+ B + i i+1 i i 2i
B + A+ B + · · · B + A+ i i i−1 i 2i − 1

Each A+ and B + represents a “run” of As or Bs, respectively. A string

has m AB and BA juxtapositions if and only if it has m + 1 runs of As and
Bs. Let Rk = Rk (a, b) denote the number of arrangements of a As and b Bs
yielding k runs of As and Bs. Then the number of arrangements of a As and b
Bs yielding exactly m AB or BA juxtapositions is Rm+1 (a, b). Formula (1) below
is well known in the theory of runs—see, for example, David and Barton [1962,
6], Freund [1992, 594–595], Hogg and Craig [1995, 517–519], Hogg and Tanis
[1993, section 10.6], or Ross [1994, 47–49, 57–58]—and the reader familiar with
the result may jump ahead to that point, but for completeness we rederive it
¡ ¢
next. Values of the probabilities of k runs—r(k; a, b) = Rk (a, b)/ a+b a —can be
found in statistical tables (e.g., Beyer [1968, Table X.6, pp. 414–424], Swed and
Eisenhart [1943]).
Now let’s count the ways to get the patterns in the table.
In the first pattern, A+ B + A+ · · · A+ B + , after putting a B + after the last
¢ the other i − 1 B s after i − 1 As (not A s), which can+be
+ +
A, we must insert
¡a−1
chosen in i−1 ways. This determines the As that are to be followed by B s,
but it does not determine the Bs that are to be followed by A+ s. Aside from
the last ¡B, there
¢ are b − 1 Bs from which we must choose
¡a−1¢¡ ¢ i − 1; this can be
done in b−1i−1 ways. All together, then, we have b−1
i−1 i−1 ways to achieve the
A B A · · · A B pattern.
+ + + + +

For the second pattern, A+ B + A+ · · · B + A+ , we must use at least¡a−1one

¢ A at
+
the end, and then insert i B s after i As, which can be chosen in i ways.
Then, aside from the last B, which is necessarily followed by A+ , we must
¡ ¢
choose i − 1 Bs to be followed immediately by A+ s, which can be done in b−1 i−1

4
 The Probability That a Queen Sits Beside a King 117

¡ ¢¡b−1¢
ways. Together, we have a−1 i i−1 ways to achieve the A B A · · · B A
+ + + + +

pattern.
The remaining patterns can be counted by switching A and B (and, corre-
spondingly, a and b) and applying the formulas just derived. The result is that
¡ ¢¡a−1¢
the number of B + A+ B + · · · A+ B + patterns is b−1 i−1 , and the number of
¡b−1¢¡a−1¢ i
B A B · · · B A patterns is i−1 i−1 .
+ + + + +

If m = 2i − 1 (first and fourth patterns), then the number of patterns having

m juxtapositions is given by
µ ¶µ ¶
a−1 b−1
Rm+1 = R2i = 2 .
i−1 i−1
If m = 2i (second and third patterns), then the number of patterns having m
juxtapositions is given by
µ ¶µ ¶ µ ¶µ ¶
a−1 b−1 a−1 b−1
Rm+1 = R2i+1 = + .
i i−1 i−1 i
We can combine the odd- and even-case formulas by using the greatest-
integer function, also known as the floor function, denoted here by b·c:
bnc = the greatest integer not exceeding n.
If m = 2i − 1, then bm/2c = i − 1 and b(m − 1)/2c = i − 1, and if m = 2i, then
bm/2c = i and b(m − 1)/2c = i − 1. Thus, the number of arrangements of a As
and b Bs having m AB or BA juxtapositions is given by
µ ¶µ ¶ µ ¶µ ¶
a−1 b−1 a−1 b−1
Rm+1 (a, b) = + . (1)
bm/2c b(m − 1)/2c b(m − 1)/2c bm/2c
Now, given an arrangement of a As and b Bs yielding m potential AB or BA
juxtapositions, we insert the remaining c objects (Cs) so as to achieve exactly
j juxtapositions. There are a + b + 1 “urns” available for these other
¡m¢ objects,
and we must keep empty j of the m AB or BA urns. There are j ways to
choose these urns. To make sure that there are no more than j juxtapositions,
we place one C in each of the other m − j AB and BA urns. Then we distribute
the remaining c − (m − j) Cs into the a + b + 1 − j urns that do not have to be
empty; the number of ways this can be done is
µ ¶ µ ¶
(c − (m − j)) + (a + b + 1 − j) − 1 n−m
= .
(a + b + 1 − j) − 1 a+b−j
¡ ¢ ¡ n ¢
Because there are nc = a+b equally likely ways to choose positions for the Cs
among the As and Bs, the conditional probability of achieving j juxtapositions
is
µ ¶µ ¶
m n−m
j a+b−j
µ ¶ = h(j; a + b, m, n − m),
n
a+b

5
118 Tools for Teaching 1998

that is, a hypergeometric probability. Note that

h(j; a + b, m, n − m) = h(m − j; c, m, n − m).

Finally, assuming that all n! permutations are equally likely and taking
into account the possible permutations of the As, Bs, and Cs, we find that
the probability pj of getting exactly j instances where an A-object is next to a
B-object (in either order) is
X µ ¶µ ¶
m n − m a!b!c!
pj = Rm+1 (a, b) (2)
m
j a+b−j n!

where a + b + c = n, the sum is taken over all possible values of m (max{j, 1} ≤

m ≤ 2 min{a, b}), and Rm+1 (a, b) is given by (1). Alternatively, pj is the sum,
over all possible m, of the probability of having m potential juxtapositions times
the conditional probability that then j of the m are kept:

X
2 min{a,b}
pj = r(m + 1; a, b)h(j; a + b, m, n − m).
m=max{j,1}

Example 1. The probability that, in an ordinary shuffled deck, we have j

Queen–King or King–Queen juxtapositions is given by equation (2) with
n = 52 and a = b = 4. Approximate values are given in the following
table. Note that the probability that some Queen is next to some King
(on either side) is 1 − p0 ≈ 0.486. This value was found via recurrence
relations in Singmaster [1991].

j 0 1 2 3 4 5 6 7
pj .514 .372 .100 .013 .001 3 × 10−5 4 × 10−7 2 × 10−9

Example 2. The probability that in an ordinary shuffled deck we have

j instances where a club is next to a diamond is given by (2) with n = 52
and a = b = 13. Approximate values that are at least 0.01 are given in the
following table.

j 2 3 4 5 6 7 8 9 10 11 12
pj .01 .04 .10 .16 .19 .19 .14 .09 .04 .02 .01

Example 3. The probability that there are j instances where an Ace is next
to a face card is given by (2) with n = 52, a = 4, and b = 12. Approximate
values are given in the following table.

j 0 1 2 3 4 5 6 7 8
pj .114 .296 .320 .189 .066 .014 .002 .000 .000

6
 The Probability That a Queen Sits Beside a King 119

Exercises
3. Consider the 5!/(2!2!1!) five-letter “words” that can be formed using two
As, two Bs, and one C. For each i (the smaller of the number of A- and
B-runs) and for each pattern in the table of possibilities, list the five-letter
words that give each number j of AB and BA juxtapositions. Confirm that
p0 = 1/15, p1 = p2 = 2/5, and p3 = 2/15.
4. Three contagious people, four susceptible people, and five immune people
line up randomly. What is the probability that a contagious person stands
next to a susceptible person in the queue?
5. Six bar magnets and six bars of metal are inserted at random and pushed
together in a horizontal plastic pipe. Suppose that the orientation of three of
the bar magnets is N-S, and for the other three it is S-N. When like magnetic
poles are adjacent, the magnets will repel. For j = 0, . . . , 5, what is the
probability that there are j gaps?

4. Ordered Juxtapositions
The preceding analysis can be adapted to the case where we count juxta-
positions only if they occur in a particular order, A to the left of B, say. If we
replace i by i + 1 in the B + A+ B + · · · B + A+ row of the table of patterns, so that
the number of AB juxtapositions stipulated there is i (as it is in all the other
rows), then we find that the number of ways to arrange a As and b Bs so as to
get m = i AB juxtapositions is
µ ¶µ ¶ µ ¶µ ¶ µ ¶µ ¶ µ ¶µ ¶
a−1 b−1 a−1 b−1 b−1 a−1 b−1 a−1
+ + +
i−1 i−1 i i−1 i i−1 i i
µ ¶µ ¶
a b
= .
i i

The simpler answer points to an easier way to get this, which is left as an
exercise for the reader. Now the probability qj of getting j ABs is
min{a,b} µ
X ¶µ ¶µ ¶µ ¶
a b m n − m a!b!c!
qj = .
m=j
m m j a+b−j n!

Example 4. If the letters of the word “STATISTICS” are written on ten

cards that are then permuted randomly, then the probability qj of getting
j STs is given as follows.
j 0 1 2 3
qj 7/24 = .2916 21/40 = .5250 7/40 = .1750 1/120 = .0083

7
120 Tools for Teaching 1998

Exercises
6. Give a combinatorial argument to explain why the the number of ways to
¡ ¢¡ ¢
arrange a As and b Bs so as to get exactly i AB juxtapositions is ai bi .

7. Suppose that 6 print jobs in a computer system are queued at random. Two
are long, two are of medium length, and two are short. What is the proba-
bility that no long job immediately precedes a short job?

8. Of the 30 students enrolled in a statistics class, 10 are female math majors

(F s), 12 are male math majors (M s), and 8 are non-math majors (N s). As
the students turned in their midterm exams, the professor noticed that quite
often a male math major turned in his exam right after a female math major
turned in hers. Thus the professor was interested in testing
H0 : The sequence of 10 F s, 12 M s, and 8 N s is random, versus
H1 : There are more F M adjacencies than would be expected under H0 .
The order in which students turned in their midterm exams was

F M N N F F M F M N M N M F M M F F M N N M F M N M F M N F.

There are 7 F M s. Find P (7 or more F M adjacencies | H0 is true). Should

we reject H0 at the 5% level of significance?

5. Mean and Variance

In order to get a better sense of the central tendency and spread of the
possible numbers of juxtapositions, let us calculate the mean and variance of
the random variable T that is defined as the total number of times that, in a
random permutation of a set of n distinguishable objects, an object of a specified
subset of a objects (As) is adjacent (on either side) to an object from a specified
disjoint subset of b objects (Bs). We claim that the mean, or expected value of
T , is
2ab
µ = E(T ) =
n
and the variance of T is

µ ¶ µ ¶
2ab a+b 2ab a+b−µ µ(µ + c − 1)
σ = 2
1− + =µ 1− = ,
n n − 1 n(n − 1) n−1 n−1
where c = n − (a + b).
Thus, for example, when T is the number of Queen–King or King–Queen
juxtapositions, we have n = 52 and a = b = 4, so µ = 2 · 4 · 4/52 = 8/13,

8
 The Probability That a Queen Sits Beside a King 121

σ 2 = (8/13)(1 − (4 + 4 − 8/13)/51) = 1512/2873, and the standard deviation is

about 0.725. If we shuffled d ordinary decks together, then the mean number
of such juxtapositions would be 2 · 4d · 4d/(52d) = (8/13)d and the√standard
deviation would be ((8d/13)(1 − (8d − 8d/13)/(52d − 1)))1/2 ≈ 0.73 d.
In the case that a + b = n, the mean and variance formulas are well known
from the theory of runs; see, for example, David and Barton [1962, 88], Freund
[1992, 596], Hogg and Tanis [1993, 634], or Ross [1994, 313–314] (mean only).
Still, we shall give an independent derivation of these results—one that works
for a + b ≤ n.
Rather than undertake the daunting task of calculating the mean and vari-
ance directly from (2), let us use the standard technique of writing T as a sum of
indicator random variables. Introduce the random variable Xi that is defined
(for 1 ≤ i ≤ n − 1) to be 1 if AB or BA P occurs in positions i and i + 1 and that is
defined to be 0 otherwise. Then T = Xi .
We observe that E(Xi ) = 1 · P (Xi = 1), the probability of a juxtaposition
in positions i and i + 1, which is (a/n)(b/(n − 1)) + (b/n)(a/(n − 1)). By the
linearity property of expectation, or mean value, we obtain
Ãn−1 !
X
E(T ) = E Xi
i=1
X
n−1
= E(Xi )
i=1
µ ¶
a b b a
= (n − 1) · + ·
n n−1 n n−1
2ab
= .
n
The calculation of the variance is quite a bit more difficult and serves as a
good illustration of the sort of calculation one must go through when finding
the variance of a sum of correlated random variables, when the answer is not
simply the sum of the variances—the sort of thing one does, for example, to
get the variance of a hypergeometric distribution. We begin with

σ 2 = E(T 2 ) − (E(T ))2

and
³X X ´ XX
E(T 2 ) = E Xi Xj = E(Xi Xj ).

Now E(Xi Xj ) = 1 · P (Xi = 1&Xj = 1), the probability of juxtapositions in

positions i and (i + 1) and positions j and (j + 1). The possibilities for the
(n − 1)2 terms are given in the following table.

9
 122 Tools for Teaching 1998

Indices #terms Patterns E(Xi Xj )

a b
j=i n−1 AB · +
n n−1
b a
BA ·
n n−1

a b a−1
j =i+1 2(n − 2) ABA · · +
n n−1 n−2
b a b−1
or j = i − 1 BAB · ·
n n−1 n−2

j ≥i+2 (n − 2)(n − 3) AB, AB

a b a−1 b−1
or AB, BA 4· · · ·
n n−1 n−2 n−3
j ≤i−2 BA, AB
BA, BA
1 ≤ i, j ≤ n − 1 (n − 1)2

Adding every E(Xi Xj ) value multiplied by its number of terms and sim-
plifying, we get
µ ¶
¡ 2 ¢ 2ab 2ab − a − b
E T = 1+ .
n n−1

Then σ 2 = E(T 2 ) − (E(T ))2 reduces to the result claimed above, completing
the calculation.

Exercises
9. What is the expected number of club-diamond and diamond-club juxtapo-
sitions in a randomly shuffled deck? What is the variance?
10. In a randomly shuffled deck, how many runs of face cards and of nonface
cards will there be on average? What is the standard deviation?

11. Suppose that when the scores of college students on a test are arranged in
order (assume no ties) and the class of each student is noted (1 = freshman,
2 = sophomore, etc.), the following sequence of classes is observed:

3 2 3 111 4 1 44 2 4 2 44 22 11 3.

Is the number of runs in this sequence greater than would be expected by

chance?

10
 The Probability That a Queen Sits Beside a King 123

12. Let U denote the number of AB juxtapositions (in that order) in a random
permutation of a As, b Bs, and c Cs. Derive formulas for the mean and
variance of U .
13. The number of runs is used as a nonparametric statistic in tests of ran-
domness. The number of juxtapositions can be used instead. For example,
suppose that a row of 14 plants shows the following pattern of 7 healthy
(H) and 7 diseased (D) plants:

HHHDDDDHHHHDDD.

Is the arrangement random?

a) Calculate the mean and standard deviation of the number of HD and
DH juxtapositions, and interpret the results.
b) Calculate the probability of getting 3 or fewer juxtapositions if the se-
quence is random.
c) Calculate the probability of getting 10 or more juxtapositions if the se-
quence is random. Notice that the maximum possible number of juxta-
positions is 13, and 13 − 3 = 10.
d) Verify that the probability of getting a number of juxtapositions as ex-
treme as the number in the sample is about 5%.
14. Five men, five women, and ten children get into a line.
a) If they line up at random, what is the mean and standard deviation of
the number of woman-child/child-woman juxtapositions?
b) A statistician suspects that children will tend to get next to women in
line. What is the probability of getting at least as many cases of this as
in the following sample?

W M CCW CW CM CCW CM CW CM CM

Does the evidence confirm the statistician’s suspicion?

6. Related Problems
The juxtaposition problems that we have considered represent just one kind
of problem connected with random permutations. Besides the run probabil-
ities considered here, there are many interesting problems in the distribution
theory of runs, including those involving runs of more than two kinds of ob-
jects; comprehensive accounts are given in David and Barton [1962] and the
classic article Mood [1940]. The former source also discusses matching and
derangement problems for (two) random permutations, and it gives extensive
calculations of moments via indicator random variables.
Takács [1981] also discusses the classical problem of ménages—finding the
probability that some husband and wife will be seated together if n couples are

11
 124 Tools for Teaching 1998

randomly seated around a circular table with men and women alternating. Bar-
bour et al. [1992, Ch. 4] address various problems connected with random per-
mutations, including matching and ménage problems; they calculate moments
via indicator random variables, and they provide Poisson approximations to
various probability distributions.
But none of these sources gives the juxtaposition probabilities presented in
this Module.

7. Random Circular Permutations

The concluding exercises develop the theory and applications of random
circular permutations.
Suppose that n letters—a As, b Bs, and c Cs—are randomly permuted in a
line, and then the line is bent so that the ends meet to form a ring.

Exercises

15. Derive formulas for the mean and variance of the number U of AB juxta-
positions.

16. Derive formulas for the mean and variance of the number T of AB and BA
juxtapositions.

17. Derive a formula for the probability of exactly j AB juxtapositions in a

random circular permutation in terms of such probabilities for linear per-
mutations.

18. Derive a formula for the probability of exactly j AB and BA juxtapositions

when a As, b Bs, and c Cs are randomly permuted and bent into a ring.

19. Three Arabs, four Israelis, and six Swiss are seated randomly at a circular
table. What are the mean and variance of the number of Arab–Israeli jux-
tapositions? What is the probability that no Arab and no Israeli are side by
side?
20. Repeat Examples 1–4 for circular permutations.

12
 The Probability That a Queen Sits Beside a King 125

8. Solutions
1. KQKQKQKQ KQKQKQQK KQKQQKQK KQQKQKQK
QKKQKQKQ QKKQKQQK QKKQQKQK QQKKQKQK
QKQKKQKQ QKQKKQQK QKQQKKQK QQKQKKQK
QKQKQKKQ QKQKQQKK QKQQKQKK QQKQKQKK

2.
m Qs Ks K–Q # ways to insert A to get
to follow to precede sequence j=0 j=1 j=2
m=0 QQ KK KKQQ 5 0 0
m=1 Q|Q |KK QKKQ 1 4 0
m=1 Q|Q K|K KQKQ 1 4 0
m=1 QQ| |KK QQKK 1 4 0
m=1 QQ| K|K KQQK 1 4 0
m=2 Q|K| |K|K QKQK 0 2 3

Therefore, q0 = 9/30 = 3/10, q1 = 18/30 = 3/5, and q2 = 3/30 = 1/10.

3.
i=1 AABB j = 0: AACBB.
j = 1: AABBC, AABCB, ACABB, CAABB.
i=1 ABBA j = 1: ABBCA, ACBBA.
j = 2: ABBAC, ABCBA, CABBA.
i=1 BAAB j = 2: BAACB, BCAAB.
j = 2: BAABC, BACAB, CBAAB.
i=1 BBAA j = 0: BBCAA.
j = 1: BBAAC, BBACA, BCBAA, CBBAA.
i=2 ABAB j = 2: ABACB, ABCAB, ACBAB.
j = 3: ABABC, CABAC.
i=2 BABA j = 2: BABCA, BACBA, BCABA.
j = 3: BABAC, CBABA.
4. Let type A be contagious; B, susceptible; and C, immune; then a = 3, b =
4, c = 5, and n = 12. We want to calculate 1 − p0 . By the formula given,
· µ ¶ µ ¶ µ ¶ µ ¶ µ ¶¸
11 10 9 8 7 3!4!5! 59
p0 = 2 · +5· + 12 · +9· +6· = ,
7 7 7 7 7 12! 924

so 1 − p0 ≈ 94%.

13
 126 Tools for Teaching 1998

5.
j 0 1 2 3 4 5

61 101 223 27 23 1
pj
440 264 660 220 1320 1320

≈ .139 ≈ .383 ≈ .338 ≈ .123 ≈ .017 ≈ .001

¡ ¢
6. There are ai ways to choose the i As that will be followed by one or more
¡¢
Bs, and there are bi ways to choose the i Bs that will be preceded by one or
more As. These two choices uniquely determine an interleaving of the As
¡ ¢¡ ¢
and Bs yielding i AB juxtapositions, so all together there are ai bi ways
to achieve i juxtapositions.
7. Here a = 2 (long), b = 2 (short), and c = 2, so the answer is q0 = 2/5.
X
10
8. P (7 or more F M adjacencies | H0 is true) = qj ≈ 0.024 < 0.05, so we re-
j=7
ject H0 at the 5% level.
9. Here a = 13, b = 13, c = 26, and n = 52, so the expected number is µ =
2ab/n = 2·13·13/52 = 13/2 = 6.50 and the variance is µ(µ+c−1)/(n−1) =
(13/2)(13/2 + 26 − 1)/51 = 273/68 ≈ 4.01.
10. The number of runs is T + 1, where T is the number of face–nonface and
nonface–face juxtapositions. Here a = 12, b = 40, c = 0, and n = 52, so
E(# runs) = E(T + 1) = E(T ) + 1 = µ + 1, where µ = 2 · 12 · 40/52 = 240/13,
so µ + 1 = 253/13 ≈ 19.46 and σT2 +1 = σT2 = µ(µ + c − 1)/(n − 1) =
18160/2873 and σT ≈ 2.51.
11. There are 6 freshmen, 5 sophomores, 3 juniors, and 6 seniors. Let Tij denote
the number of ij and ji juxtapositions, and let R denote the total number of
runs of identical digits. Then R = 1 + T12 + T13 + T14 + T23 + T24 + T34 . Each
E(Tij ) = 2ab/n for appropriate a and b, so E(R) = 1 + 2[(6)(5) + (6)(3) +
(6)(6) + (5)(3) + (5)(6) + (3)(6)]/20 = 15.7. The observed number of runs is
14—just a little below what is expected. (The theory presented here is not
adequate to compute P (R ≤ 14)—or even the variance of R—because of
the covariances involved.)
12. Here let Xi = 1 if the ith value is an A and the (i + 1)st value is a B, and let
Xi = 0 otherwise (1 ≤ i ≤ n − 1);
X
n−1
a b ab
µ = E(U ) = E(Xi ) = (n − 1) = .
i=1
nn−1 n
Also,
X n−1
n−1 X
2
σU = E(U 2 ) − [E(U )]2 = E(Xi Xj ) − µ2 ,
i=1 j=1

14
 The Probability That a Queen Sits Beside a King 127

and the counterpart of the table in the text is as follows.

Indices #terms Patterns E(Xi Xj )

a b
j=i n−1 AB ·
n n−1

j − i = ±1 2(n − 2) impossible 0

a b a−1 b−1
|j − i| ≥ 2 (n − 2)(n − 3) AB, AB · · ·
n n−1 n−2 n−3

1 ≤ i, j ≤ n − 1 (n − 1)2

Therefore,
a b a b a−1 b−1
E(U 2 ) = (n − 1) · + (n − 2)(n − 3) · · · ,
n n−1 n n−1 n−2 n−3

2 µ(µ + c)
whence, by algebra, σU = .
n−1
13. a) Mean = 7; standard deviation ≈ 1.80. The observed number of juxta-
positions (3) is more than two standard deviations away from the mean.
b) p0 + p1 + p2 + p3 ≈ .02506. Here p0 = 0.
c) p11 + p12 + p13 + p14 ≈ .02506. Here p14 = 0.
d) Consequently the P -value is about 0.051.

14. a) Mean = 5; standard deviation ≈ 1.54.

b) There are 8 W Cs and CW s, and p8 + p9 + p10 ≈ 0.04956. The evidence
supports the statistician’s suspicion (barely) at the 5% level of signifi-
cance.

15.
ab 2 µU (µU + c − 1)
µU = E(U ) = , σU = .
n−1 n−2

16.
2ab µT (µT + c − 2)
µT = E(T ) = , σT2 = .
n−1 n−2

15
 128 Tools for Teaching 1998

17. Let q(j; a, b, c) denote the probability of exactly j AB juxtapositions in a

random linear permutation of a As, b Bs, and c Cs, and let q ∗ (j; a, b, c)
denote the corresponding probability for a linear permutation bent into a
ring. There will be j AB juxtapositions in the ring if the line starts with B
and ends with A and has j − 1 AB juxtapositions, or if it does not start with
B and end with A and has j AB juxtapositions. Thus,

b a
q ∗ (j; a, b, c) = q(j − 1; a − 1, b − 1, c)
nn−1
b a
+ q(j; a, b, c) − q(j; a − 1, b − 1, c).
nn−1

18. Adapt the procedure used to find pj . Count carefully: It is easy to go astray!
For each i between 1 and min{a, b}, count the linear arrangements of a As
and b Bs yielding i circular runs of each type. There are four pattern cases
(A+ B + · · · A+ B + , etc.), and the number of circular runs, which equals the
number of juxtapositions, must be even (2i). For each arrangement, count
the ways of choosing j AB and BA contacts to keep (which sometimes
involves the “wraparound” case), place a C in the other AB and BA gaps
(sometimes a left or right end), and then, regarding these other gaps and the
gaps among the As and Bs as urns, count the ways to place the remaining
Cs in these urns. Sum over i and multiply by a!b!c!/n!, where n = a + b + c,
to get the desired probability, p∗j .
Consider, for example, the A+ B + · · · A+ B + pattern with i A+ s and i
¡ ¢¡b−1¢
B + s. With a As and b Bs, this can be arranged in a−1 i−1 i−1 ways. If the
wraparound
¡2i−1¢ contact is maintained, then there are j − 1 interior contacts to
keep— j−1 choices—and 2i − 1 − (j − 1) contacts to break up with one
C each. The remaining r = ¢c − (2i − j) Cs can then be distributed into
¡r+u−1
u = a + b − j urns in u−1 ways. If the wraparound contact is broken
up, then choose the
¡2i−1 ¢ j contacts to be maintained from the 2i − 1 interior
possibilities— j ways—and place a C in each of the other 2i − 1 − j
interior gaps. At least one of the remaining Cs must go at one end, so first
count the ways to put r = c − (2i − 1 − j) balls into u1 = a + b + 1 − j urns
(this includes both ends), and then subtract the number of ways to put the
r balls into the u2 = a + b − 1 − j non-end urns. The total for the two cases
is given by Yij below.
After the remaining three patterns are tallied, the result is:

min{a,b} · µ ¶µ ¶
X a−1 b−1
p∗j = 2 Yij
i=1
i−1 i−1
½µ ¶µ ¶ µ ¶µ ¶¾ ¸
a−1 b−1 a−1 b−1 a!b!c!
+ + Zij ,
i i−1 i−1 i n!

16
 The Probability That a Queen Sits Beside a King 129

where
µ ¶µ ¶ µ ¶ ·µ ¶ µ ¶¸
2i − 1 n − 2i − 1 2i − 1 n − 2i + 1 n − 2i − 1
Yij = + −
j−1 a+b−j−1 j a+b−j a+b−j−2

and
µ ¶µ ¶
2i n − 2i
Zij = .
j a+b−j

19. Mean = 2; variance = 12/11; p∗0 = 59/924 ≈ 0.06.

20. (1)

j 0 1 2 3 4 5 6 7
p∗j .5065 .3752 .1037 .0137 .0009 3 × 10−5 4 × 10−7 2 × 10−9

(2)
j 2 3 4 5 6 7 8 9 10 11
p∗j .01 .04 .09 .15 .19 .19 .15 .10 .05 .02

(3)
j 0 1 2 3 4 5 6 7 8
p∗j .092 .267 .322 .212 .083 .120 .003 .000 .000

(4)
j 0 1 2 3
qj∗ 5/21 ≈ .2381 15/28 ≈ .5357 3/14 ≈ .2143 1/84 ≈ .0119

References
Barbour, A.D., Lars Holst, and Svante Janson. 1992. Poisson Approximation.
New York, NY: Oxford University Press.
Barton, D.E., and F.N. David. 1957. Multiple runs. Biometrika 44: 168–178, 534.
Beyer, ed. 1968. Handbook of Tables for Probability and Statistics, 2nd ed. Boca
Raton, FL: Chemical Rubber Company.
David, F.N., and D.E. Barton. 1962. Combinatorial Chance. London, England:
Charles Griffin.
Freund, John E. 1992. Mathematical Statistics. 5th ed. Englewood Cliffs, NJ:
Prentice-Hall.

17
130 Tools for Teaching 1998

Hogg, Robert V., and Allen T. Craig. 1995. Introduction to Mathematical Statistics.
5th ed. Upper Saddle River, NJ: Prentice Hall.
Hogg, Robert V., and Elliot A. Tanis. 1993. Probability and Statistical Inference
4th ed. New York, NY: Macmillan.
Holte, John, and Mark Holte. 1993. The probability of n Ace-King adjacencies
in a shuffled deck. Mathematical Gazette 77: 368–370.
Mood, A.M. 1940. The distribution theory of runs. Annals of Mathematical
Statistics 11: 367–392.
Ross, Sheldon. 1994. A First Course in Probability. 4th ed. New York: Macmillan.
Singmaster, David. 1991. The probability of finding an adjacent pair in a deck.
Mathematical Gazette 75: 293–299.
Suman, Kenneth A. 1993. A problem in arrangements with adjacency restric-
tions. Mathematical Gazette 77: 366–367.
Swed, Frieda S., and C. Eisenhart. 1943. Tables for testing randomness of
grouping in a sequence of alternatives. Annals of Mathematical Statistics 14:
66–87.
Takács, L. 1981. On the “problème des ménages.” Discrete Mathematics 36: 289–
297.
Whitworth, William Allen. 1886. Choice and Chance. 5th ed., reprinted. New
York: Hafner, 1959.

About the Authors

John Holte earned his B.S. from Caltech and his M.S. and Ph.D. from the
University of Wisconsin–Madison, all in mathematics. His thesis research area
is probability theory. He has held faculty positions at Augustana College–Rock
Island, Rensselaer Polytechnic Institute, Kansai University of Foreign Studies
in Japan, and Gustavus Adolphus College, where he enjoys teaching a wide
variety of courses.
Mark Holte earned his B.S. in mathematics from Pacific Lutheran University
and his Ph.D. in mathematics (numerical analysis) from the University of Ore-
gon. He has worked as a computer programmer but is currently unemployed.
He and John are brothers.
Ken Suman earned his B.S. and M.S. in mathematics from Clemson Uni-
versity and his Ph.D. in theoretical statistics from Penn State University. He
is currently a professor and the chairperson of the Department of Mathemat-
ics and Statistics at Winona State University, and he is working on a book on
enumerative combinatorics and discrete probability.

18