A097592 -id:A097592 - cp's OEIS frontend

A317111 Number of permutations of [n] in which the length of every increasing run is 0 or 1 (mod 4).

1, 1, 1, 1, 2, 10, 50, 210, 840, 4200, 29400, 231000, 1755600, 13213200, 109309200, 1051050000, 11099088000, 120071952000, 1320791472000, 15317750448000, 192286654560000, 2577944809440000, 35885904294240000, 513695427204960000, 7641940962015360000

Offset: 0

Ira M. Gessel, Jul 21 2018

Similarly, 1/(1 - x + x^2/2! - ... - x^(2m-1)/(2m-1)!) is the e.g.f. for permutations in which every increasing run has length 0 or 1 (mod 2m).

			For n=4 the a(4)=2 permutations are 4321 and 1234.

G. C. Greubel, Table of n, a(n) for n = 0..485
David Galvin, John Engbers, and Clifford Smyth, Reciprocals of thinned exponential series, arXiv:2303.14057 [math.CO], 2023.
Ira M. Gessel, Reciprocals of exponential polynomials and permutation enumeration, arXiv:1807.09290 [math.CO], 2018.

Cf. A097592, A097597.

m:=25; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( 1/(1-x+x^2/2-x^3/6) )); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, Nov 30 2018

gser:=series(1/(1-x+x^2/2!-x^3/3!), x, 21): seq(n!*coeff(gser,x,n), n=0..20);

With[{nmax = 25}, CoefficientList[Series[1/(1 -x +x^2/2! -x^3/3!), {x, 0, nmax}], x]*Range[0, nmax]!] (* G. C. Greubel, Nov 30 2018 *)

my(x='x+O('x^25)); Vec(serlaplace(1/(1 -x +x^2/2 -x^3/6))) \\ G. C. Greubel, Nov 30 2018

f= 1/(1 -x +x^2/2 -x^3/6)
g=f.taylor(x,0,13)
L=g.coefficients()
coeffs={c[1]:c[0]*factorial(c[1]) for c in L}
coeffs  # G. C. Greubel, Nov 30 2018

E.g.f.: 1/(1 - x + x^2/2! - x^3/3!).

a(0) = a(1) = a(2) = 1; a(n) = n * a(n-1) - n * (n-1) * a(n-2) / 2 + n * (n-1) * (n-2) * a(n-3) / 6 for n > 2. - Ilya Gutkovskiy, Jan 22 2024

A097597 Number of permutations of [n] with no increasing runs of even length.

Original entry on oeis.org

1, 1, 1, 2, 7, 25, 102, 531, 3141, 20218, 146215, 1174889, 10225678, 96226363, 978420285, 10657592850, 123672458583, 1525420453945, 19929519469558, 274771355003651, 3987385414116085, 60764250319690666, 970085750385722631, 16190361659675002857

Offset: 0

Emeric Deutsch, Aug 29 2004

nonn

			a(4) = 7 because 2/134, 3/124, 4/123, 234/1, 134/2, 124/3 and 4/3/2/1 are the only permutations of [4] with no increasing runs of even length.

Alois P. Heinz, Table of n, a(n) for n = 0..474
Ira M. Gessel, Generating Functions and Enumeration of Sequences, Ph.D. thesis, MIT, 1977, p. 52.
Toufik Mansour and Mark Shattuck, A combinatorial proof of a result for permutation pairs, Central European Journal of Mathematics, 10 (2012), 797-806.

Column k=0 of A097592.

Cf. A000045.

G:=sqrt(5)/(sqrt(5)-2*exp(-x/2)*sinh(sqrt(5)*x/2)): Gser:=simplify(series(G,x=0,25)): 1,seq(n!*coeff(Gser,x^n),n=1..24);
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, t,
      add(b(u+j-1, o-j, irem(t+1, 2)), j=1..o)+
      `if`(t=0, 0, add(b(u-j, o+j-1, 1), j=1..u)))
    end:
a:= n-> b(n, 0, 1):
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 19 2013

CoefficientList[Series[Sqrt[5]/(Sqrt[5]-2*E^(-x/2)*(E^(Sqrt[5]*x/2)/2 - E^(-Sqrt[5]*x/2)/2)), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Sep 29 2013 *)

E.g.f.: sqrt(5)/(sqrt(5)-2*exp(-x/2)*sinh(sqrt(5)*x/2)).
E.g.f.: (1 + Sum_{n>=1} (-1)^n F_n x^n/n!)^(-1), where F_n is the n-th Fibonacci number. - Ira M. Gessel, Jul 27 2014
a(n) ~ n! * sinh(r*sqrt(5)) / (2^n*r^(n+1)*(sqrt(5)*cosh(r*sqrt(5))-sinh(r*sqrt(5)))), where r = 0.68903745689226... is the root of the equation 1-exp(-2*sqrt(5)*r) = sqrt(5)*exp((1-sqrt(5))*r). - Vaclav Kotesovec, Sep 29 2013

A097591 Triangle read by rows: T(n,k) is the number of permutations of [n] with exactly k increasing runs of odd length.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 5, 0, 1, 6, 0, 17, 0, 1, 0, 70, 0, 49, 0, 1, 90, 0, 500, 0, 129, 0, 1, 0, 1890, 0, 2828, 0, 321, 0, 1, 2520, 0, 23100, 0, 13930, 0, 769, 0, 1, 0, 83160, 0, 215292, 0, 62634, 0, 1793, 0, 1, 113400, 0, 1549800, 0, 1697430, 0, 264072, 0, 4097, 0, 1

Offset: 0

Emeric Deutsch, Aug 29 2004

			Triangle starts:
     1;
     0,    1;
     1,    0,     1;
     0,    5,     0,    1;
     6,    0,    17,    0,     1;
     0,   70,     0,   49,     0,   1;
    90,    0,   500,    0,   129,   0,   1;
     0, 1890,     0, 2828,     0, 321,   0, 1;
  2520,    0, 23100,    0, 13930,   0, 769, 0, 1;
  ...
Row n has n+1 entries.
Example: T(3,1) = 5 because we have (123), 13(2), (2)13, 23(1) and (3)12 (the runs of odd length are shown between parentheses).

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

Bisections of columns k=0-1 give: A000680, A302910.
Row sums give A000142.
T(n+1,n-1) gives A000337.
T(4n,2n) gives A308962.
Cf. A096654, A097592.

G:=t^2/(1-t*x-(1-t^2)*exp(-t*x)): Gser:=simplify(series(G,x=0,12)): P[0]:=1: for n from 1 to 11 do P[n]:=sort(expand(n!*coeff(Gser,x^n))) od: seq(seq(coeff(t*P[n],t^k),k=1..n+1),n=0..11);
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, x^t, expand(
      add(b(u+j-1, o-j, irem(t+1, 2)), j=1..o)+
      add(b(u-j, o+j-1, 1)*x^t, j=1..u)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..12);  # Alois P. Heinz, Nov 19 2013

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, x^t, Expand[Sum[b[u+j-1, o-j, Mod[t+1, 2]], {j, 1, o}] + Sum[b[u-j, o+j-1, 1]*x^t, {j, 1, u}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 1, Exponent[p, x]}]][b[n, 0, 1]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)

E.g.f.: t^2/[1-tx-(1-t^2)exp(-tx)].

Sum_{k=1..n} k * T(n,k) = A096654(n-1) for n > 0. - Alois P. Heinz, Jul 03 2019

A317327 Number T(n,k) of permutations of [n] with exactly k distinct lengths of increasing runs; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 2, 4, 0, 7, 17, 0, 2, 118, 0, 82, 436, 202, 0, 2, 3294, 1744, 0, 1456, 18164, 20700, 0, 1515, 140659, 220706, 0, 50774, 1096994, 2317340, 163692, 0, 2, 10116767, 27136103, 2663928, 0, 3052874, 94670868, 328323746, 52954112, 0, 2, 1021089326, 4317753402, 888178070

Offset: 0

Alois P. Heinz, Jul 25 2018

			T(4,1) = 7: 1234, 1324, 1423, 2314, 2413, 3412, 4321.
Triangle T(n,k) begins:
  1;
  0,       1;
  0,       2;
  0,       2,        4;
  0,       7,       17;
  0,       2,      118;
  0,      82,      436,       202;
  0,       2,     3294,      1744;
  0,    1456,    18164,     20700;
  0,    1515,   140659,    220706;
  0,   50774,  1096994,   2317340,   163692;
  0,       2, 10116767,  27136103,  2663928;
  0, 3052874, 94670868, 328323746, 52954112;
  ...

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

Columns k=0-1 give: A000007, A317329.
Row sums give A000142.
Cf. A000217, A003056, A097591, A097592, A123125, A218868, A317273.

b:= proc(u, o, t, s) option remember;
      `if`(u+o=0, x^(nops(s union {t})-1),
       add(b(u-j, o+j-1, 1, s union {t}), j=1..u)+
       add(b(u+j-1, o-j, t+1, s), j=1..o))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2, {})):
seq(T(n), n=0..16);

b[u_, o_, t_, s_] := b[u, o, t, s] = If[u + o == 0, x^(Length[s ~Union~  {t}] - 1), Sum[b[u - j, o + j - 1, 1, s ~Union~ {t}], {j, 1, u}] + Sum[b[u + j - 1, o - j, t + 1, s], {j, 1, o}]];
T[n_] := With[{p = b[n, 0, 0, {}]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
T /@ Range[0, 16] // Flatten (* Jean-François Alcover, Jan 27 2021, after Alois P. Heinz *)

T(n*(n+1)/2,n) = A317273(n).

Sum_{k=0..floor((sqrt(1+8*n)-1)/2)} k * T(n,k) = A317328(n).

A317139 Number of permutations of [n] with exactly floor(n/2) increasing runs of length two.

Original entry on oeis.org

1, 1, 1, 4, 5, 43, 61, 906, 1385, 31493, 50521, 1629248, 2702765, 117248463, 199360981, 11190963430, 19391512145, 1367267690953, 2404879675441, 208031951035452, 370371188237525, 38563334673062963, 69348874393137901, 8554779137299629314, 15514534163557086905

Offset: 0

Alois P. Heinz, Jul 22 2018

nonn

			a(3) = 4: 132, 213, 231, 312.
a(4) = 5: 1324, 1423, 2314, 2413, 3412.

Alois P. Heinz, Table of n, a(n) for n = 0..484

Bisections give: A000364 (even part), A317140 (odd part).

Cf. A004767, A097592.

b:= proc(u, o, t, c) option remember; `if`(u+o=0, 1,`if`(t=1,
       add(b(u+j-1, o-j, t+1, c), j=1..o), 0)+`if`(t<>1 or t=1 and c=1,
       add(b(u-j, o+j-1, 1, `if`(t=1 and c=1, 0, c)), j=1..u), 0))
    end:
a:= n-> b(n, 0$2, irem(n, 2)):
seq(a(n), n=0..30);

b[u_, o_, t_, c_] := b[u, o, t, c] = If[u + o == 0, 1, If[t == 1,
    Sum[b[u+j-1, o-j, t+1, c], {j, o}], 0] + If[t != 1 || t == 1 && c == 1,
    Sum[b[u-j, o+j-1, 1, If[t == 1 && c == 1, 0, c]], {j, u}], 0]];
a[n_] := b[n, 0, 0, Mod[n, 2]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Aug 31 2021, after Alois P. Heinz *)

a(n) = A097592(n,floor(n/2)).

a(n) is even <=> n == 3 (mod 4).

A317140 Number of permutations of [2n+1] with exactly n increasing runs of length two.

Original entry on oeis.org

1, 4, 43, 906, 31493, 1629248, 117248463, 11190963430, 1367267690953, 208031951035452, 38563334673062963, 8554779137299629314, 2237467931691025532493, 681305299577272105281016, 238929711424864185326131543, 95603626135129502838914478558

Offset: 0

Alois P. Heinz, Jul 22 2018

nonn

			a(1) = 4: 132, 213, 231, 312.

Alois P. Heinz, Table of n, a(n) for n = 0..242

Bisection (odd part) of A317139.

Cf. A097592.

a(n) = A317139(2n+1) = A097592(2n+1,n).

a(n) + n == 1 (mod 2).

A097593 Number of increasing runs of even length in all permutations of [n].

Original entry on oeis.org

0, 0, 1, 4, 22, 138, 998, 8174, 74898, 759634, 8451862, 102381222, 1341503546, 18907621562, 285259758366, 4587192222958, 78327809126818, 1415429225667234, 26987142531214118, 541434621007942454, 11402270678456333322

Offset: 0

Emeric Deutsch, Aug 29 2004

nonn

			Example: a(3)=4 because we have 123,(13)2,2(13),(23)1,3(12),321 (runs of even length shown between parentheses).

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A097592.

G:=(4*(exp(-x)-1)+4*x-x^2)/2/(1-x)^2: Gser:=series(G,x=0,25): 0,seq(n!*coeff(Gser,x^n),n=1..24);

Table[n!*SeriesCoefficient[(4*(E^(-x)-1)+4*x-x^2)/(2*(1-x)^2),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Nov 19 2012 *)

x='x+O('x^66); concat([0,0],Vec(serlaplace((4*(exp(-x)-1)+4*x-x^2)/(2*(1-x)^2)))) \\ Joerg Arndt, May 11 2013

E.g.f.: (4*(exp(-x)-1)+4*x-x^2)/(2*(1-x)^2).
a(n) = (2*n-1)*a(n-1) - (n-2)*(n-1)*a(n-2) - (n-2)*(n-1)*a(n-3). - Vaclav Kotesovec, Nov 19 2012
a(n) ~ n!*n*(4*exp(-1)-1)/2. - Vaclav Kotesovec, Nov 19 2012
a(n) = Sum_{k=1..floor(n/2)} k * A097592(n,k). - Alois P. Heinz, Jul 04 2019

A317281 Number of permutations of [n] with exactly one increasing run of even length.

Original entry on oeis.org

1, 4, 12, 52, 299, 1750, 11195, 83074, 675304, 5880354, 55691345, 570430818, 6235219145, 72578854088, 898625380692, 11776375141808, 162751388533495, 2367374376626798, 36156236738459671, 578320016708416430, 9668632218886209536, 168657264917156460894

Offset: 2

Alois P. Heinz, Jul 25 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..473

Column k=1 of A097592.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, x^t,
      add(b(u+j-1, o-j, irem(t+1, 2)), j=1..o)+
      add(b(u-j, o+j-1, 0)*x^t, j=1..u)), x, 2)
    end:
a:= n-> coeff(b(n, 0$2), x, 1):
seq(a(n), n=2..25);

a(n) ~ c * d^n * n^(n + 3/2), where d = 0.26695170015188549567... and c = 1.1281954524592228... - Vaclav Kotesovec, Jul 01 2019

A317282 Number of permutations of [n] with exactly two increasing runs of even length.

Original entry on oeis.org

5, 43, 258, 1853, 15634, 133697, 1207256, 11974457, 126980013, 1421291622, 16925790480, 213992804118, 2851968574855, 39996895523591, 589713707701692, 9114791365659163, 147335664946835342, 2486973983349027871, 43763134470537718258, 801419373432471123541

Offset: 4

Alois P. Heinz, Jul 25 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..472

Column k=2 of A097592.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, x^t,
      add(b(u+j-1, o-j, irem(t+1, 2)), j=1..o)+
      add(b(u-j, o+j-1, 0)*x^t, j=1..u)), x, 3)
    end:
a:= n-> coeff(b(n, 0$2), x, 2):
seq(a(n), n=4..30);

A317283 Number of permutations of [n] with exactly three increasing runs of even length.

Original entry on oeis.org

61, 906, 8965, 94398, 1088575, 12625694, 150890533, 1914036434, 25485825638, 353702731940, 5141233861254, 78259458749608, 1243051438276365, 20579839942072222, 354951501710697119, 6367683567830126402, 118640486378324764141, 2293339890430027143606

Offset: 6

Alois P. Heinz, Jul 25 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 6..472

Column k=3 of A097592.

b:= proc(u, o, t) option remember; series(`if`(u+o=0, x^t,
      add(b(u+j-1, o-j, irem(t+1, 2)), j=1..o)+
      add(b(u-j, o+j-1, 0)*x^t, j=1..u)), x, 4)
    end:
a:= n-> coeff(b(n, 0$2), x, 3):
seq(a(n), n=6..30);

cp's OEIS Frontend

A317111 Number of permutations of [n] in which the length of every increasing run is 0 or 1 (mod 4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A097597 Number of permutations of [n] with no increasing runs of even length.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A097591 Triangle read by rows: T(n,k) is the number of permutations of [n] with exactly k increasing runs of odd length.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A317327 Number T(n,k) of permutations of [n] with exactly k distinct lengths of increasing runs; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A317139 Number of permutations of [n] with exactly floor(n/2) increasing runs of length two.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A317140 Number of permutations of [2n+1] with exactly n increasing runs of length two.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A097593 Number of increasing runs of even length in all permutations of [n].

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula