login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A186735 Number of permutations of [n] with no ascending runs of length 1 or 2. 2
1, 0, 0, 1, 1, 1, 20, 69, 180, 1930, 12611, 61051, 566129, 5179750, 38348469, 376547340, 4169246332, 41559058969, 465750294781, 5905176350849, 72848728572828, 946103621115633, 13501160406995728, 195518567272213262, 2918439778172724571, 46559546190633191495 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,7

LINKS

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

FORMULA

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

EXAMPLE

a(0) = 1: the empty permutation.

a(3) = 1: 123.

a(4) = 1: 1234.

a(5) = 1: 12345.

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

MATHEMATICA

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

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

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

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

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

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

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

Table[a[n], {n, 0, 25}] (* Jean-Fran├žois Alcover, Sep 03 2021, after Alois P. Heinz in A064315 *)

CROSSREFS

Cf. A064315, A097899.

Cf. A000142, A185652, A228614.

Sequence in context: A044158 A044539 A297597 * A238101 A153728 A234367

Adjacent sequences:  A186732 A186733 A186734 * A186736 A186737 A186738

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Aug 29 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 15 20:27 EDT 2022. Contains 356148 sequences. (Running on oeis4.)