В математике и вычислительной технике треугольный массив чисел, многочленов и т.п. представляет собой дважды проиндексированную последовательность, в которой длина каждой строки равна собственному индексу строки. То есть 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), "Гармонические числа, треугольник Каталана и сетчатые узоры", Дискретная математика , 313 (14): 1515-1531, Arxiv : 1209,6423 , DOI : 10.1016 / j.disc.2013.03.017 , MR 3047390 .
- ^ Веллеман, Дэниел Дж .; Позвоните, Грегори С. (1995), "Перестановки и комбинированные замки", Математика Журнал , 68 (4): 243-253, DOI : 10,2307 / 2690567 , JSTOR 2690567 , MR 1363707 .
- ^ Миллер, Филип Л .; Миллер, Ли У .; Джексон, Первис М. (1987), Программирование по дизайну: первый курс по структурному программированию , Wadsworth Pub. Co., стр. 211–212, ISBN 9780534082444.
- ^ Хосоя, Харуо (1976), "Фибоначчи треугольник", Фибоначчи Quarterly , 14 (2): 173-178.
- ^ Losanitsch, С. М. (1897), "Die изомерного-Arten Bei ден Homologen дер парафин Reihe" , 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 .
- ^ Rota було, Самуил; Хэнкок, Эдвин Р .; Азиз, Фуркан; Pelillo, Marcello (2012), "Эффективное вычисление коэффициентов Ихаров с использованием полиномиальной рекурсии Bell", Линейная алгебра и ее приложение , 436 (5): 1436-1441, DOI : 10.1016 / j.laa.2011.08.017 , MR 2890929 .
- ^ Филдер, Дэниел С .; Олфорд, Сесил О. (1991), «Треугольник Паскаля: главный стрелок или только один из бандитов?», В Bergum, Gerald E .; Philippou, Andreas N .; Горадам, AF (ред.), Приложения чисел Фибоначчи (Труды Четвертой Международной конференции по числам Фибоначчи и их приложениям, Университет Уэйк Форест, Северная Каролина, США, 30 июля - 3 августа 1990 г.) , Springer, стр. 77–90 , ISBN 9780792313090.
- ^ Индуркхья, Нитин; Дамерау, Фред Дж., Ред. (2010), Справочник по обработке естественного языка, второе издание , CRC Press, стр. 65, ISBN 9781420085938.
- ^ Thacher младший, Генри С. (июль 1964), "Замечание о Алгоритм 60: Ромберга интеграции", коммуникаций АСМ , 7 (7): 420-421, DOI : 10,1145 / 364520,364542.
- ^ Миллар, Джессика; Слоан, штат Нью-Джерси; Янг, Нил Э. (1996), «Новая операция над последовательностями: преобразование Буструпэдона», Журнал комбинаторной теории , серия A, 76 (1): 44–54, arXiv : math.CO/0205218 , doi : 10.1006 / jcta.1996.0087.
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. «Числовой треугольник» . MathWorld .
