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
Georg Fischer, Table of n, a(n) for n = 0..200
Dmitry Efimov, The hafnian of Toeplitz matrices of a special type, perfect matchings and Bessel polynomials, arXiv:1904.08651 [math.CO], 2020.
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:
seq(a(n), n=0..22); # Alois P. Heinz, Jul 28 2020
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))
[A336400(n) for n in range(31)] # G. C. Greubel, Sep 28 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
Dmitry Efimov, Jul 22 2020
EXTENSIONS
Incorrect recurrences removed and a(18) corrected by Georg Fischer, Jul 28 2020
STATUS
approved