The Hafnian was introduced in the middle of 20th century by the Italian theoretical physicist E. R. Caianiello in connection with problems of quantum field theory. Later, the Hafnian found its application in combinatorics as an enumeration function of the number of perfect matchings of graphs. In its form, the Hafnian is close to such a better-known function as the Pfaffian. Unlike the latter, it is defined on symmetric, not skew-symmetric matrices and does not take into account the signs of permutations of indices in the corresponding monomials. In this paper, we consider the q-Hafnian, a generalization of the Hafnian that depends on formal parameters and coincides with the original function for unit values of the parameters. We indicate the combinatorial meaning of the q-Hafnian as a generating function of the number of permutations and the number of arc (linear chord) diagrams of certain classes. We prove several properties of the one- and two-parameter q-Hafnian that are generalizations of the properties of the usual Hafnian. In particular, we present an analog of the row decomposition property and an analog of the property expressing the Hafnian of the adjacency matrix of a bipartite weighted graph with equal parts through the permanent of the biadjacency matrix. These concepts and properties, in addition to their purely theoretical interest, can be used in developing algorithms that study the statistics of the number of inversions of certain classes of permutations and the statistics of the number of crossings and nestings in various classes of arc diagrams.
Download file
Counter downloads: 7
- Title Combinatorial aspects of the q-Hafnian
- Headline Combinatorial aspects of the q-Hafnian
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 69
- Date:
- DOI 10.17223/20710410/69/1
Keywords
q-analog, Hafnian, arc diagramm, permutationAuthors
References
Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. 384 с.
Смирнов Е. Ю. Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы. М.: МНИМО. 2014. 64с.
Игнатьев М. В. Квантовая комбинаторика // Матем. проев. Сер. 3. 2014. Вып. 18. С.66-111.
Haglund J. The q,t-Catalan Numbers and the Space of Diagonal Harmonics. AMS, 2007. 167 p.
Manin Yu. I. Quantum Groups and Non-Commutative Geometry. Montreal: CRM, 1988. 91 p.
Демидов E. E. Квантовые группы. M.: Факториал, 1998. 128 с.
Yang K.-W. q- Determinants and permutations // Fibonacci Quart. 1991. V. 29. No. 2. P. 160-163.
Tagawa H. A multivariable quantum determinant over a commutative ring // RIMS Kokvuroku. 1991. V. 765. P.91-103.
Shevelev V.Combinatorial minors for matrix functions and their applications // Zeszvtv Naukowe Politechniki Politech. Śląskiej. Seria: Matematvka Stosowana. 2014. No.4. P.5-16.
Bapat R. B. and Lal A.K. Inequalities for the q-permanent // Linear Algebra Appl. 1994. V.197/198. P.397-409.
Lal A. K. Inequalities for the q-permanent. II // Linear Algebra Appl. 1998. V. 274. P. 1-16.
Da Fonseca С. M. The μ-permanent of a tridiagonal matrix, orthogonal polynomials, and chain sequences // Linear Algebra Appl. 2010. V. 432. P. 1258-1266.
Da Fonseca С. M. The μ-permanent, a new graph labeling, and a known integer sequence // Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie . 2018. V.61(109). No.3. P.255-262.
De Sá E.M. Noncrossing partitions, noncrossing graphs, and q-permanental equations // Linear Algebra Appl. 2018. V. 541. P. 36-53.
De Sá E. M. Linear preservers for the q-permanent, cycle q-permanent expansions, and positive crossings in digraphs // Linear Algebra Appl. 2019. V. 561. P. 228-252.
Kocharovsky Vit. V., Kocharovsky V. V., and Tarasov S. V. The Hafnian Master Theorem // Linear Algebra Appl. 2022. V. 651. P. 144-161.
Efimov D. B. Enumeration of even and odd chord diagrams // J. Appl. Industr. Math. 2024. V. 18. No. 2. P. 216-226.
Strickland E. Classical invariant theory for the quantum symplectic group // Adv. Math. 1996. V. 123. P. 78-90.
Jing N. and Zhang J. Quantum Pfaffians and Hyper-Pfaffians // Adv. Math. 2014. V. 265. P. 336-361.
Jing N. and Zhang J. Quantum permanents and Hafnians via Pfaffans // Lett. Math. Phys. 2016. V. 106. P. 1451-1464.
Barvinok A. Combinatorics and Complexity of Partition Functions. Cham: Springer, 2016. 309 p.
Tribe R. and Zaboronski O. Pfaffian formulae for one dimensional coalescing and annihilating systems // Electronic J. Probability. 2011. V. 16. P. 2080-2103.
Sullivan E. Linear chord diagrams with long chords // Electronic J. Combinatorics. 2017. V. 24. No. 4. Article #P4.20.
Cameron N. T. and Killpatrick K. Statistics on linear chord diagrams // Discrete Math. Theoret. Computer Sci. 2019. V. 21. No. 2. Article #11.
Краско E. С., Лабутин И. H., Омельченко А. В. Перечисление помеченных и непомеченных гамильтоновых циклов в полных k- дольных графах // Зап. научн. сем. ПОМП. 2019. Т. 488. С. 119-142.
Nalli A. and Haukkanen P. On generalized Fibonacci and Lucas polynomials // Chaos, Solitons and Fractals. 2009. V. 42. P. 3179-3186.
Bednarz U. and M.M. Wołowiec-Musiał Distance Fibonacci polynomials // Symmetry. 2020. V. 12. No. 9. P. 1540.
Klazar M. On identities concerning the numbers of crossing and nesting of two edges in matchings // SIAM J. Discret. Math. 2005. V. 20. P. 960-976.
Björklund A., Gupt B., and Quesada N. A faster Hafnian formula for complex matrices and its benchmarking // J. Experimental Algorithmics. 2019. V. 24. Art. No. 1.11. P. 1-17.
Perepechko S. N. Counting near-perfect matchings on Cm ×Cn tori of odd order in the Maple system // Programming and Computer Software. 2019. V. 45. No. 2. P. 65-72.
Chmutov S., Duzhin S., and Mostovoy J. Introduction to Vassiliev Knot Invariants. Cambridge University Press, 2012. 504 p.
Reidys C. Combinatorial Computational Biology of RNA. N.Y.: Springer, 2011. 257 p.
Léger S., Costa M. B. W., and Tulpan D. Pairwise visual comparison of small RNA secondary structures with base pair probabilities. BMC Bioinformatics, 2019, vol. 20, article no. 293.
Combinatorial aspects of the q-Hafnian | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 69. DOI: 10.17223/20710410/69/1
Download full-text version
Counter downloads: 66