УДК 519.11 Теория перечисления
Понятие гафниана впервые появилось в работах Э.Р. Ка- яньелло по квантовой теории поля. Однако гафниан об- ладает также и важным комбинаторным свойством: гаф- ниан матрицы смежности неориентированного взвешенно- го графа равен сумме весов совершенных паросочетаний в этом графе. В общем случае использование гафниана ограничено сложностью его вычисления. В данной рабо- те представлен метод для точного вычисления гафниана двухпараметрических матриц. С точки зрения теории гра- фов мы считаем общую сумму весов совершенных паро- сочетаний в графах, веса ребер которых принимают толь- ко два значения. Этот метод основан на формуле, выра- жающей гафниан суммы двух матриц через произведение гафнианов их подматриц. Необходимым условием приме- нения данного метода является возможность подсчета ко- личества k-реберных паросочетаний в определенных гра- фах. Подробно разобран специальный случай, где в ка- честве двухпараметрической матрицы рассмотрена теп- лицева матрица, а как пример дана новая интерпретация некоторых последовательностей из Онлайн-энциклопедии целочисленных последовательностей, а также приведе- ны новые аналитические формулы для определения числа некоторых линейных хордовых диаграмм.
гафниан, паросочетание, взвешенный граф, теплицева матрица, дуговая диаграмма, треугольная решетка
Let A = (aij) be a symmetric matrix of even order n
over a commutative associative ring. The hafnian of A is defined
as
Hf(A) =
X
(i1i2|...|in−1in)
ai1i2
· · · ain−1in,
where the sum ranges over all unordered partitions of the
set {1, 2, . . . , n} into unordered pairs (i1i2), . . . , (in−1in).
Therefore, if n = 4, then Hf(A) = a12a34 + a13a24 +
a14a23. The hafnian of the empty matrix is considered as 1.
Note that the elements of the main diagonal are not included
in the definition of the hafnian. For the sake of convenience,
we assume that all matrices under consideration have a zero
main diagonal.
A k-edge matching in a graph is a set of its k pairwise
nonadjacent edges. Anm-edge matching in a graph with 2m
vertices is called perfect matching. If a graph is weighted,
then the weight of the matching is a product of the weights
of the edges included in this matching. The hafnian has a
useful combinatorial property related to an important problem
in graph theory and its applications: if M is the adjacency
matrix of an undirected weighted graph with an even
number of vertices, then Hf(M) equals the total sum of the
weights of the perfect matchings in the graph. Unfortunately,
Известия Коми научного центра УрО РАН, серия «Физико-математические науки» № 5 (57), 2022
www.izvestia.komisc.ru 15
the widespread use of the hafnian is limited due to the complexity
of its computations in general. For example, one of
the fastest exact algorithms to compute the hafnian of an arbitrary
complex n × n matrix runs in O(n32n/2) time, and,
as the authors show, it seems to be close to an optimal one [1].
Because the calculation of the hafnian has a high computational
complexity in general, the actual problem is the discovery
of efficient analytical formulas expressing the hafnian
for special classes of matrices. Let Tn be a symmetric (0, 1)-
matrix of order n, and let a and b be elements of a ringR. We
denote a symmetric matrix of order n by Tn(a, b), which is
obtained from Tn by replacing all instances of 1 by a and all
zero elements outside the main diagonal by b. For example
(dots denote zeros),
T3 =
0
@
· 1 ·
1 · 1
· 1 ·
1
A =⇒ T3(a, b) =
0
@
· a b
a · a
b a ·
1
A.
We can say that Tn(a, b) is a two-parameter matrix, and Tn
is the template for Tn(a, b). Note that Tn(1, 0) = Tn. In our
work, we present a method for the exact computation of the
hafnian of matrices Tn(a, b). In terms of graphs, we count
the total sum of weights of perfect matchings in two-parameter
weighted graphs (i.e., weights of the edges are only a and
b). This method is based on the formula expressing the hafnian
of a sum of two matrices through the sum of the product
of the hafnians of matrices and is also closely linked to
the combinatorial problem of counting the number of k-edge
matchings in graphs. In theoretical physics, this problem is
known as the monomer-dimer problem [2].
Recall that an arc diagram is a graph presentation method
in which all the vertices are located along a line in the plane,
whereas all edges are drawn as arcs (Figure 1). In this work,
it will be convenient for us to represent graphs in the form of
arc diagrams. Perfect matchings of arc diagrams are often
called linear chord diagrams [3, 4].
A
B C
D E F A B C D E F
Figure 1. A binary tree and its corresponding arc diagram.
Рисунок 1. Бинарное дерево и соответствующая ему дуговая диаграмма.
1. Hafnian of two-parameter matrices
To begin with, consider two properties of the hafnian. The
first one is quite obvious.
Proposition 1. Let A be a symmetric matrix of even order n
over a commutative associative ring R, and c ∈ R. Then
Hf(cA) = cn/2Hf(A). (1)
Let Qk,n denote the set of all unordered k-element subsets
of {1, 2, . . . , n}. Let A be a matrix of order n and
α ∈ Qk,n. Moreover, A[α] denotes the submatrix of A
formed by the rows and columns of A with numbers in α, and
A{α} denotes the submatrix of A formed from A by removing
the rows and columns with numbers in α.
Proposition 2. Let A and B be symmetric matrices of even
order n. Then
Hf(A + B) =
Xn/2
k=0
X
α∈Q2k,n
Hf(A[α])Hf(B{α}). (2)
Jn(b) denotes a matrix of order n whose elements outside
the main diagonal are equal to b. From the definition of
the hafnian, it follows that
Hf(J2m(b)) = bm(2m)!
m!2m. (3)
Since T2m(a, b) = J2m(b)+T2m(a−b, 0), using formulas
(1), (2), and (3), we can write the following:
Hf(T2m(a, b)) = Hf(J2m(b) + T2m(a − b, 0)) =
=
mX
k=0
X
α∈Q2k,2m
Hf(J2m(b)[α])Hf(T2m(a−b, 0){α}) =
=
mX
k=0
(a − b)m−kbk (2k)!
k!2k
X
α∈Q2k,2m
Hf(T2m{α}).
(4)
Here, we use the fact that the matrix J2m(b)[α] has the same
form as the initial matrix J2m(b), that is, J2m(b)[α] is a matrix
of order 2k whose elements outside the main diagonal are
equal to b.
If M is a symmetric nonnegative integer matrix, then
Γ(M) denotes a multigraph with the adjacency matrix M.
If α ∈ Q2k,2m, then the hafnian Hf(T2m{α}) equals the
cardinality of a set of (m − k)-edge matchings in the graph
Γ(T2m); moreover, such sets do not intersect for different
α, and their union is the set of all (m − k)-edge matchings
of the graph Γ(T2m). Given a graph Γ, let μk(Γ) denote
the number of all its k-edge matchings. By definition, we set
μ0(Γ) = 1. Thus,
X
α∈Q2k,2m
Hf(T2m{α}) = μm−k(Γ(T2m)),
and therefore,
Hf(T2m(a, b)) =
=
mX
k=0
(a − b)m−kbk (2k)!
k!2k μm−k(Γ(T2m)). (5)
Note that (5) is the special case of Theorems 1W and 3W given
in [5] in terms of matching vectors of weighted graphs and
their complements. The special case of (5) when a = 0 and
b = 1 is also given in [6] (Theorem 4).
Thus, to calculate the hafnian of a two-parameter matrix
by using formula (5), one needs to determine the number of kedge
matchings of graphs corresponding to the matrix, which
is a nontrivial task in general. One of the simplest special
cases was considered in [7]. In the following section, we consider
a more complicated special case.
16
Известия Коми научного центра УрО РАН, серия «Физико-математические науки» № 5 (57), 2022
www.izvestia.komisc.ru
2. Hafnian of Toeplitz matrices Dn(a, b)
Recall that a matrix is called Toeplitz if all its diagonals
parallel to the main diagonal consist of the same elements. It
is obvious that a symmetric Toeplitz matrix is uniquely determined
by its first row. As the template matrix Tn, consider a
symmetric Toeplitz matrix of order n with the first row
0 1 1 0 . . . 0
.
We denote it byDn. This matrix is the adjacency matrix of the
arc diagram shown in Figure 2.
1 2 3 4 n − 2 n − 1 n
Figure 2. The arc diagram Γ(Dn).
Рисунок 2. Дуговая диаграмма Γ(Dn).
Theorem 1. Let k and n be nonnegative integers such that
k ≤
n
2
. Then, the number of k-edge matchings in the arc
diagram Γ(Dn) is equal to the following:
μk(Γ(Dn)) =
Xk
i=0
Xi
p=0
n − k − i
k − p
k − p
i
i
p
.
(6)
Proof. For convenience, we use the abbreviated notation
wn,k for μk(Γ(Dn)). Consider a k-edge matching in
Γ(Dn). If n ≥ 4, then the following four cases are possible:
the first vertex of the diagram is not incident to the edge
of the matching (Figure 3(a)); the first and second vertices are
connected by an edge of the matching (Figure 3(b)); the first
vertex is incident to an edge of the matching, but the second
vertex is not (Figure 3(c)); the first and second vertices are
incident to different edges of the matching (Figure 3(d)).
1
(a)
1 2
(b)
1 2 3
(c)
1 2 3 4
(d)
Figure 3. Possible cases of matchings in the arc diagram Γ(Dn).
Рисунок 3. Возможные случаи паросочетаний в дуговой диаграмме
Γ(Dn).
It follows from the above that wn,k satisfies the recurrence
relation
wn+4,k+2 =
= wn+3,k+2 + wn+2,k+1 + wn+1,k+1 + wn,k (7)
with the initial conditions wn,k = 0 for k >
n
2
; wn,0 = 1
for all n; wn,1 = 2n − 3 for n ≥ 2. Consider the twoparameter
generating function for the sequence wn,k:
w(x, t) =
X+∞
n=0
⌊n2
⌋ X
k=0
wn,kxktn.
On multiplying (7) by xk+3tn+3 and summing over all possible
k and n, we get the following equation:
X+∞
n=0
⌊n2
⌋ X
k=0
wn+4,k+2xk+3tn+3 =
=
X+∞
n=0
⌊n2
⌋ X
k=0
wn+3,k+2xk+3tn+3+
+
X+∞
n=0
⌊n2
⌋ X
k=0
wn+2,k+1xk+3tn+3+
+
X+∞
n=0
⌊n2
⌋ X
k=0
wn+1,k+1xk+3tn+3+
+
X+∞
n=0
⌊n2
⌋ X
k=0
wn,kxk+3tn+3. (8)
On solving this equation, we obtain:
w(x, t) =
1
1 − t(1 + xt + xt2 + x2t3)
=
=
X+∞
m=0
mX
j=0
Xj
i=0
Xi
p=0
m
j
j
i
i
p
xj+ptm+j+i+p.
(9)
Fix nonnegative integers k and n ≥ 2k. From (9),
wPe see that the coefficient at xktn is equal to the sum
i
P
p
n−k−i
k−p
k−p
i
i
p
, over all i, p for which the inequalities
i ≥ p ≥ 0, k − p ≥ i, n − k − i ≥ k − p hold. It can
be shown that this system of inequalities is equivalent to the
following system of inequalities: 0 ≤ i ≤ min(k,
n−k
2
),
max(0, i + 2k − n) ≤ p ≤ min(i, k − i). If we take
weaker restrictions 0 ≤ i ≤ k, 0 ≤ p ≤ i on the indices i,
p, then the final formula will take a more compact form, but
additional zero summands may appear. This completes the
proof.
Remark 1. Note that the arc diagram Γ(Dn) is isomorphic
to the triangular lattice shown in Figure 4. Thus, formula (6)
also allows us to calculate the number of k-edge matchings
in such lattices.
2
1
4
3
6
5
n − 2
n − 3
n
n − 1
(a)
2
1
4
3
6
5
n − 1
n − 2 n
(b)
Figure 4. The triangular lattice Γ(Dn): (a) n is even; (b) n is odd.
Рисунок 4. Треугольная решетка Γ(Dn): (a) n – четное; (b) n – нечетное.
Известия Коми научного центра УрО РАН, серия «Физико-математические науки» № 5 (57), 2022
www.izvestia.komisc.ru 17
Remark 2. Several initial values μk(Γ(Dn)) are presented
in Table. The empty cells correspond to zero. Note that the
sequence of the first nonzero elements in the rows is the Fibonacci
sequence, the sequence of the second nonzero elements
in the rows has the number A023610 in [8], and
nonzero elements of the third row coincide with the sequence
A130883, excluding the starting element.
Number of k-edge matchings in the graph Γ(Dn).
Число k-реберных паросочетаний в графе Γ(Dn).
k\n 0 1 2 3 4 5 6 7 8 9 10
0 1 1 1 1 1 1 1 1 1 1 1
1 1 3 5 7 9 11 13 15 17
2 2 7 16 29 46 67 92
3 3 15 43 95 179
4 5 30 104
5 8
LetRbe a commutative associative ring with 1 and a, b ∈
R. Consider a symmetric two-parameter Toeplitz matrix
D2m(a, b) having the first row in the form
0 a a b . . . b
.
On substituting the value μm−k(Γ(D2m)) in (5), we obtain
the following theorem:
Theorem 2. If we assume that 00 = 1, then the hafnian of the
matrix D2m(a, b) is expressed using the following formula:
Hf(D2m(a, b)) =
=
mX
k=0
(a − b)m−kbk (2k)!
k!2k μm−k(Γ(D2m)) , (10)
where
μm−k(Γ(D2m)) =
=
mX−k
i=0
Xi
p=0
m + k − i
m − k − p
m − k − p
i
i
p
.
Example 1. Consider the matrix D2m(0, 1). By calculating
its hafnian using formula (10) for consecutive ms, we obtain
the sequence:
0, 0, 1, 10, 99, 1146, 15422, 237135, 4106680, . . .
In terms of graphs, the m-th member is equal to the number
of perfect matchings in the arc diagram Γ(D2m(0, 1))
(Figure 5). In other words, this is the number of linear chord
diagrams with m chords such that the length of every chord
is at least 3 (see also [4], [9]). This sequence has the number
A190823 in [8].
1 2 3 4 5 6 1 2 3 4 5 6
Figure 5. The arc diagram Γ(D6(0, 1)) and its only perfect matching.
Рисунок 5. Дуговая диаграмма Γ(D6(0, 1)) и ее единственное совер-
шенное паросочетание.
Conclusion
We presented a general scheme for computation of the
hafnian of two-parameter matrices. We provided exact formulas
for a special case of Toeplitz matrix. The resulting formulas
can be used to determine the total sum of weights of
perfect matchings in the graphs. In addition, we obtained new
results regarding the number of k-edge matchings in some
special graph. In future works, the above methods could be
used to find analytical formulas for hafnians of other (twoor
more) parameter matrices, or this method could be extended
to multidimensional matrices, hyperhafnians, and hypergraphs.
1. Bjorklund, A. A faster hafnian formula for complex matrices and its benchmarking on a Supercomputer / A. Bjorklund, B. Gupt, N. Quesada // ACM J. Exp. Algorithmics. - 2019. - V. 24. - Article 1.11. - P. 1-17. DOI:https://doi.org/10.1145/3325111.
2. Grimson, R.C. Enumeration of dimer (domino) configurations / R.C. Grimson // Discrete Math. - 1977. - V. 18. - P. 167-178. DOI:https://doi.org/10.1016/0012-365X(77)90077-2.
3. Krasko, E. Enumeration of chord diagrams without loops and parallel chords / E. Krasko, A. Omelchenko // Electron. J. Combin. - 2017. - V. 24. - № 3. - Article P3.43. - P. 1-23. DOI:https://doi.org/10.37236/6037.
4. Sullivan, E. Linear chord diagrams with long chords / E. Sullivan // Electron. J. Combin. - 2017. - V. 24. - № 4. - Article P4.20. - P. 1-8. DOI:https://doi.org/10.37236/6809.
5. Zaslavsky, T. Complementary matching vectors and the uniform matching extension property / T. Zaslavsky // European J. Combin. - 1981. - V. 2. - № 1. - P. 91-103. DOI :https://doi.org/10.1016/S0195-6698(81)80025-X. ъ
6. Young, D. The number of domino matchings in the gameof memory / D. Young // J. Integer Seq. - 2018. - V. 21. - № 8. - Article 18.8.1. - P. 1-14.
7. Ефимов, Д.Б. Гафниан теплицевых матриц специального вида, совершенные паросочетания и полиномы Бесселя / Д.Б. Ефимов // Вестник Cыктывкарского университета. Серия 1: Математика. Механика. Информатика. - 2018. - № 3 (28). - С. 56-64.
8. Sloane, N.J.A. The on-line encyclopedia of integer sequences/ N.J.A. Sloane et al. // - 2022. - [electronic resource]. URL: https://oeis.org/.
9. Cameron, N.T. Statistics on linear chord diagrams / N.T. Cameron, K. Killpatrick // Discrete Math. Theor. Comput. Sci. - 2019. - V. 21. - № 2. - Article 11. - P. 1-11. DOI:https://doi.org/10.23638/DMTCS-21-2-11.
