Prepared sequences

Here's an alternative (better) argument that the number of prepared sequences of length n is equal to n!, based on some ideas in Ilya's and Emily's papers.

Let p_n denote the number of prepared sequences of length n. Each such sequence arises from a prepared sequence of length (n-1) in one of two, mutually exclusive ways:

- By inserting a copy of the largest element to the left of the leftmost occurrence in the sequence of length (n-1)
- By inserting a new largest element (i.e. one that's larger than the previous largest element) anywhere to the right of the leftmost occurrence of the previous largest element.

Thus a sequence of length (n-1) generates n distinct sequences of length n (and every sequence of length n is generated in exactly one way), and so p_n = n p_{n-1}.

Since p_1 = 1, p_n = n! by induction.