Треугольный массив
В математике и вычислительной технике треугольный массив чисел, полиномов и т.п. представляет собой последовательность с двойным индексом, в которой длина каждой строки равна длине собственного индекса строки. То есть i -я строка содержит только i элементов.
Примеры [ править ]
Известные конкретные примеры включают в себя:
- Треугольник Белла , числа которого подсчитывают разделы множества , в котором данный элемент является наибольшим одноэлементным. [1]
- Каталонский треугольник , который подсчитывает строки круглых скобок, в которых ни одна закрывающая скобка не является непревзойденной. [2]
- Треугольник Эйлера , подсчитывающий перестановки с заданным числом восхождений. [3]
- Треугольник Флойда , элементы которого представляют собой все целые числа по порядку. [4]
- Треугольник Хосои , основанный на числах Фибоначчи. [5]
- Треугольник Лозанича , используемый в математике химических соединений. [6]
- Треугольник Нараяны , подсчитывающий строки сбалансированных круглых скобок с заданным количеством различных вложений. [7]
- Треугольник Паскаля , элементами которого являются биномиальные коэффициенты [8]
Треугольные массивы целых чисел, в которых каждая строка симметрична и начинается и заканчивается 1, иногда называют обобщенными треугольниками Паскаля ; примеры включают треугольник Паскаля, числа Нараяны и треугольник чисел Эйлера. [9]
Обобщения [ править ]
Треугольные массивы могут содержать математические значения, отличные от чисел; например, полиномы Белла образуют треугольный массив, в котором каждый элемент массива является полиномом. [10]
Также рассматривались массивы, в которых длина каждой строки растет как линейная функция номера строки (а не равна номеру строки). [11]
Приложения [ править ]
Помимо представления треугольных матриц используются треугольные массивы , в ряде алгоритмов . Одним из примеров является алгоритм CYK для разбора контекстно-свободных грамматик , пример динамического программирования . [12]
Метод Ромберга можно использовать для оценки значения определенного интеграла путем заполнения значений в треугольнике чисел. [13]
использует Преобразование Бустрофедона треугольный массив для преобразования одной целочисленной последовательности в другую. [14]
См. также [ править ]
- Треугольное число — количество записей в таком массиве до определенной строки.
Ссылки [ править ]
- ^ Шалит, Джеффри (1980), «Треугольник для чисел Белла», Сборник рукописей, связанных с последовательностью Фибоначчи (PDF) , Санта-Клара, Калифорния: Ассоциация Фибоначчи, стр. 69–71, MR 0624091 .
- ^ Китаев Сергей ; Лизе, Джеффри (2013), «Гармонические числа, каталонский треугольник и сетчатые узоры», Discrete Mathematics , 313 (14): 1515–1531, arXiv : 1209.6423 , doi : 10.1016/j.disc.2013.03.017 , MR 3047390 , S2CID 18248485 .
- ^ Веллеман, Дэниел Дж.; Колл, Грегори С. (1995), «Перестановки и кодовые замки», Mathematics Magazine , 68 (4): 243–253, doi : 10.2307/2690567 , JSTOR 2690567 , MR 1363707 .
- ^ Миллер, Филип Л.; Миллер, Ли В.; Джексон, Первис М. (1987), Программирование по дизайну: первый курс структурного программирования , Wadsworth Pub. Co., стр. 211–212, ISBN. 9780534082444 .
- ^ Хосоя, Харуо (1976), «Треугольник Фибоначчи», The Fibonacci Quarterly , 14 (2): 173–178 .
- ^ Лосанич, С.М. (1897), "Виды изомерии в гомологах парафинового ряда" , Chem. , 30 (2): 1917–1926, doi : 10.1002/cber.189703002144 .
- ^ Барри, Пол (2011), «Об обобщении треугольника Нараяны», Журнал целочисленных последовательностей , 14 (4): Статья 11.4.5, 22, MR 2792161 .
- ^ Эдвардс, AWF (2002), Арифметический треугольник Паскаля: история математической идеи , JHU Press, ISBN 9780801869464 .
- ^ Барри, П. (2006), «О конструкциях обобщенных треугольников Паскаля на основе целочисленных последовательностей» (PDF) , Journal of Integer Sequences , 9 (6.2.4): 1–34, Bibcode : 2006JIntS...9.. .24Б .
- ^ Рота Було, Самуэль; Хэнкок, Эдвин Р.; Азиз, Фуркан; Пелилло, Марчелло (2012), «Эффективное вычисление коэффициентов Ихара с использованием полиномиальной рекурсии Белла», Линейная алгебра и ее приложения , 436 (5): 1436–1441, doi : 10.1016/j.laa.2011.08.017 , MR 2890929 .
- ^ Филдер, Дэниел К.; Алфорд, Сесил О. (1991), «Треугольник Паскаля: лучший стрелок или просто один из банды?», Бергум, Джеральд Э.; Филиппу, Андреас Н.; Хорадам, А. Ф. (ред.), Применения чисел Фибоначчи (Материалы Четвертой Международной конференции по числам Фибоначчи и их применениям, Университет Уэйк Форест, Северная Каролина, США, 30 июля – 3 августа 1990 г.) , Springer, стр. 77–90. , ISBN 9780792313090 .
- ^ Индурхья, Нитин; Дамерау, Фред Дж., ред. (2010), Справочник по обработке естественного языка, второе издание , CRC Press, стр. 65, ISBN 9781420085938 .
- ^ Тэчер-младший, Генри К. (июль 1964 г.), «Замечание об алгоритме 60: Интеграция Ромберга», Communications of ACM , 7 (7): 420–421, doi : 10.1145/364520.364542 , S2CID 29898282 .
- ^ Миллар, Джессика; Слоан, Нью-Джерси; Янг, Нил Э. (1996), «Новая операция над последовательностями: преобразование Буструфедона», Журнал комбинаторной теории , серия A, 76 (1): 44–54, arXiv : math.CO/0205218 , doi : 10.1006/ jcta.1996.0087 , S2CID 15637402 .