login
A338832
Number of spanning trees in the k_1 X ... X k_j grid graph, where (k_1 - 1, ..., k_j - 1) is the partition with Heinz number n.
1
1, 1, 1, 4, 1, 15, 1, 384, 192, 56, 1, 31500, 1, 209, 2415, 42467328, 1, 49766400, 1, 2558976, 30305, 780, 1, 3500658000000, 100352, 2911, 8193540096000, 207746836, 1, 76752081000, 1, 20776019874734407680, 380160, 10864, 4140081, 242716067758080000000, 1
OFFSET
1,4
COMMENTS
a(n) > 1 precisely when n is composite.
LINKS
Pontus von Brömssen, Table of n, a(n) for n = 1..1151
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory B 24 (1978), 202-212.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Spanning Tree
FORMULA
a(n) = Product_{n_1=0..k_1-1, ..., n_j=0..k_j-1; not all n_i=0} Sum_{i=1..j} (2*(1 - cos(n_i*Pi/k_i))) / Product_{i=1..j} k_i, where (k_1 - 1, ..., k_j - 1) is the partition with Heinz number n.
EXAMPLE
The partition (2, 2, 1) has Heinz number 18 and the 3 X 3 X 2 grid graph has a(18) = 49766400 spanning trees.
CROSSREFS
2 X n grid: A001353(n) = a(2*prime(n-1))
3 X n grid: A006238(n) = a(3*prime(n-1))
4 X n grid: A003696(n) = a(5*prime(n-1))
5 X n grid: A003779(n) = a(7*prime(n-1))
6 X n grid: A139400(n) = a(11*prime(n-1))
7 X n grid: A334002(n) = a(13*prime(n-1))
8 X n grid: A334003(n) = a(17*prime(n-1))
9 X n grid: A334004(n) = a(19*prime(n-1))
10 X n grid: A334005(n) = a(23*prime(n-1))
n X n grid: A007341(n) = a(prime(n-1)^2)
m X n grid: A116469(m,n) = a(prime(m-1)*prime(n-1))
2 X 2 X n grid: A003753(n) = a(4*prime(n-1))
2 X n X n grid: A067518(n) = a(2*prime(n-1)^2)
n X n X n grid: A071763(n) = a(prime(n-1)^3)
2 X ... X 2 grid: A006237(n) = a(2^n)
Sequence in context: A328235 A293129 A200062 * A229468 A319039 A107873
KEYWORD
nonn
AUTHOR
STATUS
approved