A105292 Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having leftmost column of height k.

1, 1, 1, 2, 2, 1, 5, 4, 3, 1, 13, 10, 6, 4, 1, 34, 26, 15, 8, 5, 1, 89, 68, 39, 20, 10, 6, 1, 233, 178, 102, 52, 25, 12, 7, 1, 610, 466, 267, 136, 65, 30, 14, 8, 1, 1597, 1220, 699, 356, 170, 78, 35, 16, 9, 1, 4181, 3194, 1830, 932, 445, 204, 91, 40, 18, 10, 1, 10946, 8362

Offset

1,4

Comments

T(n,k) is the number of nondecreasing Dyck paths of semilength n, having height of leftmost peak equal to k. Example: T(3,2)=2 because we have UUDDUD and UUDUDD, where U=(1,1) and D(1,-1). Sum of row n = fibonacci(2n-1) (A001519). T(n,1)=fibonacci(2n-3) (A001519). Column 2 yields A055819.

Links

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

Elena Barcucci, Alberto del Lungo, S. Fezzi, and Renzo Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.

Emeric Deutsch and Helmut Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.

Juan B. Gil, Felix H. Xu, and William Y. Zhu, Odd-indexed Fibonacci numbers via pattern-avoiding permutations, arXiv:2506.15800 [math.CO], 2025. See p. 4. See also Integers (2025) Vol. 25, Art. No. A79. See p. 5.

Formula

T(n, k) = k*fibonacci(2n-2k-1) if k<n; T(n, n) = 1.

G.f.: t*z*(1-2z-tz+3tz^2-tz^3)/((1-3z+z^2)*(1-tz)^2).

Example

Triangle begins:
  1;
  1,1;
  2,2,1;
  5,4,3,1;
  13,10,6,4,1;

Maple

with(combinat):T:=proc(n, k) if k<n then k*fibonacci(2*n-2*k-1) elif k=n then 1 else 0 fi end:for n from 1 to 12 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form

Mathematica

Flatten[Join[{1}, #]&/@Table[k*Fibonacci[2n-2k-1], {n, 15}, {k, n-1}]] (* Harvey P. Dale, Aug 21 2013 *)

Crossrefs

Cf. A001519, A055819.

Sequence in context: A110438 A184051 A121460 * A273342 A276067 A125177

Adjacent sequences: A105289 A105290 A105291 * A105293 A105294 A105295

Keyword

nonn,tabl,changed

Author

Emeric Deutsch, Apr 25 2005

Status

approved