A225777 Number T(n,k,u) of distinct tilings of an n X k rectangle using integer-sided square tiles containing u nodes that are unconnected to any of their neighbors; irregular triangle T(n,k,u), 1 <= k <= n, u >= 0, read by rows.
1, 1, 1, 1, 1, 1, 2, 1, 4, 0, 0, 1, 1, 1, 3, 1, 1, 6, 4, 0, 2, 1, 9, 16, 8, 5, 0, 0, 0, 0, 1, 1, 1, 4, 3, 1, 8, 12, 0, 3, 4, 1, 12, 37, 34, 15, 12, 4, 0, 0, 2, 1, 16, 78, 140, 88, 44, 68, 32, 0, 4, 0, 0, 0, 0, 0, 0, 1
Offset: 1
Examples
The irregular triangle begins: n,k\u 0 1 2 3 4 5 6 7 8 9 10 11 12 ... 1,1 1 2,1 1 2,2 1 1 3,1 1 3,2 1 2 3,3 1 4 0 0 1 4,1 1 4,2 1 3 1 4,3 1 6 4 0 2 4,4 1 9 16 8 5 0 0 0 0 1 5,1 1 5,2 1 4 3 5,3 1 8 12 0 3 4 5,4 1 12 37 34 15 12 4 0 0 2 5,5 1 16 78 140 88 44 68 32 0 4 0 0 0 ... ... For n = 4, k = 3, there are 4 tilings that contain 2 isolated nodes, so T(4,3,2) = 4. A 2 X 2 square contains 1 isolated node. Consider that each tiling is composed of ones and zeros where a one represents a node with one or more links to its neighbors and a zero represents a node with no links to its neighbors. Then the 4 tilings are: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Links
- Christopher Hunt Gribble, Rows 1..36 for n=2..8 and k=1..n flattened
- Christopher Hunt Gribble, C++ program
Formula
T(n,k,0) = 1, T(n,k,1) = (n-1)(k-1), T(n,k,2) = (n^2(k-1) - n(2k^2+5k-13) + (k^2+13k-24))/2.
Sum_{u=1..(n-1)^2} T(n,n,u) = A045846(n).
Comments