A296054 Number of permutations of [n] with an equal number of occurrences of the consecutive step patterns 010 and 101, where 1=up and 0=down.

1, 1, 2, 6, 14, 84, 344, 2714, 15850, 158664, 1254536, 15066332, 151035364, 2091499222, 25438986270, 398610118170, 5712650790562, 99963273184972, 1649446030193764, 31890910904182000, 594935710367215600, 12604160312187654888, 262094375885982582488

Offset

0,3

Comments

a(n) * sqrt(n) / n! tends to 1.064409... - Vaclav Kotesovec, Aug 30 2021

Links

Alois P. Heinz, Table of n, a(n) for n = 0..300

Example

a(4) = 14: 1234, 1243, 1342, 1432, 2134, 2341, 2431, 3124, 3214, 3421, 4123, 4213, 4312, 4321 with step patterns 111, 110, 110, 100, 011, 110, 100, 011, 001, 100, 011, 001, 001, 000, respectively.

Maple

b:= proc(u, o, t, h, c) option remember; `if`(2*abs(c)-1>u+o, 0,
            `if`(u+o=0, 1, `if`(t=0, add(b(u-j, j-1, 1$2, 0), j=1..u),
       add(b(u-j, o+j-1, [1, 3, 1][t], 2, c+`if`(h=3, 1, 0)), j=1..u)+
       add(b(u+j-1, o-j, 2, [1, 3, 1][h], c-`if`(t=3, 1, 0)), j=1..o))))
    end:
a:= n-> b(n, 0$4):
seq(a(n), n=0..30);

Mathematica

b[u_, o_, t_, h_, c_] := b[u, o, t, h, c] = If[2 Abs[c] - 1 > u+o, 0,
     If[u+o == 0, 1, If[t == 0, Sum[b[u-j, j-1, 1, 1, 0], {j, u}],
     Sum[b[u-j, o+j-1, {1, 3, 1}[[t]], 2, c+If[h == 3, 1, 0]], {j, u}]+
     Sum[b[u+j-1, o-j, 2, {1, 3, 1}[[h]], c-If[t == 3, 1, 0]], {j, o}]]]];
a[n_] := b[n, 0, 0, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Aug 30 2021, after Alois P. Heinz *)

Crossrefs

Cf. A295974, A295987.

Sequence in context: A072171 A371008 A308568 * A333121 A131518 A222201

Adjacent sequences: A296051 A296052 A296053 * A296055 A296056 A296057

Keyword

nonn

Author

Alois P. Heinz, Dec 03 2017

Status

approved