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,5

Comments

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

Links

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

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)

Example

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

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

Crossrefs

Cf. A045846.

Sequence in context: A216273 A327517 A151905 * A245965 A078669 A229655

Adjacent sequences: A226994 A226995 A226996 * A226998 A226999 A227000

Keyword

nonn,tabf

Author

Christopher Hunt Gribble, Jun 26 2013

Status

approved