A121634 -id:A121634

Search: a121634 -id:a121634

Displaying 1-2 of 2 results found.

page 1

A121635

Number of deco polyominoes of height n, having no 2-cell columns starting at level 0. 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
3

1, 1, 2, 8, 42, 264, 1920, 15840, 146160, 1491840, 16692480, 203212800, 2674425600, 37841126400, 572885913600, 9240898867200, 158228598528000, 2866422214656000, 54775863926784000, 1101208277385216000, 23234214178086912000, 513342323725271040000

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..450 (n=2..101 from Muniru A Asiru)

E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

Mark Dukes, Chris D White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.

Mark Dukes, Chris D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, Electronic Journal Of Combinatorics, 23(1) (2016), #P1.45.

FORMULA

a(n) = A121634(n,0).

a(1)=1, a(n) = (n-2)!(n^2-3*n+4)/2 = A000142(n-2)*A152947(n) for n>=2.

a(1)=1, a(2)=1, a(n) = (n-2)*[(n-2)! + a(n-1)] for n>=3.

D-finite with recurrence a(n) +(-n-2)*a(n-1) +2*(n-1)*a(n-2) +2*(-n+4)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

EXAMPLE

a(2)=1 because the deco polyominoes of height 2 are the horizontal and vertical dominoes and the horizontal one has no 2-cell column starting at level 0.

MAPLE

a:= n-> `if`(n=1, 1, (n^2-3*n+4)*(n-2)!/2): seq(a(n), n=1..23);

CROSSREFS

Cf. A121634, A001710.

KEYWORD

nonn,easy

AUTHOR

Emeric Deutsch, Aug 13 2006

EXTENSIONS

Missing a(1) inserted by Alois P. Heinz, Nov 25 2018

STATUS

approved

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

0, 1, 5, 23, 122, 754, 5364, 43308, 391824, 3929616, 43287840, 519711840, 6755460480, 94527008640, 1416783432960, 22646604153600, 384576130713600, 6914404440115200, 131217341055897600, 2621176954176614400

(list; graph; refs; listen; history; text; internal format)

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