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.

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

Table of n, a(n) for n=1..20.

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

Cf. A121634, A000142.

Sequence in context: A229811 A359915 A362568 * A361305 A200028 A020032

Adjacent sequences: A121633 A121634 A121635 * A121637 A121638 A121639

Keyword

nonn

Author

Emeric Deutsch, Aug 13 2006

Status

approved