login
A121636
Number of 2-cell columns starting at level 0 in all of 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.
1
0, 1, 5, 23, 122, 754, 5364, 43308, 391824, 3929616, 43287840, 519711840, 6755460480, 94527008640, 1416783432960, 22646604153600, 384576130713600, 6914404440115200, 131217341055897600, 2621176954176614400
OFFSET
1,3
COMMENTS
a(n)/(n-2)! is also the expected number of days it takes for the '100 Prisoners and a Light Bulb' to free themselves if there are n-1 prisoners if the prisoner on the first day is the counter for n>0. - Ron L.J. van den Burg, Jan 19 2020
LINKS
E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
Brett Ferry, 100 Prisoners and a Light Bulb Riddle & Solution, Math Hacks, 2015.
FORMULA
a(1)=0, a(2)=1, a(n) = n(n-2)! + (n-1)*a(n-1) for n >= 3.
a(n) = Sum_{k=0..n-1} k*A121634(n,k).
a(n) = (n-1)!*(n^2-2n-1)/n + (n-1)!*(1/1 + 1/2 + ... + 1/n) (n >= 2). - Emeric Deutsch, Oct 22 2008
a(n) = (n-1)!*(h(n-1) + n - 2), n > 1, where h(n) = Sum_{k=1..n} 1/k. - Gary Detlefs, Oct 24 2010
a(n) = (n^2-3n+3)*(n-2)! + (n-1)*A000254(n-2), n > 2. - Ron L.J. van den Burg, Jan 19 2020
a(n+1) = (n-1)!*(n^2 + Sum_{k=1..n-1} k/(n-k)), n > 0. - Ron L.J. van den Burg, Jan 20 2020
Conjecture D-finite with recurrence a(n) +(-2*n+3)*a(n-1) +(n^2-5*n+7)*a(n-2) +(n-3)^2*a(n-3)=0. - R. J. Mathar, Jul 22 2022
EXAMPLE
a(2)=1 because the deco polyominoes of height 2 are the horizontal and vertical dominoes and only the vertical one has one 2-cell column starting at level 0.
MAPLE
a[1]:=0: a[2]:=1: for n from 3 to 23 do a[n]:=n*(n-2)!+(n-1)*a[n-1] od: seq(a[n], n=1..23);
CROSSREFS
Sequence in context: A229811 A359915 A362568 * A361305 A200028 A020032
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Aug 13 2006
STATUS
approved