Transcript Arranging The Alphabet Problem

Arranging The Alphabet
Problem: Suppose we arrange the 26 letters of the alphabet in random
order. What is the probability p that the x and the y will be next to each
other?
Solution: This is a solution offered by one of my students
Of all the ways to arrange the 26 letters, which numbers 26!, we must
count the number of outcomes when x and y are next to each other.
From the diagrams below, we see that there are 25 positions in which to
place the first of two letters.
1.
position
2.
position
x
1
y
2
_
3
_
4
.
.
.
.
.
.
_
x
y
_
.
.
1
2
3
4
.
.
_
25
_
26
.
_
_
.
25
26
…………………………………………………………………………
…………………………………………………………………………
25.
position
_
_
_
_
.
.
.
x
y
1
2
3
4
.
.
.
25
26
Then, we can permute x and y in 2! = 2 ways to obtain 2 times as many arrangements: N=50
For each of these 25*2! arrangements, the other 24 letters can be arranged in any order. Thus,
for each of the cases shown above, there are actually 24! arrangements of all the letters
which leave the x and y next to each other in the given fixed position.
Thus, there are 25 * 2! * 24! ways for the x and y to be next to each other and thus the
probability of this event is
p = (25 * 2! * 24!) / 26! = 50 / (26*25) = 1 / 13.
After reading this solution, can you find a simpler one?
Hint: the problem about rearrangements of n books on the shelf, m of which belong
to the same group and must be placed together.
Mathematica Program (Original version)* :
We shall now test this probability! To use the codes that follow, open a new
Mathematica file, then type and enter the commands. You can also highlight and copy
the lines from this page and then paste them into an open Mathematica page. Or click
here for a Mathematica file: AlphaBet_Modif.nb.
First enter the following special package.
<<DiscreteMath`Permutations`
Note: This package should only be entered once. However, if you Quit Mathematica
and re-launch the software later, then you will again have to enter this command.
We shall use the numbers 1 through 26 to represent the alphabet. For simplicity, the x
will be 1 and the y will be 2. Enter the following command to see a typical random
arrangement of the alphabet. Are the x and y next to each other?
RandomPermutation[26]
* Please find both the modification of this program and its original version in
Lect6_AlphaBet_Modif.nb
Creating a Sequence of Trials
If we re-arrange the numbers (letters) over and over again, then the 1 and 2 (x and y)
should be next to each other in about one out of thirteen times (since p = 1 / 13 from
before). Thus, we shall loop the command to iterate n times for any positive integer n of
your choice (it is perhaps best to take 500 <= n <= 1000). We will then find the
proportion (or relative frequency) of those arrangements having the two numbers next
to each other.
In the program, a[i] represents the ith arrangement. Since x = 1 and y = 2, they will be
next to each other if and only if two consecutive numbers in the arrangement sum to 3.
The jth term in the arrangement a[i] is given by the command a[i][[j]]. So we need to
sum a[i][[j]] + a[i][[j+1]] while j is less than 26, to see if this sum ever equals 3. If j
reaches 26 and the sum has never become 3, then that arrangement failed to have x and
y next to each other.
If the sum equals 3 at some point, the counter z[i] will become 1, meaning that the x
and y were next to each other in the ith arrangement. Otherwise z[i] is 0. Summing the
z[i] and dividing by n will give the proportion of "successes" which we can compare to
the real probability of 1/13.
In the program below, you must enter a value for n, the number of times
you want to arrange the letters. Then enter the remaining codes.
(* n=NumberOfIterations *)
Do[a[i]=RandomPermutation[26]; j=1; While[j<26 &&
a[i][[j]]+a[i][[j+1]]!=3, j=j+1]; If[j<26,z[i]=1,z[i]=0],{i,1,n}]
Proportion=N[Sum[z[i],{i,1,n}]/n]
RealProb=p=N[1/13]
The following command displaces the order number of the iteration and
its outcome: either 1 (for success) or 0 (for failure).
Table[{i,z[i]},{i,1,n}]
To see a particular arrangement, for instance the 14th, type and evaluate
a[14]. Pick a successful arrangement (z=1) and check if indeed the 0 and
1 are next to each other.
Exercises
1. If the 26 letters of the alphabet are randomly arranged, compute and
explain the probability that the x, y, and z are all next to each other.
2. The general problem is as follows: If m distinct objects are arranged in
random order, what is the probability that k pre-chosen objects will be
adjacent? Derive the solution. (You should check that the solution agrees
with that of Exercise 1 for n = 26 and m = 3.) Compare with the solution
AlphaBet_Modif_SolutionForMN.nb
3. Find the theoretical probability that m out of n randomly permuted
objects are positioned next to each other. Check you prediction using the
Solution of #2