A145408 Number of spanning trees with degrees 1 and 3 in O_6 X P_n.

24, 6048, 1431936, 326820576, 74610584016, 17042758679136, 3892782584508480, 889156265863827264, 203093678317841507424, 46388970280261506291456, 10595782951389630699006144

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..11.

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

Formula

Recurrence:

a(1) = 24,

a(2) = 6048,

a(3) = 1431936,

a(4) = 326820576,

a(5) = 74610584016,

a(6) = 17042758679136,

a(7) = 3892782584508480,

a(8) = 889156265863827264,

a(9) = 203093678317841507424,

a(10) = 46388970280261506291456,

a(11) = 10595782951389630699006144,

a(12) = 2420200657566556505910445056,

a(13) = 552802114842508189665069539328,

a(14) = 126266463574145216525332543882752,

a(15) = 28840735944058922301478239666093696,

a(16) = 6587561148465308380773642743145878016,

a(17) = 1504675954488241136540734409327760801024,

a(18) = 343685573004895910322683065681242613824000,

a(19) = 78501801493782514393269579891334793783725056,

a(20) = 17930728904007407186715098489007832537944898560,

a(21) = 4095588036339152450673664069192988041090603630080,

a(22) = 935480172234132922409579369697482180561394428018688,

a(23) = 213674604202973780616456330975690211137136284005071872,

a(24) = 48805776794027507492059897929493900401349262859294019584,

a(25) = 11147809808065542806068516072966273546419446268999208919040,

a(26) = 2546290043518168376834989430543237695836588812241991243628544,

a(27) = 581602404180668450165151946330917571438380808408493632503515136,

a(28) = 132844786244917841301527538905934215543556848752364451671176863744,

a(29) = 30343301722280768281510520455705056105378106879356525016733484257280, and

a(n) = 188a(n-1) + 7998a(n-2) + 259876a(n-3) + 4850072a(n-4) + 22611752a(n-5)

- 292045860a(n-6) - 2811308992a(n-7) - 5710829000a(n-8) + 433981312a(n-9) + 78400774784a(n-10)

+ 212072291968a(n-11) + 563060463616a(n-12) + 1319709281280a(n-13) + 2571710809600a(n-14) + 902094094336a(n-15)

- 1347718762496a(n-16) - 6119057686528a(n-17) + 5645245612032a(n-18) + 24549642993664a(n-19) - 31793514283008a(n-20)

- 1125851856896a(n-21) - 5436031893504a(n-22) - 890735951872a(n-23) + 630487777280a(n-24) - 281320357888a(n-25).

Crossrefs

Sequence in context: A002198 A277001 A163576 * A175672 A181749 A266312

Adjacent sequences: A145405 A145406 A145407 * A145409 A145410 A145411

Keyword

nonn

Author

N. J. A. Sloane, Feb 03 2009

Status

approved