|
|
A336400
|
|
The hafnian of a symmetric Toeplitz matrix of order 2*n, n>=2 with the first row (0,2,1,...,1,2); a(0)=1, a(1)=2.
|
|
12
|
|
|
1, 2, 9, 44, 303, 2697, 29438, 380529, 5683359, 96290588, 1824544857, 38229811083, 877643031554, 21906313145979, 590665804363833, 17109084307014332, 529833078045763263, 17468521692479218209, 610901505126064857854, 22586913755160674065113
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Number of perfect matchings of a chord diagram with 2*n vertices, where neighboring vertices are joined by two chords, and any other pair of vertices is joined by one chord.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = n*Sum_{k=0..n} (n+k-1)!/(k!*(n-k)!*2^(k-1)), n>=2.
a(n) ~ (2*n)!*e/(n!*2^n).
a(n) = 2^(n+1)*U(n, 1+2*n, 2) for n >= 2, where U(a, b, c) is the confluent hypergeometric function. - Stefano Spezia, Jul 22 2020
a(n) = ((22*n^2-74*n+43)*a(n-1) + (10*n^2-54*n+77)*a(n-2) + 5*(n-4)*a(n-3)) / (11*n-29) for n >= 3. - Alois P. Heinz, Jul 28 2020
E.g.f.: - 1 - x + (1 + 1/sqrt(1-2*x))*exp(1 - sqrt(1-2* x)). - G. C. Greubel, Sep 28 2023
|
|
EXAMPLE
|
A symmetric 4x4 Toeplitz matrix A with the first row (0,2,1,2) has the form:
0 2 1 2
2 0 2 1
1 2 0 2
2 1 2 0.
Its hafnian equals Hf(A)=a12*a34+a13*a24+a14*a23=2*2+1*1+2*2=9.
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<3, [1, 2, 9][n+1],
((22*n^2-74*n+43)*a(n-1)+(10*n^2-54*n+77)*a(n-2)
+5*(n-4)*a(n-3))/(11*n-29))
end:
|
|
MATHEMATICA
|
Join[{1, 2}, Table[2^(n+1)*HypergeometricU[n, 1+2 n, 2], {n, 2, 19}]] (* Stefano Spezia, Jul 22 2020 *)
(* or *) Join[{1, 2}, Table[n*Sum[(n+k-1)!/(k!*(n-k)!*2^(k-1)), {k, 0, n}], {n, 2, 200}]] (* Georg Fischer, Jul 28 2020 *)
|
|
PROG
|
(Magma) I:=[1, 2, 9]; [n le 3 select I[n] else ( (22*n^2-118*n+139)*Self(n-1) + (10*n^2-74*n+141)*Self(n-2) + 5*(n-5)*Self(n-3) )/(11*n-40): n in [1..30]]; // G. C. Greubel, Sep 28 2023
(SageMath)
def A336400(n): return n+1 if n<2 else (2/factorial(n-1))*sum(binomial(n, k)*gamma(n+k)/2^k for k in range(n+1))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Incorrect recurrences removed and a(18) corrected by Georg Fischer, Jul 28 2020
|
|
STATUS
|
approved
|
|
|
|