Задача перечисления разбиений прямоугольника заданных целочисленных размеров h × w на прямоугольники 1 × 2 рассматривалась рядом авторов в связи с вопросами термодинамики потоков жидкости и проблемой перечисления совершенных паросочетаний плоского графа за полиномиальное время. В данной работе методами теории графов разработан алгоритм, компьютерное воплощение которого способно генерировать систему взаимно-рекуррентных формул для искомого перечисления разбиений прямоугольника произвольных целочисленных размеров. Решены вопросы инициализации рекуррентных формул; показано, что решение задачи организации вычислений в соответствии с системой формул, сгенерированных компьютером, сводится к топологической сортировке ациклического орграфа; сформулированы открытые задачи.
Скачать электронную версию публикации
Загружен, раз: 89
- Title Взаимно-рекуррентные формулы для перечисления разбиений прямоугольника
- Headline Взаимно-рекуррентные формулы для перечисления разбиений прямоугольника
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 46
- Date:
- DOI 10.17223/20710410/46/9
Ключевые слова
перечисление разбиений прямоугольника, рекуррентные формулы, перечисление разбиений прямоугольника, рекуррентные формулы, enumeration of rectangle partitions, recurrent formulasАвторы
Ссылки
Stanley R. P. Enumerative Combinatorics. V. 2. Cambridge: Cambridge University Press, 1999. 228 p
Montroll E. W. Lattice statistics // Applied Combinatorial Mathematics / ed. E. F. Beckenbach. N.Y.: John Wiley and Sons, 1964. P. 96-143
Караваев А. М., Перепечко С. Н. Задача о димерах на цилиндрах: рекуррентные соотношения и производящие функции // Математическое моделирование. 2014. Т. 26. №11. С. 18-22
Kateleyn P. W. The statistic of dimers on a lattice I: The number of dimer arrangements on quadratic lattice // Physica. 1961. V. 27. P. 1209-1225
Temperley H.N.V. and Fisher M.E. Dimer problem in statistical mechanics - an exact result // Phil. Mag. 1961. V. 6. P. 1061-1063
Matousek J. Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra: Amer. Math. Soc., 2010. 182 p
Klarner D. and Pollack J. Domino tilings of rectangles with fixed width // Discr. Math. 1980. V. 32. P. 45-52
Read R. C. A note on tiling rectangles with dominoes // Fib. Q. 1980. V. 18. No. 1. P. 24-27
Graham R. L., Knuth D. E., and Patashnik O. Concrete Mathematics. Massachusetts: Addison-Wesley, 1994. 657 p
Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: пер. с англ. М.: Мир, 1998. 703 с
http://neerc . ifmo . ru/school/archive/1993-1994/ru-olymp-roi-1994-problems . html - Олимпиады по информатике. 1994
Кирюхин В. М. VI Всероссийская олимпиада школьников по информатике // Информатика и образование. 1994. №3. С. 47-50
Волченков С. Г. Задача «Паркет» // Информатика и образование. 1994. №3. С. 52-54
Магомедов А. М., Магомедов Т. А. Компьютерный вывод рекуррентных формул разбиения прямоугольника // Тез. докл. X Белорусской матем. конф., 3-7 ноября 2008 г. Ч. 4. Минск: Институт математики НАН Беларуси, 2008. С. 44
Albahari J. and Albahari B. C# 5.0 in a Nutshell. The Definitive Reference. 5th ed. O'Reilly Media, 2012. 1064 p
Swamy M. N. and Thulasiraman K. Graphs, Networks and Algorithms. N.Y.: Wiley-Inter-science, 1981. 590 p
Магомедов А. М. Цепочечные структуры в задачах о расписаниях // Прикладная дискретная математика. 2016. № 3(33). С. 67-77
Garey M. R. and Jonson D. S. Computers and Intractability. San Francisco: Freeman and Company, 1979. 347 p
Lawler E. L. Combinatorial Optimization: Networks and Matroids. N.Y.: Holt, Rinehart, and Winston, 1976. 384 p
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Книжный дом «Либроком», 2009. 392 с
Взаимно-рекуррентные формулы для перечисления разбиений прямоугольника | Прикладная дискретная математика. 2019. № 46. DOI: 10.17223/20710410/46/9
Скачать полнотекстовую версию
Загружен, раз: 433