login
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.
15

%I #44 Oct 05 2018 20:46:33

%S 1,2,1,6,5,1,24,23,10,1,120,119,78,17,1,720,719,588,207,26,1,5040,

%T 5039,4611,2279,458,37,1,40320,40319,38890,24553,6996,891,50,1,362880,

%U 362879,358018,268521,101072,18043,1578,65,1,3628800,3628799,3612004,3042210,1438112,337210,40884,2603,82,1

%N 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.

%H Alois P. Heinz, <a href="/A214152/b214152.txt">Rows n = 1..55, flattened</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PermutationPattern.html">Permutation Pattern</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem">Longest increasing subsequence problem</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Young_tableau">Young tableau</a>

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

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

%e T(3,2) = 5. All 3! = 6 permutations of {1,2,3} contain an increasing subsequence of length 2 with the exception of 321.

%e Triangle T(n,k) begins:

%e : 1;

%e : 2, 1;

%e : 6, 5, 1;

%e : 24, 23, 10, 1;

%e : 120, 119, 78, 17, 1;

%e : 720, 719, 588, 207, 26, 1;

%e : 5040, 5039, 4611, 2279, 458, 37, 1;

%p h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j

%p +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)

%p end:

%p g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,

%p add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):

%p T:= (n, k)-> n! -g(n, k-1, []):

%p seq(seq(T(n, k), k=1..n), n=1..12);

%t 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 *)

%Y Columns k=1-10 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.

%Y Row sums give: A003316.

%Y T(2n,n) gives A269021.

%Y Diagonal and lower diagonals give: A000012, A002522, A217200, A217193.

%Y Cf. A047874, A214015.

%K nonn,tabl

%O 1,2

%A _Alois P. Heinz_, Jul 05 2012