A249402 - OEIS

%I #22 Mar 24 2017 00:47:57

%S 1,1,1,2,3,11,40,99,589,3194,11259,92159,666160,3052323,31799041,

%T 287316122,1620265923,20497038755,222237912664,1488257158851,

%U 22149498351205,280180369563194,2172534146099019,37183508549366519,537546603651987424,4736552519729393091

%N The number of 3-alternating permutations of [n].

%C 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].

%H Alois P. Heinz, <a href="/A249402/b249402.txt">Table of n, a(n) for n = 0..500</a>

%H R. P. Stanley, <a href="http://arxiv.org/abs/0912.4240">A survey of alternating permutations</a>, arXiv:0912.4240, page 17.

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

%e 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 ].

%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1,

%p      `if`(t=1, add(b(u-j, o+j-1, irem(t+1, 3)), j=1..u),

%p                add(b(u+j-1, o-j, irem(t+1, 3)), j=1..o)))

%p     end:

%p a:= n-> b(0, n, 0):

%p seq(a(n), n=0..35);  # _Alois P. Heinz_, Oct 27 2014

%t 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_ *)

%Y Cf. A065619 (2-alternating).

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

%Y Column k=3 of A250261.

%K nonn

%O 0,4

%A _R. J. Mathar_, Oct 27 2014

%E a(16)-a(25) from _Alois P. Heinz_, Oct 27 2014