Hafnian

In mathematics, the hafnian of an adjacency matrix of a graph is the number of perfect matchings in the graph. It was so named by Eduardo R. Caianiello "to mark the fruitful period of stay in Copenhagen (Hafnia in Latin)."[1]

The hafnian of a 2n × 2n symmetric matrix is computed as

${\displaystyle \operatorname {haf} (A)={\frac {1}{n!2^{n}}}\sum _{\sigma \in S_{2n}}\prod _{j=1}^{n}A_{\sigma (2j-1),\sigma (2j)},}$

where ${\displaystyle S_{2n}}$ is the symmetric group on [2n].[2]

Equivalently,

${\displaystyle \operatorname {haf} (A)=\sum _{M\in {\mathcal {M}}}\prod _{\scriptscriptstyle (u,v)\in M}A_{u,v}}$

where ${\displaystyle {\mathcal {M}}}$ is the set of all 1-factors (perfect matchings) on the complete graph ${\displaystyle K_{2n}}$, namely the set of all ${\displaystyle (2n)!/(n!2^{n})}$ ways to partition the set ${\displaystyle \{1,2,\dots ,2n\}}$ into ${\displaystyle n}$ subsets of size ${\displaystyle 2}$.[3][4]

References

1. F. Guerra, in Imagination and Rigor: Essays on Eduardo R. Caianiello's Scientific Heritage, edited by Settimo Termini, Springer Science & Business Media, 2006, page 98
2. Rudelson, Mark; Samorodnitsky, Alex; Zeitouni, Ofer (2016). "Hafnians, perfect matchings and Gaussian matrices". The Annals of Probability. 44 (4): 2858–2888. arXiv:1409.3905. doi:10.1214/15-AOP1036.
3. Alexander Barvinok (13 March 2017). Combinatorics and Complexity of Partition Functions. p. 93. ISBN 9783319518299.
4. Barvinok, Alexander; Regts, Guus (2019). "Weighted counting of integer points in a subspace". Combinator. Probab. Comp. 28: 696–719. arXiv:1706.05423. doi:10.1017/S0963548319000105.