About Warm-ups Problems News

Problem 8

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

We say permutation `\sigma=\sigma_1\sigma_2\sigma_3\cdots\sigma_n` is an up-up-down permutation if `\sigma_1<\sigma_2<\sigma_3>\sigma_4<\sigma_5<\sigma_6>\sigma_7<\sigma_8<\sigma_9>\cdots`. For example, `\sigma=(1\ 5\ 6\ 2\ 4\ 7\ 3)` is an up-up-down permutation of length `7`.

We say permutation `\sigma=\sigma_1\sigma_2\sigma_3\cdots\sigma_n` is a derangement if `\sigma_k\ne k` for any `1\leq k\leq n`.

`a(n)` is the number of up-up-down derangements of length `n`. For example, `\sigma=(2\ 5\ 6\ 1\ 4\ 7\ 3)` is an up-up-down derangement of length `7`. Number of up-down derangements is counted by sequence A129815 on OEIS.

Find `a(n)`.




Back to top