cp's OEIS Frontend

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

%I A228614 #19 Aug 30 2021 03:11:05
%S A228614 0,1,1,5,18,101,611,4452,36287,333395,3382758,37688597,456839351,
%T A228614 5989023768,84421235807,1273482972215,20470309460322,349326503482301,
%U A228614 6307682420743595,120157254334350828,2408293016265606623,50663563124372167787,1116225038923857181614
%N A228614 Number of permutations of [n] having a shortest ascending run of length one.
%H A228614 Alois P. Heinz, <a href="/A228614/b228614.txt">Table of n, a(n) for n = 0..200</a>
%F A228614 a(n) = A000142(n) - A097899(n).
%F A228614 E.g.f.: 1/(1-x) - sqrt(3)*exp(-x/2) / (2*cos(sqrt(3)*x/2+Pi/6)).
%e A228614 a(1) = 1: 1.
%e A228614 a(2) = 1: 21.
%e A228614 a(3) = 5: 132, 213, 231, 312, 321.
%e A228614 a(4) = 18: 1243, 1342, 1432, 2134, 2143, 2341, 2431, 3124, 3142, 3214, 3241, 3421, 4123, 4132, 4213, 4231, 4312, 4321.
%p A228614 g:= proc(u, o) option remember; `if`(u+o<2, u,
%p A228614       add(b(u-i, o+i-1), i=1..u) +add(g(u+i-1, o-i), i=1..o))
%p A228614     end:
%p A228614 b:= proc(u, o) option remember; `if`(u+o<2, 1-o,
%p A228614       u*(u+o-1)! +add(g(u+i-1, o-i), i=1..o))
%p A228614     end:
%p A228614 a:= n-> add(b(j-1, n-j), j=1..n):
%p A228614 seq(a(n), n=0..25);
%t A228614 g[u_, o_] := g[u, o] = If[u + o < 2, u,
%t A228614      Sum[b[u - i, o + i - 1], {i, u}] +
%t A228614      Sum[g[u + i - 1, o - i], {i, o}]];
%t A228614 b[u_, o_] := b[u, o] = If[u + o < 2, 1 - o, u*(u + o - 1)! +
%t A228614      Sum[g[u + i - 1, o - i], {i, o}]];
%t A228614 a[n_] := Sum[b[j - 1, n - j], {j, n}];
%t A228614 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Aug 30 2021, after _Alois P. Heinz_ *)
%Y A228614 Column k=1 of A064315.
%K A228614 nonn
%O A228614 0,4
%A A228614 _Alois P. Heinz_, Aug 27 2013