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.

1, 2, 9, 44, 303, 2697, 29438, 380529, 5683359, 96290588, 1824544857, 38229811083, 877643031554, 21906313145979, 590665804363833, 17109084307014332, 529833078045763263, 17468521692479218209, 610901505126064857854, 22586913755160674065113

Offset: 0

Author

Dmitry Efimov, Jul 22 2020

Keywords

• nonn

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.

Examples

			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.
		

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.

Crossrefs

Cf. A001515, A336114, A336286.

Programs

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

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 *)

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

Formula

a(n) = n*Sum_{k=0..n} (n+k-1)!/(k!*(n-k)!*2^(k-1)), n>=2.

a(n) = A001515(n) + A001515(n-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

Extensions

Incorrect recurrences removed and a(18) corrected by Georg Fischer, Jul 28 2020