Sequence counting using bijection

Question

How many sequences a1, a2, . . . , a2009 are there such that each of the numbers 1, 2, . . . , 2009 occurs in the sequence, and i ∈ {a1, a2,..., ai} for all i ≥ 2? I am not able to understand if 'i' is greater or equal to 2 then we have 2008 integer and the set of 2008 integer will create 2^2n-1 sequence but I am not able to biject and count the sequence ai

Answer 1

$2$ needs to be one of $a_1,a_2$. Let $k$ be the other one. We can assume $k=a_1, 2=a_2$ then multiply by $2$. Assuming $k$ is reasonably large, we need $a_3=3,$ then $a_4=4$ and on to $a_{k-1}=k-1$. Now $a_k$ can be $1$ or it can be anything greater than $k$. If it is $1$ all the rest have $a_i=i$. If it is $m$ we have to have $a_i=1$ up to $m-1$ and we have choices for $a_m$ just like we had for $k$.

If you follow this construction, we can make a bijection between the acceptable sequences and the subsets of $\{2,3,4,5,\ldots 2009\}$ If $2$ is present we have $a_1=2$ and otherwise we have $a_2=2$. The other of $a_1,a_2$ is the lowest element of the subset. After that, each element in the subset is in the position of the next lower element. Finally $1$ is in the position of the highest element. There are $2^{2008}$ acceptable sequences.

Added: as an example, let us work with the numbers up to $10$. The subset $\{3,6,8\}$ would correspond to the sequence $(3,2,6,4,5,8,8,1,9,10)$. The lowest memeber of the subset goes in position $1$ or $2$, each other one goes into the position of the next lower number, and $1$ goes in the position of the highest.