A212798 -id:A212798 - cp's OEIS frontend

A212796 Square array read by antidiagonals: T(m,n) = number of spanning trees in C_m X C_n.

1, 2, 2, 3, 32, 3, 4, 294, 294, 4, 5, 2304, 11664, 2304, 5, 6, 16810, 367500, 367500, 16810, 6, 7, 117600, 10609215, 42467328, 10609215, 117600, 7, 8, 799694, 292626432, 4381392020, 4381392020, 292626432, 799694, 8, 9, 5326848, 7839321861, 428652000000, 1562500000000, 428652000000, 7839321861, 5326848, 9

Offset: 1

N. J. A. Sloane, May 27 2012

			Array begins:
  1,    2,      3,        4,          5,            6               7, ...
  2,   32,    294,     2304,      16810,       117600,         799694, ...
  3,  294,  11664,   367500,   10609215,    292626432,     7839321861, ...
  4, 2304, 367500, 42467328, 4381392020, 428652000000, 40643137651228, ...
  ...

Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. See p. 210, Parag. 4.
Eric Weisstein's World of Mathematics, Spanning Tree
Eric Weisstein's World of Mathematics, Torus Grid Graph

Rows and columns 1..10 give A000027, A212797, A212798, A212799, A358810, A358811, A358812, A358813, A358814, A358815.
Diagonal gives A212800.
Cf. A116469, A173958, A340560.

Digits:=200;
T:=(m,n)->round(Re(evalf(simplify(expand(
m*n*mul(mul( 4*sin(h*Pi/m)^2+4*sin(k*Pi/n)^2, h=1..m-1), k=1..n-1))))));

default(realprecision, 120);
{T(n, k) = round(n*k*prod(a=1, n-1, prod(b=1, k-1, 4*sin(a*Pi/n)^2+4*sin(b*Pi/k)^2)))} \\ Seiichi Manyama, Jan 13 2021

T(m,n) = m*n*Prod(Prod( 4*sin(h*Pi/m)^2+4*sin(k*Pi/n)^2, h=1..m-1), k=1..n-1).

A175243 Array read by antidiagonals: total number of spanning trees R_n(m) of the complete prism K_m X C_n.

Original entry on oeis.org

1, 2, 1, 3, 12, 3, 4, 75, 294, 16, 5, 384, 11664, 16384, 125, 6, 1805, 367500, 5647152, 1640250, 1296, 7, 8100, 10609215, 1528823808, 6291456000, 259200000, 16807, 8, 35287, 292626432, 380008339280, 18911429680500, 13556617751088, 59549251454

Offset: 1

R. J. Mathar, Mar 13 2010

			The array starts in row n=1 as:
  1,    1,        3,         16,        125
  2,   12,      294,      16384,    1640250
  3,   75,    11664,    5647152, 6291456000
  4,  384,   367500, 1528823808,
  5, 1805, 10609215,

F. T. Boesch and H. Prodinger, Spanning tree formulas and Chebyshev polynomials, Graphs Combinat. 2 (1986) 191-200.
Index entries for sequences related to trees

Cf. A006235 (column 2), A000272, A212798 (column 3).

A175243 := proc(n,m) n*2^(m-1)/m*( orthopoly[T](n,1+m/2)-1)^(m-1) ; end proc:
for d from 2 to 10 do for m from 1 to d-1 do n := d-m ; printf("%d,",A175243(n,m)) ; end do: end do:

r[n_, m_] := n*2^(m-1)*(ChebyshevT[n, 1+m/2]-1)^(m-1)/m; Table[r[n-m, m], {n, 2, 9}, {m, 1, n-1}] // Flatten (* Jean-François Alcover, Jan 10 2014 *)

R_n(m) = n*2^(m-1)* (T(n,1+m/2)-1)^(m-1)/m, where T(n,x) are Chebyshev polynomials, A008310.

Each column of the array is a linear divisibility sequence. Conjecturally, the k-th column satisfies a linear recurrence of order 4*k - 2. - Peter Bala, May 04 2014

A212799 Row 4 of array in A212796.

Original entry on oeis.org

4, 2304, 367500, 42467328, 4381392020, 428652000000, 40643137651228, 3771854305099776, 344499209234302500, 31074298464967845120, 2774871814779003772844, 245741556726521856000000, 21611621448116558812137652, 1889376666754339457990201088, 164334311374716912516773437500

Offset: 1

N. J. A. Sloane, May 27 2012

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..24
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. See p. 210, Parag. 4.

Cf. A003696, A212796, A212798.

Table[2^(6*n-4)*n*Product[Sin[j*Pi/4]^2 + Sin[k*Pi/n]^2, {j,1,3}, {k,1,n-1}], {n,1,20}]//Round (* Vaclav Kotesovec, Feb 26 2021 *)

# Using graphillion
from graphillion import GraphSet
def make_CnXCk(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))
        grids.append((i + (n - 1) * k, i))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
        grids.append((i + k - 1, i))
    return grids
def A212799(n):
    if n == 1: return 4
    if n == 2: return 2304
    universe = make_CnXCk(4, n)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
print([A212799(n) for n in range(1, 8)])  # Seiichi Manyama, Nov 22 2020

From Vaclav Kotesovec, Feb 26 2021: (Start)
a(n) ~ (21 + 12*sqrt(3) + 2*sqrt(2*(97 + 56*sqrt(3))))^n * n/4.
G.f.: 4*x*(1 + 310*x - 33278*x^2 + 785814*x^3 + 4923451*x^4 - 476492324*x^5 + 8394222196*x^6 - 74272031652*x^7 + 371582629705*x^8 - 981246223862*x^9 + 441533151262*x^10 + 6161037199338*x^11 - 23802532730757*x^12 + 46995963516168*x^13 - 58240430817576*x^14 + 46995963516168*x^15 - 23802532730757*x^16 + 6161037199338*x^17 + 441533151262*x^18 - 981246223862*x^19 + 371582629705*x^20 - 74272031652*x^21 + 8394222196*x^22 - 476492324*x^23 + 4923451*x^24 + 785814*x^25 - 33278*x^26 + 310*x^27 + x^28)/ ((1 - x)^2*(1 - 14*x + x^2)^2*(1 - 6*x + x^2)^2*(1 - 4*x + x^2)^2* (1 - 84*x + 230*x^2 - 84*x^3 + x^4)^2*(1 - 24*x + 50*x^2 - 24*x^3 + x^4)^2). (End)

a(10)-a(15) from Seiichi Manyama, Nov 22 2020

cp's OEIS Frontend

A212796 Square array read by antidiagonals: T(m,n) = number of spanning trees in C_m X C_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A175243 Array read by antidiagonals: total number of spanning trees R_n(m) of the complete prism K_m X C_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212799 Row 4 of array in A212796.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions