A216964 -id:A216964 - cp's OEIS frontend

A217204 Triangle read by rows, related to Bell numbers A000110: A216962 interlaced with A216964.

1, 2, 1, 5, 6, 1, 15, 22, 9, 2, 52, 94, 63, 26, 5, 203, 460, 416, 244, 101, 16, 877, 2532, 2741, 2124, 1361, 384, 61, 4140, 15420, 18425, 18536, 15602, 6092, 2153, 272, 21147, 102620, 127603, 166440, 165786, 83436, 46959, 10384, 1385, 115975, 739512, 914508, 1550864, 1700220, 1082712, 823256, 247776, 74841, 7936

Offset: 1

N. J. A. Sloane, Sep 27 2012

See Ma (2012) for precise definition (cf. On combinations of polynomials and Euler numbers).

			Triangle begins:
    1;
    2,   1;
    5,   6,   1;
   15,  22,   9,   2;
   52,  94,  63,  26,   5;
  203, 460, 416, 244, 101, 16;
  ...

S.-M. Ma, Enumeration of permutations by number of cyclic peaks and cyclic valleys, arXiv preprint arXiv:1203.6264 [math.CO], 2012.

First column is A000110.

Cf. A216962, A216964.

P[1] := x y; P[n_] := P[n] = ((n-1) q + x y) P[n-1] + 2 q (1-q) D[P[n-1], q] + x (1-q) D[P[n-1], x] + (1-y) D[P[n-1], y] // Simplify;
V[1] = x y; V[n_] := V[n] = ((n-1) q + x y) V[n-1] + 2 q (1-q) D[V[n-1], q] + 2 x (1-q) D[V[n-1], x] + (1 - 2 y + q y) D[V[n-1], y] // Simplify;
M[n_] := P[n] /. {x -> 1, y -> 1};
Mbar[n_] := V[n] /. {x -> 1, y -> 1};
R[1]=1; R[2] = 2+q; R[n_] := (M[n] /. q -> q^2) + q (Mbar[n] /. q -> q^2);
Table[CoefficientList[R[n], q], {n, 1, 10}] // Flatten (* Jean-François Alcover, Sep 25 2018 *)

tabl(m) = {Pa = x; Pb = x*y; for (n=1, m, Pa1 = subst(Pa, x, 1); Pb1 = subst(Pb, x, 1); Pb1 = subst(Pb1, y, 1); if (n==1, R = 1, if (n==2, R = 2+q, R = subst(Pa1, q, q^2) + q*subst(Pb1, q, q^2););); for (d=0, poldegree(R, q), print1(polcoeff(R, d, q), ", "); ); print(""); Pa = (n*q+x)*Pa + 2*q*(1-q)*deriv(Pa, q)+ x*(1-q)*deriv(Pa,x); Pb = (n*q+x*y)*Pb + 2*q*(1-q)*deriv(Pb, q)+ 2*x*(1-q)*deriv(Pb,x)+ (1-2*y+q*y)*deriv(Pb,y););} \\ Michel Marcus, Feb 11 2013

Example and tabf keyword corrected, and extended by Michel Marcus, Feb 11 2013

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

Original entry on oeis.org

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

cp's OEIS Frontend

A217204 Triangle read by rows, related to Bell numbers A000110: A216962 interlaced with A216964.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

PARI

Formula