There is a sequence of n numbers as 1,2,3,...,n How many combinations of the connections between two numbers in the sequence without overlaping?
Take a sequence 1,2,3,4,5,6,7,8,9,10 for example:
combination 1: (1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10) is allowable
combination 2: (1,2),(3,4),(5,6),(7,8),(9,10) is allowable
combination 3: (1,3),(3,5),(6,8) is allowable
combination 4: (2,6),(7,8) is allowable
combination 5: (2,5),(4,6) is unallowable, because the overlaping exsits
As Gerry Myerson comments, there are $F_{2n-1}$ such combinations for $\{1,\dots,n\}$. One way to see this is via a bijection with the Morse code sequences of length $2n-2$ that looks like this:
$$ \begin{align*} &{\cdot}\;{\cdot}\;{\cdot}\;{\cdot}\;{\cdot}\;{\cdot} &&\emptyset\\ &{\cdot}\;{\cdot}\;{\cdot}\;{\cdot}\;- &&(34)\\ &{\cdot}\;{\cdot}\;{\cdot}\;-{\cdot} &&(24)\\ &{\cdot}\;{\cdot}\;-{\cdot}\;{\cdot} &&(23)\\ &{\cdot}-\;{\cdot}\;{\cdot}\;{\cdot} &&(13)\\ &-\;{\cdot}\;{\cdot}\;{\cdot}\;{\cdot} &&(12)\\ &{\cdot}\;{\cdot}\;-\;- &&(23)(34)\\ &{\cdot}\;-\;{\cdot}\;- &&(13)(34)\\ &{\cdot}\;-\;-\;{\cdot} &&(14)\\ &-\;{\cdot}\;{\cdot}\;- &&(12)(34)\\ &-\;{\cdot}-{\cdot} &&(12)(24)\\ &-\;-\;{\cdot}\;{\cdot} &&(12)(23)\\ &-\;-\;- &&(12)(23)(34) \end{align*} $$ There are $n-1$ pairs of dots, representing the $n-1$ adjacent numbers $(12)$, $(23)$, ..., $(n\!-\!1\;n)$ in order. For example, $(12)(23)$ is represented by $--\cdot\;\cdot$, since the first two pairs are activated. Lines joining two pairs combine them, so $(13)$ is represented by $\cdot-\cdot\cdot\cdot$ since it joins $(12)$ with $(23)$.
It is then easily seen that the Morse code sequences of length $n$ (where a dot has length $1$ and a dash has length $2$) are counted by the Fibonacci numbers $F_{n+1}$, since every length $n$ Morse code sequence is either a dot followed by a length $n-1$ Morse code sequence, or a dash followed by a length $n-2$ Morse code sequence.
