A274207 Number T(n,k) of bargraphs of site-perimeter n having area k; triangle T(n,k), n>=4, floor((n-1)/2)<=k<=floor(((n-1)^2+3)/12), read by rows.

1, 2, 2, 2, 2, 4, 4, 2, 4, 7, 1, 6, 6, 10, 4, 2, 9, 13, 14, 12, 2, 8, 13, 22, 18, 24, 10, 2, 2, 15, 27, 40, 29, 38, 28, 12, 2, 10, 24, 45, 65, 59, 58, 56, 40, 16, 4, 2, 23, 52, 84, 104, 112, 100, 95, 88, 56, 28, 7, 1, 12, 40, 92, 148, 181, 205, 191, 172, 163, 132, 96, 48, 16, 4

Offset: 4

Author

Alois P. Heinz, Jun 13 2016

Keywords

• nonn
• tabf

Comments

A bargraph is a polyomino whose bottom is a segment of the nonnegative x-axis and whose upper part is a lattice path starting at (0,0) and ending with its first return to the x-axis using steps U=(0,1), D=(0,-1) and H=(1,0), where UD and DU are not allowed.

The site-perimeter of a polyomino is the number of exterior cells having a common edge with at least one polyomino cell.

Examples

			              _
T(4,1) = 1:  |_|
              _
             | |     ___
T(6,2) = 2:  |_|    |___|
              _        _
             | |_    _| |
T(7,3) = 2:  |___|  |___|
              _
             | |
             | |     _____
T(8,3) = 2:  |_|    |_____|
              ___      _
             |   |   _| |_
T(8,4) = 2:  |___|  |_____|
              _        _
             | |      | |   _            _
             | |_    _| |  | |___    ___| |
T(9,4) = 4:  |___|  |___|  |_____|  |_____|
              _        _
             | |_    _| |   ___        ___
             |   |  |   |  |   |_    _|   |
T(9,5) = 4:  |___|  |___|  |_____|  |_____|
                _
              _| |_
             |     |
T(10,7) = 1: |_____|
.
Triangle T(n,k) begins:
n\k: 1 2 3 4 5 6  7  8  9 10  11  12  13 14 15 16 17 . .
---+----------------------------------------------------
04 : 1
05 :
06 :   2
07 :     2
08 :     2 2
09 :       4 4
10 :       2 4 7  1
11 :         6 6 10  4
12 :         2 9 13 14 12  2
13 :           8 13 22 18 24  10   2
14 :           2 15 27 40 29  38  28  12  2
15 :             10 24 45 65  59  58  56 40 16  4
16 :              2 23 52 84 104 112 100 95 88 56 28 7 1
		

Links

• Alois P. Heinz, Rows n = 4..100, flattened
• M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.
• Wikipedia, Polyomino

Crossrefs

Row sums give A075126.

Column sums give A000079(k-1).

Cf. A001787, A273346, A274208, A274217.

Programs

Maple

b:= proc(n, y, t, w) option remember; `if`(n<0, 0, `if`(n=0, (1-t),
     `if`(t<0, 0, b(n-`if`(w>0 or t=0, 1, 2), y+1, 1, max(0, w-1)))+
     `if`(t>0 or y<2, 0, b(n, y-1, -1, `if`(t=0, 1, w+1))) +expand(
     `if`(y<1, 0, z^y*b(n-`if`(t<0, 1, 2), y, 0, `if`(t<0, w, 0))))))
    end:
T:= n-> (p-> seq(coeff(p, z, i),
         i= iquo(n-1, 2)..iquo((n-1)^2+3, 12)))(b(n, 0, 1, 0)):
seq(T(n), n=4..20);

Mathematica

b[n_, y_, t_, w_] := b[n, y, t, w] = If[n<0, 0, If[n==0, (1-t), If[t<0, 0, b[n - If[w>0 || t==0, 1, 2], y+1, 1, Max[0, w-1]]] + If[t>0 || y<2, 0, b[n, y-1, -1, If[t==0, 1, w+1]]] + Expand[If[y<1, 0, z^y*b[n - If[t<0, 1, 2], y, 0, If[t<0, w, 0]]]]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, Quotient[n-1, 2], Quotient[(n-1)^2 + 3, 12]}]][b[n, 0, 1, 0]];
Table[T[n], {n, 4, 20}] // Flatten (* Jean-François Alcover, Apr 28 2018, after Alois P. Heinz *)

Formula

Sum_{k=floor((n-1)/2)..floor(((n-1)^2+3)/12)} k * T(n,k) = A274208(n).

Sum_{n>=4} k * T(n,k) = A001787(k).

Sum_{n>=4} n * T(n,k) = A274217(k).