A186735 - OEIS

%I #18 Sep 03 2021 09:02:09

%S 1,0,0,1,1,1,20,69,180,1930,12611,61051,566129,5179750,38348469,

%T 376547340,4169246332,41559058969,465750294781,5905176350849,

%U 72848728572828,946103621115633,13501160406995728,195518567272213262,2918439778172724571,46559546190633191495

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

%H Alois P. Heinz, <a href="/A186735/b186735.txt">Table of n, a(n) for n = 0..150</a>

%F a(n) = A000142(n) - A228614(n) - A185652(n).

%e a(0) = 1: the empty permutation.

%e a(3) = 1: 123.

%e a(4) = 1: 1234.

%e a(5) = 1: 12345.

%e a(6) = 20: 123456, 124356, 125346, 126345, 134256, 135246, 136245, 145236, 146235, 156234, 234156, 235146, 236145, 245136, 246135, 256134, 345126, 346125, 356124, 456123.

%t A[n_, k_] := A[n, k] = Module[{b}, b[u_, o_, t_] := b[u, o, t] =

%t      If[t + o <= k, (u + o)!,

%t      Sum[b[u + i - 1, o - i, Min[k, t] + 1], {i, 1, o}] +

%t      If[t <= k, u*(u + o - 1)!,

%t      Sum[b[u - i, o + i - 1, 1], {i, 1, u}]]];

%t   Sum[b[j - 1, n - j, 1], {j, 1, n}]];

%t a[n_] := n! - A[n, 2];

%t Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Sep 03 2021, after _Alois P. Heinz_ in A064315 *)

%Y Cf. A064315, A097899.

%Y Cf. A000142, A185652, A228614.

%K nonn

%O 0,7

%A _Alois P. Heinz_, Aug 29 2013