cp's OEIS Frontend

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).

%I A097899 #29 Aug 30 2021 03:10:52
%S A097899 1,0,1,1,6,19,109,588,4033,29485,246042,2228203,22162249,237997032,
%T A097899 2757055393,34191395785,452480427678,6360924613699,94691284984405,
%U A097899 1487846074481172,24608991911033377,427379047337272213,7775688853750498386,147900024951747279643
%N 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).
%D A097899 Ira. M. Gessel, Generating functions and enumeration of sequences, Ph. D. Thesis, MIT, 1977, p. 52.
%H A097899 Alois P. Heinz, <a href="/A097899/b097899.txt">Table of n, a(n) for n = 0..200</a>
%H A097899 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 A097899 a(n) = A000142(n) - A228614(n).
%F A097899 E.g.f.: (sqrt(3)/2)exp(-x/2)/cos(sqrt(3)x/2 + Pi/6).
%F A097899 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 A097899 a(n) ~ n! * exp(-Pi*sqrt(3)/9) * (3*sqrt(3)/(2*Pi))^(n+1). - _Vaclav Kotesovec_, Oct 08 2013
%F A097899 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 A097899 Example: a(4)=6 because 1234, 1324, 1423, 2314, 2413, 3412 are the only permutations of [4] with no runs of length 1.
%p A097899 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 A097899 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 A097899 g[u_, o_] := g[u, o] = If[u + o < 2, u,
%t A097899      Sum[b[u - i, o + i - 1], {i, u}] +
%t A097899      Sum[g[u + i - 1, o - i], {i, o}]];
%t A097899 b[u_, o_] := b[u, o] = If[u + o < 2, 1 - o, u*(u + o - 1)! +
%t A097899      Sum[g[u + i - 1, o - i], {i, o}]] ;
%t A097899 a[n_] := n! - Sum[b[j - 1, n - j], {j, n}];
%t A097899 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Aug 30 2021, after _Alois P. Heinz_ in A228614 *)
%Y A097899 Cf. A186735.
%K A097899 nonn
%O A097899 0,5
%A A097899 _Emeric Deutsch_ and _Ira M. Gessel_, Sep 03 2004