|
|
A028470
|
|
Number of perfect matchings in graph P_{8} X P_{n}.
|
|
7
|
|
|
1, 1, 34, 153, 2245, 14824, 167089, 1292697, 12988816, 108435745, 1031151241, 8940739824, 82741005829, 731164253833, 6675498237130, 59554200469113, 540061286536921, 4841110033666048, 43752732573098281, 393139145126822985, 3547073578562247994, 31910388243436817641
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
REFERENCES
|
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
|
|
LINKS
|
Index entries for linear recurrences with constant coefficients, signature (1, 76, 69, -921, -584, 4019, 829, -7012, 829, 4019, -584, -921, 69, 76, 1, -1).
|
|
FORMULA
|
Recurrence from Faase web site:
a(1) = 1,
a(2) = 34,
a(3) = 153,
a(4) = 2245,
a(5) = 14824,
a(6) = 167089,
a(7) = 1292697,
a(8) = 12988816,
a(9) = 108435745,
a(10) = 1031151241,
a(11) = 8940739824,
a(12) = 82741005829,
a(13) = 731164253833,
a(14) = 6675498237130,
a(15) = 59554200469113,
a(16) = 540061286536921,
a(17) = 4841110033666048,
a(18) = 43752732573098281,
a(19) = 393139145126822985,
a(20) = 3547073578562247994,
a(21) = 31910388243436817641,
a(22) = 287665106926232833093,
a(23) = 2589464895903294456096,
a(24) = 23333526083922816720025,
a(25) = 210103825878043857266833,
a(26) = 1892830605678515060701072,
a(27) = 17046328120997609883612969,
a(28) = 153554399246902845860302369,
a(29) = 1382974514097522648618420280,
a(30) = 12457255314954679645007780869,
a(31) = 112199448394764215277422176953,
a(32) = 1010618564986361239515088848178, and
a(n) = 153a(n-2) - 7480a(n-4) + 151623a(n-6) - 1552087a(n-8) + 8933976a(n-10) - 30536233a(n-12) + 63544113a(n-14) - 81114784a(n-16) + 63544113a(n-18) - 30536233a(n-20) + 8933976a(n-22) - 1552087a(n-24) + 151623a(n-26) - 7480a(n-28) + 153a(n-30) - a(n-32).
G.f.: (1 -43*x^2 -26*x^3 +360*x^4 +110*x^5 -1033*x^6 +1033*x^8 -110*x^9 -360*x^10 +26*x^11 +43*x^12 -x^14) /(1 -x -76*x^2 -69*x^3 +921*x^4 +584*x^5 -4019*x^6 -829*x^7 +7012*x^8 -829*x^9 -4019*x^10 +584*x^11 +921*x^12 -69*x^13 -76*x^14 -x^15 +x^16). - Sergey Perepechko, Nov 22 2012
|
|
MAPLE
|
a:= n-> (Matrix(16, (i, j)-> `if` (i=j-1, 1, `if` (i=16, [-1, 1, 76, 69, -921, -584, 4019, 829, -7012][min(j, 18-j)], 0)))^n. <<seq([1292697, 167089, 14824, 2245, 153, 34, 1, 1, 0][min(k, 18-k)], k=1..16)>>)[10, 1]: seq(a(n), n=0..50); # Alois P. Heinz, Apr 14 2011
|
|
MATHEMATICA
|
a[n_] := Product[2(2+Cos[(2j Pi)/9] + Cos[(2k Pi)/(n+1)]), {k, 1, n/2}, {j, 1, 4}] // Round; Join[{1}, Array[a, 21]] (* Jean-François Alcover, Aug 11 2018; a(0)=1 prepended by Georg Fischer, Apr 17 2020 *)
|
|
PROG
|
(PARI) {a(n) = sqrtint(polresultant(polchebyshev(8, 2, x/2), polchebyshev(n, 2, I*x/2)))} \\ Seiichi Manyama, Apr 13 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|