A250259 - OEIS

%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