A245377 Number of 2-alternating permutations of 1,2,...,n, that is, a(n) is the number of down/up permutations (A000111) of 1,2,...,n such that any two consecutive terms differ by at least two.

1, 1, 0, 0, 1, 4, 17, 80, 422, 2480, 16095, 114432, 884969, 7398464, 66502048, 639653632, 6556170841, 71340409600, 821408397105, 9977630263296, 127518757153174, 1710576547456000, 24030971882538671, 352843606806499328

Offset: 0

Author

Richard Stanley, Jul 19 2014

Keywords

• nonn
• more

Examples

			For n=5 there are the four permutations 31425, 31524, 52413, 42513.
		

Crossrefs

Cf. A002464.

Programs

Maple

b:= proc(n, s, t) option remember; `if`(s={}, 1, add(
     `if`(t*(n-j)>=2, b(j, s minus{j}, -t), 0), j=s))
    end:
a:= n->`if`(n=0, 1, add(b(j, {$1..j-1, $j+1..n}, 1), j=1..n)):
seq(a(n), n=0..16);  # Alois P. Heinz, Oct 27 2014

Mathematica

b[n_, s_, t_] := b[n, s, t] = If[s == {}, 1, Sum[If[t*(n - j) >= 2, b[j, s ~Complement~ {j}, -t], 0], {j, s}]]; a[n_] := a[n] = If[n == 0, 1, Sum[b[j, DeleteCases[Range[n], j], 1], {j, 1, n}]]; Table[Print[a[n]]; a[n], {n, 0, 16}] (* Jean-François Alcover, Oct 24 2016, after Alois P. Heinz *)

Extensions

a(11)-a(15) from R. J. Mathar, Oct 27 2014

a(16)-a(21) from Alois P. Heinz, Oct 27 2014

a(22) from Alois P. Heinz, Feb 18 2024

a(23) from Max Alekseyev, Feb 19 2024