|
Search: id:A092582
|
|
|
| A092582 |
|
Triangle read by rows: T(n,k) is the number of permutations p of [n] having length of first run equal to k. |
|
+0
6
|
|
| 1, 1, 1, 3, 2, 1, 12, 8, 3, 1, 60, 40, 15, 4, 1, 360, 240, 90, 24, 5, 1, 2520, 1680, 630, 168, 35, 6, 1, 20160, 13440, 5040, 1344, 280, 48, 7, 1, 181440, 120960, 45360, 12096, 2520, 432, 63, 8, 1, 1814400, 1209600, 453600, 120960, 25200, 4320, 630, 80, 9, 1
(list; table; graph; listen)
|
|
|
OFFSET
|
1,4
|
|
|
COMMENT
|
Row sums are the factorial numbers (A000142). First column is A001710.
T(n,k)=number of permutations of [n] in which 1,2,...,k is a subsequence but 1,2,...,k,k+1 is not. Example: T(4,2)=8 because 1324, 1342, 1432, 4132, 3124, 3142, 3412 and 4312, are the only permutations of [4] in which 12 is a subsequence but 123 is not. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 12 2004
T(n,k) is the number of deco polyominoes of height n with k cells in the last column. (A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 06 2005
T(n,k) is the number of permutations p of [n] for which the smallest i such that p(i)<p(i+1) is k (it is assumed that p(n+1)=infinity). Example: T(4,3)=3 because we have 4312, 4213 and 3214. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Feb 23 2008
Adding columns 2,4,6,... one obtains the derangement numbers 0,1,2,9,44,... (A000166). See the Bona reference (p. 118, Exercises 41,42). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Feb 23 2008
Matrix inverse of A128227*A154990. [From Mats Granvik (mats.granvik(AT)abo.fi), Feb 08 2009]
|
|
REFERENCES
|
E. Barcucci, A. del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
E. Deutsch and W. P. Johnson, Create your own permutation statistic, Math. Mag., 77, 130-134, 2004.
M. Bona, Combinatorics of Permutations, Chapman&Hall/CRC, Boca Raton, Florida, 2004.
|
|
FORMULA
|
T(n, k)=n!*k/(k+1)! for k<n; T(n, n)=1.
|
|
EXAMPLE
|
T(4,3)=3 because 1243, 1342 and 2341 are the only permutations of [4] having length of first run equal to 3.
1; 1,1; 3,2,1; 12,8,3,1; 60,40,15,4,1; 360,240,90,24,5,1; 2520,1680,630,168,35,6,1;
|
|
CROSSREFS
|
Cf. A000166.
Sequence in context: A115085 A110616 A059418 this_sequence A068440 A048647 A059438
Adjacent sequences: A092579 A092580 A092581 this_sequence A092583 A092584 A092585
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu) and Warren P. Johnson (wjohnson(AT)bates.edu), Apr 10 2004
|
|
|
Search completed in 0.002 seconds
|
