A226997 Irregular triangle read by rows: T(n,k) is the number of distinct tilings by squares of an n X n square lattice that contain k nodes unconnected to any of their neighbors.

1, 1, 1, 1, 4, 0, 0, 1, 1, 9, 16, 8, 5, 0, 0, 0, 0, 1, 1, 16, 78, 140, 88, 44, 68, 32, 0, 4, 0, 0, 0, 0, 0, 0, 1, 1, 25, 228, 964, 2003, 2178, 1842, 1626, 725, 290, 376, 184, 140, 76, 4, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 36, 520, 3920, 16859, 42944, 67312

Offset: 1

Author

Christopher Hunt Gribble, Jun 26 2013

Keywords

• nonn
• tabf

Comments

The n-th row contains (n-1)^2 + 1 elements.

Examples

			For n = 3, there are 4 tilings that contain 1 isolated node, so T(3,1) = 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 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 1 1 1    1 1 1 1    1 1 1 1    1 1 1 1
The irregular triangle begins:
\ k 0     1     2     3     4     5     6     7     8     9  ...
n
1   1
2   1     1
3   1     4     0     0     1
4   1     9    16     8     5     0     0     0     0     1
5   1    16    78   140    88    44    68    32     0     4  ...
6   1    25   228   964  2003  2178  1842  1626   725   290  ...
7   1    36   520  3920 16859 42944 67312 72980 69741 62952  ...
		

Links

• Alois P. Heinz, Rows n = 1..16, flattened (Rows n = 1..7 from Christopher Hunt Gribble)

Crossrefs

Cf. A045846.

Programs

Maple

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then 0 elif n=0 or l=[] then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; s:=0;
         for i from k to nops(l) while l[i]=0 do s:=s+x^((i-k)^2)
          *b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])
         od; expand(s)
      fi
    end:
T:= n-> (l-> seq(coeff(l,x,i), i=0..degree(l)))(b(n, [0$n])):
seq(T(n), n=1..9);  # Alois P. Heinz, Jun 27 2013

Formula

Sum_{k=0..(n-1)^2} T(n,k) = A045846(n).

From Christopher Hunt Gribble, Jul 02 2013: (Start)

It appears that:

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

T(n,2) = (n-2)(n-3)(n^2+n-4)/2, n>2 = A061995(n-1).

T(n,3) = (n-2)(n-3)(n^4-n^3-23n^2+15n+140)/6, n>2 = A061996(n-1).

T(n,4) = (n^8 - 8n^7 - 26*n^6 + 340*n^5 - 105*n^4 - 4708*n^3 + 6814*n^2 + 20852*n - 40248)/24, n>3. (End)