login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #45 May 12 2017 11:27:04

%S 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 0,0,0,0,1,1,25,228,964,2003,2178,1842,1626,725,290,376,184,140,76,4,

%U 0,5,0,0,0,0,0,0,0,0,1,1,36,520,3920,16859,42944,67312

%N 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 The n-th row contains (n-1)^2 + 1 elements.

%H Alois P. Heinz, <a href="/A226997/b226997.txt">Rows n = 1..16, flattened</a> (Rows n = 1..7 from Christopher Hunt Gribble)

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

%F From _Christopher Hunt Gribble_, Jul 02 2013: (Start)

%F It appears that:

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

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

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

%F 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 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1

%e 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1

%e 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e The irregular triangle begins:

%e \ k 0 1 2 3 4 5 6 7 8 9 ...

%e n

%e 1 1

%e 2 1 1

%e 3 1 4 0 0 1

%e 4 1 9 16 8 5 0 0 0 0 1

%e 5 1 16 78 140 88 44 68 32 0 4 ...

%e 6 1 25 228 964 2003 2178 1842 1626 725 290 ...

%e 7 1 36 520 3920 16859 42944 67312 72980 69741 62952 ...

%p b:= proc(n, l) option remember; local i, k, s, t;

%p if max(l[])>n then 0 elif n=0 or l=[] then 1

%p elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))

%p else for k do if l[k]=0 then break fi od; s:=0;

%p for i from k to nops(l) while l[i]=0 do s:=s+x^((i-k)^2)

%p *b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])

%p od; expand(s)

%p fi

%p end:

%p T:= n-> (l-> seq(coeff(l,x,i), i=0..degree(l)))(b(n, [0$n])):

%p seq(T(n), n=1..9); # _Alois P. Heinz_, Jun 27 2013

%Y Cf. A045846.

%K nonn,tabf

%O 1,5

%A _Christopher Hunt Gribble_, Jun 26 2013