|
%I #34 May 04 2023 19:24:31
%S 1,1,3,13,70,446,3276,27252,253296,2602224,29288160,358457760,
%T 4740577920,67375532160,1024208720640,16583626886400,284953145702400,
%U 5178968115148800,99268112350310400,2001336861359001600,42337994134947840000,937755916997437440000
%N 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.
%C 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. - _Emeric Deutsch_, Nov 10 2008
%H E. Barcucci, A. Del Lungo and R. Pinzani, <a href="http://dx.doi.org/10.1016/0304-3975(95)00199-9">"Deco" polyominoes, permutations and random generation</a>, Theoretical Computer Science, 159, 1996, 29-42.
%F a(n) = (n+1)! - |s(n+1,2)|, where s(n,k) are the signed Stirling numbers of the first kind (A008275).
%F Recurrence relation: a(n) = n*a(n-1) + (n-1)!*(n-1); (see the Barcucci et al. reference, p. 34).
%F a(n) = Sum_{k=1..n} k*A094638(n,k).
%F From _Emeric Deutsch_, Nov 10 2008: (Start)
%F a(n) = (n-1)!*(n^2 + n - 1 - n*H(n-1)) for n >= 1, where H(j) = 1/1+1/2+...+1/j.
%F a(n) = Sum_{k=1..n} k*A145888(n,k) for n >= 1. (End)
%F From _Gary Detlefs_, Sep 12 2010: (Start)
%F a(n) = n!*((n+1) - h(n)), where h(n) = Sum_{k=1..n} 1/k.
%F a(n) = (n+1)! - A000254(n). (End)
%F E.g.f.: (1 - (x - 1)*log(1 - x))/(x - 1)^2. - _Benedict W. J. Irwin_, Sep 27 2016
%F a(n) = Sum_{k=0..n*(n-1)/2} (k+1) * A129177(n,k). - _Alois P. Heinz_, May 04 2023
%e a(2)=3 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having, respectively, 1 and 2 columns.
%p a[0] := 1; a[1] := 1: for n from 2 to 22 do a[n] := n*a[n-1] + (n-1)!*(n-1) od:
%p seq(a[n], n = 0..22);
%p # Second program:
%p egf := (1 - (x - 1)*log(1 - x))/(x - 1)^2: ser := series(egf, x, 20):
%p seq(n!*coeff(ser, x, n), n = 0..19); # _Peter Luschny_, Dec 09 2021
%t Join[{1}, Table[CoefficientList[Series[((x-1)Log[1-x]-x-1)/(x-1)^3, {x, 0, 20}],x][[n]] (n-1)!, {n, 1, 20}]] (* _Benedict W. J. Irwin_, Sep 27 2016 *)
%Y Cf. A008275, A094638, A129177, A145888.
%K nonn
%O 0,3
%A _Emeric Deutsch_, Aug 14 2006
%E a(0) = 1 prepended by _Peter Luschny_, Dec 09 2021
|
