Maths Olympiad Prep

Library / /94 of 144

Combinatorics Difficulty 8.4 Shortlist Find the answer

Let nn be a positive integer. A sequence of nn positive integers (not necessarily distinct) is called full if it satisfies the following condition: for each positive integer k2k\geq2, if the number kk appears in the sequence then so does the number k1k-1, and moreover the first occurrence of k1k-1 comes before the last occurrence of kk. For each nn, how many full sequences are there ?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to determine how many sequences of length n n 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 k k appears, then k1 k-1 must also appear before the last occurrence of k k .

We can approach the problem inductively:

1. Base Case: For n=1 n = 1 , the only sequence is [1][1], which trivially satisfies the condition as there are no integers k2 k \geq 2 .

2. Inductive Step: Assume that for some n n , all sequences of positive integers of length n n are full. Now consider sequences of length n+1 n+1 .

To form a full sequence of length n+1 n+1 , consider placing the number n+1 n+1 in the sequence. According to the condition, for any occurrence of n+1 n+1 , an n n must appear before the last occurrence of n+1 n+1 . The rest of the sequence before placing n+1 n+1 can be any full sequence of length n n .

We can insert n+1 n+1 at any position in the sequence of length n n , resulting in (n+1)! (n+1)! permutations of sequences.

Thus, each choice of ordering for the integers from 1 1 through n n is independent in a full sequence, therefore we have n! n! full sequences for any positive integer n n .

Hence, the number of full sequences of length n n is:
n! \boxed{n!}
\

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.