A269021 -id:A269021 - cp's OEIS frontend

A214152 Number of permutations T(n,k) in S_n containing an increasing subsequence of length k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

1, 2, 1, 6, 5, 1, 24, 23, 10, 1, 120, 119, 78, 17, 1, 720, 719, 588, 207, 26, 1, 5040, 5039, 4611, 2279, 458, 37, 1, 40320, 40319, 38890, 24553, 6996, 891, 50, 1, 362880, 362879, 358018, 268521, 101072, 18043, 1578, 65, 1, 3628800, 3628799, 3612004, 3042210, 1438112, 337210, 40884, 2603, 82, 1

Offset: 1

Alois P. Heinz, Jul 05 2012

			T(3,2) = 5.  All 3! = 6 permutations of {1,2,3} contain an increasing subsequence of length 2 with the exception of 321.
Triangle T(n,k) begins:
     1;
     2,    1;
     6,    5,    1;
    24,   23,   10,    1;
   120,  119,   78,   17,   1;
   720,  719,  588,  207,  26,  1;
  5040, 5039, 4611, 2279, 458, 37,  1;
  ...

Alois P. Heinz, Rows n = 1..55, flattened
Eric Weisstein's World of Mathematics, Permutation Pattern
Wikipedia, Longest increasing subsequence problem
Wikipedia, Young tableau

Columns k=1-10 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.
Row sums give: A003316.
T(2n,n) gives A269021.
Diagonal and lower diagonals give: A000012, A002522, A217200, A217193.
Cf. A047874, 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:= (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))):
T:= (n, k)-> n! -g(n, k-1, []):
seq(seq(T(n, k), k=1..n), n=1..12);

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}]]]; t[n_, k_] := n! - g[n, k-1, {}]; Table[Table[t[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

T(n,k) = Sum_{i=k..n} A047874(n,i).

T(n,k) = A000142(n) - A214015(n,k-1).

A269042 Number of permutations of [2n] avoiding the pattern 12...n.

Original entry on oeis.org

0, 0, 1, 132, 15767, 2190688, 370531683, 77182248916, 19835792076675, 6266271456118776, 2413632612087046844, 1120958514818713738544, 619918692943471064695593, 403190647991638511052901232, 304867528413299672718870216538, 265248225675908889875489731636920

Offset: 0

Alois P. Heinz, Feb 18 2016

nonn

			a(2) = 1: 4321.
a(3) = 132: 165432, 216543, 261543, 265143, 265413, 265431, 316542, ..., 653412, 653421, 654132, 654213, 654231, 654312, 654321.

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

Cf. A010050, A214015, A267532, A269021.

h:= proc(l) (n-> 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))(nops(l))
    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-> `if`(n=0, 0, g(2*n, n-1, [])):
seq(a(n), n=0..15);

h[l_] := Function[n, 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}]][Length[l]];
g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Table[1, {n}]]]^2, If[i < 1, 0, Sum[g[n - i*j, i-1, Join[l, Table[i, {j}]]], {j, 0, n/i}]]];
a[n_] := If[n == 0, 0, g[2n, n-1, {}]];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Apr 01 2017, translated from Maple *)

a(n) = (2n)! - A269021(n).
a(n) = A214015(2n,n-1) for n>0.
a(n) ~ (2*n)!. - Vaclav Kotesovec, Mar 26 2016

cp's OEIS Frontend

A214152 Number of permutations T(n,k) in S_n containing an increasing subsequence of length k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula