Перечисление чётных и нечётных хордовых диаграмм

Перечисление чётных и нечётных хордовых диаграмм

Ефимов Д. Б.
Дискретный анализ и исследование операций, 31, 2, 63–79 (2024)
Скачать статью

УДК 519.1+512.64 
DOI: 10.33048/daio.2024.31.767

Аннотация:

Рассматривается общий метод перечисления различных классов хордовых диаграмм с чётным и нечётным числом пересечений хорд. В основе метода лежит вычисление пфаффиана и гафниана матрицы ограничений, характеризующей класс диаграмм. 
Табл. 3, ил. 6, библиогр. 23.

Литература:
  1. Acan H. An enumerative-probabilistic study of chord diagrams: PhD Thes. Columbus: Ohio State Univ., 2013. 144 p.
     
  2. Краско Е. С., Лабутин И. Н., Омельченко А. В. Перечисление помеченных и непомеченных гамильтоновых циклов в полных $k$-дольных графах // Зап. науч. сем. ПОМИ. 2019. Т. 488. С. 119–142.
     
  3. Nakamigawa T. The expansion of a chord diagram and the Genocchi numbers // Ars Math. Contemp. 2020. V. 18. P. 381–391.
     
  4. Sullivan E. Linear chord diagrams with long chords // Electron. J. Comb. 2017. V. 24, No. 4. Paper ID P4.20. 8 p. 
     
  5. Cameron N. T., Killpatrick K. Statistics on linear chord diagrams // Discrete Math. Theor. Comput. Sci. 2020. V. 21, No. 2. Paper ID 11. 10 p.
     
  6. Acan H. On a uniformly random chord diagram and its intersection graph // Discrete Math. 2017. V. 340, No. 8. P. 1967–1985.
     
  7. Touchard J. Sur un problème de configurations et sur les fractions continues // Canad. J. Math. 1952. V. 4. P. 2–25. [French].
     
  8. Riordan J. The distribution of crossing of chords joining pairs of $2n$ points on a circle // Math. Comput. 1975. V. 29, No. 129. P. 215–222.
     
  9. Courtiel J., Yeats K., Zeilberger N. Connected chord diagrams and bridgeless maps // Electron. J. Comb. 2019. V. 26, No. 4. Paper ID P4.37. 56 p.
     
  10. Mahmoud A. A., Yeats K. Connected chord diagrams and the combinatorics of asymptotic expansions // J. Integer Seq. 2022. V. 25, No. 7. Paper ID 22.7.5. 22 p.
     
  11. Shevelev V. S. Combinatorial minors for matrix functions and their applications // Zesz. Nauk. Politech. Śląsk. Ser. Mat. Stosow. 2014. No. 4. P. 5–16.
     
  12. Шевелев В. С. Некоторые вопросы теории перечисления перестановок с ограниченными позициями // Итоги науки и техники. Сер. Теория вероятностей. Мат. статистика. Теор. кибернетика. Т. 30. М.: ВИНИТИ, 1992. С. 113–177.
     
  13. Минк Х. Перманенты. М.: Мир, 1982. 211 с.
     
  14. Stembridge J. R. Nonintersecting paths, Pfaffians, and plane partitions // Adv. Math. 1990. V. 83. P. 96–131.
     
  15. Barvinok A. Combinatorics and complexity of partition functions. Cham: Springer, 2016. 304 p. (Algorithms Comb.; V. 30).
     
  16. Fishel S., Grojnowski I. Canonical bases for the Brauer centralizer algebra // Math. Res. Lett. 1995. V. 2. P. 15–26.
     
  17. Barcelo H., Ram A. Combinatorial representation theory // New perspectives in algebraic combinatorics. New York: Camb. Univ. Press, 1999. P. 23–90. (Math. Sci. Res. Inst. Publ.; V. 38).
     
  18. Shalile A. On the center of the Brauer algebra // Algebr. Represent. Theory. 2013. V. 16. P. 65–100.
     
  19. Schwartz M. Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices // Linear Algebra Appl. 2009. V. 430. P. 1364–1374.
     
  20. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998. 656 с.
     
  21. Gabiati G., Maffioli F. On the computation of Pfaffians // Discrete Appl. Math. 1994. V. 51. P. 269–275.
     
  22. Wimmer M. Algorithm 923: Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices // ACM Trans. Math. Softw. 2012. V. 38, No. 4. Paper ID 30. 17 p. DOI: 10.1145/2331130.2331138.
     
  23. The on-line encyclopedia of integer sequences. Highland Park, NJ: OEIS Found., 2024. URL: oeis.org (accessed Mar. 3, 2024).

Исследование выполнено в рамках плановой гос. бюджетной темы НИР Физико-математического института ФИЦ Коми НЦ УрО РАН «Математические проблемы теории стохастических и детерминированных систем, включая системы большой размерности» (номер гос. регистрации 122040600066–5). 

Ефимов Дмитрий Борисович
  1. Физико-математический институт ФИЦ Коми НЦ УрО РАН, 
    ул. Коммунистическая, 24, 167982 Сыктывкар, Россия

E-mail: defimov@ipm.komisc.ru

Статья поступила 3 апреля 2023 г. 
После доработки — 11 октября 2023 г. 
Принята к публикации 22 декабря 2023 г.

Abstract:

A general method for the enumeration of various classes of chord diagrams with even and odd numbers of chord intersections is considered. The method is based on the calculation of the Pfaffian and Hafnian of the constraint matrix characterizing a class of diagrams. 
Tab. 3, illustr. 6, bibliogr. 23.

References:
  1. H. Acan, An enumerative-probabilistic study of chord diagrams, PhD Thesis (Ohio State Univ., Columbus, 2013).
     
  2. E. S. Krasko, I. N. Labutin, and A. V. Omelchenko, Enumeration of labelled and unlabelled Hamiltonian cycles in complete k-partite graphs, Zap. Nauchn. Semin. POMI, 488, 119–142 (2019) [Russian].
     
  3. T. Nakamigawa, The expansion of a chord diagram and the Genocchi numbers, Ars Math. Contemp. 18, 381–391 (2020).
     
  4. E. Sullivan, Linear chord diagrams with long chords, Electron. J. Comb. 24 (4), Paper ID P4.20 (2017).
     
  5. N. T. Cameron and K. Killpatrick, Statistics on linear chord diagrams, Discrete Math. Theor. Comput. Sci. 21 (2), Paper ID 11 (2020).
     
  6. H. Acan, On a uniformly random chord diagram and its intersection graph, Discrete Math. 340 (8), 1967–1985 (2017).
     
  7. J. Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math. 4, 2–25 (1952) [French].
     
  8. J. Riordan, The distribution of crossing of chords joining pairs of $2n$ points on a circle, Math. Comput. 29 (129), 215–222 (1975).
     
  9. J. Courtiel, K. Yeats, and N. Zeilberger, Connected chord diagrams and bridgeless maps, Electron. J. Comb. 26 (4), Paper ID P4.37 (2019).
     
  10. A. A. Mahmoud and K. Yeats, Connected chord diagrams and the combinatorics of asymptotic expansions, J. Integer Seq. 25 (7), Paper ID 22.7.5 (2022).
     
  11. V. S. Shevelev, Combinatorial minors for matrix functions and their applications, Zesz. Nauk. Politech. Śląsk. Ser. Mat. Stosow. No. 4, 5–16 (2014).
     
  12. V. S. Shevelev, Some problems of the theory of enumerating the permutations with restricted positions, in Itogi Nauki Tekhn., Teoriya Veroyatn. Mat. Stat. Teor. Kibern., Vol. 30 (VINITI, Moscow, 1992), pp. 113–177 [Russian] [J. Sov. Math. 61 (4), 2272–2317 (1992)].
     
  13. H. Minc, Permanents (Addison-Wesley, Reading, MA, 1978; Mir, Moscow, 1982 [Russian]).
     
  14. J. R. Stembridge, Nonintersecting paths, Pfaffians, and plane partitions, Adv. Math. 83, 96–131 (1990).
     
  15. A. Barvinok, Combinatorics and Complexity of Partition Functions (Springer, Cham, 2016) (Algorithms Comb., Vol. 30).
     
  16. S. Fishel and I. Grojnowski, Canonical bases for the Brauer centralizer algebra, Math. Res. Lett. 2, 15–26 (1995). 
     
  17. H. Barcelo and A. Ram, Combinatorial representation theory, in New Perspectives in Algebraic Combinatorics (Camb. Univ. Press, New York, 1999), pp. 23–90 (Math. Sci. Res. Inst. Publ., Vol. 38).
     
  18. A. Shalile, On the center of the Brauer algebra, Algebr. Represent. Theory 16, 65–100 (2013).
     
  19. M. Schwartz, Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices, Linear Algebra Appl. 430, 1364–1374 (2009).
     
  20. L. Lovász and M. D. Plummer, Matching Theory (North-Holland, Amsterdam, 1986; Mir, Moscow, 1998 [Russian]).
     
  21. G. Gabiati and F. Maffioli, On the computation of Pfaffians, Discrete Appl. Math. 51, 269–275 (1994).
     
  22. M. Wimmer, Algorithm 923: Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices, ACM Trans. Math. Softw. 38 (4), Paper ID 30 (2012), DOI: 10.1145/2331130.2331138.
     
  23. The On-Line Encyclopedia of Integer Sequences (OEIS Found., Highland Park, NJ, 2024), URL: oeis.org (accessed Mar. 3, 2024).