Треугольный массив - Triangular array

Не путать с Треугольная матрица.

Треугольный массив, правая диагональная последовательность которого состоит из Номера звонков

В математике и информатике треугольная решетка чисел, многочленов и т.п. представляет собой дважды проиндексированную последовательность, в которой длина каждой строки равна собственному индексу строки. Это я-я строка содержит только я элементы.

Примеры

Примечательные частные примеры включают в себя:

• В Треугольник колокола, номера которых подсчитывают перегородки набора в котором данный элемент является самым большим одиночка^[1]
• Каталонский треугольник, который считает строки круглых скобок, в которых нет непревзойденных закрывающих скобок^[2]
• Треугольник Эйлера, который считает перестановки с заданным количеством подъемов^[3]
• Треугольник Флойда, все записи которого представляют собой целые числа в порядке^[4]
• Треугольник Хосои, на основе Числа Фибоначчи^[5]
• Треугольник Лозанича, используемый в математике химических соединений^[6]
• Треугольник Нараяны, подсчитывая строки сбалансированных круглых скобок с заданным количеством различных вложений^[7]
• Треугольник Паскаля, чьи записи являются биномиальные коэффициенты^[8]

Треугольные массивы целых чисел, в которых каждая строка симметрична и начинается и заканчивается на 1, иногда называют обобщенные треугольники Паскаля; примеры включают треугольник Паскаля, числа Нараяны и треугольник чисел Эйлера.^[9]

Обобщения

Треугольные массивы могут содержать математические значения, отличные от чисел; например Полиномы Белла образуют треугольный массив, в котором каждый элемент массива является полиномом.^[10]

Также рассматривались массивы, в которых длина каждой строки растет как линейная функция от номера строки (а не равна номеру строки).^[11]

Приложения

Помимо представления треугольные матрицы, треугольные решетки используются в нескольких алгоритмы. Одним из примеров является CYK алгоритм для разбора контекстно-свободные грамматики, пример динамическое программирование.^[12]

Метод Ромберга может использоваться для оценки стоимости определенный интеграл заполнив значения в треугольнике чисел.^[13]

В Преобразование Бустрофедона использует треугольный массив для преобразования одного целочисленная последовательность в другой.^[14]

Смотрите также

• Треугольное число, количество записей в таком массиве до некоторой конкретной строки

Рекомендации

1. Шаллит, Джеффри (1980), «Треугольник для чисел Белла», Сборник рукописей, связанных с последовательностью Фибоначчи (PDF), Санта-Клара, Калифорния: Ассоциация Фибоначчи, стр. 69–71, МИСТЕР  0624091.
2. Китаев, Сергей; Лизе, Джеффри (2013), «Числа гармоник, каталонский треугольник и сетчатые узоры», Дискретная математика, 313 (14): 1515–1531, arXiv:1209.6423, Дои:10.1016 / j.disc.2013.03.017, МИСТЕР  3047390.
3. Веллеман, Дэниел Дж .; Звоните, Грегори С. (1995), "Перестановки и кодовые замки", Математический журнал, 68 (4): 243–253, Дои:10.2307/2690567, JSTOR  2690567, МИСТЕР  1363707.
4. Миллер, Филип Л .; Миллер, Ли У .; Джексон, Первис М. (1987), Программирование по дизайну: первый курс по структурному программированию, Паб Уодсворт. Co., стр. 211–212, ISBN  9780534082444.
5. Хосоя, Харуо (1976), «Треугольник Фибоначчи», Ежеквартальный отчет Фибоначчи, 14 (2): 173–178.
6. Лосанич, С. М. (1897 г.), "Die Isomerie-Arten bei den Homologen der Paraffin-Reihe", Chem. Бер., 30 (2): 1917–1926, Дои:10.1002 / cber.189703002144.
7. Барри, Пол (2011), «Об обобщении треугольника Нараяны», Журнал целочисленных последовательностей, 14 (4): статьи 11.4.5, 22, МИСТЕР  2792161.
8. Эдвардс, А. В. Ф. (2002), Арифметический треугольник Паскаля: история математической идеи, JHU Press, ISBN  9780801869464.
9. Барри, П. (2006), «О построении обобщенных треугольников Паскаля на основе целочисленных последовательностей» (PDF), Журнал целочисленных последовательностей, 9 (6.2.4): 1–34.
10. Рота Було, Самуэль; Хэнкок, Эдвин Р .; Азиз, Фуркан; Пелилло, Марчелло (2012), «Эффективное вычисление коэффициентов Ихары с использованием полиномиальной рекурсии Белла», Линейная алгебра и ее приложения, 436 (5): 1436–1441, Дои:10.1016 / j.laa.2011.08.017, МИСТЕР  2890929.
11. Fielder, Daniel C .; Олфорд, Сесил О. (1991), «Треугольник Паскаля: лучший пистолет или только один из бандитов?», В Bergum, Gerald E .; Philippou, Andreas N .; Хорадам, А. Ф. (ред.), Приложения чисел Фибоначчи (Труды Четвертой Международной конференции по числам Фибоначчи и их применениям, Университет Уэйк Форест, Северная Каролина, США, 30 июля - 3 августа 1990 г.), Springer, стр. 77–90, ISBN  9780792313090.
12. Индуркхья, Нитин; Дамерау, Фред Дж., Ред. (2010), Справочник по обработке естественного языка, второе издание, CRC Press, стр. 65, ISBN  9781420085938.
13. Тэчер-младший, Генри К. (июль 1964 г.), "Замечание по алгоритму 60: интеграция Ромберга", Коммуникации ACM, 7 (7): 420–421, Дои:10.1145/364520.364542.
14. Миллар, Джессика; Sloane, N.J.A .; Янг, Нил Э. (1996), "Новая операция над последовательностями: преобразование Буструпэдона", Журнал комбинаторной теории, Серия А, 76 (1): 44–54, arXiv:math.CO/0205218, Дои:10.1006 / jcta.1996.0087.

внешняя ссылка

• Вайсштейн, Эрик В. «Числовой треугольник». MathWorld.