A344855 -id:A344855 - 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

A345341 Total number of cycles in all permutations of [n] having cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Original entry on oeis.org

0, 1, 3, 11, 48, 238, 1318, 8054, 53728, 387836, 3007940, 24917668, 219375104, 2043792680, 20074003368, 207186660712, 2240632127232, 25324980662544, 298471543286448, 3660469596095280, 46627358889945344, 615855211031451104, 8421273619742748256

Offset: 0

Alois P. Heinz, Jun 14 2021

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..527
Wikipedia, Permutation

Cf. A344855.

b:= proc(n) option remember; `if`(n=0, [1, 0], add((p-> p+[0,
      p[1]])(b(n-j)*binomial(n-1, j-1)*ceil(2^(j-2))), j=1..n))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=0..23);

b[n_] := b[n] = If[n == 0, {1, 0}, Sum[Function[p, p + {0,
    p[[1]]}][b[n-j] Binomial[n-1, j-1] Ceiling[2^(j-2)]], {j, 1, n}]];
a[n_] := b[n][[2]];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Aug 25 2021, after Alois P. Heinz *)

a(n) = Sum_{k=1..n} k * A344855(n,k).

A345342 Number of permutations of [2n] having n cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Original entry on oeis.org

1, 1, 11, 195, 5033, 171465, 7264499, 368258891, 21740278417, 1465044247953, 110975742044635, 9334724676616339, 863320991981279033, 87072657503374176985, 9511213780859395685955, 1118615909510940858978075, 140933163945864346869845025, 18937018020284359019138011425

Offset: 0

Alois P. Heinz, Jun 14 2021

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..332
Wikipedia, Permutation

Cf. A344855.

b:= proc(n) option remember; `if`(n=0, 1, add(expand(x*
      b(n-j)*binomial(n-1, j-1)*ceil(2^(j-2))), j=1..n))
    end:
a:= n-> coeff(b(2*n), x, n):
seq(a(n), n=0..18);

b[n_] := b[n] = If[n == 0, 1, Sum[Expand[x b[n-j] Binomial[n-1, j-1]* Ceiling[2^(j-2)]], {j, n}]];
a[n_] := Coefficient[b[2n], x, n];
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Aug 25 2021, after Alois P. Heinz *)
a[0] := 1; a[n_] := Sum[Binomial[2*n, n + k + 1]*StirlingS2[n + k + 1, k + 1], {k, 0, n}]; Flatten[Table[a[n] , {n, 0, 17}]] (* Detlef Meya, Jan 18 2024 *)

a(n) = A344855(2n,n).
a(n) ~ c * (1 + exp(2))^n * (n-1)!, where c = sqrt((exp(2) + 1)/(exp(2) - 1))/(2*Pi) = 0.1823720711148962856100934464088354177502714116352616187167... - Vaclav Kotesovec, Jul 15 2021, updated Mar 17 2024
a(0) = 1; a(n) = Sum_{k=0..n} binomial(2*n, n + k + 1)*Stirling2(n + k + 1, k + 1). - Detlef Meya, Jan 18 2024

A346317 Number of permutations of [n] having two cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Original entry on oeis.org

1, 3, 11, 40, 148, 560, 2160, 8448, 33344, 132352, 527104, 2103296, 8401920, 33583104, 134279168, 537001984, 2147762176, 8590524416, 34360983552, 137441574912, 549761318912, 2199034789888, 8796117139456, 35184422420480, 140737593212928, 562950171525120

Offset: 2

Alois P. Heinz, Jul 13 2021

Alois P. Heinz, Table of n, a(n) for n = 2..1000
Index entries for linear recurrences with constant coefficients, signature (8,-20,16).

Column k=2 of A344855.

G.f.: (4*x^3-7*x^2+5*x-1)*x^2/((4*x-1)*(2*x-1)^2).

For n>2, a(n) = 2^(2*n-5) + (n-1)*2^(n-4). - Vaclav Kotesovec, Jul 15 2021

A346318 Number of permutations of [n] having three cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Original entry on oeis.org

1, 6, 35, 195, 1078, 5992, 33632, 190800, 1093664, 6327552, 36904192, 216676096, 1279012352, 7581628416, 45086720000, 268774576128, 1605129183232, 9598558142464, 57453899350016, 344139257020416, 2062361588793344, 12363724057214976, 74138363625472000

Offset: 3

Alois P. Heinz, Jul 13 2021

Alois P. Heinz, Table of n, a(n) for n = 3..1000
Index entries for linear recurrences with constant coefficients, signature (20,-160,656,-1456,1664,-768).

Column k=3 of A344855.

Drop[CoefficientList[Series[(96x^6-256x^5+298x^4-201x^3+75x^2-14x+1)x^3/((6x-1)(4x-1)^2 (2x-1)^3),{x,0,30}],x],3] (* Harvey P. Dale, Jun 11 2024 *)

G.f.: (96*x^6-256*x^5+298*x^4-201*x^3+75*x^2-14*x+1)*x^3 / ((6*x-1) *(4*x-1)^2 *(2*x-1)^3).

For n>3, a(n) = 2^(n-7)*3^(n-1) + (n-2)*2^(2*n-8) + (n^2 - 3*n + 1)*2^(n-7). - Vaclav Kotesovec, Jul 15 2021

A346319 Number of permutations of [n] having four cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Original entry on oeis.org

1, 10, 85, 665, 5033, 37632, 280760, 2100560, 15799344, 119598336, 911432704, 6991479040, 53960703232, 418803056640, 3266623490048, 25590201536512, 201220024528896, 1587256170708992, 12553933544030208, 99511621823561728, 790240133265817600, 6284788112052715520

Offset: 4

Alois P. Heinz, Jul 13 2021

Alois P. Heinz, Table of n, a(n) for n = 4..1000
Index entries for linear recurrences with constant coefficients, signature (40,-700,7056,-45360,194304,-561728,1082624,-1332224,946176,-294912).

Column k=4 of A344855.

G.f.: (18432*x^10 -68352*x^9 +115136*x^8 -117072*x^7 +80628*x^6 -38652*x^5 +12733*x^4 -2791*x^3 +385*x^2 -30*x+1)*x^4 / ((8*x-1) *(6*x-1)^2 *(4*x-1)^3 *(2*x-1)^4).

A346320 Number of permutations of [n] having five cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Original entry on oeis.org

1, 15, 175, 1820, 17913, 171465, 1619090, 15203100, 142623624, 1340443104, 12641487040, 119734858880, 1139445627392, 10895927375616, 104687442226688, 1010398777492480, 9793403768723456, 95295673342836736, 930591031216799744, 9116681462478864384

Offset: 5

Alois P. Heinz, Jul 13 2021

Alois P. Heinz, Table of n, a(n) for n = 5..1000
Index entries for linear recurrences with constant coefficients, signature (70, -2240, 43456, -571424, 5393344, -37736448, 199267328, -800498944, 2446126592, -5639102464, 9631809536, -11801133056, 9794617344, -4926210048, 1132462080).

Column k=5 of A344855.

G.f.: (35389440*x^15 -171638784*x^14 +387477504*x^13 -541806592*x^12 +526946304*x^11 -379603968*x^10 +209286000*x^9 -89384640*x^8 +29543056*x^7 -7487228*x^6 +1432429*x^5 -202097*x^4 +20286*x^3 -1365*x^2 +55*x -1)*x^5 / ((10*x-1) *(8*x-1)^2 *(6*x-1)^3 *(4*x-1)^4 *(2*x-1)^5).

A346321 Number of permutations of [n] having six cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Original entry on oeis.org

1, 21, 322, 4284, 52941, 627627, 7264499, 82948008, 940359420, 10628025408, 120071145376, 1358324810752, 15403850755456, 175232115148032, 2000450203866368, 22922052379355136, 263639657993643008, 3043516686354636800, 35260990780587196416, 409914386080322027520

Offset: 6

Alois P. Heinz, Jul 13 2021

Alois P. Heinz, Table of n, a(n) for n = 6..932
Index entries for linear recurrences with constant coefficients, signature (112, -5880, 192416, -4402160, 74858880, -981976576, 10178341888, -84702207744, 571843371008, -3151736133632, 14222131077120, -52534235435008, 158334587600896, -386804516978688, 757761436024832, -1171275127980032, 1394246317768704, -1231344289972224, 758836566687744, -290924978503680, 52183852646400).

Column k=6 of A344855.

b:= proc(n) option remember; series(`if`(n=0, 1, add(b(n-j)
      *binomial(n-1, j-1)*x*ceil(2^(j-2)), j=1..n)), x, 7)
    end:
a:= n-> coeff(b(n), x, 6):
seq(a(n), n=6..29);

A346322 Number of permutations of [n] having seven cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Original entry on oeis.org

1, 28, 546, 9030, 136521, 1956570, 27124955, 368258891, 4934711782, 65608599056, 868543125632, 11476719098208, 151628071536832, 2005351952310016, 26570735233245952, 352902891363604736, 4699994984738296320, 62779734338836996096, 841132871051793858560

Offset: 7

Alois P. Heinz, Jul 13 2021

Alois P. Heinz, Table of n, a(n) for n = 7..879
Index entries for linear recurrences with constant coefficients, signature (168, -13440, 681632, -24615360, 673960320, -14545867776, 254017792512, -3655881782784, 43944394303488, -445483185094656, 3835837793820672, -28195256256282624, 177510573498728448, -958975703677403136, 4447744859322580992, -17695513525640822784, 60260448721418846208, -175010175041662877696, 431158568263920648192, -894423403170908602368, 1546792199062741319680, -2199976821097607725056, 2525948081813952921600, -2280501363206944456704, 1556924686713055346688, -754785240817587978240, 231325591660815974400, -33664847019245568000).

Column k=7 of A344855.

b:= proc(n) option remember; series(`if`(n=0, 1, add(b(n-j)
      *binomial(n-1, j-1)*x*ceil(2^(j-2)), j=1..n)), x, 8)
    end:
a:= n-> coeff(b(n), x, 7):
seq(a(n), n=7..29);

A346323 Number of permutations of [n] having eight cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Original entry on oeis.org

1, 36, 870, 17490, 317031, 5390814, 87942569, 1395590625, 21740278417, 334497665216, 5105159585136, 77525496199008, 1173978347855008, 17756444087253504, 268561449630791680, 4065329910324860672, 61628507048573158144, 936035967482288414720

Offset: 8

Alois P. Heinz, Jul 13 2021

Alois P. Heinz, Table of n, a(n) for n = 8..838
Index entries for linear recurrences with constant coefficients, signature (240, -27720, 2052512, -109501392, 4485157248, -146762730752, 3941544701952, -88583039660544, 1690201339101184, -27683252247785472, 392554888743665664, -4851695318748831744, 52537637204482129920, -500491057082699612160, 4207381516172517703680, -31281978226696900116480, 206014309171875372072960, -1202762064346113966080000, 6226143028325392507207680, -28563943556332339917225984, 116011182450800820653916160, -416382609918980503445176320, 1317358503859988420213342208, -3661679575789298214196215808, 8903229523611559893896527872, -18833310289690908029676945408, 34420123100871095086594654208, -53876192282750532975146827776, 71417640290027267167749144576, -79011046920360642901671149568, 71540341196238752070915588096, -51594033438349863071458000896, 28478927494742679928795299840, -11290083667294698757265817600, 2859932711332506431913984000, -347485857744891213250560000).

Column k=8 of A344855.

b:= proc(n) option remember; series(`if`(n=0, 1, add(b(n-j)
      *binomial(n-1, j-1)*x*ceil(2^(j-2)), j=1..n)), x, 9)
    end:
a:= n-> coeff(b(n), x, 8):
seq(a(n), n=8..29);

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

PARI

Formula

A345341 Total number of cycles in all permutations of [n] having cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A345342 Number of permutations of [2n] having n cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A346317 Number of permutations of [n] having two cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Views

Author

Keywords

Links

Crossrefs

Formula

A346318 Number of permutations of [n] having three cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A346319 Number of permutations of [n] having four cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Views

Author

Keywords

Links

Crossrefs

Formula

A346320 Number of permutations of [n] having five cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Views

Author

Keywords

Links

Crossrefs

Formula

A346321 Number of permutations of [n] having six cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A346322 Number of permutations of [n] having seven cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i.

Views

Author

Keywords

Links

Crossrefs