login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A174579 Number of spanning trees in the n-triangular grid graph. 1
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

Alois P. Heinz, Table of n, a(n) for n = 0..50

Eric Weisstein's World of Mathematics, Spanning Tree

Eric Weisstein's World of Mathematics, Triangular Grid Graph

Wikipedia, Kirchhoff's theorem

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

Table[a[n], {n, 0, 12}] (* Jean-Fran├žois Alcover, Jun 02 2018, from Maple *)

CROSSREFS

Cf. A000217.

Sequence in context: A003027 A054545 A158103 * A171739 A157568 A156911

Adjacent sequences:  A174576 A174577 A174578 * A174580 A174581 A174582

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Nov 29 2010

EXTENSIONS

Indexing changed by Alois P. Heinz, Jun 14 2017

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 27 05:24 EDT 2020. Contains 334649 sequences. (Running on oeis4.)