login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 3
1, 0, 1, 1, 6, 19, 109, 588, 4033, 29485, 246042, 2228203, 22162249, 237997032, 2757055393, 34191395785, 452480427678, 6360924613699, 94691284984405, 1487846074481172, 24608991911033377, 427379047337272213, 7775688853750498386, 147900024951747279643 (list; graph; refs; listen; history; text; internal format)
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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 16 20:51 EDT 2021. Contains 347473 sequences. (Running on oeis4.)