About Warm-ups Problems News

Exercise D

Posted 02/21/2015
Refresh the webpage if formulas are not shown correctly.
--------------------------
Previous    Next
--------------------------

We say a permutation `\sigma=\sigma_1\sigma_2\cdots\sigma_n` of length of `n` avoids `123` consecutively if there does not exist integer `j` such that `\sigma_j \lt \sigma_{j+1} \lt \sigma_{j+2}`.

`a(n)` is the number of permutations of length `n` avoiding `123` consecutively.

For example, `a(3)=5` because `123` is excluded and `a(4)=19` because `1234`,`1243`,`1342`,`2341` and `4123` contain `123` consecutively.

Find `a(n)`.