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!)
A338100 Number of spanning trees in the n X 2 king graph. 2
1, 16, 192, 2304, 27648, 331776, 3981312, 47775744, 573308928, 6879707136, 82556485632, 990677827584, 11888133931008, 142657607172096, 1711891286065152, 20542695432781824, 246512345193381888, 2958148142320582656, 35497777707846991872, 425973332494163902464, 5111679989929966829568 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

Table of n, a(n) for n=1..21.

Eric Weisstein's World of Mathematics, King Graph

Eric Weisstein's World of Mathematics, Spanning Tree

Index entries for linear recurrences with constant coefficients, signature (12).

FORMULA

a(n) = 12 * a(n-1) for n > 2.

a(n) = 3^(n-2) * 4^n for n > 1.

G.f.: x*(1 + 4*x)/(1 - 12*x). - Stefano Spezia, Nov 29 2020

PROG

(Python)

# Using graphillion

from graphillion import GraphSet

def make_nXk_king_graph(n, k):

    grids = []

    for i in range(1, k + 1):

        for j in range(1, n):

            grids.append((i + (j - 1) * k, i + j * k))

            if i < k:

                grids.append((i + (j - 1) * k, i + j * k + 1))

            if i > 1:

                grids.append((i + (j - 1) * k, i + j * k - 1))

    for i in range(1, k * n, k):

        for j in range(1, k):

            grids.append((i + j - 1, i + j))

    return grids

def A338029(n, k):

    if n == 1 or k == 1: return 1

    universe = make_nXk_king_graph(n, k)

    GraphSet.set_universe(universe)

    spanning_trees = GraphSet.trees(is_spanning=True)

    return spanning_trees.len()

def A338100(n):

    return A338029(n, 2)

print([A338100(n) for n in range(1, 20)])

CROSSREFS

Column 2 of A338029.

Sequence in context: A317601 A000767 A053539 * A218176 A120994 A016178

Adjacent sequences:  A338097 A338098 A338099 * A338101 A338102 A338103

KEYWORD

nonn,easy

AUTHOR

Seiichi Manyama, Nov 29 2020

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 June 23 04:15 EDT 2021. Contains 345395 sequences. (Running on oeis4.)