A336286 The hafnian of a symmetric Toeplitz matrix of order 2n, n>=2 with the first row (0,1,2,...,2,0); a(0)=a(1)=1.

1, 1, 5, 57, 859, 16087, 362781, 9593105, 291347603, 9998539791, 382732896853, 16169762600329, 747423640472235, 37523173542935207, 2033249827596197549, 118278700627740322977, 7352204062275501662371

Offset

0,3

Comments

Number of perfect matchings of an arc diagram with 2*n vertices, where neighboring vertices are joined by one arc, the vertices 1 and 2*n are not adjacent if n>=2, and all other pairs of vertices are joined by two arcs.

Links

Table of n, a(n) for n=0..16.

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) = Sum_{k=0..n} (-1)^(n-k-1)*(n+k-1)!*(-3*n+k)/(k!*(n-k)!), n>=2.

D-finite with recurrence a(n+1) = (4n+4)*a(n) - (8n-13)*a(n-1) - 2*a(n-2), n>=4.

D-finite with recurrence a(n+1) = ((32*n^2-12*n+2)*a(n) + (8*n+1)*a(n-1))/(8*n-7), n>=3.

a(n) = |A002119(n)| - 2*|A002119(n-1)|, n>=2.

a(n) ~ (2*n)!/sqrt(e)*n!.

Example

A symmetric 4 X 4 Toeplitz matrix A with the first row (0,1,2,0) has the form:
  0 1 2 0
  1 0 1 2
  2 1 0 1
  0 2 1 0.
Its hafnian equals Hf(A)= a12*a34 + a13*a24 + a14*a23 = 1*1 + 2*2 + 0*1 = 5.

Maple

[1, 1, seq(add((-1)^(n-k-1)*(n+k-1)!*(-3*n+k)/(k!*(n-k)!), k=0..n), n=2..32)] # Georg Fischer, Jun 05 2021

Mathematica

Join[{1, 1}, RecurrenceTable[{a[n+1] == (4*n+4)*a[n]-(8*n-13)*a[n-1]-2*a[n-2], a[2]==5, a[3]==57, a[4]==859}, a[n], {n, 2, 32}]] (* Georg Fischer, Jun 05 2021 *)

Crossrefs

Cf. A002119, A336114, A336400.

Sequence in context: A277831 A333091 A223382 * A155539 A285067 A234293

Adjacent sequences: A336283 A336284 A336285 * A336287 A336288 A336289

Keyword

nonn

Author

Dmitry Efimov, Jul 16 2020

Status

approved