A158005 -id:A158005 - cp's OEIS frontend

A217057 Number of permutations in S_n containing exactly one increasing subsequence of length 4.

0, 0, 0, 0, 1, 12, 102, 770, 5545, 39220, 276144, 1948212, 13817680, 98679990, 710108396, 5150076076, 37641647410, 277202062666, 2056218941678, 15358296210724, 115469557503753, 873561194459596, 6647760790457218, 50871527629923754, 391345137795371013

Offset: 0

Alois P. Heinz, Sep 25 2012

nonn

			a(4) = 1: 1234.
a(5) = 12: 12453, 12534, 13425, 13452, 14235, 15234, 23145, 23415, 23451, 31245, 41235, 51234.

Brian Nakamura and Doron Zeilberger, Table of n, a(n) for n = 0..70
Andrew R. Conway and Anthony J. Guttmann, Counting occurrences of patterns in permutations, arXiv:2306.12682 [math.CO], 2023. See p. 16.
Brian Nakamura and Doron Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes; Local copy, pdf file only, no active links
Brian Nakamura and Doron Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes, arXiv preprint arXiv:1209.2353, 2012.
Wikipedia, Enumerations of specific permutation classes
Wikipedia, Subsequence

Cf. A005802, A117158, A158005, A214015, A214152.

# programs can be obtained from the Nakamura & Zeilberger link.

A158432 Number of permutations of 1..n containing the relative rank sequence { 45312 } at any spacing.

Original entry on oeis.org

1, 26, 458, 6996, 101072, 1438112, 20598112, 300892896, 4521034917, 70286670034, 1135485759114, 19121776482564, 336412530327804, 6191800556586104, 119301546930406184, 2406376964044265344, 50786085223779295344, 1120447461653440780128, 25810064637612342838624

Offset: 5

R. H. Hardin, Mar 18 2009

nonn

Same series for 54321 12345 45321 21345 12354 54312 34521 32145 12543 54123 23451 43215 15432 51234 21354 34512 32154 21543 45123.

Alois P. Heinz, Table of n, a(n) for n = 5..200
Eric Weisstein's World of Mathematics, Permutation Pattern

Cf. A000142, A047889, A056986, A158005, A214015, A214152.

h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
      +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                 add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
a:= n-> n! -g(n, 4, []):
seq(a(n), n=5..25);  # Alois P. Heinz, Jul 05 2012
# second Maple program
a:= proc(n) option remember; `if`(n<5, 0, `if`(n=5, 1,
     ((132-142*n-301*n^2-35*n^3+25*n^4+n^5)*a(n-1)
     -2*(10*n^3+33*n^2-181*n-2)*(n-1)^2*a(n-2)
     +64*(n-2)^2*(n-1)^3*a(n-3))/ ((n+4)*(n-5)*(n+3)^2)))
    end:
seq(a(n), n=5..30);  # Alois P. Heinz, Sep 26 2012

h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]!/Product[Product[1+l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := If[n == 0 || i === 1, h[Join[l, Array[1 &, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i - 1, Join[l, Array[i &, j]]], {j, 0, n/i}]]];
a[n_] := n! - g[n, 4, {}];
Table[a[n], {n, 5, 25}] (* Jean-François Alcover, Jun 19 2018, after Alois P. Heinz's first program *)

a(n) = A214152(n,5) = A000142(n)-A047889(n) = A000142(n)-A214015(n,4).

Extended beyond a(16) by Alois P. Heinz, Jul 05 2012

A159139 Number of permutations of 1..n containing the relative rank sequence { 213465 } at any spacing.

Original entry on oeis.org

1, 37, 891, 18043, 337210, 6081686, 108469917, 1941309261, 35187952132, 649951312000, 12286366975723, 238445927000811, 4762398793018878, 98074791689121162, 2085684931155975120, 45859509146309390064, 1043533983233372354613, 24590543663448304800169

Offset: 6

R. H. Hardin, Apr 05 2009

nonn

Same series for 654321 123456 564321 213456 123465 654312 456321 321456 123654 654123 345621 432156 126543 651234 564312 456312 321465 213654 564123 345612 432165 216543 561234 234561 543216 165432 612345 456123 321654.

Alois P. Heinz, Table of n, a(n) for n = 6..200
Eric Weisstein's World of Mathematics, Permutation Pattern

Cf. A000142, A047890, A056986, A158005, A158423, A214015, A214152.

h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
      +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= proc(n, i, l)
      `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
       add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i)))
    end:
a:= n-> n! -g(n, 5, []):
seq(a(n), n=6..30);  # Alois P. Heinz, Jul 05 2012
# second Maple program
a:= proc(n) option remember; `if`(n<6, 0, `if`(n=6, 1,
     ((2475-4819*n^2-2985*n+175*n^4-1021*n^3+n^6+49*n^5)*a(n-1)
     -(35*n^4+441*n^3-845*n^2-4147*n-489)*(n-1)^2*a(n-2)
     +(-1668+329*n+259*n^2)*(n-1)^2*(n-2)^2*a(n-3)
     -225*(n-1)^2*(n-2)^2*(n-3)^2*a(n-4))/ ((n-6)*(n+6)^2*(n+4)^2)))
    end:
seq(a(n), n=6..30);  # Alois P. Heinz, Sep 26 2012

h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]!/Product[Product[1+l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := If[n == 0 || i === 1, h[Join[l, Array[1 &, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i - 1, Join[l, Array[i &, j]]], {j, 0, n/i}]]];
a[n_] := n! - g[n, 5, {}];
Table[a[n], {n, 6, 30}] (* Jean-François Alcover, Jun 19 2018, from first Maple program *)

a(n) = A214152(n,6) = A000142(n)-A047890(n) = A000142(n)-A214015(n,5). - Alois P. Heinz, Jul 05 2012

More terms from Alois P. Heinz, Jul 05 2012

A159175 Number of permutations of 1..n containing the relative rank sequence { 1234567 } at any spacing.

Original entry on oeis.org

1, 50, 1578, 40884, 958809, 21353634, 463945294, 9996042284, 215831724525, 4702905606350, 103912444955422, 2336099774748540, 53567906041439136, 1255172323669315848, 30095426182382305848, 739238316780966277616, 18619024923770934306358, 481234428294016650524172

Offset: 7

R. H. Hardin Apr 05 2009

nonn

Same series (among rank sequences with inversion = reversal) for 3214765 2134576.

Alois P. Heinz, Table of n, a(n) for n = 7..200
Eric Weisstein's World of Mathematics, Permutation Pattern

Cf. A000142, A052399, A056986, A158005, A158423, A214015, A214152.

h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
      +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                 add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
a:= n-> n! -g(n, 6, []):
seq(a(n), n=7..25);  # Alois P. Heinz, Jul 05 2012
# second Maple program
a:= proc(n) option remember; `if`(n<7, 0, `if`(n=7, 1, ((-93464*n+1072*n^4
      +72128-125284*n^2+84*n^6+994*n^5-30491*n^3+n^7) *a(n-1)
      -4*(14*n^5+399*n^4+1124*n^3-7354*n^2-23983*n-5042)*(n-1)^2 *a(n-2)
      +4*(-7359-2629*n+1596*n^2+196*n^3)*(n-1)^2*(n-2)^2 *a(n-3)
      -1152*(1+2*n)*(n-1)^2*(n-2)^2*(n-3)^2 *a(n-4))/
       ((n-7)*(n+9)*(n+8)^2*(n+5)^2)))
    end:
seq(a(n), n=7..30);  # Alois P. Heinz, Sep 27 2012

h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]!/Product[Product[1+l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := If[n == 0 || i === 1, h[Join[l, Array[1 &, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i - 1, Join[l, Array[i &, j]]], {j, 0, n/i}]]];
a[n_] := n! - g[n, 6, {}];
Table[a[n], {n, 7, 25}] (* Jean-François Alcover, Jun 19 2018, from first Maple program *)

a(n) = A214152(n,7) = A000142(n)-A052399(n) = A000142(n)-A214015(n,6). - Alois P. Heinz, Jul 05 2012

Extended beyond a(16) by Alois P. Heinz, Jul 05 2012

A158434 Number of permutations of 1..n containing the relative rank sequence { 51342 } at any spacing.

Original entry on oeis.org

1, 26, 460, 7068, 102676, 1466870, 21055493, 307660035, 4616675543, 71598646435, 1153132523804

Offset: 5

R. H. Hardin, Mar 18 2009

Same series for 25341, 41325, 14352, 52314, 24315, 42351, 15324.

Eric Weisstein's World of Mathematics, Permutation Pattern

Cf. A000142, A056986, A158005, A256200.

a(n) = n! - A256200(n). - Alois P. Heinz, May 19 2020

A158424 Number of permutations of 1..n containing the relative rank sequence { 41235 } at any spacing.

Original entry on oeis.org

1, 26, 459, 7037, 102075, 1457407, 20922336, 305907060, 4594540541, 71326622649, 1149849718045

Offset: 5

R. H. Hardin Mar 18 2009

nonn

Same series for 43251 23415 15234 51432 25431 13452 53214

Eric Weisstein's World of Mathematics, Permutation Pattern

A056986 A158005

A158425 Number of permutations of 1..n containing the relative rank sequence { 41352 } at any spacing.

Original entry on oeis.org

1, 26, 462, 7136, 104123, 1491822, 21438666, 313144000, 4691684510, 72594030500

Offset: 5

R. H. Hardin Mar 18 2009

nonn

Same series for 25314

Eric Weisstein's World of Mathematics, Permutation Pattern

A056986 A158005

A158426 Number of permutations of 1..n containing the relative rank sequence { 41523 } at any spacing.

Original entry on oeis.org

1, 26, 460, 7071, 102788, 1469419, 21101676, 308396208, 4627521637, 71750494216, 1155187096545

Offset: 5

R. H. Hardin Mar 18 2009

nonn

Same series for 32514 34152 25143 24513 42153 31542 35124

Eric Weisstein's World of Mathematics, Permutation Pattern

A056986 A158005

A158427 Number of permutations of 1..n containing the relative rank sequence { 41532 } at any spacing.

Original entry on oeis.org

1, 26, 461, 7102, 103397, 1479242, 21244523, 310353510, 4653395194, 72084982176, 1159451127978

Offset: 5

R. H. Hardin Mar 18 2009

nonn

Same series for 35214 31452 41253 25413 23514 43152 25134

Eric Weisstein's World of Mathematics, Permutation Pattern

A056986 A158005

A158428 Number of permutations of 1..n containing the relative rank sequence { 42513 } at any spacing.

Original entry on oeis.org

1, 26, 461, 7104, 103479, 1481275, 21284288, 311031666, 4663993186, 72241115375, 1161657944287

Offset: 5

R. H. Hardin Mar 18 2009

nonn

Same series for 24153 31524 35142

Eric Weisstein's World of Mathematics, Permutation Pattern

A056986 A158005

cp's OEIS Frontend

A217057 Number of permutations in S_n containing exactly one increasing subsequence of length 4.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A158432 Number of permutations of 1..n containing the relative rank sequence { 45312 } at any spacing.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A159139 Number of permutations of 1..n containing the relative rank sequence { 213465 } at any spacing.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A159175 Number of permutations of 1..n containing the relative rank sequence { 1234567 } at any spacing.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A158434 Number of permutations of 1..n containing the relative rank sequence { 51342 } at any spacing.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A158424 Number of permutations of 1..n containing the relative rank sequence { 41235 } at any spacing.

Views

Author

Keywords

Comments

Links

Crossrefs

A158425 Number of permutations of 1..n containing the relative rank sequence { 41352 } at any spacing.

Views

Author

Keywords

Comments

Links

Crossrefs

A158426 Number of permutations of 1..n containing the relative rank sequence { 41523 } at any spacing.

Views

Author

Keywords

Comments

Links

Crossrefs

A158427 Number of permutations of 1..n containing the relative rank sequence { 41532 } at any spacing.

Views

Author

Keywords

Comments