A003746 Number of spanning trees with degrees 1 and 3 in O_5 X P_2n.

540, 1751352, 5386703316, 16582103036544, 51045000577926816, 157132783947988296192, 483704801377335372564480, 1488997578825205151673656448, 4583609224965381313988566950144

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

Table of n, a(n) for n=1..9.

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 O_5 X P_n then

b(1) = 0,

b(2) = 540,

b(3) = 0,

b(4) = 1751352,

b(5) = 0,

b(6) = 5386703316,

b(7) = 0,

b(8) = 16582103036544,

b(9) = 0,

b(10) = 51045000577926816,

b(11) = 0,

b(12) = 157132783947988296192,

b(13) = 0,

b(14) = 483704801377335372564480,

b(15) = 0,

b(16) = 1488997578825205151673656448,

b(17) = 0,

b(18) = 4583609224965381313988566950144,

b(19) = 0,

b(20) = 14109810402621649533503234558344704,

b(21) = 0,

b(22) = 43434494483860386599671308650864330496,

b(23) = 0,

b(24) = 133705220498070622788909783421076412386304,

b(25) = 0,

b(26) = 411587292562609297454750726054600269987912704,

b(27) = 0,

b(28) = 1266996896366237649178359003459366628005457649664,

b(29) = 0,

b(30) = 3900220352788196660232362097608501848215326938755072,

b(31) = 0,

b(32) = 12006121596612176283154633057320394687803565435297505280,

b(33) = 0,

b(34) = 36958669704287162536274146164634194441880201040907341168640,

b(35) = 0,

b(36) = 113770567399219775084499535791661980035376168565367523333734400,

b(37) = 0,

b(38) = 350222075358923174025212352063864697242943327666094722900436582400,

b(39) = 0,

b(40) = 1078095195203820521745918151197065855397382661823414208194364252422144,

b(41) = 0,

b(42) = 3318720696661962582358070874565591095886422622888933137425721520537337856, and

b(n) = 2976b(n-2) + 311460b(n-4) + 10745408b(n-6) + 185361600b(n-8) - 11015685472b(n-10)

- 384432909824b(n-12) + 12586530486400b(n-14) - 142686379766272b(n-16) + 471457558327040b(n-18) + 3354655475796480b(n-20)

- 12936942677605376b(n-22) + 29721236628888576b(n-24) - 167487137019375616b(n-26) - 745271272714235904b(n-28) + 1043959728550182912b(n-30)

- 1512329782916284416b(n-32) + 206265260306202624b(n-34) + 59399388450127872b(n-36) + 26359905185169408b(n-38) + 154793410560000b(n-40).

Crossrefs

Sequence in context: A054562 A056934 A238933 * A203408 A259165 A293393

Adjacent sequences: A003743 A003744 A003745 * A003747 A003748 A003749

Keyword

nonn

Author

Frans J. Faase

Extensions

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

Status

approved