|
Search: id:A047874
|
|
|
| A047874 |
|
Triangle of numbers T(n,k) = number of permutations of (1,2,...,n) with longest increasing subsequence of length k (1<=k<=n). |
|
+0
11
|
|
| 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; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
Mirror image of triangle in A126065.
|
|
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
|
|
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.
|
|
CROSSREFS
|
Cf. A047887 and A047888. Rows give A001453, A001454, A001455, A001456, A001457, A001458.
Sequence in context: A158815 A101275 A039755 this_sequence A080248 A139382 A157180
Adjacent sequences: A047871 A047872 A047873 this_sequence A047875 A047876 A047877
|
|
KEYWORD
|
nonn,easy,nice,tabl
|
|
AUTHOR
|
Eric Rains (rains(AT)caltech.edu)
|
|
|
Search completed in 0.002 seconds
|
