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:

• GDO
• OGD

Now, let A_n denote the number of unique proper orientations of a string s of length n. It should be fairly clear that A₁=0 and A₂=1; also, assume A₀=1.

• 1. Determine A₃ and A₄.
• 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 a₁a₂...a_n.

Then, there are six permutations of a string of length 3: a₁a₂a₃, a₁a₃a₂, a₂a₁a₃, a₂a₃a₁, a₃a₁a₂, and a₃a₂a₁. Verifying by inspection, we can see that exactly two of these permutations are proper orientations of the original string, so A₃=2.

Using a similar method for A₄, we find A₄=9.

2. To determine a recursive relationship in A, consider a string of length n: a₁a₂...a_n. 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 a_k. Next, consider the numbers from a₁ to a_n, excluding a_k: these digits must be placed in the digits 2 through n, as the first digit has already been taken up by a_k.

If a₁ 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 A_n-2.

If a₁, on theo ther hand, does not end up as the kth digit of the orientation, consider all proper orientations of the numbers a₂ through a_n, including a_k, mapped onto the 2nd through nth digits of the orientation; by definition, this can be done A_n-1 ways. By replacing the number a_k in the final orientation with a₁, 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; A_n-2 ways from there if a₁ fills the kth digit, and A_n-1 otherwise. Summing this all up, we get A_n=(n-1)(A_n-1+A_n-2) to describe the recursive relationship.