A187245 -id:A187245 - cp's OEIS frontend

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

1, 1, 2, 6, 22, 94, 460, 2532, 15420, 102620, 739512, 5729192, 47429896, 417429800, 3888426512, 38192416048, 394239339792, 4264424937488, 48212317486112, 568395755184224, 6973300915138656, 88860103591344864, 1174131206436335296, 16061756166912244800

Offset: 0

Emeric Deutsch, Mar 08 2011

nonn

a(n) = A187250(n,0).
It appears that a(n) = A216964(n,1), for n>0. - Michel Marcus, May 17 2013.
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.

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

Alois P. Heinz, Table of n, a(n) for n = 0..528
Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024. See p. 56.

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

Row sums of A344855.

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);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      a(n-j)*binomial(n-1, j-1)*ceil(2^(j-2)), j=1..n))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, May 30 2021

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

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 */

x='x+O('x^66); Vec(serlaplace(exp( (2*x-1+exp(2*x))/4 ))) /* Joerg Arndt, Apr 26 2011 */

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

E.g.f.: exp( (2*z-1+exp(2*z))/4 ).
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]
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
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
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
Sum_{k=0..n} binomial(n,k) * a(k) * a(n-k) = A007405(n). - Vaclav Kotesovec, Apr 17 2020
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

A187244 Triangle read by rows: T(n,k) is the number of permutations of [n] having k cycles with 2 alternating runs (it is assumed that the smallest element of the cycle is in the first position), 0<=k<=floor(n/3).

Original entry on oeis.org

1, 1, 2, 5, 1, 17, 7, 78, 42, 463, 247, 10, 3315, 1550, 175, 27164, 11049, 2107, 247975, 92596, 22029, 280, 2492539, 906427, 220734, 9100, 27422698, 10044963, 2264724, 184415, 328607417, 122314296, 25036462, 3028025, 15400, 4266367567, 1607778568, 307273681, 44800184, 800800

Offset: 0

Emeric Deutsch, Mar 07 2011

Number of entries in row n is 1+floor(n/3).
Sum of entries in row n is n!.
T(n,0)=A187245(n).
Sum(k*T(n,k), k>=0) = A187246(n).

			T(4,1)=7 because we have (132)(4), (142)(3), (1)(243), (143)(2), (1432), (1243), and (1342).
Triangle starts:
1;
1;
2;
5,1;
17,7;
78,42;
463, 247, 10;

Alois P. Heinz, Rows n = 0..200, flattened

Cf. A187245, A187246.

G := exp((1/4)*(t-1)*(2*z-4*exp(z)+exp(2*z)+3))/(1-z): Gser := simplify(series(G, z = 0, 15)): for n from 0 to 13 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n from 0 to 13 do seq(coeff(P[n], t, k), k = 0 .. floor((1/3)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(
      `if`(n=0, 1, add(b(n-j)*binomial(n-1, j-1)*
      `if`(j=1, 1, (j-1)!+(2^(j-2)-1)*(x-1)), j=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..14);  # Alois P. Heinz, Apr 15 2017

b[n_] := b[n] = Expand[If[n == 0, 1, Sum[b[n - j]*Binomial[n - 1, j - 1]* If[j == 1, 1, (j - 1)! + (2^(j - 2) - 1)*(x - 1)], {j, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, May 03 2017, after Alois P. Heinz *)

E.g.f.: G(t,z) = exp[(1/4)(t-1)(2z-4exp(z)+exp(2z)+3)]/(1-z).
The 4-variate g.f. H(u,v,w,z) (exponential with respect z), where u marks number of cycles with 1 alternating run, v marks number of cycles with 2 alternating runs, w marks the number of all cycles, and z marks the size of the permutation, is given by
H(u,v,w,z)=exp[(1/4)w((v-1)(exp(2z)+2z)+4(u-v)exp(z)+1-4u+3v)]/(1-z)^w.
We have G(t,z)=H(1,t,1,z).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI