cp's OEIS Frontend

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.

%I A226997 #45 May 12 2017 11:27:04
%S A226997 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,
%T A226997 0,0,0,0,1,1,25,228,964,2003,2178,1842,1626,725,290,376,184,140,76,4,
%U A226997 0,5,0,0,0,0,0,0,0,0,1,1,36,520,3920,16859,42944,67312
%N 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.
%C A226997 The n-th row contains (n-1)^2 + 1 elements.
%H A226997 Alois P. Heinz, <a href="/A226997/b226997.txt">Rows n = 1..16, flattened</a> (Rows n = 1..7 from Christopher Hunt Gribble)
%F A226997 Sum_{k=0..(n-1)^2} T(n,k) = A045846(n).
%F A226997 From _Christopher Hunt Gribble_, Jul 02 2013: (Start)
%F A226997 It appears that:
%F A226997 T(n,1) = (n-1)^2, n>1 = A000290(n-1).
%F A226997 T(n,2) = (n-2)(n-3)(n^2+n-4)/2, n>2 = A061995(n-1).
%F A226997 T(n,3) = (n-2)(n-3)(n^4-n^3-23n^2+15n+140)/6, n>2 = A061996(n-1).
%F A226997 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)
%e A226997 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:
%e A226997 1 1 1 1    1 1 1 1    1 1 1 1    1 1 1 1
%e A226997 1 0 1 1    1 1 0 1    1 1 1 1    1 1 1 1
%e A226997 1 1 1 1    1 1 1 1    1 0 1 1    1 1 0 1
%e A226997 1 1 1 1    1 1 1 1    1 1 1 1    1 1 1 1
%e A226997 The irregular triangle begins:
%e A226997 \ k 0     1     2     3     4     5     6     7     8     9  ...
%e A226997 n
%e A226997 1   1
%e A226997 2   1     1
%e A226997 3   1     4     0     0     1
%e A226997 4   1     9    16     8     5     0     0     0     0     1
%e A226997 5   1    16    78   140    88    44    68    32     0     4  ...
%e A226997 6   1    25   228   964  2003  2178  1842  1626   725   290  ...
%e A226997 7   1    36   520  3920 16859 42944 67312 72980 69741 62952  ...
%p A226997 b:= proc(n, l) option remember; local i, k, s, t;
%p A226997       if max(l[])>n then 0 elif n=0 or l=[] then 1
%p A226997     elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
%p A226997     else for k do if l[k]=0 then break fi od; s:=0;
%p A226997          for i from k to nops(l) while l[i]=0 do s:=s+x^((i-k)^2)
%p A226997           *b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])
%p A226997          od; expand(s)
%p A226997       fi
%p A226997     end:
%p A226997 T:= n-> (l-> seq(coeff(l,x,i), i=0..degree(l)))(b(n, [0$n])):
%p A226997 seq(T(n), n=1..9);  # _Alois P. Heinz_, Jun 27 2013
%Y A226997 Cf. A045846.
%K A226997 nonn,tabf
%O A226997 1,5
%A A226997 _Christopher Hunt Gribble_, Jun 26 2013