login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A174579 Number of spanning trees in the n-triangular grid graph. 3

%I #38 Nov 30 2020 10:32:28

%S 1,3,54,5292,2723220,7242690816,98719805835000,6861326937782575104,

%T 2423821818614367091537296,4342290918217084382837760000000,

%U 39389085041906366256386454778172877408,1807026244113880332171608161401397806958116864

%N Number of spanning trees in the n-triangular grid graph.

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

%H Alois P. Heinz, <a href="/A174579/b174579.txt">Table of n, a(n) for n = 0..50</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SpanningTree.html">Spanning Tree</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TriangularGridGraph.html">Triangular Grid Graph</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem">Kirchhoff's theorem</a>

%p with(LinearAlgebra):

%p tr:= n-> n*(n+1)/2:

%p a:= proc(n) local h, i, M;

%p if n=0 then 1 else

%p M:= Matrix(tr(n+1), shape=symmetric);

%p for h in [seq(seq([[i, i+j], [i, i+j+1], [i+j, i+j+1]][],

%p i=tr(j-1)+1 .. tr(j-1)+j), j=1..n)]

%p do M[h[]]:= -1 od;

%p for i to tr(n+1) do M[i, i]:= -add(M[i, j], j=1..tr(n+1)) od;

%p Determinant(DeleteColumn(DeleteRow(M, 1), 1))

%p fi

%p end:

%p seq(a(n), n=0..12);

%t tr[n_] := n*(n + 1)/2;

%t 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]]];

%t Table[a[n], {n, 0, 12}] (* _Jean-François Alcover_, Jun 02 2018, from Maple *)

%o (Python)

%o # Using graphillion

%o from graphillion import GraphSet

%o def make_n_triangular_grid_graph(n):

%o s = 1

%o grids = []

%o for i in range(n + 1, 1, -1):

%o for j in range(i - 1):

%o a, b, c = s + j, s + j + 1, s + i + j

%o grids.extend([(a, b), (a, c), (b, c)])

%o s += i

%o return grids

%o def A174579(n):

%o if n == 0: return 1

%o universe = make_n_triangular_grid_graph(n)

%o GraphSet.set_universe(universe)

%o spanning_trees = GraphSet.trees(is_spanning=True)

%o return spanning_trees.len()

%o print([A174579(n) for n in range(8)]) # _Seiichi Manyama_, Nov 30 2020

%Y Cf. A000217, A112676, A266513.

%K nonn

%O 0,2

%A _Alois P. Heinz_, Nov 29 2010

%E Indexing changed by _Alois P. Heinz_, Jun 14 2017

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 06:05 EDT 2024. Contains 370952 sequences. (Running on oeis4.)