cp's OEIS Frontend

A186735 Number of permutations of [n] with no ascending runs of length 1 or 2.

%I A186735 #18 Sep 03 2021 09:02:09
%S A186735 1,0,0,1,1,1,20,69,180,1930,12611,61051,566129,5179750,38348469,
%T A186735 376547340,4169246332,41559058969,465750294781,5905176350849,
%U A186735 72848728572828,946103621115633,13501160406995728,195518567272213262,2918439778172724571,46559546190633191495
%N A186735 Number of permutations of [n] with no ascending runs of length 1 or 2.
%H A186735 Alois P. Heinz, <a href="/A186735/b186735.txt">Table of n, a(n) for n = 0..150</a>
%F A186735 a(n) = A000142(n) - A228614(n) - A185652(n).
%e A186735 a(0) = 1: the empty permutation.
%e A186735 a(3) = 1: 123.
%e A186735 a(4) = 1: 1234.
%e A186735 a(5) = 1: 12345.
%e A186735 a(6) = 20: 123456, 124356, 125346, 126345, 134256, 135246, 136245, 145236, 146235, 156234, 234156, 235146, 236145, 245136, 246135, 256134, 345126, 346125, 356124, 456123.
%t A186735 A[n_, k_] := A[n, k] = Module[{b}, b[u_, o_, t_] := b[u, o, t] =
%t A186735      If[t + o <= k, (u + o)!,
%t A186735      Sum[b[u + i - 1, o - i, Min[k, t] + 1], {i, 1, o}] +
%t A186735      If[t <= k, u*(u + o - 1)!,
%t A186735      Sum[b[u - i, o + i - 1, 1], {i, 1, u}]]];
%t A186735   Sum[b[j - 1, n - j, 1], {j, 1, n}]];
%t A186735 a[n_] := n! - A[n, 2];
%t A186735 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Sep 03 2021, after _Alois P. Heinz_ in A064315 *)
%Y A186735 Cf. A064315, A097899.
%Y A186735 Cf. A000142, A185652, A228614.
%K A186735 nonn
%O A186735 0,7
%A A186735 _Alois P. Heinz_, Aug 29 2013