|
Search: id:A121586
|
|
|
| A121586 |
|
Number of columns in all deco polyominoes of height n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. |
|
+0
3
|
|
| 1, 3, 13, 70, 446, 3276, 27252, 253296, 2602224, 29288160, 358457760, 4740577920, 67375532160, 1024208720640, 16583626886400, 284953145702400, 5178968115148800, 99268112350310400, 2001336861359001600
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
a(n)=Sum(k*A094638(n,k),k=1..n).
Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 10 2008: (Start)
a(n) is also the largest entry in the cycle containing 1, summed over all permutations of {1,2,...,n}. Example: a(3)=13 because the permutations (1)(2)(3), (1)(23), (12)(3), (13)(2), (123), (132), written in cycle notation, yield 1+1+2+3+3+3=13.
a(n)=Sum(k*A145888(n,k), k=1..n). (End)
|
|
REFERENCES
|
E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
|
|
FORMULA
|
a(n)=(n+1)!-|s(n+1,2)|, where s(n,k) are the signed Stirling numbers of the first kind (A008275). Recurrence relation: a(n)=na(n-1) + (n-1)!(n-1); a(1)=1 (see the Barcucci et al. reference, p. 34).
a(n)=(n-1)!(n^2 + n - 1 - nH(n-1)), where H(j)=1/1+1/2+...+1/j. [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 10 2008]
|
|
EXAMPLE
|
a(2)=3 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having, respectively, 1 and 2 columns.
|
|
MAPLE
|
a[1]:=1: for n from 2 to 22 do a[n]:=n*a[n-1]+(n-1)!*(n-1) od: seq(a[n], n=1..22);
|
|
CROSSREFS
|
Cf. A008275, A094638.
A145888 [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 10 2008]
Sequence in context: A119906 A059726 A154677 this_sequence A024337 A001495 A162326
Adjacent sequences: A121583 A121584 A121585 this_sequence A121587 A121588 A121589
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 14 2006
|
|
|
Search completed in 0.002 seconds
|
