Let A = (aij) be a symmetric matrix of even order nover a commutative associative ring. The hafnian of A is definedasHf(A) =X(i1i2|...|in−1in)ai1i2· · · ain−1in,where the sum ranges over all unordered partitions of theset {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 includedin the definition of the hafnian. For the sake of convenience,we assume that all matrices under consideration have a zeromain diagonal.A k-edge matching in a graph is a set of its k pairwisenonadjacent edges. Anm-edge matching in a graph with 2mvertices is called perfect matching. If a graph is weighted,then the weight of the matching is a product of the weightsof the edges included in this matching. The hafnian has auseful combinatorial property related to an important problemin graph theory and its applications: if M is the adjacencymatrix of an undirected weighted graph with an evennumber of vertices, then Hf(M) equals the total sum of theweights of the perfect matchings in the graph. Unfortunately,Известия Коми научного центра УрО РАН, серия «Физико-математические науки» № 5 (57), 2022www.izvestia.komisc.ru 15the widespread use of the hafnian is limited due to the complexityof its computations in general. For example, one ofthe fastest exact algorithms to compute the hafnian of an arbitrarycomplex 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 computationalcomplexity in general, the actual problem is the discoveryof efficient analytical formulas expressing the hafnianfor 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. Wedenote a symmetric matrix of order n by Tn(a, b), which isobtained from Tn by replacing all instances of 1 by a and allzero elements outside the main diagonal by b. For example(dots denote zeros),T3 =0@· 1 ·1 · 1· 1 ·1A =⇒ T3(a, b) =0@· a ba · ab a ·1A.We can say that Tn(a, b) is a two-parameter matrix, and Tnis the template for Tn(a, b). Note that Tn(1, 0) = Tn. In ourwork, we present a method for the exact computation of thehafnian of matrices Tn(a, b). In terms of graphs, we countthe total sum of weights of perfect matchings in two-parameterweighted graphs (i.e., weights of the edges are only a andb). This method is based on the formula expressing the hafnianof a sum of two matrices through the sum of the productof the hafnians of matrices and is also closely linked tothe combinatorial problem of counting the number of k-edgematchings in graphs. In theoretical physics, this problem isknown as the monomer-dimer problem [2].Recall that an arc diagram is a graph presentation methodin 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 ofarc diagrams. Perfect matchings of arc diagrams are oftencalled linear chord diagrams [3, 4].AB CD E F A B C D E FFigure 1. A binary tree and its corresponding arc diagram.Рисунок 1. Бинарное дерево и соответствующая ему дуговая диаграмма.1. Hafnian of two-parameter matricesTo begin with, consider two properties of the hafnian. Thefirst one is quite obvious.Proposition 1. Let A be a symmetric matrix of even order nover a commutative associative ring R, and c ∈ R. ThenHf(cA) = cn/2Hf(A). (1)Let Qk,n denote the set of all unordered k-element subsetsof {1, 2, . . . , n}. Let A be a matrix of order n andα ∈ Qk,n. Moreover, A[α] denotes the submatrix of Aformed by the rows and columns of A with numbers in α, andA{α} denotes the submatrix of A formed from A by removingthe rows and columns with numbers in α.Proposition 2. Let A and B be symmetric matrices of evenorder n. ThenHf(A + B) =Xn/2k=0Xα∈Q2k,nHf(A[α])Hf(B{α}). (2)Jn(b) denotes a matrix of order n whose elements outsidethe main diagonal are equal to b. From the definition ofthe hafnian, it follows thatHf(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)) ==mXk=0Xα∈Q2k,2mHf(J2m(b)[α])Hf(T2m(a−b, 0){α}) ==mXk=0(a − b)m−kbk (2k)!k!2kXα∈Q2k,2mHf(T2m{α}).(4)Here, we use the fact that the matrix J2m(b)[α] has the sameform as the initial matrix J2m(b), that is, J2m(b)[α] is a matrixof order 2k whose elements outside the main diagonal areequal 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 thecardinality 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 matchingsof the graph Γ(T2m). Given a graph Γ, let μk(Γ) denotethe number of all its k-edge matchings. By definition, we setμ0(Γ) = 1. Thus,Xα∈Q2k,2mHf(T2m{α}) = μm−k(Γ(T2m)),and therefore,Hf(T2m(a, b)) ==mXk=0(a − b)m−kbk (2k)!k!2k μm−k(Γ(T2m)). (5)Note that (5) is the special case of Theorems 1W and 3W givenin [5] in terms of matching vectors of weighted graphs andtheir complements. The special case of (5) when a = 0 andb = 1 is also given in [6] (Theorem 4).Thus, to calculate the hafnian of a two-parameter matrixby using formula (5), one needs to determine the number of kedgematchings of graphs corresponding to the matrix, whichis a nontrivial task in general. One of the simplest specialcases was considered in [7]. In the following section, we considera more complicated special case.16Известия Коми научного центра УрО РАН, серия «Физико-математические науки» № 5 (57), 2022www.izvestia.komisc.ru2. Hafnian of Toeplitz matrices Dn(a, b)Recall that a matrix is called Toeplitz if all its diagonalsparallel to the main diagonal consist of the same elements. Itis obvious that a symmetric Toeplitz matrix is uniquely determinedby its first row. As the template matrix Tn, consider asymmetric 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 thearc diagram shown in Figure 2.1 2 3 4 n − 2 n − 1 nFigure 2. The arc diagram Γ(Dn).Рисунок 2. Дуговая диаграмма Γ(Dn).Theorem 1. Let k and n be nonnegative integers such thatk ≤n2. Then, the number of k-edge matchings in the arcdiagram Γ(Dn) is equal to the following:μk(Γ(Dn)) =Xki=0Xip=0n − k − ik − pk − piip.(6)Proof. For convenience, we use the abbreviated notationwn,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 edgeof the matching (Figure 3(a)); the first and second vertices areconnected by an edge of the matching (Figure 3(b)); the firstvertex is incident to an edge of the matching, but the secondvertex is not (Figure 3(c)); the first and second vertices areincident 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 recurrencerelationwn+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 >n2; wn,0 = 1for all n; wn,1 = 2n − 3 for n ≥ 2. Consider the twoparametergenerating function for the sequence wn,k:w(x, t) =X+∞n=0⌊n2⌋ Xk=0wn,kxktn.On multiplying (7) by xk+3tn+3 and summing over all possiblek and n, we get the following equation:X+∞n=0⌊n2⌋ Xk=0wn+4,k+2xk+3tn+3 ==X+∞n=0⌊n2⌋ Xk=0wn+3,k+2xk+3tn+3++X+∞n=0⌊n2⌋ Xk=0wn+2,k+1xk+3tn+3++X+∞n=0⌊n2⌋ Xk=0wn+1,k+1xk+3tn+3++X+∞n=0⌊n2⌋ Xk=0wn,kxk+3tn+3. (8)On solving this equation, we obtain:w(x, t) =11 − t(1 + xt + xt2 + x2t3)==X+∞m=0mXj=0Xji=0Xip=0mjjiipxj+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 sumiPp􀀀n−k−ik−p􀀀k−pi􀀀ip, over all i, p for which the inequalitiesi ≥ p ≥ 0, k − p ≥ i, n − k − i ≥ k − p hold. It canbe shown that this system of inequalities is equivalent to thefollowing system of inequalities: 0 ≤ i ≤ min(k,n−k2),max(0, i + 2k − n) ≤ p ≤ min(i, k − i). If we takeweaker restrictions 0 ≤ i ≤ k, 0 ≤ p ≤ i on the indices i,p, then the final formula will take a more compact form, butadditional zero summands may appear. This completes theproof.Remark 1. Note that the arc diagram Γ(Dn) is isomorphicto the triangular lattice shown in Figure 4. Thus, formula (6)also allows us to calculate the number of k-edge matchingsin such lattices.214365n − 2n − 3nn − 1(a)214365n − 1n − 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), 2022www.izvestia.komisc.ru 17Remark 2. Several initial values μk(Γ(Dn)) are presentedin Table. The empty cells correspond to zero. Note that thesequence of the first nonzero elements in the rows is the Fibonaccisequence, the sequence of the second nonzero elementsin the rows has the number A023610 in [8], andnonzero elements of the third row coincide with the sequenceA130883, 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 100 1 1 1 1 1 1 1 1 1 1 11 1 3 5 7 9 11 13 15 172 2 7 16 29 46 67 923 3 15 43 95 1794 5 30 1045 8LetRbe a commutative associative ring with 1 and a, b ∈R. Consider a symmetric two-parameter Toeplitz matrixD2m(a, b) having the first row in the form􀀀0 a a b . . . b.On substituting the value μm−k(Γ(D2m)) in (5), we obtainthe following theorem:Theorem 2. If we assume that 00 = 1, then the hafnian of thematrix D2m(a, b) is expressed using the following formula:Hf(D2m(a, b)) ==mXk=0(a − b)m−kbk (2k)!k!2k μm−k(Γ(D2m)) , (10)whereμm−k(Γ(D2m)) ==mX−ki=0Xip=0m + k − im − k − pm − k − piip.Example 1. Consider the matrix D2m(0, 1). By calculatingits hafnian using formula (10) for consecutive ms, we obtainthe sequence:0, 0, 1, 10, 99, 1146, 15422, 237135, 4106680, . . .In terms of graphs, the m-th member is equal to the numberof perfect matchings in the arc diagram Γ(D2m(0, 1))(Figure 5). In other words, this is the number of linear chorddiagrams with m chords such that the length of every chordis at least 3 (see also [4], [9]). This sequence has the numberA190823 in [8].1 2 3 4 5 6 1 2 3 4 5 6Figure 5. The arc diagram Γ(D6(0, 1)) and its only perfect matching.Рисунок 5. Дуговая диаграмма Γ(D6(0, 1)) и ее единственное совер-шенное паросочетание.ConclusionWe presented a general scheme for computation of thehafnian of two-parameter matrices. We provided exact formulasfor a special case of Toeplitz matrix. The resulting formulascan be used to determine the total sum of weights ofperfect matchings in the graphs. In addition, we obtained newresults regarding the number of k-edge matchings in somespecial graph. In future works, the above methods could beused to find analytical formulas for hafnians of other (twoormore) parameter matrices, or this method could be extendedto multidimensional matrices, hyperhafnians, and hypergraphs.