The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A047874 Triangle of numbers T(n,k) = number of permutations of (1,2,...,n) with longest increasing subsequence of length k (1<=k<=n). 25
 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, 421, 36, 1, 1, 1429, 14337, 17557, 6105, 841, 49, 1, 1, 4861, 89497, 167449, 83029, 16465, 1513, 64, 1, 1, 16795, 569794, 1604098, 1100902, 296326, 38281, 2521, 81, 1 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,5 COMMENTS Mirror image of triangle in A126065. 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 Table I "Distribution of L_n" on p. 98 of the Pilpel reference. - Joerg Arndt, Apr 13 2013 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 LINKS Alois P. Heinz, Rows n = 1..60, flattened P. Diaconis, Group Representations in Probability and Statistics, IMS, 1988; see p. 112. FindStat - Combinatorial Statistic Finder, The length of the longest increasing subsequence of the permutation. Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285. J. M. Hammersley, A few seedings of research, 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. Guo-Niu Han, A promenade in the garden of hook length formulas, Slides, 61st SLC Curia, Portugal - September 22, 2008. [From Wouter Meeussen, Sep 16 2010] J. Hunt and T. Szymanski, A fast algorithm for computing longest common subsequences, Commun. ACM, 20 (1977), 350-353. E. Irurozki, B. Calvo, and J. A. Lozano, Sampling and learning the Mallows model under the Ulam distance, 2014 S. Pilpel, Descending subsequences of random permutations, J. Combin. Theory, A 53 (1990), 96-116. A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), 115-136. C. Schensted, Longest increasing and decreasing subsequences, Canadian J. Math. 13 (1961), 179-191. Richard P. Stanley, Increasing and Decreasing Subsequences of Permutations and Their Variants, arXiv:math/0512035 [math.CO], 2005. Wikipedia, Longest increasing subsequence problem FORMULA Sum_{k=1..n} k * T(n,k) = A003316(n). - Alois P. Heinz, Nov 04 2018 EXAMPLE T(3,2) = 4 because 132, 213, 231, 312 have longest increasing subsequences of length 2. Triangle T(n,k) begins: 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, 421, 36, 1; ... MAPLE 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-> seq(g(n-k, min(n-k, k), [k]), k=1..n): seq(T(n), n=1..12); # Alois P. Heinz, Jul 05 2012 MATHEMATICA Table[Total[NumberOfTableaux[#]^2&/@ IntegerPartitions[n, {k}]], {n, 7}, {k, n}] (* Wouter Meeussen, Sep 16 2010, revised Nov 19 2013 *) 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 *) CROSSREFS Cf. A047887 and A047888. Columns k=1-10 give: A000012, A001453, A001454, A001455, A001456, A001457, A001458, A239432, A245665, A245666. Row sums give A000142. Cf. A047884. - Wouter Meeussen, Sep 16 2010 Cf. A224652 (Table II "Distribution of F_n" on p. 99 of the Pilpel reference). Cf. A245667. T(2n,n) gives A267433. Cf. A003316. Sequence in context: A262494 A039755 A247502 * A080248 A139382 A157180 Adjacent sequences: A047871 A047872 A047873 * A047875 A047876 A047877 KEYWORD nonn,easy,nice,tabl AUTHOR Eric Rains (rains(AT)caltech.edu) STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 30 23:40 EST 2023. Contains 367464 sequences. (Running on oeis4.)