February 2010: Problem
If a string s with n unique letters can be rearranged such that none
of the letters end up in their original positions, such a rearrangement is called
an proper orientation of s. Consider, for example, the string "DOG"
has the following proper orientations:
Now, let An denote the number of unique proper orientations of
a string s of length n. It should be fairly clear that A1=0
and A2=1; also, assume A0=1.
- 1. Determine A3 and A4.
- 2. Determine a recursive relationship in the sequence A.
February 2010: Solution
1. Suppose that a string of length n is represented by the characters a1a2...an.
Then, there are six permutations of a string of length 3: a1a2a3,
a1a3a2, a2a1a3,
a2a3a1, a3a1a2,
and a3a2a1. Verifying by inspection, we
can see that exactly two of these permutations are proper orientations of the original
string, so A3=2.
Using a similar method for A4, we find A4=9.
2. To determine a recursive relationship in A, consider a string of length
n: a1a2...an. In order to construct
all possible proper orientations of this string, first consider which of the last
n-1 numbers will occupy the first digit of the string; suppose this number
is the kth digit, or ak. Next, consider the numbers from
a1 to an, excluding ak: these
digits must be placed in the digits 2 through n, as the first digit has already
been taken up by ak.
If a1 ends up as the kth digit of the orientation, we can
see that there are n-2 remaining numbers that must be placed in the same
n-2 digits they were originally from. We need to ensure that none of the
original n-2 digits ends up in their original n-2 positions; but by
definition, this is An-2.
If a1, on theo ther hand, does not end up as the kth digit
of the orientation, consider all proper orientations of the numbers a2
through an, including ak, mapped onto
the 2nd through nth digits of the orientation; by definition, this can be
done An-1 ways. By replacing the number ak in
the final orientation with a1, we achieve an orientation of the
original n digits that satisfies the conditions of a proper orientation.
Thus, there are n-1 ways to determine which number fills the first digit;
An-2 ways from there if a1 fills the kth
digit, and An-1 otherwise. Summing this all up, we get An=(n-1)(An-1+An-2)
to describe the recursive relationship.