cp's OEIS Frontend

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

%I A249402 #22 Mar 24 2017 00:47:57
%S A249402 1,1,1,2,3,11,40,99,589,3194,11259,92159,666160,3052323,31799041,
%T A249402 287316122,1620265923,20497038755,222237912664,1488257158851,
%U A249402 22149498351205,280180369563194,2172534146099019,37183508549366519,537546603651987424,4736552519729393091
%N A249402 The number of 3-alternating permutations of [n].
%C A249402 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 A249402 Alois P. Heinz, <a href="/A249402/b249402.txt">Table of n, a(n) for n = 0..500</a>
%H A249402 R. P. Stanley, <a href="http://arxiv.org/abs/0912.4240">A survey of alternating permutations</a>, arXiv:0912.4240, page 17.
%e A249402 The a(4)=3 3-alternating permutations of [4] are: [2 1 3 4 ] [3 1 2 4 ] and [4 1 2 3 ].
%e A249402 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 A249402 b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p A249402      `if`(t=1, add(b(u-j, o+j-1, irem(t+1, 3)), j=1..u),
%p A249402                add(b(u+j-1, o-j, irem(t+1, 3)), j=1..o)))
%p A249402     end:
%p A249402 a:= n-> b(0, n, 0):
%p A249402 seq(a(n), n=0..35);  # _Alois P. Heinz_, Oct 27 2014
%t A249402 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 A249402 Cf. A065619 (2-alternating).
%Y A249402 Cf. A178963, A249583 (alternative definitions of 3-alternating permutations).
%Y A249402 Column k=3 of A250261.
%K A249402 nonn
%O A249402 0,4
%A A249402 _R. J. Mathar_, Oct 27 2014
%E A249402 a(16)-a(25) from _Alois P. Heinz_, Oct 27 2014