A097899 - OEIS

%I #29 Aug 30 2021 03:10:52

%S 1,0,1,1,6,19,109,588,4033,29485,246042,2228203,22162249,237997032,

%T 2757055393,34191395785,452480427678,6360924613699,94691284984405,

%U 1487846074481172,24608991911033377,427379047337272213,7775688853750498386,147900024951747279643

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

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

%H Alois P. Heinz, <a href="/A097899/b097899.txt">Table of n, a(n) for n = 0..200</a>

%H Paul Barry, <a href="https://arxiv.org/abs/1802.03443">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.

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

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

%F 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

%F a(n) ~ n! * exp(-Pi*sqrt(3)/9) * (3*sqrt(3)/(2*Pi))^(n+1). - _Vaclav Kotesovec_, Oct 08 2013

%F 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

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

%p 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);

%t 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 *)

%t g[u_, o_] := g[u, o] = If[u + o < 2, u,

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

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

%t b[u_, o_] := b[u, o] = If[u + o < 2, 1 - o, u*(u + o - 1)! +

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

%t a[n_] := n! - Sum[b[j - 1, n - j], {j, n}];

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

%Y Cf. A186735.

%K nonn

%O 0,5

%A _Emeric Deutsch_ and _Ira M. Gessel_, Sep 03 2004