Sign In     

February 2010: Problem and Solution

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 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.

« Back to Problems