A003753 -id:A003753 - cp's OEIS frontend

A173958 Number A(n,k) of spanning trees in C_k X P_n; square array A(n,k), n>=1, k>=1, read by antidiagonals.

1, 2, 1, 3, 12, 1, 4, 75, 70, 1, 5, 384, 1728, 408, 1, 6, 1805, 31500, 39675, 2378, 1, 7, 8100, 508805, 2558976, 910803, 13860, 1, 8, 35287, 7741440, 140503005, 207746836, 20908800, 80782, 1, 9, 150528, 113742727, 7138643400, 38720000000, 16864848000, 479991603, 470832, 1

Offset: 1

Alois P. Heinz, Nov 26 2010

Every row and every column of the array is a divisibility sequence, i.e., the terms satisfy the property that if n divides m then a(n) divides a(m) provided a(n) > 0. This follows from the representation of the elements of the array as a resultant. - Peter Bala, May 01 2014

			Square array A(n,k) begins:
  1,    2,      3,         4,           5,  ...
  1,   12,     75,       384,        1805,  ...
  1,   70,   1728,     31500,      508805,  ...
  1,  408,  39675,   2558976,   140503005,  ...
  1, 2378, 910803, 207746836, 38720000000,  ...

Alois P. Heinz, Antidiagonals n = 1..60, flattened
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. See p. 210. - From _N. J. A. Sloane_, May 27 2012
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Path Graph
Wikipedia, Kirchhoff's theorem

Columns k=1-11 give: A000012, A001542, A003690, A003753, A003733, A158880, A158898, A210812, A174001, A210813, A174089.
Rows n=1-2 give: A000027, A006235.
Main diagonal gives A252767.
Cf. A156308.

with(LinearAlgebra):
A:= proc(n, m) local M, i, j;
     if m=1 then 1 else
      M:= Matrix(n*m, shape=symmetric);
      for i to n do
        for j to m-1 do M[m*(i-1)+j, m*(i-1)+j+1]:=-1 od;
        M[m*(i-1)+1, m*i]:= M[m*(i-1)+1, m*i]-1
      od;
      for i to n-1 do
        for j to m do M[m*(i-1)+j, m*i+j]:=-1 od
      od;
      for i to n*m do
        M[i,i]:= -add(M[i,j], j=1..n*m)
      od;
      Determinant(DeleteColumn(DeleteRow(M, 1), 1))
     fi
    end:
seq(seq(A(n, 1+d-n), n=1..d), d=1..9);
# Crude Maple program from N. J. A. Sloane, May 27 2012:
Digits:=200;
T:=(m,n)->round(Re(evalf(simplify(expand(
m*mul(mul( 4*sin(h*Pi/m)^2+4*sin(k*Pi/(2*n))^2, h=1..m-1), k=1..n-1))))));
# Alternative program using the resultant:
for n from 1 to 10 do seq(k*resultant(simplify((2*(ChebyshevT(k,(x + 2)/2) - 1))/x), simplify(ChebyshevU(n-1,1 - x/2)), x), k = 1 .. 10) end do; # Peter Bala, May 01 2014

t[m_, n_] := m*Product[Product[4*Sin[h*Pi/m]^2 + 4*Sin[k*Pi/(2*n)]^2, {h, 1, m-1}], {k, 1, n-1}]; Table[t[m, n-m+1] // Round, {n, 1, 9}, {m, n, 1, -1}] // Flatten (* Jean-François Alcover, Dec 05 2013, after N. J. A. Sloane *)

A(n,k) = m*Prod(Prod( 4*sin(h*Pi/m)^2+4*sin(k*Pi/(2*n))^2, h=1..m-1), k=1..n-1) [Kreweras]. - From N. J. A. Sloane, May 27 2012

Let T(n,x) and U(n,x) denote the Chebyshev polynomials of the first and second kind respectively. Let R(n,x) = 2*( T(n,(x + 2)/2) - 1 )/x (the row polynomials of A156308). Then the (n,k)-th element of the array equals k times the resultant (R(k,x), U(n-1,(2 - x)/2)). - Peter Bala, May 01 2014 [Corrected by Pontus von Brömssen, Apr 08 2025]

A158880 Number of spanning trees in C_6 X P_n.

Original entry on oeis.org

6, 8100, 7741440, 7138643400, 6551815840350, 6009209192448000, 5511006731579419434, 5054037303588059379600, 4634949992739663836897280, 4250612670512943969574312500, 3898145031429828405122837863554

Offset: 1

Alois P. Heinz, Mar 28 2009

A linear divisibility sequence of order 18. - Peter Bala, May 02 2014

Alois P. Heinz, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Path Graph
Eric Weisstein's World of Mathematics, Spanning Tree
Index to divisibility sequences

Column 6 of A173958.

Cf. A001353, A003690, A003753, A003733, A158898. A001109, A001906, A004254.

a:= n-> 6* (Matrix(1,18, (i,j)-> -sign(j-10) *[0, 1, 1350, 1290240, 1189773900, 1091969306725, 1001534865408000, 918501121929903239, 842339550598009896600, 772491665456610639482880][1+abs(j-10)]). Matrix(18, (i,j)-> if i=j-1 then 1 elif j=1 then [842608511100, -639641521152, 276457068288, -65829977967, 8292106368, -524839680, 16393554, -232704, 1152, -1][1+abs(i-9)] else 0 fi)^n) [1,10]: seq(a(n), n=1..15);

See program.

a(n) = 6*U(n-1,3/2)^2*U(n-1,5/2)^2*U(n-1,3) = 6*A001906(n)^2*A004254(n)^2*A001109(n), where U(n,x) is a Chebyshev polynomial of the second kind. - Peter Bala, May 02 2014

A158898 Number of spanning trees in C_7 X P_n.

Original entry on oeis.org

7, 35287, 113742727, 347251215703, 1050773495363767, 3174564739209417463, 9588099190533549457408, 28957256518828921149989143, 87453655435340440175476698487, 264117827347202707929587420182327

Offset: 1

Alois P. Heinz, Mar 29 2009

Alois P. Heinz, Table of n, a(n) for n = 1..288
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Path Graph

7th column of A173958.

Cf. A001353, A003690, A003753, A003733, A158880.

a:= n-> 7* (Matrix([222727, 4031, 71, 1, 0, -1, -71, -4031]). Matrix(8, (i,j)-> if i=j-1 then 1 elif j=1 then [71, -952, 3976, -6384, 3976, -952, 71, -1][i] else 0 fi)^n)[1,5]^2: seq(a(n), n=1..15);

See program.

A174001 Number of spanning trees in C_9 X P_n.

Original entry on oeis.org

9, 632025, 23057815104, 763341471963225, 24743382596536452489, 797880028172050676793600, 25694231385152383926116001849, 827147402338052897443922764419225, 26625078176206788678765153788526329856

Offset: 1

Alois P. Heinz, Nov 26 2010

Alois P. Heinz, Table of n, a(n) for n = 1..70
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Path Graph
Eric Weisstein's World of Mathematics, Spanning Tree

9th column of A173958.

Cf. A000012, A001542, A003690, A003753, A003733, A158880, A158898.

a:= n-> 9* (Matrix([[0, 1, 265, 50616, 9209545, 1658090689, 297747101520, 53431400864569, 9586723471888105][1+abs(i)]$i=-7..8]). Matrix(16, (i, j)-> if i=j-1 then 1 elif j=1 then [[-427427424, 327381265, -146975161, 38357160, -5699687, 457655, -17736, 265, -1][1+abs(k)]$k=-7..8][i] else 0 fi)^n)[1, 8]^2: seq(a(n), n=1..20);

See program.

A174089 Number of spanning trees in C_11 X P_n.

Original entry on oeis.org

11, 10759331, 4435600730891, 1584603178322856659, 545701094921321191290251, 185861400461684004931359802019, 63080339061067311398935095930531419, 21384626538080492686675351682716886393459

Offset: 1

Alois P. Heinz, Nov 26 2010

Alois P. Heinz, Table of n, a(n) for n = 1..180
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Path Graph
Eric Weisstein's World of Mathematics, Spanning Tree

11th column of A173958.

Cf. A000012, A001542, A003690, A003753, A003733, A158880, A158898.

a:= n-> 11* (Matrix([[0, 1, 989, 635009, 379545563, 222731206721, 129986502957277, 75726985139241127, 44091461282285910613, 25667108238650778993721, 14940759758135641310394029, 8696803311384043382138568704, 5062251640287899331740697744283, 2946638531103878161891572927216367, 1715179927870529863091149494541065923, 998372029710787510889689081784904921409, 581132402632124482558541496059410958698763][1+abs(i)]*
signum(-i)$i=-15..16]). Matrix(32, (i, j)-> if i=j-1 then 1 elif j=1 then [[-9866686348925002518, 8584218556222705486, -5646220475933195574, 2797526034931937278, -1038052511465703094, 286230180847745070, -58096997326051905, 8585065341436957, -911803001143321, 68534901051869, -3574487862001, 125866549709, -2870938929, 39687581, -297177, 989, -1] [1+abs(k)]$k=-15..16][i] else 0 fi)^n)[1, 16]^2: seq(a(n), n=1..20);

See program.

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.

Original entry on oeis.org

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

Pontus von Brömssen, Nov 11 2020

nonn

a(n) > 1 precisely when n is composite.

			The partition (2, 2, 1) has Heinz number 18 and the 3 X 3 X 2 grid graph has a(18) = 49766400 spanning trees.

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

X n grid: A001353(n) = a(2*prime(n-1))
X n grid: A006238(n) = a(3*prime(n-1))
X n grid: A003696(n) = a(5*prime(n-1))
X n grid: A003779(n) = a(7*prime(n-1))
X n grid: A139400(n) = a(11*prime(n-1))
X n grid: A334002(n) = a(13*prime(n-1))
X n grid: A334003(n) = a(17*prime(n-1))
X n grid: A334004(n) = a(19*prime(n-1))
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))
X 2 X n grid: A003753(n) = a(4*prime(n-1))
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)
X ... X 2 grid: A006237(n) = a(2^n)

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.

cp's OEIS Frontend

A173958 Number A(n,k) of spanning trees in C_k X P_n; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A158880 Number of spanning trees in C_6 X P_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A158898 Number of spanning trees in C_7 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A174001 Number of spanning trees in C_9 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A174089 Number of spanning trees in C_11 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula