A121636 - OEIS

%I #35 Jul 22 2022 13:23:57

%S 0,1,5,23,122,754,5364,43308,391824,3929616,43287840,519711840,

%T 6755460480,94527008640,1416783432960,22646604153600,384576130713600,

%U 6914404440115200,131217341055897600,2621176954176614400

%N 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.

%C 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

%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.

%H Brett Ferry, <a href="https://medium.com/i-math/100-prisoners-and-a-light-bulb-573426272f4c">100 Prisoners and a Light Bulb Riddle & Solution</a>, Math Hacks, 2015.

%F a(1)=0, a(2)=1, a(n) = n(n-2)! + (n-1)*a(n-1) for n >= 3.

%F a(n) = Sum_{k=0..n-1} k*A121634(n,k).

%F a(n) = (n-1)!*(n^2-2n-1)/n + (n-1)!*(1/1 + 1/2 + ... + 1/n) (n >= 2). - _Emeric Deutsch_, Oct 22 2008

%F 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

%F a(n) = (n^2-3n+3)*(n-2)! + (n-1)*A000254(n-2), n > 2. - _Ron L.J. van den Burg_, Jan 19 2020

%F 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

%F 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

%e 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.

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

%Y Cf. A121634, A000142.

%K nonn

%O 1,3

%A _Emeric Deutsch_, Aug 13 2006