A227009 Irregular triangle read by rows: T(n,k) is the number of partitions of an n X n square lattice into squares that contain k nodes unconnected to any of their neighbors, considering only the number of parts.
1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 2, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 2, 2, 2, 2, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 3, 3, 4, 4, 4, 3, 4, 3, 2, 2, 2, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
Offset: 1
Examples
For n = 6, there are 3 partitions that contain 8 isolated nodes, so T(6,8) = 3. An m X m square contains (m-1)^2 isolated nodes. Consider that each partition 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 3 partitions are: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Links
- Alois P. Heinz, Rows n = 1..13, flattened (Rows n = 1..7 from Christopher Hunt Gribble)
Crossrefs
Cf. A034295.
Programs
-
Maple
b:= proc(n, l) option remember; local i, k, s, t; if max(l[])>n then {} elif n=0 or l=[] then {0} 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:={}; for i from k to nops(l) while l[i]=0 do s:=s union map(v->v+x^(1+i-k), b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])) od; s fi end: T:= n-> (w->seq(coeff(w, z, h), h=0..(n-1)^2))(add(z^add( coeff(p, x, i)*(i-1)^2, i=2..degree(p)), p=b(n, [0$n]))): seq(T(n), n=1..9); # Alois P. Heinz, Jun 27 2013 -
Mathematica
b[n_, l_List] := b[n, l] = Module[{i, k , s, t}, Which[Max[l] > n, {}, n == 0 || l == {}, {0}, Min[l] > 0, t = Min[l]; b[n-t, l-t], True, For[k = 1, k <= Length[l], k++, If[l[[k]] == 0, Break[]]]; s = {}; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s ~Union~ Map[# + x^(1+i-k)&, b[n, Join[l[[1 ;; k-1]], Array[1+i-k&, i-k+1], l[[i+1 ;; Length[l]]]]]]]; s]]; T[n_] := Function[w, Table[Coefficient[w, z, h], {h, 0, (n-1)^2}]][Sum[ z^Sum[Coefficient[p, x, i]*(i-1)^2, {i, 2, Exponent[p, x]}], {p, b[n, Array[0&, n]]}]]; Table[T[n], {n, 1, 9}] // Flatten (* Jean-François Alcover, Jan 24 2016, after Alois P. Heinz *)
Formula
It appears that T(n,k) = T(n-1,k), n odd, n > 1 and k = 0..(n-1)^2/4.
Sum_{k=0..(n-1)^2} T(n,k) = A034295(n).
Comments