A228614 Number of permutations of [n] having a shortest ascending run of length one.

0, 1, 1, 5, 18, 101, 611, 4452, 36287, 333395, 3382758, 37688597, 456839351, 5989023768, 84421235807, 1273482972215, 20470309460322, 349326503482301, 6307682420743595, 120157254334350828, 2408293016265606623, 50663563124372167787, 1116225038923857181614

Offset

0,4

Links

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

Formula

a(n) = A000142(n) - A097899(n).

E.g.f.: 1/(1-x) - sqrt(3)*exp(-x/2) / (2*cos(sqrt(3)*x/2+Pi/6)).

Example

a(1) = 1: 1.
a(2) = 1: 21.
a(3) = 5: 132, 213, 231, 312, 321.
a(4) = 18: 1243, 1342, 1432, 2134, 2143, 2341, 2431, 3124, 3142, 3214, 3241, 3421, 4123, 4132, 4213, 4231, 4312, 4321.

Maple

g:= proc(u, o) option remember; `if`(u+o<2, u,
      add(b(u-i, o+i-1), i=1..u) +add(g(u+i-1, o-i), i=1..o))
    end:
b:= proc(u, o) option remember; `if`(u+o<2, 1-o,
      u*(u+o-1)! +add(g(u+i-1, o-i), i=1..o))
    end:
a:= n-> add(b(j-1, n-j), j=1..n):
seq(a(n), n=0..25);

Mathematica

g[u_, o_] := g[u, o] = If[u + o < 2, u,
     Sum[b[u - i, o + i - 1], {i, u}] +
     Sum[g[u + i - 1, o - i], {i, o}]];
b[u_, o_] := b[u, o] = If[u + o < 2, 1 - o, u*(u + o - 1)! +
     Sum[g[u + i - 1, o - i], {i, o}]];
a[n_] := Sum[b[j - 1, n - j], {j, n}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 30 2021, after Alois P. Heinz *)

Crossrefs

Column k=1 of A064315.

Sequence in context: A188329 A165962 A127756 * A158455 A009442 A332784

Adjacent sequences: A228611 A228612 A228613 * A228615 A228616 A228617

Keyword

nonn

Author

Alois P. Heinz, Aug 27 2013

Status

approved