Tessellate S.T.E.M.S. (2019) - Mathematics - Category A (School) - Set 4 - Objective Problem 2

Given a positive integer $n$ , a sequence of $n$ (not necessarily distinct) positive integers is called "full" if it satisfies the property that: for each positive integer $k \geq 2$ if the number $k$ appears in the sequence then so does $k - 1$ such that the first occurrence of $k -1$ comes before the last occurrence of $k$ . For each $n \in \mathbb{N}$ how many full sequences are there?