|
|
A174579
|
|
Number of spanning trees in the n-triangular grid graph.
|
|
3
|
|
|
1, 3, 54, 5292, 2723220, 7242690816, 98719805835000, 6861326937782575104, 2423821818614367091537296, 4342290918217084382837760000000, 39389085041906366256386454778172877408, 1807026244113880332171608161401397806958116864
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
The n-triangular grid graph has n+1 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The Graph has A000217(n+1) vertices and 3*A000217(n) edges altogether.
|
|
LINKS
|
|
|
MAPLE
|
with(LinearAlgebra):
tr:= n-> n*(n+1)/2:
a:= proc(n) local h, i, M;
if n=0 then 1 else
M:= Matrix(tr(n+1), shape=symmetric);
for h in [seq(seq([[i, i+j], [i, i+j+1], [i+j, i+j+1]][],
i=tr(j-1)+1 .. tr(j-1)+j), j=1..n)]
do M[h[]]:= -1 od;
for i to tr(n+1) do M[i, i]:= -add(M[i, j], j=1..tr(n+1)) od;
Determinant(DeleteColumn(DeleteRow(M, 1), 1))
fi
end:
seq(a(n), n=0..12);
|
|
MATHEMATICA
|
tr[n_] := n*(n + 1)/2;
a[0] = 1; a[n_] := Module[{T, M}, T = Table[Table[{{i, i+j}, {i, i+j+1}, {i + j, i+j+1}}, {i, tr[j-1]+1, tr[j-1] + j}], {j, 1, n}] // Flatten[#, 2]&; M = Array[0&, {tr[n+1], tr[n+1]}]; Do[{i, j} = h; M[[i, j]] = -1, {h, T}]; M = M + Transpose[M]; For[i = 1, i <= tr[n+1], i++, M[[i, i]] = -Sum[M[[i, j]], {j, 1, tr[n+1]}]]; Det[Rest /@ Rest[M]]];
|
|
PROG
|
(Python)
# Using graphillion
from graphillion import GraphSet
def make_n_triangular_grid_graph(n):
s = 1
grids = []
for i in range(n + 1, 1, -1):
for j in range(i - 1):
a, b, c = s + j, s + j + 1, s + i + j
grids.extend([(a, b), (a, c), (b, c)])
s += i
return grids
if n == 0: return 1
universe = make_n_triangular_grid_graph(n)
GraphSet.set_universe(universe)
spanning_trees = GraphSet.trees(is_spanning=True)
return spanning_trees.len()
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|