%I #19 Jul 10 2017 15:03:14
%S 1,1,1,2,3,4,19,78,217,496,3961,25442,105963,349504,3908059,34227438,
%T 190065457,819786496,11785687921,130746521282,907546301523,
%U 4835447317504,84965187064099,1141012634368398,9504085749177097,60283564499562496,1251854782837499881
%N The number of 4-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).
%H Alois P. Heinz, <a href="/A250259/b250259.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 [math.CO], 2009, page 17.
%p onestep := proc(n::integer,ups::integer,downs::integer,uplen::integer)
%p local thisstep,left,doup,tak,ret ;
%p option remember;
%p left := ups+downs ;
%p if left = 0 then
%p return 1;
%p end if;
%p thisstep := n-left+1 ;
%p if modp(thisstep-2,uplen+1) = 0 then
%p doup := false;
%p else
%p doup := true;
%p end if;
%p if doup then
%p ret := 0 ;
%p for tak from 1 to ups do
%p ret := ret+procname(n,ups-tak,downs+tak-1,uplen) ;
%p end do:
%p return ret ;
%p else
%p ret := 0 ;
%p for tak from 1 to downs do
%p ret := ret+procname(n,ups+tak-1,downs-tak,uplen) ;
%p end do:
%p return ret ;
%p end if;
%p end proc:
%p downupP := proc(n::integer,uplen::integer)
%p local ret,tak;
%p if n = 0 then
%p return 1;
%p end if;
%p ret := 0 ;
%p for tak from 1 to n do
%p ret := ret+onestep(n,n-tak,tak-1,uplen) ;
%p end do:
%p return ret ;
%p end proc:
%p A250259 :=proc(n)
%p downupP(n,3) ;
%p end proc:
%p seq(A250259(n),n=0..20) ; # _R. J. Mathar_, Nov 15 2014
%p # second Maple program:
%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, 4)), j=1..u),
%p add(b(u+j-1, o-j, irem(t+1, 4)), j=1..o)))
%p end:
%p a:= n-> b(0, n, 0):
%p seq(a(n), n=0..35); # _Alois P. Heinz_, Nov 15 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, 4]], {j, 1, u}], Sum[b[u + j - 1, o - j, Mod[t + 1, 4]], {j, 1, o}]]]; a[n_] := b[0, n, 0]; Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Jul 10 2017, after _Alois P. Heinz_ *)
%Y Cf. A249402 (3-alternating), A065619 (2-alternating), A250260 (5-alternating).
%Y Column k=4 of A250261.
%K nonn
%O 0,4
%A _R. J. Mathar_, Nov 15 2014