A231386 Number of permutations of [n] with exactly one occurrence of one of the consecutive step patterns UUD, UDU, DUU (U=up, D=down).

0, 0, 0, 0, 11, 52, 233, 1344, 8197, 49846, 351946, 2799536, 22764021, 200196218, 1947350444, 19753229932, 210793513246, 2425636703848, 29307938173409, 369141523106550, 4920501544208343, 68771635812423192, 998694091849893095, 15169308298544690802

Offset

0,5

Links

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

A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

S. Kitaev and T. Mansour, On multi-avoidance of generalized patterns

Formula

a(n) ~ c * d^n * n! * n, where d = 0.63140578989563018836..., c = 1.015673... . - Vaclav Kotesovec, Aug 28 2014

Example

a(4) = 11: 1243, 1342, 2341 (=UUD), 1324, 1423, 2314, 2413, 3412 (=UDU), 2134, 3124, 4123 (=DUU).
a(5) = 52: 12354, 12453, 12543, ..., 53124, 53412, 54123.
a(6) = 233: 123465, 123564, 123654, ..., 653124, 653412, 654123.
a(7) = 1344: 1234576, 1234675, 1234765, ..., 7653124, 7653412, 7654123.

Maple

b:= proc(u, o, t) option remember; `if`(t=13, 0, `if`(u+o=0,
      `if`(t>6, 1, 0), add(b(u+j-1, o-j,
          [2, 3, 3, 6, 12, 9, 8, 9, 9, 12, 13, 13][t]), j=1..o)+
      add(b(u-j, o+j-1,
          [4, 5, 11, 4, 4, 5, 10, 11, 13, 10, 10, 11][t]), j=1..u)))
    end:
a:= n-> add(b(j-1, n-j, 1), j=1..n):
seq(a(n), n=0..30);

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[t==13, 0, If[u + o == 0, If[t > 6, 1, 0],
  Sum[b[u+j-1, o-j,
    {2, 3, 3, 6, 12, 9, 8, 9, 9, 12, 13, 13}[[t]]], {j, 1, o}] +
  Sum[b[u-j, o+j-1,
    {4, 5, 11, 4, 4, 5, 10, 11, 13, 10, 10, 11}[[t]]], {j, 1, u}]]];
a[n_] := Sum[b[j - 1, n - j, 1], {j, 1, n}];
a /@ Range[0, 30] (* Jean-François Alcover, Dec 22 2020, after Alois P. Heinz *)

Crossrefs

Column k=1 of A231384.

Sequence in context: A317021 A199895 A304280 * A191099 A325727 A370502

Adjacent sequences: A231383 A231384 A231385 * A231387 A231388 A231389

Keyword

nonn

Author

Alois P. Heinz, Nov 08 2013

Status

approved