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

Author

Emeric Deutsch, Aug 13 2006

Keywords

• nonn

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

Examples

			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.
		

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.

Crossrefs

Cf. A121634, A000142.

Programs

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);

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