A047889 -id:A047889 - cp's OEIS frontend

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

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

A072167 T_10(n) in the notation of Bergeron et al., u_10(n) in the notation of Gessel: Related to Young tableaux of bounded height.

Original entry on oeis.org

1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916799, 479001478, 6227012074, 87177809092, 1307651456625, 20921799763626, 355647213494682, 6400805686152436, 121585553747301448, 2430677026538811240

Offset: 1

Jesse Carlsson (j.carlsson(AT)physics.unimelb.edu.au), Jun 29 2002

nonn

In general, column k > 1 of A214015 is asymptotic to (Product_{j=1..k} j!) * k^(2*n + k^2/2) / (Pi^((k-1)/2) * 2^((k-1)*(k+2)/2) * n^((k^2-1)/2)). - Vaclav Kotesovec, Sep 10 2014

Vaclav Kotesovec, Table of n, a(n) for n = 1..500
F. Bergeron and F. Gascon, Counting Young tableaux of bounded height, J. Integer Sequences, Vol. 3 (2000), #00.1.7.
Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r, arXiv:1504.02513 [math.CO], 2015.
Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285.
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.

Cf. A052399 for T_6(n), A047890 for T_5(n), A047889 for T_4(n).

Column k=10 of A214015.

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) option remember;
      `if`(n=0, h(l)^2, `if`(i<1, 0, `if`(i=1, h([l[], 1$n])^2,
       g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i, [l[], i])))))
    end:
a:= n-> g(n, 10, []):
seq(a(n), n=0..25); # Vaclav Kotesovec, Sep 10 2014, after Alois P. Heinz

RecurrenceTable[{-7372800*(-4 + n)^2*(-3 + n)^2*(-2 + n)^2*(-1 + n)^2*(15 + 2*n)*a[-5 + n] + 256*(-3 + n)^2*(-2 + n)^2*(-1 + n)^2*(11018760 + 4743323*n + 577824*n^2 + 21076*n^3)*a[-4 + n]-8*(-2 + n)^2*(-1 + n)^2*(2488711560 + 2208119423*n + 580006399*n^2 + 64938154*n^3 + 3273732*n^4 + 61160*n^5)*a[-3 + n] + 4*(-1 + n)^2*(8002290720 + 21962910556*n + 10433770264*n^2 + 2088552609*n^3 + 215646686*n^4 + 12084237*n^5 + 349536*n^6 + 4092*n^7)*a[-2 + n]-2*(-45705600000 + 64584000000*n + 68412531600*n^2 + 22314826244*n^3 + 3672058745*n^4 + 350428790*n^5 + 20286926*n^6 + 704088*n^7 + 13497*n^8 + 110*n^9)*a[-1 + n] + (9 + n)^2*(16 + n)^2*(21 + n)^2*(24 + n)^2*(25 + n)*a[n]==0,a[1]==1,a[2]==2,a[3]==6,a[4]==24,a[5]==120},a,{n,1,20}] (* Vaclav Kotesovec, Sep 10 2014 *)

a(n) ~ 546852789 * 2^(2*n + 26)* 5^(2*n + 55) / (n^(99/2) * Pi^(9/2)). - Vaclav Kotesovec, Sep 10 2014

Recurrence: (n+9)^2*(n + 16)^2*(n + 21)^2*(n + 24)^2*(n + 25)*a(n) = 2*(110*n^9 + 13497*n^8 + 704088*n^7 + 20286926*n^6 + 350428790*n^5 + 3672058745*n^4 + 22314826244*n^3 + 68412531600*n^2 + 64584000000*n - 45705600000)*a(n-1) - 4*(n-1)^2*(4092*n^7 + 349536*n^6 + 12084237*n^5 + 215646686*n^4 + 2088552609*n^3 + 10433770264*n^2 + 21962910556*n + 8002290720)*a(n-2) + 8*(n-2)^2*(n-1)^2*(61160*n^5 + 3273732*n^4 + 64938154*n^3 + 580006399*n^2 + 2208119423*n + 2488711560)*a(n-3) - 256*(n-3)^2*(n-2)^2*(n-1)^2*(21076*n^3 + 577824*n^2 + 4743323*n + 11018760)*a(n-4) + 7372800*(n-4)^2*(n-3)^2*(n-2)^2*(n-1)^2*(2*n + 15)*a(n-5). - Vaclav Kotesovec, Sep 10 2014

A141824 Antidiagonals of table A047888 (which counts longest increasing subsequences and pattern avoidances).

Original entry on oeis.org

1, 2, 4, 9, 24, 75, 269, 1095, 5039, 26084, 150356, 952526, 6553011, 48553418, 385693800, 3277413802, 29741002168, 287555932433, 2952769116993, 32079033571080, 367336668735826, 4419518218479215, 55733223965845539, 735448682261126767, 10142738983005750681

Offset: 1

Alford Arnold, Jul 08 2008

nonn

Note that:
A000108 avoids string "123"
A005808 avoids string "1234"
A047889 avoids string "12345"
Note also that the left half and central diagonal of A047888 are partial sums of table A047874.

			We can write A141824(n) = 1 2 4 9 24 ... because A047888 begins
  1;
  1,  1;
  1,  2,  1;
  1,  5,  2,  1;
  1, 14,  6,  2,  1;
etc.

Cf. A000108 (Catalan numbers), A005808, A047889, A047874.

a(12)-a(25) from Alois P. Heinz, Apr 10 2012

A256200 Number of permutations in S_n that avoid the pattern 42351.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4580, 33252, 260204, 2161930, 18861307, 171341565, 1610345257, 15579644765, 154541844196, 1566713947713, 16190122718865, 170171678529883, 1816001425551270, 19646035298044543, 215179180467834605, 2383465957654163227, 26673704385975326866

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..27
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952, A158434.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {4, 2, 3, 5, 1}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

a(n) = n! - A158434(n). - Andrew Howroyd, May 18 2020

a(14)-a(15) added by Andrew Howroyd, May 18 2020

More terms from Anthony Guttmann, Sep 29 2021

A224248 Number of permutations in S_n containing exactly one increasing subsequence of length 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 20, 270, 3142, 34291, 364462, 3844051, 40632886, 432715409, 4655417038, 50667480496, 558143676522, 6223527776874, 70228214538096, 801705888742781, 9254554670121572, 107975393459449243, 1272651313142352772, 15145990284267530992

Offset: 0

Brian Nakamura, Apr 02 2013

nonn

B. Nakamura and D. Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes, Adv. in Appl. Math. 50 (2013), 356-366.

B. Nakamura and D. Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes

Cf. A047889, A217057.

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

A248900 Number of permutations of [n] avoiding patterns 2431 and 54321.

Original entry on oeis.org

1, 1, 2, 6, 23, 102, 492, 2492, 13003, 69172, 372963, 2031174, 11148948, 61588814, 342068774, 1908740089, 10694374242, 60137305751, 339276548456, 1919787554118, 10892575241125, 61957028188350, 353224194632459, 2018076850631391, 11552829351121139, 66259093178740462

Offset: 0

Nathaniel Shar, Mar 06 2015

nonn

			a(4) = 23 because all permutations of length 4 except 2431 lie in this set.

Nathaniel Shar, Table of n, a(n) for n = 0..80
Nathaniel Shar, Maple code

Cf. A022558, A047889.

A256196 Number of permutations in S_n that avoid the pattern 31524.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4579, 33216, 259401, 2147525, 18632512, 167969934, 1563027614, 14937175825, 146016423713, 1455402205257, 14753501614541, 151783381341695, 1582029822426003, 16681492660789425, 177726496203056670, 1911230701872865231, 20726637978574528119

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..25
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {3, 1, 5, 2, 4}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

a(14)-a(16) from Bert Dobbelaere, Mar 18 2021

More terms from Anthony Guttmann, Sep 29 2021

A256197 Number of permutations in S_n that avoid the pattern 35214.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4579, 33218, 259483, 2149558, 18672277, 168648090, 1573625606, 15093309024, 148223240022, 1485673163882, 15159644212775, 157142812302992, 1651865171372967, 17582693993265148, 189269329080075275, 2058215511081891400, 22589841589522026553

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..26
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {3, 5, 2, 1, 4}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

More terms from Anthony Guttmann, Sep 29 2021

A256198 Number of permutations in S_n that avoid the pattern 35124.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4580, 33249, 260092, 2159381, 18815124, 170605392, 1599499163, 15427796984, 152487271455, 1539554179950, 15836801521762, 165625811815111, 1757953168747511, 18908510233855411, 205838673911323648, 2265393020812413370, 25182471016157568626

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..27
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {3, 5, 1, 2, 4}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

More terms from Anthony Guttmann, Sep 29 2021

A256199 Number of permutations in S_n that avoid the pattern 53124.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 694, 4580, 33252, 260202, 2161837, 18858720, 171285237, 1609282391, 15561356705, 154246419725, 1562151687940, 16121960812335, 169178376076607, 1801800479418116, 19446010522240384, 212394673429250090, 2345064355131025130, 26148064110299271293

Offset: 0

N. J. A. Sloane, Mar 19 2015

nonn

Anthony Guttmann, Table of n, a(n) for n = 0..25
Nathan Clisby, Andrew R. Conway, Anthony J. Guttmann, Yuma Inoue, Classical length-5 pattern-avoiding permutations, arXiv:2109.13485 [math.CO], 2021.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001.

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208.

Cf. A099952.

avoid[n_, pat_] := Module[{p1 = pat[[1]], p2 = pat[[2]], p3 = pat[[3]], p4 = pat[[4]], p5 = pat[[5]], lseq = {}, i, p,
    lpat = Subsets[(n + 1) - Range[n], {Length[pat]}],
    psn = Permutations[Range[n]]},
   For[i = 1, i <= Length[lpat], i++,
    p = lpat[[i]];
    AppendTo[lseq, Select[psn, MemberQ[#, {_, p[[p1]], _, p[[p2]], _, p[[p3]], _, p[[p4]], _, p[[p5]], _}, {0}] &]];
    ]; n! - Length[Union[Flatten[lseq, 1]]]];
Table[avoid[n, {5, 3, 1, 2, 4}], {n, 0, 8}]  (* Robert Price, Mar 27 2020 *)

More terms from Anthony Guttmann, Sep 29 2021

cp's OEIS Frontend

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

A072167 T_10(n) in the notation of Bergeron et al., u_10(n) in the notation of Gessel: Related to Young tableaux of bounded height.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A141824 Antidiagonals of table A047888 (which counts longest increasing subsequences and pattern avoidances).

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A256200 Number of permutations in S_n that avoid the pattern 42351.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A224248 Number of permutations in S_n containing exactly one increasing subsequence of length 5.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

A248900 Number of permutations of [n] avoiding patterns 2431 and 54321.

Views

Author

Keywords

Examples

Links

Crossrefs

A256196 Number of permutations in S_n that avoid the pattern 31524.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A256197 Number of permutations in S_n that avoid the pattern 35214.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A256198 Number of permutations in S_n that avoid the pattern 35124.

Views

Author

Keywords