A177250 -id:A177250 - cp's OEIS frontend

A177251 Number of permutations of [n] having no adjacent 3-cycles, i.e., no cycles of the form (i, i+1, i+2).

1, 1, 2, 5, 22, 114, 697, 4923, 39612, 357899, 3588836, 39556420, 475392841, 6187284605, 86701097310, 1301467245329, 20835850494474, 354382860600678, 6381494425302865, 121290065781743383, 2426510081356069016, 50969474697328055063, 1121571023472780698152

Offset: 0

Emeric Deutsch, May 07 2010

nonn

			a(4)=22 because the only permutations of {1,2,3,4} having adjacent 3-cycles are (123)(4) and (1)(234).

Seiichi Manyama, Table of n, a(n) for n = 0..449
R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Cf. A000166, A008290, A177248, A177249, A177250, A177252, A177253.

Cf. A370324, A370569.

A177251:= func< n | (&+[(-1)^j*Factorial(n-2*j)/Factorial(j): j in [0..Floor(n/3)]]) >;
[A177251(n): n in [0..30]]; // G. C. Greubel, Apr 28 2024

a := proc (n) options operator, arrow: sum((-1)^j*factorial(n-2*j)/factorial(j), j = 0 .. floor((1/3)*n)) end proc: seq(a(n), n = 0 .. 22);

a[n_] := Sum[(-1)^j*(n - 2*j)!/j!, {j, 0, n/3}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 17 2017 *)

def A177251(n): return sum((-1)^j*factorial(n-2*j)/factorial(j) for j in range(1+n//3))
[A177251(n) for n in range(31)] # G. C. Greubel, Apr 28 2024

a(n) = Sum_{j=0..floor(n/3)} (-1)^j*(n-2*j)!/j!.
a(n) = A177250(n,0).
a(n) - n*a(n-1) = 2*a(n-3) + 3*(-1)^(n/3) if 3 | n, otherwise a(n) - n*a(n-1) = 2*a(n-3).
lim_{n -> oo} a(n)/n! = 1.
The o.g.f. g(z) satisfies z^2*(1+z^3)*g'(z) - (1+z^3)(1-z-2z^3)g(z) + 1 - 2z^3 = 0; g(0)=1.
G.f.: hypergeometric2F0([1,1], [], x/(1+x^3))/(1+x^3). - Mark van Hoeij, Nov 08 2011
D-finite with recurrence a(n) = n*a(n-1) + a(n-3) + (n-3)*a(n-4) + 2*a(n-6). - R. J. Mathar, Jul 26 2022
G.f.: Sum_{k>=0} k! * x^k / (1+x^3)^(k+1). - Seiichi Manyama, Feb 20 2024

Crossreferences corrected by Emeric Deutsch, May 09 2010

A177249 Number of permutations of [n] having no adjacent transpositions, that is, no cycles of the form (i, i+1).

Original entry on oeis.org

1, 1, 1, 4, 19, 99, 611, 4376, 35621, 324965, 3285269, 36462924, 440840359, 5767387591, 81184266631, 1223531387056, 19657686459529, 335404201199049, 6056933308042409, 115417137054004820, 2314399674388138811, 48717810299204919851, 1074106226256896375531

Offset: 0

Emeric Deutsch, May 07 2010

nonn

			a(3)=4 because we have (1)(2)(3), (13)(2), (123), and (132).

Michael De Vlieger, Table of n, a(n) for n = 0..449
R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.
Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, University of Iceland (2020).
Anders Claesson and Henning Ulfarsson, Turning cycle restrictions into mesh patterns via Foata's fundamental transformation, Univ. of Iceland (2023).

Cf. A000166, A008290, A177248, A177250, A177251, A177252, A177253.

[(&+[(-1)^j*Factorial(n-j)/Factorial(j): j in [0..Floor(n/2)]]): n in [0..30]]; // G. C. Greubel, Apr 28 2024

a := proc (n) options operator, arrow: sum((-1)^j*factorial(n-j)/factorial(j), j = 0 .. floor((1/2)*n)) end proc: seq(a(n), n = 0 .. 22);

a[n_] := Sum[(-1)^j*(n - j)!/j!, {j, 0, n/2}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 20 2017 *)

[sum((-1)^j*factorial(n-j)/factorial(j) for j in range(1+n//2)) for n in range(31)] # G. C. Greubel, Apr 28 2024

a(n) = A177248(n,0).
Limit_{n->oo} a(n)/n! = 1.
a(n) = Sum_{j=0..floor(n/2)} (-1)^j*(n-j)!/j!.
a(n) - n*a(n-1) = a(n-2) if n is odd.
a(n) - n*a(n-1) = a(n-2) + 2*(-1)^(n/2) if n is even.
The o.g.f. g(z) satisfies z^2*(1+z^2)*g'(z)-(1+z^2)(1-z-z^2)g(z)+1-z^2=0; g(0)=1.
The e.g.f. G(z) satisfies (1-z)G"(z)-2G'(z)-G(z)=-2cos(z); G(0)=1, G'(0)=1.
The o.g.f. is hypergeometric2F0([1,1], [], x/(1+x^2))/(1+x^2). - Mark van Hoeij, Nov 08 2011
G.f.: 1/Q(0), where Q(k)= 1 + x^2 - x*(k+1)/(1-x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 20 2013
D-finite with recurrence a(n) = n*a(n-1) + (n-2)*a(n-3) + a(n-4). - R. J. Mathar, Jul 26 2022
G.f.: Sum_{k>=0} k! * x^k / (1+x^2)^(k+1). - Seiichi Manyama, Feb 20 2024

A177248 Triangle read by rows: T(n,k) is the number of permutations of [n] having k adjacent transpositions (0 <= k <= floor(n/2)). An adjacent transposition is a cycle of the form (i, i+1).

Original entry on oeis.org

1, 1, 1, 1, 4, 2, 19, 4, 1, 99, 18, 3, 611, 99, 9, 1, 4376, 612, 48, 4, 35621, 4376, 306, 16, 1, 324965, 35620, 2190, 100, 5, 3285269, 324965, 17810, 730, 25, 1, 36462924, 3285270, 162480, 5940, 180, 6, 440840359, 36462924, 1642635, 54160, 1485, 36, 1

Offset: 0

Emeric Deutsch, May 07 2010

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

Sum of entries in row n = n! (A000142).

			T(5,2)=3 because we have (12)(34)(5), (12)(3)(45), and (1)(23)(45).
Triangle starts:
    1;
    1;
    1,  1;
    4,  2;
   19,  4,  1;
   99, 18,  3;
  611, 99,  9,  1;

Seiichi Manyama, Rows n = 0..200, flattened
R. A. Brualdi and E. Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Columns k=0..3 give A177249, A370524, A370426, A370529.
Cf. A000166, A008290, A177249, A177250, A177251, A177252, A177253.
Cf. A000142 (row sums).

F:=Factorial;
A177248:= func< n,k | (&+[(-1)^j*F(n-k-j)/(F(k)*F(j)): j in [0..Floor((n-2*k)/2)]]) >;
[A177248(n,k): k in [0..Floor(n/2)], n in [0..16]]; // G. C. Greubel, Apr 28 2024

T := proc (n, k) options operator, arrow: sum((-1)^(k+j)*binomial(j, k)*factorial(n-j)/factorial(j), j = 0 .. floor((1/2)*n)) end proc: for n from 0 to 12 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

T[n_, k_] := Sum[(-1)^(k + j)*Binomial[j, k]*(n - j)!/j!, {j, 0, n/2}];
Table[T[n, k], {n, 0, 12}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Nov 20 2017 *)

T(n, k) = sum(j=0, n\2, (-1)^(k+j)*binomial(j,k)*(n-j)!/j!);
tabf(nn) = for (n=0, nn, for (k=0, n\2, print1(T(n,k), ", ")); print); \\ Michel Marcus, Nov 21 2017

f=factorial;
def A177248(n,k): return sum((-1)^j*f(n-k-j)/(f(k)*f(j)) for j in range(1+(n-2*k)//2))
flatten([[A177248(n,k) for k in range(1+n//2)] for n in range(17)]) # G. C. Greubel, Apr 28 2024

T(n, k) = Sum_{j=0..floor(n/2)} (-1)^(k+j)*binomial(j,k)*(n-j)!/j!.
T(n, 0) = A177249(n).
Sum_{k=0..floor(n/2)} k*T(n,k) = (n-1)! (n >= 2).
G.f. of column k: (1/k!) * Sum_{j>=k} j! * x^(j+k) / (1+x^2)^(j+1). - Seiichi Manyama, Feb 24 2024

A177252 Triangle read by rows: T(n,k) is the number of permutations of [n] having k adjacent 4-cycles (0 <= k <= floor(n/4)), i.e., having k cycles of the form (i, i+1, i+2, i+3).

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 118, 2, 714, 6, 5016, 24, 40201, 118, 1, 362163, 714, 3, 3623772, 5016, 12, 39876540, 40200, 60, 478639079, 362163, 357, 1, 6223394516, 3623772, 2508, 4, 87138394540, 39876540, 20100, 20, 1307195547720, 478639080, 181080, 120

Offset: 0

Emeric Deutsch, May 07 2010

Row n contains 1 + floor(n/4) entries.

Sum of entries in row n = n! (A000142).

			T(9,2)=3 because we have (1234)(5678)(9), (1234)(5)(6789), and (1)(2345)(6789).
Triangle starts:
     1;
     1;
     2;
     6;
    23,  1;
   118,  2;
   714,  6;
  5016, 24;

Seiichi Manyama, Rows n = 0..200, flattened
R. A. Brualdi and E. Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Columns k=0-3 give A177253, A369098, A370652, A370653.
Cf. A000166, A008290, A177248, A177249, A177250, A177251.
Cf. A000142 (row sums).

A177252:= func< n,k | (&+[(-1)^j*Factorial(n-3*k-3*j)/(Factorial(k) *Factorial(j)): j in [0..Floor((n-4*k)/4)]]) >;
[A177252(n,k): k in [0..Floor(n/4)], n in [0..20]]; // G. C. Greubel, Apr 28 2024

T := proc (n, k) options operator, arrow: sum((-1)^(k+j)*binomial(j, k)*factorial(n-3*j)/factorial(j), j = 0 .. floor((1/4)*n)) end proc: for n from 0 to 15 do seq(T(n, k), k = 0 .. floor((1/4)*n)) end do; % yields sequence in triangular form

T[n_, k_]:= T[n, k]= Sum[(-1)^(k+j)*Binomial[j,k]*(n-3 j)!/j!, {j,0,n/4}];
Table[T[n, k], {n, 0, 15}, {k, 0, n/4}] // Flatten (* Jean-François Alcover, Nov 17 2017 *)

def A177252(n,k): return sum((-1)^j*factorial(n-3*k-3*j)/(factorial(k) *factorial(j)) for j in range(1+(n-4*k)//4))
flatten([[A177252(n,k) for k in range(1+n//4)] for n in range(21)]) # G. C. Greubel, Apr 28 2024

T(n,k) = Sum_{j=0..floor(n/4)} (-1)^(k+j)*binomial(j,k)*(n-3*j)!/j!.
T(n,0) = A177253(n).
Sum_{k>=0} k*T(n,k) = (n-3)! (n >= 4).
G.f. of column k: (1/k!) * Sum_{j>=k} j! * x^(j+3*k) / (1+x^4)^(j+1). - Seiichi Manyama, Feb 24 2024

A177253 Number of permutations of [n] having no adjacent 4-cycles, i.e., no cycles of the form (i, i+1, i+2, i+3).

Original entry on oeis.org

1, 1, 2, 6, 23, 118, 714, 5016, 40201, 362163, 3623772, 39876540, 478639079, 6223394516, 87138394540, 1307195547720, 20916564680761, 355600269756485, 6401066270800350, 121624180731849810, 2432546364331038479, 51084540451761077514, 1123879093137556106358

Offset: 0

Emeric Deutsch, May 07 2010

nonn

			a(5)=118 because the only permutations of {1,2,3,4,5} having adjacent 4-cycles are (1234)(5) and (1)(2345).

Seiichi Manyama, Table of n, a(n) for n = 0..449
Richard A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Cf. A000166, A008290, A177248, A177249, A177250, A177251, A177252.

[(&+[(-1)^j*Factorial(n-3*j)/Factorial(j): j in [0..Floor(n/4)]]): n in [0..30]]; // G. C. Greubel, May 11 2024

a := proc (n) options operator, arrow: sum((-1)^j*factorial(n-3*j)/factorial(j), j = 0 .. floor((1/4)*n)) end proc: seq(a(n), n = 0 .. 22);

a[n_] := Sum[(-1)^j*(n - 3*j)!/j!, {j, 0, n/4}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 20 2017 *)

[sum((-1)^j*factorial(n-3*j)/factorial(j) for j in range(1+n//4)) for n in range(31)] # G. C. Greubel, May 11 2024

a(n) = Sum_{j=0..floor(n/4)} (-1)^j*(n-3*j)!/j!.
a(n) - n*a(n-1) = 3*a(n-4) + 4*(-1)^{n/4} if 4|n otherwise a(n) - n*a(n-1) = 3*a(n-4).
a(n) = A177252(n,0).
limit_{n->oo} a(n)/n! = 1.
The o.g.f. g(z) satisfies z^2*(1+z^4)*g'(z) - (1+z^4)(1-z-3z^4)g(z) + 1 - 3z^4 = 0; g(0)=1.
D-finite with recurrence a(n) = n*a(n-1) + 2*a(n-4) + (n-4)*a(n-5) + 3*a(n-8). - R. J. Mathar, Jul 26 2022
G.f.: Sum_{k>=0} k! * x^k / (1+x^4)^(k+1). - Seiichi Manyama, Feb 20 2024

Crossreferences corrected by Emeric Deutsch, May 09 2010

A370528 Number of permutations of [n] having exactly two adjacent 3-cycles.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 3, 12, 57, 348, 2460, 19806, 178950, 1794420, 19778210, 237696420, 3093642300, 43350548655, 650733622665, 10417925247240, 177191430300339, 3190747212651432, 60645032890871688, 1213255040678034508, 25484737348664027532, 560785511736390349080

Offset: 0

Seiichi Manyama, Feb 21 2024

nonn

G. C. Greubel, Table of n, a(n) for n = 0..450
R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Column k=2 of A177250.

Cf. A177251, A370525, A370530.

[n le 5 select 0 else (&+[(-1)^k*Factorial(n-2*k-4)/Factorial(k): k in [0..Floor((n-6)/3)]])/2: n in [0..30]]; // G. C. Greubel, May 01 2024

Table[Sum[(-1)^k*(n-2*k-4)!/k!, {k,0,Floor[(n-6)/3]}]/2, {n,0,30}] (* G. C. Greubel, May 01 2024 *)

my(N=30, x='x+O('x^N)); concat([0, 0, 0, 0, 0, 0], Vec(sum(k=2, N, k!*x^(k+4)/(1+x^3)^(k+1))/2))

a(n, k=2, q=3) = sum(j=0, n\q-k, (-1)^j*(n-(q-1)*(j+k))!/j!)/k!;

[sum((-1)^k*factorial(n-2*k-4)/factorial(k) for k in range(1+(n-6)//3))/2 for n in range(31)] # G. C. Greubel, May 01 2024

G.f.: (1/2) * Sum_{k>=2} k! * x^(k+4) / (1+x^3)^(k+1).

a(n) = (1/2) * Sum_{k=0..floor(n/3)-2} (-1)^k * (n-2*k-4)! / k!.

A370530 Number of permutations of [n] having exactly three adjacent 3-cycles.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 20, 116, 820, 6600, 59650, 598140, 6592740, 79232140, 1031214100, 14450182880, 216911207555, 3472641749080, 59063810100120, 1063582404217144, 20215010963623896, 404418346892678160, 8494912449554675844, 186928503912130116360

Offset: 0

Seiichi Manyama, Feb 21 2024

nonn

G. C. Greubel, Table of n, a(n) for n = 0..450
R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Column k=3 of A177250.

Cf. A177251, A370525, A370528.

[n le 8 select 0 else (&+[(-1)^k*Factorial(n-2*k-6)/Factorial(k): k in [0..Floor((n-9)/3)]])/6: n in [0..30]]; // G. C. Greubel, May 01 2024

Table[Sum[(-1)^k*(n-2*k-6)!/k!, {k,0,Floor[(n-9)/3]}]/6, {n,0,30}] (* G. C. Greubel, May 01 2024 *)

my(N=30, x='x+O('x^N)); concat([0, 0, 0, 0, 0, 0, 0, 0, 0], Vec(sum(k=3, N, k!*x^(k+6)/(1+x^3)^(k+1))/6))

a(n, k=3, q=3) = sum(j=0, n\q-k, (-1)^j*(n-(q-1)*(j+k))!/j!)/k!;

[sum((-1)^k*factorial(n-2*k-6)/factorial(k) for k in range(1+(n-9)//3))/6 for n in range(31)] # G. C. Greubel, May 01 2024

G.f.: (1/6) * Sum_{k>=3} k! * x^(k+6) / (1+x^3)^(k+1).

a(n) = (1/6) * Sum_{k=0..floor(n/3)-3} (-1)^k * (n-2*k-6)! / k!.

A370525 Number of permutations of [n] having exactly one adjacent 3-cycle.

Original entry on oeis.org

0, 0, 0, 1, 2, 6, 22, 114, 696, 4923, 39612, 357900, 3588836, 39556420, 475392840, 6187284605, 86701097310, 1301467245330, 20835850494474, 354382860600678, 6381494425302864, 121290065781743383, 2426510081356069016, 50969474697328055064, 1121571023472780698152

Offset: 0

Seiichi Manyama, Feb 21 2024

nonn

R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Column k=3 of A370527.
Column k=1 of A177250.
Cf. A177251, A370528, A370530.

my(N=30, x='x+O('x^N)); concat([0, 0, 0], Vec(sum(k=1, N, k!*x^(k+2)/(1+x^3)^(k+1))))

a(n, k=1, q=3) = sum(j=0, n\q-k, (-1)^j*(n-(q-1)*(j+k))!/j!)/k!;

G.f.: Sum_{k>=1} k! * x^(k+2) / (1+x^3)^(k+1).

a(n) = Sum_{k=0..floor(n/3)-1} (-1)^k * (n-2*k-2)! / k!.

A370527 Triangle read by rows: T(n,k) = number of permutations of [n] having exactly one adjacent k-cycle. (n>=1, 1<=k<=n).

Original entry on oeis.org

1, 0, 1, 3, 2, 1, 8, 4, 2, 1, 45, 18, 6, 2, 1, 264, 99, 22, 6, 2, 1, 1855, 612, 114, 24, 6, 2, 1, 14832, 4376, 696, 118, 24, 6, 2, 1, 133497, 35620, 4923, 714, 120, 24, 6, 2, 1, 1334960, 324965, 39612, 5016, 718, 120, 24, 6, 2, 1, 14684571, 3285270, 357900, 40200, 5034, 720, 120, 24, 6, 2, 1

Offset: 1

Seiichi Manyama, Feb 21 2024

			Triangle starts:
      1;
      0,    1;
      3,    2,   1;
      8,    4,   2,   1;
     45,   18,   6,   2,  1;
    264,   99,  22,   6,  2, 1;
   1855,  612, 114,  24,  6, 2, 1;
  14832, 4376, 696, 118, 24, 6, 2, 1;

R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Columns k=1..4 give A000240, A370524, A370525, A369098.

Cf. A008290, A177248, A177250, A177252.

T(n, k) = sum(j=0, n\k-1, (-1)^j*(n-(k-1)*(j+1))!/j!);

G.f. of column k: Sum_{j>=1} j! * x^(j+k-1) / (1+x^k)^(j+1).

T(n,k) = Sum_{j=0..floor(n/k)-1} (-1)^j * (n-(k-1)*(j+1))! / j!.

cp's OEIS Frontend

A177251 Number of permutations of [n] having no adjacent 3-cycles, i.e., no cycles of the form (i, i+1, i+2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A177249 Number of permutations of [n] having no adjacent transpositions, that is, no cycles of the form (i, i+1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A177248 Triangle read by rows: T(n,k) is the number of permutations of [n] having k adjacent transpositions (0 <= k <= floor(n/2)). An adjacent transposition is a cycle of the form (i, i+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A177252 Triangle read by rows: T(n,k) is the number of permutations of [n] having k adjacent 4-cycles (0 <= k <= floor(n/4)), i.e., having k cycles of the form (i, i+1, i+2, i+3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A177253 Number of permutations of [n] having no adjacent 4-cycles, i.e., no cycles of the form (i, i+1, i+2, i+3).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A370528 Number of permutations of [n] having exactly two adjacent 3-cycles.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica