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

Author

Alois P. Heinz, Aug 27 2013

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Column k=1 of A064315.

Programs

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 *)

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)).