A003739 Number of spanning trees in W_5 X P_n.

45, 55125, 59719680, 64416925125, 69471840376125, 74922901143552000, 80801651828175064605, 87141671714980415665125, 93979154798291442260459520, 101353134069755356151903203125

Offset: 1

Author

Frans J. Faase

Keywords

• nonn
• easy

References

• F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Links

• P. Raff, Table of n, a(n) for n = 1..200
• F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
• F. Faase, Counting Hamiltonian cycles in product graphs
• F. Faase, Results from the counting program
• P. Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008.
• P. Raff, Analysis of the Number of Spanning Trees of W_5 x P_n. Contains sequence, recurrence, generating function, and more.
• P. Raff, Analysis of the Number of Spanning Trees of Grid Graphs.
• Index entries for sequences related to trees
• Index entries for linear recurrences with constant coefficients, signature (1152,-80640,1442883,-4477824,4477824,-1442883,80640,-1152,1).

Programs

Magma

R:=PowerSeriesRing(Integers(), 20); Coefficients(R!( 45*x*(1 +73*x -3456*x^2 +4534*x^3 +4534*x^4 -3456*x^5 +73*x^6 +x^7)/(1 -1152*x +80640*x^2 -1442883*x^3 +4477824*x^4 -447782*x^5 +1442883*x^6 -80640*x^7 +1152*x^8 -x^9) )); // G. C. Greubel, Dec 25 2019

Maple

seq(coeff(series(45*x*(1+73*x-3456*x^2+4534*x^3+4534*x^4-3456*x^5+73*x^6 +x^7)/(1-1152*x+80640*x^2-1442883*x^3+4477824*x^4-447782*x^5+1442883*x^6 -80640*x^7+1152*x^8-x^9), x, n+1), x, n), n = 1..20); # G. C. Greubel, Dec 25 2019

Mathematica

Rest@CoefficientList[Series[45*x*(1 +73*x -3456*x^2 +4534*x^3 +4534*x^4 -3456*x^5 +73*x^6 +x^7)/(1 -1152*x +80640*x^2 -1442883*x^3 +4477824*x^4 -447782*x^5 +1442883*x^6 -80640*x^7 +1152*x^8 -x^9), {x,0,20}], x] (* G. C. Greubel, Dec 25 2019 *)

PARI

my(x='x+O('x^20)); Vec(45*x*(1 +73*x -3456*x^2 +4534*x^3 +4534*x^4 -3456*x^5 +73*x^6 +x^7)/(1 -1152*x +80640*x^2 -1442883*x^3 +4477824*x^4 -447782*x^5 +1442883*x^6 -80640*x^7 +1152*x^8 -x^9)) \\ G. C. Greubel, Dec 25 2019

Sage

def A077952_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 45*x*(1 +73*x -3456*x^2 +4534*x^3 +4534*x^4 -3456*x^5 +73*x^6 +x^7)/(1 -1152*x +80640*x^2 -1442883*x^3 +4477824*x^4 -447782*x^5 +1442883*x^6 -80640*x^7 +1152*x^8 -x^9) ).list()
a=A077952_list(20); a[1:] # G. C. Greubel, Dec 25 2019

Formula

a(n) = 1152*a(n-1) - 80640*a(n-2) + 1442883*a(n-3) - 4477824*a(n-4) + 4477824*a(n-5) - 1442883*a(n-6) + 80640*a(n-7) - 1152*a(n-8) + a(n-9).

G.f.: 45*x*(1 +73*x -3456*x^2 +4534*x^3 +4534*x^4 -3456*x^5 +73*x^6 +x^7)/(1 -1152*x +80640*x^2 -1442883*x^3 +4477824*x^4 -447782*x^5 +1442883*x^6 -80640*x^7 +1152*x^8 -x^9).

Extensions

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009