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.

%I A214152 #47 Feb 18 2025 07:54:35
%S A214152 1,2,1,6,5,1,24,23,10,1,120,119,78,17,1,720,719,588,207,26,1,5040,
%T A214152 5039,4611,2279,458,37,1,40320,40319,38890,24553,6996,891,50,1,362880,
%U A214152 362879,358018,268521,101072,18043,1578,65,1,3628800,3628799,3612004,3042210,1438112,337210,40884,2603,82,1
%N 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.
%H A214152 Alois P. Heinz, <a href="/A214152/b214152.txt">Rows n = 1..55, flattened</a>
%H A214152 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PermutationPattern.html">Permutation Pattern</a>
%H A214152 Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem">Longest increasing subsequence problem</a>
%H A214152 Wikipedia, <a href="https://en.wikipedia.org/wiki/Young_tableau">Young tableau</a>
%F A214152 T(n,k) = Sum_{i=k..n} A047874(n,i).
%F A214152 T(n,k) = A000142(n) - A214015(n,k-1).
%e A214152 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 A214152 Triangle T(n,k) begins:
%e A214152      1;
%e A214152      2,    1;
%e A214152      6,    5,    1;
%e A214152     24,   23,   10,    1;
%e A214152    120,  119,   78,   17,   1;
%e A214152    720,  719,  588,  207,  26,  1;
%e A214152   5040, 5039, 4611, 2279, 458, 37,  1;
%e A214152   ...
%p A214152 h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
%p A214152       +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
%p A214152     end:
%p A214152 g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
%p A214152                  add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
%p A214152 T:= (n, k)-> n! -g(n, k-1, []):
%p A214152 seq(seq(T(n, k), k=1..n), n=1..12);
%t A214152 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 A214152 Columns k=1-10 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.
%Y A214152 Row sums give: A003316.
%Y A214152 T(2n,n) gives A269021.
%Y A214152 Diagonal and lower diagonals give: A000012, A002522, A217200, A217193.
%Y A214152 Cf. A047874, A214015.
%K A214152 nonn,tabl
%O A214152 1,2
%A A214152 _Alois P. Heinz_, Jul 05 2012