# Permutation Problem

There are n children that are randomly seated. In how many ways will the oldest child always be seated to the right of the youngest child? (It does not have to be directly to the right).

-

HINT: In half of the possible seatings the oldest child is seated to the right of the youngest, and in the other half the oldest child is seated to the left of the youngest. Why? And how many seatings are there altogether?

If we consider only those arrangements in which the youngest child is not in the leftmost position, how many are there with the oldest child to the right of the youngest?

An equivalent question that’s a little easier to talk about:

Of those permutations of $[n]=\{1,\dots,n\}$ whose first element is not $1$, how many have $n$ to the right of $1$?

For each $k\in[n]$ there are $(n-1)!$ permutations of $[n]$ with $k$ in the first position. We’re given that $k\ne 1$. If $1<k<n$, half of these permutations have $1$ to the left of $n$, and half have $1$ to the right of $n$. If $k=n$, clearly $n$ cannot be to the right of $1$. Thus, there are $$\frac{(n-2)(n-1)!}2=\frac{n!-2(n-1)!}2=\frac{n!}2-(n-1)!\tag{1}$$

permutations that do not have $1$ in the first position and do have $n$ to the right of $1$.

Note that the final expression in $(1)$ implicitly shows another way of arriving at the result. There are altogether $\frac{n!}2$ permutations of $[n]$ that have $n$ to the right of $1$, so we need only remove those that have $1$ in the first position. Every permutation with $1$ in the first position has $n$ to the right of $1$, so we must remove all of them. Since there are $(n-1)!$ such permutations, we must subtract $(n-1)!$.

-
There's n! total seatings. That means n!/2 is the answer? –  user58570 Jan 17 '13 at 7:10
@user58570: That’s right. If O is the oldest and Y the youngest child, every seating with O to the left of Y can be turned into one with O to the right of Y by interchanging O and Y, and vice versa, so they must be split half and half. –  Brian M. Scott Jan 17 '13 at 7:12
What if I add this case to the question: The youngest child is never on the left-most position. –  user58570 Jan 17 '13 at 7:31
@user58570: I’m not sure which of two questions you’re asking. (1) How many arrangements are there with the youngest child not in the leftmost position? (2) If we consider only those arrangements in which the youngest child is not in the leftmost position, how many are there with the oldest child to the right of the youngest? –  Brian M. Scott Jan 17 '13 at 7:50
Yes I meant (2) –  user58570 Jan 17 '13 at 18:02