A140709 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n in which the maximal number of initial consecutive columns ending at the same level is k (1 <= k <= n).

1, 1, 1, 3, 2, 1, 15, 5, 3, 1, 87, 20, 8, 4, 1, 567, 107, 28, 12, 5, 1, 4167, 674, 135, 40, 17, 6, 1, 34407, 4841, 809, 175, 57, 23, 7, 1, 316647, 39248, 5650, 984, 232, 80, 30, 8, 1, 3219687, 355895, 44898, 6634, 1216, 312, 110, 38, 9, 1, 35878887, 3575582, 400793, 51532, 7850, 1528, 422, 148, 47, 10, 1

Offset

1,4

Comments

A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.

Links

G. C. Greubel, Rows n = 1..50 of the triangle, flattened

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

Formula

T(n,k) = binomial(n-1, k-1) + Sum_{j=2..n-1} j!*(j-1)*binomial(n-1-j, k-1).

T(n,k) = T(n-1, k) + T(n-1, k-1) for n,k >= 2.

Sum of entries in row n is n! (A000142).

T(n,1) = A132371(n).

Sum_{k=1..n} k*T(n,k) = A140710(n).

Example

T(2,1)=1 (the vertical domino); T(2,2)=1 (the horizontal domino); T(3,1)=3 because we have (3), (1,2) and (2,1,1), where (a,b,c,...) stands for a polyomino with columns of lengths a,b,c,..., starting at level 0.
Triangle starts:
    1;
    1,   1;
    3,   2,   1;
   15,   5,   3,   1;
   87,  20,   8,   4,   1;
  567, 107,  28,  12,   5,   1;

Maple

T:=proc(n, k) options operator, arrow: binomial(n-1, k-1)+sum(factorial(j)*(j-1)*binomial(n-1-j, k-1), j=2..n-1) end proc: for n to 11 do seq(T(n, k), k=1..n) end do; # yields sequence in triangular form

Mathematica

T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[k==1, n! -Sum[j!, {j, n-1}], T[n-1, k] + T[n-1, k-1] ]];
Table[T[n, k], {n, 14}, {k, n}]//Flatten (* G. C. Greubel, May 02 2021 *)

Prog

(PARI) T(n, k) = binomial(n-1, k-1) + sum(j=2, n-1, j!*(j-1)*binomial(n-1-j, k-1));
tabl(nn) = for (n=1, nn, for (k=1, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, Nov 16 2019
(Sage)
@CachedFunction
def T(n, k):
    if (k < 0 or k > n): return 0
    elif (k==1): return factorial(n) - sum(factorial(j) for j in (1..n-1))
    else: return T(n-1, k-1) + T(n-1, k)
flatten([[T(n, k) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, May 02 2021

Crossrefs

Cf. A000142, A132371, A140710.

Sequence in context: A291978 A342217 A111548 * A109282 A135902 A135876

Adjacent sequences: A140706 A140707 A140708 * A140710 A140711 A140712

Keyword

nonn,tabl

Author

Emeric Deutsch, Jun 03 2008

Status

approved