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

Author

Linus Hamilton, Nov 26 2015

Keywords

• nonn
• tabl

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.

Examples

			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
		

Links

• 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.

Crossrefs

A078469 is the second column of this triangle.

Formula

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

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