A000255

This is the sequence of the number of permutations of [1,...,n+1] which have no substring [k,k+1]. To bring an example: for [A, B, C, D] the permutation [A, C, D, B] has a subbstring [C, D], while [C, A, D, B] has no substring.

Example

A set with 4 different elements [A, B, C, D] has 24 permutations:

A B C D	B A C D	C A B D	D A B C
A B D C	B A D C	C A D B	D A C B
A C B D	B C A D	C B A D	D B A C
A C D B	B C D A	C B D A	D B C A
A D B C	B D A C	C D A B	D C A B
A D C B	B D C A	C D B A	D C B A

All permutations which contain one of the following substrings: [A B], [B C] or [C D], will be removed:

A B C D	B A C D	C A B D	D A B C
A B D C	B A D C	C A D B	D A C B
A C B D	B C A D	C B A D	D B A C
A C D B	B C D A	C B D A	D B C A
A D B C	B D A C	C D A B	D C A B
A D C B	B D C A	C D B A	D C B A

There remain 11 permutations:

A C B D

A D C B

B D A C

B A D C

B D C A

C A D B

C B A D

C B D A

D A C B

D B A C

D C B A

Formula

$a_{n}=n\cdot a_{n-1}+(n-1)\cdot a_{n-2}\,$ with $\scriptstyle a_{0}\,=\,1,\,a_{1}\,=\,1\,$

Other formulae

It is possible to calculate over the |Number of derangements:

$\scriptstyle a_{n}\,=\,!(n+1)+!n$

$\scriptstyle a_{n}\,=\,!(n+2)/(n+1)$