A264841 Triangle read by rows: T(n,k) is the number of ways to partition an n X k square grid into any number of parts along the gridlines.

1, 2, 12, 4, 74, 1442, 8, 456, 28028, 1716098, 16, 2810, 544844, 105093828, 20276816980, 32, 17316, 10591310, 6435880414, 3912156203494, 2378025136264102, 64, 106706, 205886234, 394129505248, 754801786191820, 1445496758320387318, 2768227968406304217000, 128, 657552, 4002256640, 24136256828880

Offset

1,2

Comments

A set of edges forms a valid partition if and only if it includes the entire boundary of the grid, and there are no vertices of degree 1.

Links

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

Danny Rorabaugh, A264841 Example: T(2,2)

R. J. Mathar, Counting 2-way monotonic terrace forms over rectangular landscapes, see Section 6.3, Combinatorics and Graph Theory, viXra:1511.0225, 2015.

Formula

T(n,1) = 2^(n-1).

T(n,2) = A078469(n).

Example

The triangle T(n,k) begins:
n\k 1  2    3      4         5
1:  1
2:  2  12
3:  4  74   1442
4:  8  456  28028  1716098
5:  16 2810 544844 105093828 20276816980

Crossrefs

A078469 is the second column of this triangle.

Sequence in context: A066700 A159323 A038218 * A191249 A333544 A005760

Adjacent sequences: A264838 A264839 A264840 * A264842 A264843 A264844

Keyword

nonn,tabl

Author

Linus Hamilton, Nov 26 2015

Status

approved