A097597 -id:A097597 - cp's OEIS frontend

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

1, 1, 1, 1, 2, 4, 7, 12, 5, 25, 52, 43, 102, 299, 258, 61, 531, 1750, 1853, 906, 3141, 11195, 15634, 8965, 1385, 20218, 83074, 133697, 94398, 31493, 146215, 675304, 1207256, 1088575, 460929, 50521, 1174889, 5880354, 11974457, 12625694, 6632158

Offset: 0

Emeric Deutsch, Aug 29 2004

Row n has 1+floor(n/2) entries.

			Triangle starts:
    1;
    1;
    1,   1;
    2,   4;
    7,  12,   5;
   25,  52,  43;
  102, 299, 258, 61;
Example: T(4,2) = 5 because we have 13/24, 14/23, 23/14, 24/13 and 34/12.

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

Columns k=0-10 give: A097597, A317281, A317282, A317283, A317284, A317285, A317286, A317287, A317288, A317289, A317290.
Row sums give A000142.
T(n,floor(n/2)) gives A317139.
T(2n,n) gives A000364.
T(2n+1,n) gives A317140.
Cf. A097591, A097593.

G:=2*(t-1)*u/(-2*u+(2-t+t*u)*exp((-1+u)*x/2)+(t-2+t*u)*exp(-(1+u)*x/2)): u:=sqrt(5-4*t): Gser:=simplify(series(G,x=0,12)): P[0]:=1: for n from 1 to 11 do P[n]:=sort(n!*coeff(Gser,x^n)) od: seq(seq(coeff(t*P[n],t^k),k=1..1+floor(n/2)),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, 0)*x^t, j=1..u)))
    end:
T:= n->(p->seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
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, 0]*x^t, {j, 1, u}]]]; T[n_] := Function[ {p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 0]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Apr 29 2015, after Alois P. Heinz *)

E.g.f.: 2(t-1)u/[ -2u+(2-t+tu)exp((-1+u)x/2)+(t-2+tu)exp(-(1+u)x/2)], where u=sqrt(5-4t).

Sum_{k=1..floor(n/2)} k * T(n,k) = A097593(n). - Alois P. Heinz, Jul 04 2019

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

Original entry on oeis.org

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

A317130 Number of permutations of [n] whose lengths of increasing runs are triangular numbers.

Original entry on oeis.org

1, 1, 1, 2, 7, 24, 93, 483, 2832, 17515, 123226, 978405, 8312802, 75966887, 756376739, 8070649675, 91320842018, 1099612368110, 14054043139523, 189320856378432, 2682416347625463, 39945105092501742, 623240458310527252, 10160826473676346731, 172871969109661492526

Offset: 0

Alois P. Heinz, Jul 21 2018

nonn

			a(2) = 1: 21.
a(3) = 2: 123, 321.
a(4) = 7: 1243, 1342, 2134, 2341, 3124, 4123, 4321.
a(5) = 24: 12543, 13542, 14532, 21354, 21453, 23541, 24531, 31254, 31452, 32145, 32451, 34521, 41253, 41352, 42135, 42351, 43125, 51243, 51342, 52134, 52341, 53124, 54123, 54321.

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

Cf. A000217, A097597, A193374, A317111, A317128, A317129, A317131, A317132, A317446.

g:= n-> `if`(issqr(8*n+1), 1, 0):
b:= proc(u, o, t) option remember; `if`(u+o=0, g(t),
      `if`(g(t)=1, add(b(u-j, o+j-1, 1), j=1..u), 0)+
       add(b(u+j-1, o-j, t+1), j=1..o))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..27);

g[n_] := If[IntegerQ @ Sqrt[8n+1], 1, 0];
b[u_, o_, t_] := b[u, o, t] = If[u+o==0, g[t], If[g[t]==1, Sum[b[u-j, o+j-1, 1], {j, 1, u}], 0] + Sum[b[u+j-1, o-j, t+1], {j, 1, o}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 27] (* Jean-François Alcover, Apr 29 2020, after Alois P. Heinz *)

A317128 Number of permutations of [n] whose lengths of increasing runs are Fibonacci numbers.

Original entry on oeis.org

1, 1, 2, 6, 23, 112, 652, 4425, 34358, 299971, 2910304, 31059715, 361603228, 4560742758, 61947243329, 901511878198, 13994262184718, 230811430415207, 4030772161073249, 74301962970014978, 1441745847111969415, 29374226224980834077, 626971133730275593916

Offset: 0

Alois P. Heinz, Jul 21 2018

nonn

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

Cf. A000045, A097597, A273001, A317111, A317129, A317130, A317131, A317132, A317444.

g:= n-> (t-> `if`(issqr(t+4) or issqr(t-4), 1, 0))(5*n^2):
b:= proc(u, o, t) option remember; `if`(u+o=0, g(t),
      `if`(g(t)=1, add(b(u-j, o+j-1, 1), j=1..u), 0)+
       add(b(u+j-1, o-j, t+1), j=1..o))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..27);

g[n_] := With[{t = 5n^2}, If[IntegerQ@Sqrt[t+4] || IntegerQ@Sqrt[t-4], 1, 0]];
b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, g[t],
     If[g[t] == 1, Sum[b[u - j, o + j - 1, 1], {j, 1, u}], 0] +
     Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 27] (* Jean-François Alcover, Mar 29 2021, after Alois P. Heinz *)

A317129 Number of permutations of [n] whose lengths of increasing runs are squares.

Original entry on oeis.org

1, 1, 1, 1, 2, 9, 40, 151, 571, 2897, 19730, 140190, 953064, 6708323, 54631552, 510143776, 4987278692, 49168919669, 505209884549, 5638095015594, 67921924172174, 852861260421398, 10992380368532792, 147296144926635359, 2082906807168675698, 30973237281668975230

Offset: 0

Alois P. Heinz, Jul 21 2018

nonn

			a(3) = 1: 321.
a(4) = 2: 1234, 4321.
a(5) = 9: 12354, 12453, 13452, 21345, 23451, 31245, 41235, 51234, 54321.

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

Cf. A000290, A097597, A205801, A317111, A317128, A317130, A317131, A317132, A317445.

g:= n-> `if`(issqr(n), 1, 0):
b:= proc(u, o, t) option remember; `if`(u+o=0, g(t),
      `if`(g(t)=1, add(b(u-j, o+j-1, 1), j=1..u), 0)+
       add(b(u+j-1, o-j, t+1), j=1..o))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..27);

g[n_] := If[IntegerQ@Sqrt[n], 1, 0];
b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, g[t],
     If[g[t] == 1, Sum[b[u - j, o + j - 1, 1], {j, 1, u}], 0] +
     Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 27] (* Jean-François Alcover, Mar 29 2021, after Alois P. Heinz *)

A317131 Number of permutations of [n] whose lengths of increasing runs are prime numbers.

Original entry on oeis.org

1, 0, 1, 1, 5, 19, 80, 520, 2898, 22486, 171460, 1509534, 14446457, 147241144, 1650934446, 19494460567, 248182635904, 3340565727176, 47659710452780, 718389090777485, 11381176852445592, 189580213656445309, 3305258537062221020, 60273557241570401742

Offset: 0

Alois P. Heinz, Jul 21 2018

nonn

			a(2) = 1: 12.
a(3) = 1: 123.
a(4) = 5: 1324, 1423, 2314, 2413, 3412.
a(5) = 19: 12345, 12435, 12534, 13245, 13425, 13524, 14235, 14523, 15234, 23145, 23415, 23514, 24135, 24513, 25134, 34125, 34512, 35124, 45123.

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

Cf. A000040, A097597, A218002, A317111, A317128, A317129, A317130, A317132, A317447.

g:= n-> `if`(n=0 or isprime(n), 1, 0):
b:= proc(u, o, t) option remember; `if`(u+o=0, g(t),
      `if`(g(t)=1, add(b(u-j, o+j-1, 1), j=1..u), 0)+
       add(b(u+j-1, o-j, t+1), j=1..o))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..27);

g[n_] := If[n == 0 || PrimeQ[n], 1, 0];
b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, g[t],
     If[g[t] == 1, Sum[b[u - j, o + j - 1, 1], {j, 1, u}], 0] +
     Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 27] (* Jean-François Alcover, Mar 29 2021, after Alois P. Heinz *)

from functools import lru_cache
from sympy import isprime
def g(n): return int(n == 0 or isprime(n))
@lru_cache(maxsize=None)
def b(u, o, t):
  if u + o == 0: return g(t)
  return (sum(b(u-j,  o+j-1,  1) for j in range(1, u+1)) if g(t) else 0) +\
          sum(b(u+j-1, o-j, t+1) for j in range(1, o+1))
def a(n): return b(n, 0, 0)
print([a(n) for n in range(28)]) # Michael S. Branicky, Mar 29 2021 after Alois P. Heinz

A317132 Number of permutations of [n] whose lengths of increasing runs are factorials.

Original entry on oeis.org

1, 1, 2, 5, 17, 70, 350, 2029, 13495, 100813, 837647, 7652306, 76282541, 823684964, 9578815164, 119346454671, 1586149739684, 22397700381817, 334879465463998, 5285103821004717, 87800206978975107, 1531533620821692217, 27987305231654121046, 534688325008397289484

Offset: 0

Alois P. Heinz, Jul 21 2018

nonn

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

Cf. A000142, A097597, A272603, A317111, A317128, A317129, A317130, A317131, A317448.

g:= proc(n) local i; 1; for i from 2 do
      if n=% then 1; break elif n<% then 0; break fi;
      %*i od; g(n):=%
    end:
b:= proc(u, o, t) option remember; `if`(u+o=0, g(t),
      `if`(g(t)=1, add(b(u-j, o+j-1, 1), j=1..u), 0)+
       add(b(u+j-1, o-j, t+1), j=1..o))
    end:
a:= n-> `if`(n=0, 1, add(b(j-1, n-j, 1), j=1..n)):
seq(a(n), n=0..27);

g[n_] := g[n] = Module[{i, k = 1}, For[i = 2, True, i++,
     If[n == k, k = 1; Break[]]; If[n < k, k = 0; Break[]];
     k = k*i]; k];
b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, g[t],
     If[g[t] == 1, Sum[b[u - j, o + j - 1, 1], {j, 1, u}], 0] +
     Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]];
a[n_] := If[n == 0, 1, Sum[b[j - 1, n - j, 1], {j, 1, n}]];
a /@ Range[0, 27] (* Jean-François Alcover, Mar 29 2021~, after Alois P. Heinz *)

a(3) = 5: 132, 213, 231, 312, 321.

a(4) = 17: 1324, 1423, 1432, 2143, 2314, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312, 4321.

A308940 Expansion of e.g.f. 1 / (1 - Sum_{k>=1} Fibonacci(k)*x^k/k!).

Original entry on oeis.org

1, 1, 3, 14, 85, 645, 5878, 62495, 759351, 10379878, 157652085, 2633903669, 48005235886, 947849607015, 20154635314591, 459170181891230, 11158379672316837, 288109467764819749, 7876576756719778854, 227299554620022188879, 6904560742996004248135

Offset: 0

Ilya Gutkovskiy, Jul 01 2019

nonn

Cf. A000045, A097597, A215928.

nmax = 20; CoefficientList[Series[Sqrt[5]/(Sqrt[5] - 2 Exp[x/2] Sinh[Sqrt[5] x/2]), {x, 0, nmax}], x] Range[0, nmax]!
a[0] = 1; a[n_] := a[n] = Sum[Binomial[n, k] Fibonacci[k] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 20}]

E.g.f.: sqrt(5)/(sqrt(5) - 2*exp(x/2)*sinh(sqrt(5)*x/2)).
a(0) = 1; a(n) = Sum_{k=1..n} binomial(n,k) * Fibonacci(k) * a(n-k).
a(n) ~ n! * 5^((n+1)/2) * (exp(2*r) - 1) / ((sqrt(5) - 1 + (1 + sqrt(5))*exp(2*r)) * 2^n * r^(n+1)), where r = 0.7361181605960590527095268838693519750655284224... is the root of the equation exp(2*r) = 1 + sqrt(5)*exp(r*(1 - 1/sqrt(5))). - Vaclav Kotesovec, Jul 01 2019

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A317130 Number of permutations of [n] whose lengths of increasing runs are triangular numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A317128 Number of permutations of [n] whose lengths of increasing runs are Fibonacci numbers.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A317129 Number of permutations of [n] whose lengths of increasing runs are squares.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A317131 Number of permutations of [n] whose lengths of increasing runs are prime numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A317132 Number of permutations of [n] whose lengths of increasing runs are factorials.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A308940 Expansion of e.g.f. 1 / (1 - Sum_{k>=1} Fibonacci(k)*x^k/k!).

Views