A003740 Number of spanning trees with degrees 1 and 3 in W_5 X P_2n.

208, 335344, 503672968, 757005488704, 1137734095903816, 1709944335224262352, 2569941155563565968488, 3862463470575397280285088, 5805045002479537990606632936

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

Sean A. Irvine, Table of n, a(n) for n = 1..100

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

Formula

If b(n) denotes the number of spanning trees with degrees 1 and 3 in W_5 X P_n we have:

b(1) = 0,

b(2) = 208,

b(3) = 0,

b(4) = 335344,

b(5) = 0,

b(6) = 503672968,

b(7) = 0,

b(8) = 757005488704,

b(9) = 0,

b(10) = 1137734095903816,

b(11) = 0,

b(12) = 1709944335224262352,

b(13) = 0,

b(14) = 2569941155563565968488,

b(15) = 0,

b(16) = 3862463470575397280285088,

b(17) = 0,

b(18) = 5805045002479537990606632936,

b(19) = 0,

b(20) = 8724625549856078166453269723376,

b(21) = 0,

b(22) = 13112575518826856642901203139743240,

b(23) = 0,

b(24) = 19707394403851935411114869745719526144,

b(25) = 0,

b(26) = 29619001517386258600018494299567252781896,

b(27) = 0,

b(28) = 44515537310983054901068606912734277302893072,

b(29) = 0,

b(30) = 66904114270101652083096747543361961556161338280,

b(31) = 0,

b(32) = 100552768239022085083137539569611934600600485769824,

b(33) = 0,

b(34) = 151124625306471850563573728012268031905685321872309416,

b(35) = 0,

b(36) = 227131015624872535892492790329036203871753015873169846576,

b(37) = 0,

b(38) = 341363944851262010688127945467040823127463725134532755058760,

b(39) = 0,

b(40) = 513049010606610528824074852666729120665123598849369486838352320,

b(41) = 0,

b(42) = 771081103480659083177648561305159418338110532879217116850112505608,

b(43) = 0,

b(44) = 1158887466602766746036049127283646002598030062997458201209529788050000, and

b(n) = 1498b(n-2) + 9727b(n-4) - 3430420b(n-6) - 51780334b(n-8) + 2175631056b(n-10)

- 3049771912b(n-12) + 20785260864b(n-14) - 885420351008b(n-16) + 2723994857536b(n-18) + 5274700679360b(n-20)

+ 125883661338368b(n-22) + 354089303896576b(n-24) - 880465464686592b(n-26) - 28529345908736b(n-28) + 3938132497694720b(n-30)

- 1757770863747072b(n-32) - 1334108047147008b(n-34) - 337906312937472b(n-36) - 49853396680704b(n-38) - 3371549327360b(n-40).

Crossrefs

Sequence in context: A184276 A268091 A209300 * A303688 A080532 A153442

Adjacent sequences: A003737 A003738 A003739 * A003741 A003742 A003743

Keyword

nonn

Author

Frans J. Faase

Extensions

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

Status

approved