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, 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
Keywords
Examples
The partition (2, 2, 1) has Heinz number 18 and the 3 X 3 X 2 grid graph has a(18) = 49766400 spanning trees.
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
- Index entries for sequences related to 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)
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.
Comments