A097899 Number of permutations of [n] with no runs of length 1. (The permutation 3574162 has two runs of length 1: 357/4/16/2).

1, 0, 1, 1, 6, 19, 109, 588, 4033, 29485, 246042, 2228203, 22162249, 237997032, 2757055393, 34191395785, 452480427678, 6360924613699, 94691284984405, 1487846074481172, 24608991911033377, 427379047337272213, 7775688853750498386, 147900024951747279643

Offset

0,5

References

Ira. M. Gessel, Generating functions and enumeration of sequences, Ph. D. Thesis, MIT, 1977, p. 52.

Links

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

Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.

Formula

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

E.g.f.: (sqrt(3)/2)exp(-x/2)/cos(sqrt(3)x/2 + Pi/6).

E.g.f.: 1/(1-x^2/2!-x^3/3! +x^5/5! + x^6/6! - x^8/8! -x^9/9! + ... ) - Ira M. Gessel, Jul 27 2014

a(n) ~ n! * exp(-Pi*sqrt(3)/9) * (3*sqrt(3)/(2*Pi))^(n+1). - Vaclav Kotesovec, Oct 08 2013

G.f.: T(0), where T(k) = 1 - x^2*(k+1)^2/( x^2*(k+1)^2 - (1-x*(k+1))*(1-x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 03 2013

Example

Example: a(4)=6 because 1234, 1324, 1423, 2314, 2413, 3412 are the only permutations of [4] with no runs of length 1.

Maple

G:=sqrt(3)*exp(-x/2)/2/cos(sqrt(3)*x/2+Pi/6): Gser:=series(G, x, 26): seq(n!*coeff(Gser, x, n), n=0..25);

Mathematica

FullSimplify[CoefficientList[Series[(Sqrt[3]/2)*E^(-x/2)/Cos[Sqrt[3]*x/2 + Pi/6], {x, 0, 20}], x]* Range[0, 20]!] (* Vaclav Kotesovec, Oct 08 2013 *)
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_] := 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 in A228614 *)

Crossrefs

Cf. A186735.

Sequence in context: A323686 A285853 A138748 * A223505 A054236 A118411

Adjacent sequences: A097896 A097897 A097898 * A097900 A097901 A097902

Keyword

nonn

Author

Emeric Deutsch and Ira M. Gessel, Sep 03 2004

Status

approved