A003733 -id:A003733 - 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]

A143699 a(n) = 19a(n-1) - 41a(n-2) + 19*a(n-3) - a(n-4).

Original entry on oeis.org

0, 1, 19, 319, 5301, 88000, 1460701, 24245719, 402446619, 6680076601, 110880352000, 1840465787401, 30549274537419, 507077165538919, 8416803858813901, 139707705280792000, 2318961358994380101

Offset: 0

N. J. A. Sloane, based on email from R. K. Guy, Feb 08 2009

This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m).
A003733 = 5 * (A143699)^2. - R. K. Guy, Mar 11 2010
The sequence is the case P1 = 19, P2 = 39, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Apr 03 2014

G. C. Greubel, Table of n, a(n) for n = 0..750
Per Hakan Lundow, Enumeration of matchings in polygraphs, Section 8.1.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (19,-41,19,-1).

Cf. A003733, A100047.

I:=[0,1,19,319]; [n le 4 select I[n] else 19*Self(n-1) -41*Self(n-2) +19*Self(n-3) -Self(n-4): n in [1..30]]; // G. C. Greubel, May 31 2021

LinearRecurrence[{19,-41,19,-1}, {0,1,19,319}, 20] (* Jean-François Alcover, Dec 12 2016 *)

{a(n) = n = abs(n); polcoeff( x*(1-x^2)/(1 -19*x +41*x^2 -19*x^3 +x^4) + x*O(x^n), n)} \\ Michael Somos, Feb 24 2009

def A143699_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(1-x^2)/(1 -19*x +41*x^2 -19*x^3 +x^4) ).list()
A143699_list(30) # G. C. Greubel, May 31 2021

Equals sqrt(A003733(n)/5).
G.f.: x*(1+x)*(1-x)/(1 - 19*x + 41*x^2 - 19*x^3 + x^4). - R. J. Mathar, Feb 09 2009
a(-n) = a(n). - Michael Somos, Feb 24 2009
a(n) = (r1^n + r2^n - r3^n - r4^n) / s1 where s1 = sqrt(205), s2 = sqrt(550 + 38*s1), s3 = 36 * sqrt(5) / s2, r1 = (19 + s1 + s2) / 4, r2 = 1/r1, r3 = (19 - s1 + s3) / 4, r4 = 1/r3. - Michael Somos, Feb 12 2012
From Peter Bala, Apr 03 2014: (Start)
a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), n >= 1, where alpha = (1/4)*(19 + sqrt(205)), beta = (1/4)*(19 - sqrt(205)) and where T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n)= U(n-1, (sqrt(5) - 9)/4)*U(n-1, -(sqrt(5) + 9)/4) for n >= 1, where U(n,x) denotes the Chebyshev polynomial of the second kind.
a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, -39/4; 1, 19/2]. See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)

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.

A210813 Number of spanning trees in C_10 X P_n.

Original entry on oeis.org

10, 2620860, 321437558750, 34966152200584440, 3696387867279360000000, 387686455761449000565832500, 40568852698294278820875719309510, 4242420895960521871557351517779467760, 443556393051604632125747307341249759676250

Offset: 1

Alois P. Heinz, Mar 26 2012

A linear divisibility sequence: Factorizes as a product of second-order and fourth-order linear divisibility sequences. See the Formula section. - Peter Bala, May 02 2014

Alois P. Heinz, Table of n, a(n) for n = 1..50
Index to divisibility sequences

10th column of A173958.

Cf. A001109, A003733, A143699, A241606.

seq(expand(10*ChebyshevU(n-1,3)*( ChebyshevU(n-1,(7 + sqrt(5))/4)*ChebyshevU(n-1,(7 - sqrt(5))/4) )^2 * ( ChebyshevU(n-1,(9 + sqrt(5))/4)*ChebyshevU(n-1,(9 - sqrt(5))/4) )^2), n = 1..10); # Peter Bala, May 02 2014

From Peter Bala, May 02 2014: (Start)
a(n) = 10*U(n-1,3)*( U(n-1,(7 + sqrt(5))/4)*U(n-1,(7 - sqrt(5))/4) )^2 * ( U(n-1,(9 + sqrt(5))/4)*U(n-1,(9 - sqrt(5))/4) )^2, where U(n,x) is a Chebyshev polynomial of the second kind,
a(n) = 10*A001109(n) * A241606(n)^2 * A143699(n)^2 = 2*A001109(n) * A241606(n)^2 * A003733(n). (End)

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

A143699 a(n) = 19*a(n-1) - 41*a(n-2) + 19*a(n-3) - a(n-4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

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

A210813 Number of spanning trees in C_10 X P_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A143699 a(n) = 19a(n-1) - 41a(n-2) + 19*a(n-3) - a(n-4).