A249402 The number of 3-alternating permutations of [n].

1, 1, 1, 2, 3, 11, 40, 99, 589, 3194, 11259, 92159, 666160, 3052323, 31799041, 287316122, 1620265923, 20497038755, 222237912664, 1488257158851, 22149498351205, 280180369563194, 2172534146099019, 37183508549366519, 537546603651987424, 4736552519729393091

Offset: 0

Author

R. J. Mathar, Oct 27 2014

Keywords

• nonn

Comments

A sequence a(1),a(2),... is called k-alternating if a(i) > a(i+1) iff i=1 (mod k). a(n) gives the number of 3-alternating permutations of [n].

Examples

			The a(4)=3 3-alternating permutations of [4] are: [2 1 3 4 ] [3 1 2 4 ] and [4 1 2 3 ].
The a(5)=11 3-alternating permutations of [5] are: [2 1 3 5 4 ] [2 1 4 5 3 ] [3 1 2 5 4 ] [3 1 4 5 2 ] [3 2 4 5 1 ] [4 1 2 5 3 ] [4 1 3 5 2 ] [4 2 3 5 1 ] [5 1 2 4 3 ] [5 1 3 4 2 ] and [5 2 3 4 1 ].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..500
• R. P. Stanley, A survey of alternating permutations, arXiv:0912.4240, page 17.

Crossrefs

Cf. A065619 (2-alternating).

Cf. A178963, A249583 (alternative definitions of 3-alternating permutations).

Column k=3 of A250261.

Programs

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
     `if`(t=1, add(b(u-j, o+j-1, irem(t+1, 3)), j=1..u),
               add(b(u+j-1, o-j, irem(t+1, 3)), j=1..o)))
    end:
a:= n-> b(0, n, 0):
seq(a(n), n=0..35);  # Alois P. Heinz, Oct 27 2014

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, If[t == 1, Sum[b[u-j, o+j-1, Mod[t+1, 3]], {j, 1, u}], Sum[b[u+j-1, o-j, Mod[t+1, 3]], {j, 1, o}]]]; a[n_] := b[0, n, 0]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 22 2015, after Alois P. Heinz *)

Extensions

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