Let be a positive integer. A sequence of positive integers (not necessarily distinct) is called full if it satisfies the following condition: for each positive integer , if the number appears in the sequence then so does the number , and moreover the first occurrence of comes before the last occurrence of . For each , how many full sequences are there ?
Solution
To solve this problem, we need to determine how many sequences of length consisting of positive integers are considered "full" according to the defined condition. The condition implies a hierarchical appearance of integers in the sequence, such that if an integer appears, then must also appear before the last occurrence of .
We can approach the problem inductively:
1. Base Case: For , the only sequence is , which trivially satisfies the condition as there are no integers .
2. Inductive Step: Assume that for some , all sequences of positive integers of length are full. Now consider sequences of length .
To form a full sequence of length , consider placing the number in the sequence. According to the condition, for any occurrence of , an must appear before the last occurrence of . The rest of the sequence before placing can be any full sequence of length .
We can insert at any position in the sequence of length , resulting in permutations of sequences.
Thus, each choice of ordering for the integers from through is independent in a full sequence, therefore we have full sequences for any positive integer .
Hence, the number of full sequences of length is:
\