login
Number of spanning trees in G X P_n, where G = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {3, 4}}.
1

%I #20 Jun 15 2024 11:49:35

%S 16,12096,7526400,4600399104,2805387952400,1710196656537600,

%T 1042505162050645904,635487948490723808256,387378914569568374118400,

%U 236137288417488262321070400,143943863916057463999036728976,87744870926093811441456945561600,53487256495669025156132129844140944

%N Number of spanning trees in G X P_n, where G = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {3, 4}}.

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

%H P. Raff, <a href="/A167062/b167062.txt">Table of n, a(n) for n = 1..200</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H P. Raff, <a href="http://arxiv.org/abs/0809.2551">Spanning Trees in Grid Graphs</a>, arXiv:0809.2551 [math.CO], 2008.

%H P. Raff, <a href="http://www.math.rutgers.edu/~praff/span/5/12-13-14-15-23-24-34/index.xml">Analysis of the Number of Spanning Trees of G x P_n, where G = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {3, 4}}.</a> Contains sequence, recurrence, generating function, and more.

%H P. Raff, <a href="http://www.myraff.com/projects/spanning-trees-in-grid-graphs">Analysis of the Number of Spanning Trees of Grid Graphs</a>.

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%H <a href="/index/Rec#order_12">Index entries for linear recurrences with constant coefficients</a>, signature (735, -80115, 2269596, -23630145, 89290005, -139636406, 89290005, -23630145, 2269596, -80115, 735, -1).

%F a(n) = 735*a(n-1) - 80115*a(n-2) + 2269596*a(n-3) - 23630145*a(n-4) + 89290005*a(n-5) - 139636406*a(n-6) + 89290005*a(n-7) - 23630145*a(n-8) + 2269596*a(n-9) - 80115*a(n-10) + 735*a(n-11) - a(n-12).

%F G.f.: -16*x*(x^10 + 21*x^9 - 5145*x^8 + 78288*x^7 - 175246*x^6 + 175246*x^4 - 78288*x^3 + 5145*x^2 - 21*x - 1) / (x^12 - 735*x^11 + 80115*x^10 - 2269596*x^9 + 23630145*x^8 - 89290005*x^7 + 139636406*x^6 - 89290005*x^5 + 23630145*x^4 - 2269596*x^3 + 80115*x^2 - 735*x + 1).

%t CoefficientList[Series[-16 (x^10 + 21 x^9 - 5145 x^8 + 78288 x^7 - 175246 x^6 + 175246 x^4 - 78288 x^3 + 5145 x^2 - 21 x - 1)/(x^12 - 735 x^11 + 80115 x^10 - 2269596 x^9 + 23630145 x^8 - 89290005 x^7 + 139636406 x^6 - 89290005 x^5 + 23630145 x^4 - 2269596 x^3 + 80115 x^2 - 735 x + 1), {x, 0, 12}], x] (* _Wesley Ivan Hurt_, Jan 15 2024 *)

%t LinearRecurrence[{735,-80115,2269596,-23630145,89290005,-139636406,89290005,-23630145,2269596,-80115,735,-1},{16,12096,7526400,4600399104,2805387952400,1710196656537600,1042505162050645904,635487948490723808256,387378914569568374118400,236137288417488262321070400,143943863916057463999036728976,87744870926093811441456945561600},20] (* _Harvey P. Dale_, Jun 15 2024 *)

%K nonn,easy

%O 1,1

%A _Paul Raff_