login
Number of permutations of [n] having no cycle with 3 or more alternating runs (it is assumed that the smallest element of a cycle is in the first position).
6

%I #67 Aug 19 2021 07:25:03

%S 1,1,2,6,22,94,460,2532,15420,102620,739512,5729192,47429896,

%T 417429800,3888426512,38192416048,394239339792,4264424937488,

%U 48212317486112,568395755184224,6973300915138656,88860103591344864,1174131206436335296,16061756166912244800

%N Number of permutations of [n] having no cycle with 3 or more alternating runs (it is assumed that the smallest element of a cycle is in the first position).

%C a(n) = A187250(n,0).

%C It appears that a(n) = A216964(n,1), for n>0. - _Michel Marcus_, May 17 2013.

%C The above comment is correct. Let b(n) be the n-th element of the first column of the triangle in A216964. By definition, b(n) is the number of permutations of [n] with no cyclic valleys. Recall that alternating runs of permutations are monotonically increasing or decreasing subsequences. In other words, b(n) is the number of permutations of [n] with the restriction that every cycle has at most two alternating runs, so b(n) = A187251(n) = a(n). - _Shi-Mei Ma_, May 18 2013.

%H Alois P. Heinz, <a href="/A187251/b187251.txt">Table of n, a(n) for n = 0..528</a>

%F E.g.f.: exp( (2*z-1+exp(2*z))/4 ).

%F For n>=1: a(n)=n!*sum(k=1..n, 2^(n-2*k)*sum(j=0..k, binomial(k,j)*stirling2(n-k+j,j)*j!/(n-k+j)!)/k!); [From _Vladimir Kruchinin_, Apr 25 2011]

%F G.f.: 1/Q(0) where Q(k) = 1 - x*k - x/(1 - x*(k+1)/Q(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Mar 07 2013

%F G.f.: 1/Q(0) where Q(k) = 1 - x*(2*k+1) - m*x^2*(k+1)/Q(k+1) and m=1 (continued fraction); setting m=2 gives A004211, m=4 gives A124311 without signs. - _Sergei N. Gladkovskii_, Sep 26 2013

%F G.f.: T(0)/(1-x), where T(k) = 1 - x^2*(k+1)/( x^2*(k+1) - (1-x-2*x*k)*(1-3*x-2*x*k)/T(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Oct 25 2013

%F Sum_{k=0..n} binomial(n,k) * a(k) * a(n-k) = A007405(n). - _Vaclav Kotesovec_, Apr 17 2020

%F a(n) = Sum_{j=1..n} a(n-j)*binomial(n-1,j-1)*ceiling(2^(j-2)) for n > 0, a(0) = 1. - _Alois P. Heinz_, May 30 2021

%e a(4)=22 because only the permutations 3421=(1324) and 4312=(1423) have cycles with more than 2 alternating runs.

%p g := exp((2*z-1+exp(2*z))*1/4): gser := series(g, z = 0, 28): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 23);

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n=0, 1, add(

%p a(n-j)*binomial(n-1, j-1)*ceil(2^(j-2)), j=1..n))

%p end:

%p seq(a(n), n=0..23); # _Alois P. Heinz_, May 30 2021

%t nmax = 20; CoefficientList[Series[E^((2*x-1+E^(2*x))/4), {x, 0, nmax}], x] * Range[0, nmax]! (* _Vaclav Kotesovec_, Apr 17 2020 *)

%o (Maxima)

%o a(n):=n!*sum(2^(n-2*k)*sum(binomial(k,j)*stirling2(n-k+j,j)*j!/(n-k+j)!,j,0,k)/k!,k,1,n); [_Vladimir Kruchinin_, Apr 25 2011]

%o (PARI) x='x+O('x^66); Vec(serlaplace(exp( (2*x-1+exp(2*x))/4 ))) /* _Joerg Arndt_, Apr 26 2011 */

%o (PARI) lista(m) = {P = x*y; for (n=1, m, M = subst(P, x, 1); M = subst(M, y, 1); print1(polcoeff(M, 0, q), ", "); P = (n*q+x*y)*P + 2*q*(1-q)*deriv(P, q)+ 2*x*(1-q)*deriv(P, x)+ (1-2*y+q*y)*deriv(P, y); ); } \\ (adapted from PARI prog in A216964) \\ _Michel Marcus_, May 17 2013

%Y Cf. A001519, A187245, A187248, A187250, A216964.

%Y Row sums of A344855.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Mar 08 2011