|
| |
|
|
A047874
|
|
Triangle of numbers T(n,k) = number of permutations of (1,2,...,n) with longest increasing subsequence of length k (1<=k<=n).
|
|
12
| |
|
|
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
(list; table; graph; refs; listen; history; 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). [From Wouter Meeussen (wouter.meeussen(AT)pandora.be), Sep 16 2010]
|
|
|
REFERENCES
| P. Diaconis, Group Representations in Probability and Statistics, IMS, 1988; see p. 112.
Gessel, Ira M.; 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.
Hunt, J. and Szymanski, T., "A fast algorithm for computing longest common subsequences". Commun. ACM, 20 (1977), 350-353.
Schensted, C., "Longest increasing and decreasing subsequences". Canadian J. Math. 13 (1961), 179-191.
|
|
|
LINKS
| Wikipedia, Longest increasing subsequence problem
Guo-Niu Han, A promenade in the garden of hook length formulas [From Wouter Meeussen (wouter.meeussen(AT)pandora.be), Sep 16 2010]
|
|
|
EXAMPLE
| 1; 1 1; 1 4 1; 1 13 9 1; 1 41 61 16 1; ...
T(3,2)=4 because 132, 213, 231, 312 have longest increasing subsequences of length 2.
|
|
|
MATHEMATICA
| (*Needs["DiscreteMath`Combinatorica`"]; hooklength[(p_)?PartitionQ] := Block[{ferr = (PadLeft[1 + 0*Range[ #1], Max[p]] & ) /@ p}, DeleteCases[(Rest[FoldList[Plus, 0, #1]] & ) /@ ferr + Reverse /@ Reverse[Transpose[(Rest[FoldList[Plus, 0, #1]] & ) /@ Reverse[Reverse /@ Transpose[ferr]]]], 0, {2}] - 1]; partitionexact[n_, m_] := TransposePartition /@ (Prepend[ #1, m] & ) /@ Partitions[n - m, m] *) Table[ Tr[ n!^2 /Times @@ Flatten[hooklength[ # ]]^2 &/@ partitionexact[n, k] ], {n, 9}, {k, n}] [From Wouter Meeussen (wouter.meeussen(AT)pandora.be), Sep 16 2010]
|
|
|
CROSSREFS
| Cf. A047887 and A047888. Rows give A001453, A001454, A001455, A001456, A001457, A001458.
A047884 [From Wouter Meeussen (wouter.meeussen(AT)pandora.be), Sep 16 2010]
Sequence in context: A158815 A101275 A039755 * A080248 A139382 A157180
Adjacent sequences: A047871 A047872 A047873 * A047875 A047876 A047877
|
|
|
KEYWORD
| nonn,easy,nice,tabl
|
|
|
AUTHOR
| Eric Rains (rains(AT)caltech.edu)
|
| |
|
|
