Good Sequences

Discrete Mathematics Level 5

For all \(n \in \mathbb{N},\) a sequence \((x_1, x_2, \cdots , x_n)\) of positive integers (not necessarily distinct) is called good if

  • for all \(k \geq 1,\) if \(k+1\) appears in the sequence, so does \(k\), and
  • the first occurrence of \(k\) happens before the last occurrence of \(k+1\) (i.e. if \(j\) is the smallest integer such that \(x_j=k\) and \(h\) is the largest integer such that \(x_h= k+1,\) then \(j<h\)).

Find the number of good sequences of length \(5\).

Details and assumptions

  • This problem is not original.
  • The five integers need not be distinct.
  • For example, \((1, 2, 3, 4,5)\) and \( (1,2, 4, 3, 4) \) are two good sequences of length \(5\).

Problem Loading...

Note Loading...

Set Loading...