A250259 The number of 4-alternating permutations of [n].

1, 1, 1, 2, 3, 4, 19, 78, 217, 496, 3961, 25442, 105963, 349504, 3908059, 34227438, 190065457, 819786496, 11785687921, 130746521282, 907546301523, 4835447317504, 84965187064099, 1141012634368398, 9504085749177097, 60283564499562496, 1251854782837499881

Offset: 0

Author

R. J. Mathar, Nov 15 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).

Links

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

Crossrefs

Cf. A249402 (3-alternating), A065619 (2-alternating), A250260 (5-alternating).

Column k=4 of A250261.

Programs

Maple

onestep := proc(n::integer,ups::integer,downs::integer,uplen::integer)
    local thisstep,left,doup,tak,ret ;
    option remember;
    left := ups+downs ;
    if left = 0 then
        return 1;
    end if;
    thisstep := n-left+1 ;
    if modp(thisstep-2,uplen+1) = 0 then
        doup := false;
    else
        doup := true;
    end if;
    if doup then
        ret := 0 ;
        for tak from 1 to ups do
            ret := ret+procname(n,ups-tak,downs+tak-1,uplen) ;
        end do:
        return ret ;
    else
        ret := 0 ;
        for tak from 1 to downs do
            ret := ret+procname(n,ups+tak-1,downs-tak,uplen) ;
        end do:
        return ret ;
    end if;
end proc:
downupP := proc(n::integer,uplen::integer)
    local ret,tak;
    if n = 0 then
        return 1;
    end if;
    ret := 0 ;
    for tak from 1 to n do
        ret := ret+onestep(n,n-tak,tak-1,uplen) ;
    end do:
    return ret ;
end proc:
A250259 :=proc(n)
    downupP(n,3) ;
end proc:
seq(A250259(n),n=0..20) ; # R. J. Mathar, Nov 15 2014
# second Maple program:
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, 4)), j=1..u),
               add(b(u+j-1, o-j, irem(t+1, 4)), j=1..o)))
    end:
a:= n-> b(0, n, 0):
seq(a(n), n=0..35);  # Alois P. Heinz, Nov 15 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, 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 *)