informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-178Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGВЫЧИСЛЕНИЕ ВЕРШИН ПОЛИТОПОВ РАЗБИЕНИЙ ЧИСЕЛCOMPUTING VERTICES OF INTEGER PARTITION POLYTOPESВрублевскийА. С.VroublevskiA. S.

Минск, Шаранговича, 22-А

alvrub@gmail.comШлыкВ. А.ShlykV. A.

Минск, Машиностроителей, 25

v.shlyk@gmail.comИООО «Управляющая компания ”Атлант-М”»BelarusКомандно-инженерный институт МЧС Республики БеларусьBelarus201512112016043448Copyright © Врублевский А.С., Шлык В.А., 20162016Врублевский А.С., Шлык В.А.Vroublevski A.S., Shlyk V.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/178

Описывается метод генерирования вершин политопов разбиений чисел, с помощью которого авторами были вычислены все вершины и опорные вершины политопов разбиений всех n ≤ 105 и все рюкзачные разбиения n ≤ 165. Метод не требует построения всех разбиений n. Вершины определяются с помощью достаточных и необходимых условий, в трудных случаях применяется известная программа Polymake. Подробно излагаются алгоритм проверки критерия, характеризующего разбиения, являющиеся выпуклыми комбинациями двух других; методика применения двух комбинаторных операций, преобразующих известные вершины в новые вершины, и способ применения программы Polymake для распознавания небольшого (для малых n) числа разбиений, являющихся выпуклыми комбинациями трех и более разбиений. Представляются результаты вычислений и формулируются новые проблемы, к которым приводят полученные данные о числах вершин и опорных вершин политопов разбиений чисел.

The paper describes a method of generating vertices of the polytopes of integer partitions that was used by the authors to calculate all vertices and support vertices of the partition polytopes for all n ≤ 105 and all knapsack partitions of n ≤ 165. The method avoids generating all partitions of n. The vertices are determined with the help of sufficient and necessary conditions; in the hard cases, the well-known program Polymake is used. Some computational aspects are exposed in more detail. These are the algorithm for checking the criterion that characterizes partitions that are convex combinations of two other partitions; the way of using two combinatorial operations that transform the known vertices to the new ones; and employing the Polymake to recognize a limited number (for small n) of partitions that need three or more other partitions for being convexly expressed. We discuss the computational results on the numbers of vertices and support vertices of the partition polytopes and some appealing problems these results give rise to.

ReferencesЭндрюс, Г. Теория разбиений / Г. Эндрюс. – М. : Наука, 1982. – 256 с.Эндрюс, Г. Теория разбиений / Г. Эндрюс. – М. : Наука, 1982. – 256 с.Эйлер, Л. Введение в анализ бесконечных / Л. Эйлер. – М. : Гос. изд. физ.-мат. лит., 1961. – Т. 1. – 316 с.Эйлер, Л. Введение в анализ бесконечных / Л. Эйлер. – М. : Гос. изд. физ.-мат. лит., 1961. – Т. 1. – 316 с.Dickson, L.E. History of the Theory of Numbers / L.E. Dickson. – Vol. II : Diophantine Analysis. – Washington : Carnegie Inst., 1919. – 520 p.Dickson, L.E. History of the Theory of Numbers / L.E. Dickson. – Vol. II : Diophantine Analysis. – Washington : Carnegie Inst., 1919. – 520 p.Шлык, В.А. Политопы разбиений чисел / В.А. Шлык // Весці Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 1996. – № 3. – С. 89–92.Шлык, В.А. Политопы разбиений чисел / В.А. Шлык // Весці Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 1996. – № 3. – С. 89–92.Shlyk, V.A. Polytopes of partitions of numbers / V.A. Shlyk // European J. Combin. – 2005. – Vol. 26, № 8. – P. 1139–1153.Shlyk, V.A. Polytopes of partitions of numbers / V.A. Shlyk // European J. Combin. – 2005. – Vol. 26, № 8. – P. 1139–1153.Емеличев, В.А. Многогранники, графы, оптимизация (комбинаторная теория многогранников) / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. – М. : Наука, 1981. – 341 с.Емеличев, В.А. Многогранники, графы, оптимизация (комбинаторная теория многогранников) / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. – М. : Наука, 1981. – 341 с.Шлык, В.А. Комбинаторные операции порождения вершин политопа разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. – 2009. – Т. 53, № 6. – С. 27–32.Шлык, В.А. Комбинаторные операции порождения вершин политопа разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. – 2009. – Т. 53, № 6. – С. 27–32.Холл, М. Комбинаторика / М. Холл. – М. : Мир, 1970. – 424 с.Холл, М. Комбинаторика / М. Холл. – М. : Мир, 1970. – 424 с.Gupta, H. Tables of partitions / H. Gupta, C.E. Gwyther, C.P. Winter // Royal society mathematical tables. – Vol. 4. – Cambridge : University Press, 1958. – 132 p.Gupta, H. Tables of partitions / H. Gupta, C.E. Gwyther, C.P. Winter // Royal society mathematical tables. – Vol. 4. – Cambridge : University Press, 1958. – 132 p.Sloane, N.J.A. a(n) = number of partitions of n (the partition numbers) [Electronic resource] / N.J.A. Sloane. – 2010. – Mode of access : http://oeis.org/A000041. – Date of access : 11.10.2015.Sloane, N.J.A. a(n) = number of partitions of n (the partition numbers) [Electronic resource] / N.J.A. Sloane. – 2010. – Mode of access : http://oeis.org/A000041. – Date of access : 11.10.2015.Zoghbi, A. Fast algorithms for generating integer partitions / A. Zoghbi, I. Stojmenovic // Intern. J. Computer Math. – 1998. – Vol. 70. – P. 319–332.Zoghbi, A. Fast algorithms for generating integer partitions / A. Zoghbi, I. Stojmenovic // Intern. J. Computer Math. – 1998. – Vol. 70. – P. 319–332.Рейнгольд, Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М. : Мир, 1980. – 476 с.Рейнгольд, Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М. : Мир, 1980. – 476 с.Nijenhius, A. A method and two algorithms on the theory of partitions / A. Nijenhius, H.S. Wilf // J. Comb. Theory A. – 1975. – Vol. 18. – P. 219–222.Nijenhius, A. A method and two algorithms on the theory of partitions / A. Nijenhius, H.S. Wilf // J. Comb. Theory A. – 1975. – Vol. 18. – P. 219–222.Riha, W. Efficient algorithms for doubly and multiply restricted partitions / W. Riha, K.R. James // Algorithm 29. Computing. – 1976. – Vol. 16. – P. 163–168.Riha, W. Efficient algorithms for doubly and multiply restricted partitions / W. Riha, K.R. James // Algorithm 29. Computing. – 1976. – Vol. 16. – P. 163–168.Constant time generation of integer partitions / K. Yamanaka [et al.] // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. – 2007. – Vol. E90-A, № 5. – P. 888–895.Constant time generation of integer partitions / K. Yamanaka [et al.] // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. – 2007. – Vol. E90-A, № 5. – P. 888–895.Knuth, D.E. Generating all partitions. Pre-fascicle 3B of The Art of Computer Programming. A draft of sections 7.2.1.4-5 [Electronic resource] / D.E. Knuth. – 2004. – Mode of access : http://www.cs.utsa.edu/~wagner/knuth/fasc3b.pdf. – Date of access : 11.10.2015.Knuth, D.E. Generating all partitions. Pre-fascicle 3B of The Art of Computer Programming. A draft of sections 7.2.1.4-5 [Electronic resource] / D.E. Knuth. – 2004. – Mode of access : http://www.cs.utsa.edu/~wagner/knuth/fasc3b.pdf. – Date of access : 11.10.2015.Kelleher, J. Generating all partitions: a comparison of two encodings [Electronic resource] / J. Kelleher, В. O'Sullivan. – 2009. – Mode of access : http://arxiv.org/pdf/0909.2331v1.pdf. – Date of access : 11.10.2015.Kelleher, J. Generating all partitions: a comparison of two encodings [Electronic resource] / J. Kelleher, В. O'Sullivan. – 2009. – Mode of access : http://arxiv.org/pdf/0909.2331v1.pdf. – Date of access : 11.10.2015.Opdyke, J.D. A unified approach to algorithms generating unrestricted and restricted integer compositions and integer partitions / J.D. Opdyke // J. Math. Model. Algor. – 2010. – Vol. 9, № 1. – P. 53–97.Opdyke, J.D. A unified approach to algorithms generating unrestricted and restricted integer compositions and integer partitions / J.D. Opdyke // J. Math. Model. Algor. – 2010. – Vol. 9, № 1. – P. 53–97.Stojmenovic, I. Generating all and random instances of a combinatorial object / I. Stojmenovic // Handbook of applied algorithms: solving scientific, engineering, and practical problem. – Hoboken : John Wiley&Sons, 2008. – P. 1–38.Stojmenovic, I. Generating all and random instances of a combinatorial object / I. Stojmenovic // Handbook of applied algorithms: solving scientific, engineering, and practical problem. – Hoboken : John Wiley&Sons, 2008. – P. 1–38.Shlyk, V.A. Number of vertices of the integer partition polytope [Electronic resource] / V.A. Shlyk. – 2012. – Mode of access : http://oeis.org/A203898. – Date of access : 11.10.2015.Shlyk, V.A. Number of vertices of the integer partition polytope [Electronic resource] / V.A. Shlyk. – 2012. – Mode of access : http://oeis.org/A203898. – Date of access : 11.10.2015.Shlyk, V.A. Number of support partitions-vertices [Electronic resource] / V.A. Shlyk. – 2012. – Mode of access : http://oeis.org/A203899. – Date of access : 11.10.2015.Shlyk, V.A. Number of support partitions-vertices [Electronic resource] / V.A. Shlyk. – 2012. – Mode of access : http://oeis.org/A203899. – Date of access : 11.10.2015.Ehrenborg, R. Number of knapsack partitions of n [Electronic resource] / R. Ehrenborg. – 2005. – Mode of access : http://oeis.org/A108917. – Date of access : 11.10.2015.Ehrenborg, R. Number of knapsack partitions of n [Electronic resource] / R. Ehrenborg. – 2005. – Mode of access : http://oeis.org/A108917. – Date of access : 11.10.2015.Шлык, В.А. Критерий представления разбиений чисел в виде выпуклой комбинации двух разбиений / В.А. Шлык // Вестник БГУ. Сер. 1. – 2009. – № 2. – С. 109–114.Шлык, В.А. Критерий представления разбиений чисел в виде выпуклой комбинации двух разбиений / В.А. Шлык // Вестник БГУ. Сер. 1. – 2009. – № 2. – С. 109–114.Shlyk, V.A. Integer partitions from the polyhedral point of view / V.A. Shlyk // Electron. Notes Discrete Math. – 2013. – Vol. 43. – P. 319–327.Shlyk, V.A. Integer partitions from the polyhedral point of view / V.A. Shlyk // Electron. Notes Discrete Math. – 2013. – Vol. 43. – P. 319–327.Shlyk, V.A. Polyhedral approach to integer partitions / V.A. Shlyk // Journal of Combinatorial Mathematics and Combinatorial Computing. – 2014. – Vol. 89. – P. 113–128.Shlyk, V.A. Polyhedral approach to integer partitions / V.A. Shlyk // Journal of Combinatorial Mathematics and Combinatorial Computing. – 2014. – Vol. 89. – P. 113–128.Gawrilow, E. Polymake: a framework for analyzing convex polytopes / E. Gawrilow, E.M. Joswig // Polytopes – combinatorics and computation. – Basel : Birkhäuser, 2000. – P. 43–73.Gawrilow, E. Polymake: a framework for analyzing convex polytopes / E. Gawrilow, E.M. Joswig // Polytopes – combinatorics and computation. – Basel : Birkhäuser, 2000. – P. 43–73.Шлык, В.А. О вершинах политопов разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. – 2008. – Т. 52, № 3. – С. 5–10.Шлык, В.А. О вершинах политопов разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. – 2008. – Т. 52, № 3. – С. 5–10.Handbook of Mathematical Functions / M. Abramowitz, I.A. Stegun [eds]. – Applied Math. Series 55. – Washington : Government Printing Office, 1972. – 1046 p.Handbook of Mathematical Functions / M. Abramowitz, I.A. Stegun [eds]. – Applied Math. Series 55. – Washington : Government Printing Office, 1972. – 1046 p.Barvinok, A.I. Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed / A.I. Barvinok // Math. Oper. Res. – 1994. – Vol. 19. – P. 769–779.Barvinok, A.I. Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed / A.I. Barvinok // Math. Oper. Res. – 1994. – Vol. 19. – P. 769–779.Effective lattice point counting in rational convex polytopes / J.A. De Loera [et al.] // Journal of Symbolic Computation. – 2004. – Vol. 38, № 4. – P. 1273–1302.Effective lattice point counting in rational convex polytopes / J.A. De Loera [et al.] // Journal of Symbolic Computation. – 2004. – Vol. 38, № 4. – P. 1273–1302.Ehrenborg, R. The Möbius function of partitions with restricted block sizes / R. Ehrenborg, M.A. Readdy // Adv. in Appl. Math. – 2007. – Vol. 39, № 3. – P. 283–292.Ehrenborg, R. The Möbius function of partitions with restricted block sizes / R. Ehrenborg, M.A. Readdy // Adv. in Appl. Math. – 2007. – Vol. 39, № 3. – P. 283–292.

The authors declare that there are no conflicts of interest present.