A003774 Number of spanning trees with degrees 1 and 3 in K_4 X P_n.

4, 48, 672, 8496, 106944, 1349760, 17032800, 214925952, 2712031104, 34221651456, 431824387584, 5448956749824, 68757417818112, 867612411420672, 10947928532312064, 138145948088696832, 1743188486941802496, 21996346205207396352, 277559913918513414144, 3502377399216197074944

Offset

1,1

References

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

Links

Andrew Howroyd, Table of n, a(n) for n = 1..500

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

Index entries for sequences related to trees

Index entries for linear recurrences with constant coefficients, signature (12,4,48).

Formula

a(n) = 12*a(n-1) + 4*a(n-2) + 48*a(n-3) for n > 7.

G.f.: 4*x*(1+20*x^2+12*x^3+48*x^5+24*x^6)/(1-12*x-4*x^2-48*x^3). - R. J. Mathar, Dec 16 2008

Mathematica

LinearRecurrence[{12, 4, 48}, {4, 48, 672, 8496, 106944, 1349760, 17032800}, 20] (* Harvey P. Dale, Jun 02 2026 *)

Crossrefs

Sequence in context: A126967 A098402 A333481 * A214819 A211198 A179235

Adjacent sequences: A003771 A003772 A003773 * A003775 A003776 A003777

Keyword

nonn,easy,changed

Author

Frans J. Faase

Extensions

a(17) onward from Andrew Howroyd, Nov 07 2025

Status

approved