A214152 -id:A214152 - cp's OEIS frontend

A056986 Number of permutations on {1,...,n} containing any given pattern alpha in the symmetric group S_3.

0, 0, 1, 10, 78, 588, 4611, 38890, 358018, 3612004, 39858014, 478793588, 6226277900, 87175616760, 1307664673155, 20922754530330, 355687298451210, 6402373228089300, 121645098641568810, 2432902001612519580, 51090942147243172980, 1124000727686125116360

Offset: 1

Eric W. Weisstein

This is well-defined because for all patterns alpha in S_3 the number of permutations in S_n avoiding alpha is the same (the Catalan numbers). - Emeric Deutsch, May 05 2008

			a(4) = 10 because, taking, for example, the pattern alpha=321, we have 3214, 3241, 1432, 2431, 3421, 4213, 4132, 4231, 4312 and 4321.

Alois P. Heinz, Table of n, a(n) for n = 1..170
FindStat - Combinatorial Statistic Finder, The number of occurrences of the pattern [1,2,3] inside a permutation of length at least 3, The number of occurrences of the pattern [1,3,2] in a permutation, The number of occurrences of the pattern [2,1,3] in a permutation, The number of occurrences of the pattern [2,3,1] in a permutation, The number of occurrences of the pattern [3,1,2] in a permutation
R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin., 6, pp. 383-406, 1985.
Eric Weisstein's World of Mathematics, Permutation Pattern

Cf. A000108, A000142, A138159, A214015, A214152.

A056986:= func< n | Factorial(n) - Catalan(n) >;
[A056986(n): n in [1..30]]; // G. C. Greubel, Oct 06 2024

a:= n-> n! -binomial(2*n, n)/(n+1):
seq(a(n), n=1..25);  # Alois P. Heinz, Jul 05 2012

Mathematica
```
Table[n! -CatalanNumber[n], {n,30}]
```

a(n)=n!-binomial(n+n,n+1)/n \\ Charles R Greathouse IV, Jun 10 2011

def A056986(n): return factorial(n) - catalan_number(n)
[A056986(n) for n in range(1,31)] # G. C. Greubel, Oct 06 2024

From Alois P. Heinz, Jul 05 2012: (Start)
a(n) = A214152(n, 3).
a(n) = A000142(n) - A000108(n).
a(n) = A000142(n) - A214015(n, 2). (End)
E.g.f.: 1/(1 - x) - exp(2*x)*(BesselI(0,2*x) - BesselI(1,2*x)). - Ilya Gutkovskiy, Jan 21 2017

A158005 Numbers of pattern-matching permutations of (1234) for the permutations of {1, 2, ..., n} on n = 4, 5, 6, ... elements.

Original entry on oeis.org

1, 17, 207, 2279, 24553, 268521, 3042210, 36153510, 454208895, 6059942223, 86030083110, 1299647574882, 20865826165777, 355277740280849, 6399391841784282, 121623163346687166, 2432739049821421911, 51089720946192154791, 1123991502048375026337

Offset: 4

Eric W. Weisstein, Mar 11 2009

nonn

Same series for 1243 1432 2134 2143 4123 3214 3412 2341 3421 4321 4312. - R. H. Hardin, Mar 15 2009

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

Cf. A000142, A005802, 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, 3, []):
seq(a(n), n=4..30);  # Alois P. Heinz, Jul 05 2012
# second Maple program
a:= proc(n) option remember; `if`(n<3, 0, `if`(n=4, 1,
      ((13-11*n-40*n^2+10*n^3+n^4)*a(n-1) -(10*n^2-9*n-31)*(n-1)^2*a(n-2)
       +9*(n-1)^2*(n-2)^2*a(n-3)) / ((n-4)*(n+2)^2)))
    end:
seq(a(n), n=4..30);  # Alois P. Heinz, Sep 26 2012

a[2] = a[3] = 0; a[4] = 1; a[n_] := a[n] = (1/((n-4)*(n+2)^2))* (9*(n-2)^2*a[n-3]*(n-1)^2 - (10*n^2 - 9*n - 31)*a[n-2]*(n-1)^2 + (n^4 + 10*n^3 - 40*n^2 - 11*n + 13)*a[n-1]); Table[a[n], {n, 4, 22}] (* Jean-François Alcover, Oct 22 2012, after Alois P. Heinz *)

a(n) = A214152(n,4) = A000142(n) - A005802(n) = A000142(n) - A214015(n,3). - Alois P. Heinz, Jul 05 2012

More terms from R. H. Hardin, Mar 15 2009
Two more terms from Vladeta Jovovic, Aug 17 2009
Corrected a(19)-a(20) and extended by Alois P. Heinz, Jul 05 2012

A214015 Number of permutations A(n,k) in S_n with longest increasing subsequence of length <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 5, 1, 0, 1, 1, 2, 6, 14, 1, 0, 1, 1, 2, 6, 23, 42, 1, 0, 1, 1, 2, 6, 24, 103, 132, 1, 0, 1, 1, 2, 6, 24, 119, 513, 429, 1, 0, 1, 1, 2, 6, 24, 120, 694, 2761, 1430, 1, 0, 1, 1, 2, 6, 24, 120, 719, 4582, 15767, 4862, 1, 0

Offset: 0

Alois P. Heinz, Jul 01 2012

A(n,k) is also the sum of the squares of numbers of standard Young tableaux (SYT) of height <= k over all partitions of n.
This array is a larger and reflected version of A047888.
Column k>1 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

			A(4,2) = 14 because 14 permutations of {1,2,3,4} do not contain an increasing subsequence of length > 2: 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312, 4321.  Permutation 1423 is not counted because it contains the noncontiguous increasing subsequence 123.
A(4,2) = 14 = 2^2 + 3^2 + 1^2 because the partitions of 4 with <= 2 parts are [2,2], [3,1], [4] with 2, 3, 1 standard Young tableaux, respectively:
  +------+  +------+  +---------+  +---------+  +---------+  +------------+
  | 1  3 |  | 1  2 |  | 1  3  4 |  | 1  2  4 |  | 1  2  3 |  | 1  2  3  4 |
  | 2  4 |  | 3  4 |  | 2 .-----+  | 3 .-----+  | 4 .-----+  +------------+
  +------+  +------+  +---+        +---+        +---+
Square array A(n,k) begins:
  1,  1,   1,    1,    1,    1,    1,    1, ...
  0,  1,   1,    1,    1,    1,    1,    1, ...
  0,  1,   2,    2,    2,    2,    2,    2, ...
  0,  1,   5,    6,    6,    6,    6,    6, ...
  0,  1,  14,   23,   24,   24,   24,   24, ...
  0,  1,  42,  103,  119,  120,  120,  120, ...
  0,  1, 132,  513,  694,  719,  720,  720, ...
  0,  1, 429, 2761, 4582, 5003, 5039, 5040, ...

Alois P. Heinz, Antidiagonals n = 0..70, flattened
Wikipedia, Longest increasing subsequence problem
Wikipedia, Young tableau

Columns k=0-10 give: A000007, A000012, A000108, A005802, A047889, A047890, A052399, A072131, A072132, A072133, A072167.
Differences between A000142 and columns k=0-9 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.
Main diagonal and first lower diagonal give: A000142, A033312.
A(2n,n-1) gives A269042(n) for n>0.
Cf. A047887, A047888, A182172, A208447, A214152, A267479.

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, k)-> `if`(k>=n, n!, g(n, k, [])):
seq(seq(A(n, d-n), n=0..d), d=0..14);

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_, k_] := If[k >= n, n!, g[n, k, {}]];
Table [Table [A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 09 2013, translated from Maple *)

A003316 Sum of lengths of longest increasing subsequences of all permutations of n elements.

Original entry on oeis.org

1, 3, 12, 58, 335, 2261, 17465, 152020, 1473057, 15730705, 183571817, 2324298010, 31737207034, 464904410985, 7272666016725, 121007866402968, 2133917906948645, 39756493513248129, 780313261631908137, 16093326774432620874, 347958942706716524974

Offset: 1

N. J. A. Sloane and Richard Stanley

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..80
R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
A. M. Vershik and S. V. Kerov, Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux, Doklady Akademii Nauk SSSR, 1977, Volume 233, Number 6, Pages 1024-1027. In Russian.
Wikipedia, Longest increasing subsequence

Cf. A008304 (which is concerned with runs of adjacent elements).
Row sums of A214152.
Cf. A047874, A321273, A321274.

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-> add(k* (g(n-k, k, [k])), k=1..n):
seq(a(n), n=1..22);  # Alois P. Heinz, Jul 05 2012

h[l_List] := Module[{n = Length[l]}, Total[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_] := Sum[k*g[n-k, k, {k}], {k, 1, n}]; Table[a[n], {n, 1, 22}] (* Jean-François Alcover, Feb 11 2014, after Alois P. Heinz *)

From Alois P. Heinz, Nov 04 2018: (Start)
a(n) = Sum_{k=1..n} k * A047874(n,k).
A321274(n) < a(n) < A321273(n) for n > 1. (End)
A theorem of Vershik and Kerov (1977) implies that a(n) ~ 2 * sqrt(n) * n!. - Ludovic Schwob, Apr 04 2024

Corrected a(13) and extended beyond a(16) by Alois P. Heinz, Jul 05 2012

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

Original entry on oeis.org

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

A217193 Number of permutations in S_{n+3} containing an increasing subsequence of length n.

Original entry on oeis.org

6, 24, 119, 588, 2279, 6996, 18043, 40884, 83923, 159404, 284431, 482108, 782799, 1225508, 1859379, 2745316, 3957723, 5586364, 7738343, 10540204, 14140151, 18710388, 24449579, 31585428, 40377379, 51119436, 64143103, 79820444, 98567263, 120846404, 147171171

Offset: 0

Alois P. Heinz, Sep 27 2012

			a(2) = 119: only one of 5! = 120 permutations of {1,2,3,4,5} has no increasing subsequence of length 2: 54321.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (7, -21, 35, -35, 21, -7, 1).

A diagonal of A214152.

a:= n-> 11+(62+(19+(4+(10+(6+n)*n)*n)*n)*n)*n/6-`if`(n<2, 5-n, 0):
seq(a(n), n=0..40);

CoefficientList[Series[(4x^8-23x^7+53x^6-60x^5+32x^4+49x^3+77x^2-18x+6)/ (1-x)^7,{x,0,40}],x] (* or *) LinearRecurrence[{7,-21,35,-35,21,-7,1},{6,24,119,588,2279,6996,18043,40884,83923},50] (* Harvey P. Dale, Jul 28 2021 *)

a(0) = 6, a(1) = 24, a(n) = (n^6+6*n^5+10*n^4+4*n^3+19*n^2+62*n+66)/6 for n>1.

G.f.: (4*x^8-23*x^7+53*x^6-60*x^5+32*x^4+49*x^3+77*x^2-18*x+6)/(1-x)^7.

A217675 Number of permutations in S_n containing an increasing subsequence of length 8.

Original entry on oeis.org

1, 65, 2603, 83923, 2410291, 64864819, 1683724308, 42918747000, 1086997811325, 27571922195325, 704311698875426, 18189847735254134, 476311846323448840, 12672229166094171240, 343069245941729668380, 9461927811882316662636, 266091066751920438364275

Offset: 8

Alois P. Heinz, Oct 10 2012

nonn

			a(8) = 1: 12345678.

Alois P. Heinz, Table of n, a(n) for n = 8..200

Cf. A000142, A072131, A214015, A214152.

b:= proc(n) option remember; `if`(n<8, n!, ((-343035+429858*n
       +238440*n^3+38958*n^4+634756*n^2+2940*n^5+84*n^6)*b(n-1)
       -(1974*n^4+36336*n^3+213240*n^2+407840*n+82425)*(n-1)^2*b(n-2)
       +2*(49875+42646*n+6458*n^2)*(n-1)^2*(n-2)^2*b(n-3)
       -11025*(n-1)^2*(n-2)^2*(n-3)^2*b(n-4))/ ((n+6)^2*(n+10)^2*(n+12)^2))
    end:
a:= n-> n! -b(n):
seq(a(n), n=8..25);

a(n) = A214152(n,8) = A000142(n)-A072131(n) = A000142(n)-A214015(n,7).

cp's OEIS Frontend

A056986 Number of permutations on {1,...,n} containing any given pattern alpha in the symmetric group S_3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A158005 Numbers of pattern-matching permutations of (1234) for the permutations of {1, 2, ..., n} on n = 4, 5, 6, ... elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A214015 Number of permutations A(n,k) in S_n with longest increasing subsequence of length <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A003316 Sum of lengths of longest increasing subsequences of all permutations of n elements.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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