This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A047874 #90 May 28 2025 00:13:37
%S A047874 1,1,1,1,4,1,1,13,9,1,1,41,61,16,1,1,131,381,181,25,1,1,428,2332,1821,
%T A047874 421,36,1,1,1429,14337,17557,6105,841,49,1,1,4861,89497,167449,83029,
%U A047874 16465,1513,64,1,1,16795,569794,1604098,1100902,296326,38281,2521,81,1
%N A047874 Triangle of numbers T(n,k) = number of permutations of (1,2,...,n) with longest increasing subsequence of length k (1<=k<=n).
%C A047874 Mirror image of triangle in A126065.
%C A047874 T(n,m) is also the sum of squares of n!/(product of hook lengths), summed over the partitions of n in exactly m parts (Robinson-Schensted correspondence). - _Wouter Meeussen_, Sep 16 2010
%C A047874 Table I "Distribution of L_n" on p. 98 of the Pilpel reference. - _Joerg Arndt_, Apr 13 2013
%C A047874 In general, for column k is a(n) ~ product(j!, j=0..k-1) * k^(2*n+k^2/2) / (2^((k-1)*(k+2)/2) * Pi^((k-1)/2) * n^((k^2-1)/2)) (result due to Regev) . - _Vaclav Kotesovec_, Mar 18 2014
%H A047874 Leonid Petrov, <a href="/A047874/b047874.txt">Rows n = 1..120, flattened</a> (first 60 rows from Alois P. Heinz)
%H A047874 P. Diaconis, <a href="https://doi.org/10.1214/lnms/1215467407">Group Representations in Probability and Statistics</a>, IMS, 1988; see p. 112.
%H A047874 FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000062">The length of the longest increasing subsequence of the permutation</a>.
%H A047874 Ira M. Gessel, <a href="http://dx.doi.org/10.1016/0097-3165(90)90060-A">Symmetric functions and P-recursiveness</a>, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285.
%H A047874 J. M. Hammersley, <a href="http://projecteuclid.org/euclid.bsmsp/1200514101">A few seedings of research</a>, in Proc. Sixth Berkeley Sympos. Math. Stat. and Prob., ed. L. M. le Cam et al., Univ. Calif. Press, 1972, Vol. I, pp. 345-394.
%H A047874 Guo-Niu Han, <a href="http://www.emis.de/journals/SLC/wpapers/s61vortrag/han.pdf">A promenade in the garden of hook length formulas</a>, Slides, 61st SLC Curia, Portugal - September 22, 2008. [From _Wouter Meeussen_, Sep 16 2010]
%H A047874 J. Hunt and T. Szymanski, <a href="http://dx.doi.org/10.1145/359581.359603">A fast algorithm for computing longest common subsequences</a>, Commun. ACM, 20 (1977), 350-353.
%H A047874 E. Irurozki, B. Calvo, and J. A. Lozano, <a href="http://hdl.handle.net/10810/11241">Sampling and learning the Mallows model under the Ulam distance</a>, Technical Report, 2014.
%H A047874 S. Pilpel, <a href="http://dx.doi.org/10.1016/0097-3165(90)90022-O">Descending subsequences of random permutations</a>, J. Combin. Theory, A 53 (1990), 96-116.
%H A047874 A. Regev, <a href="http://dx.doi.org/10.1016/0001-8708(81)90012-8">Asymptotic values for degrees associated with strips of Young diagrams</a>, Adv. in Math. 41 (1981), 115-136.
%H A047874 C. Schensted, <a href="http://dx.doi.org/10.4153/CJM-1961-015-3">Longest increasing and decreasing subsequences</a>, Canadian J. Math. 13 (1961), 179-191.
%H A047874 Richard P. Stanley, <a href="http://arxiv.org/abs/math/0512035">Increasing and Decreasing Subsequences of Permutations and Their Variants</a>, arXiv:math/0512035 [math.CO], 2005.
%H A047874 Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem">Longest increasing subsequence problem</a>
%F A047874 Sum_{k=1..n} k * T(n,k) = A003316(n). - _Alois P. Heinz_, Nov 04 2018
%e A047874 T(3,2) = 4 because 132, 213, 231, 312 have longest increasing subsequences of length 2.
%e A047874 Triangle T(n,k) begins:
%e A047874 1;
%e A047874 1, 1;
%e A047874 1, 4, 1;
%e A047874 1, 13, 9, 1;
%e A047874 1, 41, 61, 16, 1;
%e A047874 1, 131, 381, 181, 25, 1;
%e A047874 1, 428, 2332, 1821, 421, 36, 1;
%e A047874 ...
%p A047874 h:= proc(l) local n; n:= nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
%p A047874 +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n) end:
%p A047874 g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
%p A047874 add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
%p A047874 T:= n-> seq(g(n-k, min(n-k, k), [k]), k=1..n):
%p A047874 seq(T(n), n=1..12); # _Alois P. Heinz_, Jul 05 2012
%t A047874 Table[Total[NumberOfTableaux[#]^2&/@ IntegerPartitions[n,{k}]],{n,7},{k,n}] (* _Wouter Meeussen_, Sep 16 2010, revised Nov 19 2013 *)
%t A047874 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_List] := 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_] := Table[g[n-k, Min[n-k, k], {k}], {k, 1, n}]; Table[T[n], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Mar 06 2014, after _Alois P. Heinz_ *)
%Y A047874 Cf. A047887 and A047888.
%Y A047874 Columns k=1-10 give: A000012, A001453, A001454, A001455, A001456, A001457, A001458, A239432, A245665, A245666.
%Y A047874 Row sums give A000142.
%Y A047874 Cf. A047884. - _Wouter Meeussen_, Sep 16 2010
%Y A047874 Cf. A224652 (Table II "Distribution of F_n" on p. 99 of the Pilpel reference).
%Y A047874 Cf. A245667.
%Y A047874 T(2n,n) gives A267433.
%Y A047874 Cf. A003316.
%K A047874 nonn,easy,nice,tabl
%O A047874 1,5
%A A047874 Eric Rains (rains(AT)caltech.edu)