Массив Риордан

Массив Риордана представляет собой бесконечную нижнюю треугольную матрицу , $D$ , построенный из двух формальных степенных рядов , $d(t)$ порядка 0 и $h(t)$ порядка 1, такой, что $d_{n,k}=[t^{n}]d(t)h(t)^{k}$ .

Массив Риордана является элементом группы Риордан. ^[1] Он был определен математиком Луисом Шапиро и назван в честь Джона Риордана . ^[1]Изучение массивов Риордана является растущей областью, на которую влияют и вносят свой вклад в другие области, такие как комбинаторика , теория групп , теория матриц , теория чисел , вероятность , последовательности и ряды , группы Ли и алгебры Ли , ортогональные многочлены , теория графов , сети , унимодальные последовательности, комбинаторные тождества, эллиптические кривые , численная аппроксимация , асимптотический анализ и анализ данных . Массивы Риордана также объединяют важные инструменты, такие как производящие функции , системы компьютерной алгебры , формальные языки и модели путей . ^[2] Книги по этой теме, такие как The Riordan Array. ^[1] (Шапиро и др., 1991).

Формальное определение

Формальный степенной ряд $a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots =\sum _{j\geq 0}a_{j}x^{j}\in \mathbb {C} [[x]]$ (где $\mathbb {C} [[x]]$ — кольцо формальных степенных рядов с комплексными коэффициентами), говорят, что он имеет порядок $r$ если $a_{0}=\cdots =a_{r-1}=0\neq a_{r}$ . Писать ${\mathcal {F}}_{r}$ для множества формальных степенных рядов порядка r. $r.$ Силовой ряд $a(x)$ имеет мультипликативную обратную (т.е. $1/a(x)$ является степенным рядом) тогда и только тогда, когда он имеет порядок 0, т. е. тогда и только тогда, когда он лежит в ${\mathcal {F}}_{0}$ ; у него есть обратная композиция , то есть существует степенной ряд ${\bar {a}}$ такой, что ${\bar {a}}(a(x))=x$ тогда и только тогда, когда оно имеет порядок 1, т.е. тогда и только тогда, когда оно лежит в ${\mathcal {F}}_{1}$ .

Как упоминалось ранее, массив Риордана обычно определяется как пара степенных рядов ( $(a(t),b(t))\in {\mathcal {F}}_{0}\times {\mathcal {F}}_{1}$ . Часть «массив» в его названии связана с тем фактом, что человек ассоциируется с (a $(a(t),b(t))$ массив комплексных чисел, определенный dn, $d_{n,k}:=[t^{n}]a(t)b(t)^{k},$ $n,k\in \mathbb {N} =\mathbb {Z} _{\geq 0}.$ (Здесь [т $[t^{n}]\cdots$ означает коэффициент $t^{n}$ в $\cdots$ ). Таким образом, столбец $k$ массива состоит из последовательности коэффициентов степенного ряда $a(t)b(t)^{k};$ в частности, столбец 0 определяет и определяется степенным рядом $a(t).$ Как $a(t)$ имеет порядок 0, имеет мультипликативную обратную операцию, и отсюда следует, что по столбцу 1 массива мы можем восстановить b (t $b(t)$ как б (т $b(t)=a(t)^{-1}a(t)b(t).$ С $b(t)=b_{1}t+b_{2}t^{2}+\cdots$ имеет порядок 1, b (t $b(t)^{k}$ имеет порядок $k$ и поэтому имеет (t $a(t)b(t)^{k}.$ Отсюда следует, что массив dn, $d_{n,k}$ представляет собой бесконечный треугольник, демонстрирующий геометрическую прогрессию $(d_{k,k})_{k\geq 0}=(a_{0}b_{1}^{k})_{k\geq 0}$ на его главной диагонали. Отсюда также следует, что отображение, ассоциированное с парой степенных рядов (a $(a(t),b(t))\in {\mathcal {F}}_{0}\times {\mathcal {F}}_{1}$ его треугольный массив инъективен.

Пример

Примером массива Риордана является пара степенных рядов

$\left({\frac {1}{1-x}},{\frac {x}{1-x}}\right)=\left(\sum _{j\geq 0}x^{j},\sum _{j\geq 0}x^{j+1}\right)\in {\mathcal {F}}_{0}\times {\mathcal {F}}_{1}$ .

Нетрудно показать, что эта пара порождает бесконечный треугольный массив биномиальных коэффициентов $d_{n,k}={\binom {n}{k}}$ , также называемая матрицей Паскаля:

$P=\left({\begin{array}{ccccccc}1&&&&&&\\1&1&&&&&\\1&2&1&&&&\cdots \\1&3&3&1&&&\\1&4&6&4&1&&\\&&\vdots &&&&\ddots \end{array}}\right)$ .

Доказательство: если $q(x)=\sum _{j\geq 0}q_{j}x^{j}$ представляет собой степенной ряд с соответствующей последовательностью коэффициентов $(q_{0},q_{1},q_{2},...)$ , затем умножением Коши степенного ряда, $q(x){\frac {x}{1-x}}=\sum _{j\geq 0}(0+q_{0}+q_{1}+\cdots +q_{j-1})x^{j}.$ Таким образом, последний ряд имеет последовательность коэффициентов $(0,q_{0},q_{0}+q_{1},q_{0}+q_{1}+q_{2},....)$ , и, следовательно, $[t^{n}]q(x){\frac {x}{1-x}}=q_{0}+\cdots +q_{n-1}$ . Исправьте любой $k\in \mathbb {Z} _{\geq 0}.$ Если $q_{n}={\binom {n}{k}}$ , так что $(q_{n})_{n\geq 0}$ представляет столбец $k$ массива Паскаля, то $\sum _{j=0}^{n-1}q_{j}=\sum _{j=0}^{n-1}{\binom {j}{k}}={\binom {n}{k+1}}$ . Этот аргумент позволяет увидеть индукцией по $k$ что ${\frac {1}{1-x}}\left({\frac {x}{1-x}}\right)^{k}$ есть столбец $k$ массива Паскаля как последовательность коэффициентов.

Характеристики

Ниже приведены некоторые часто используемые факты о массивах Риордана. Обратите внимание, что правила умножения матриц, применяемые к бесконечным нижне-треугольным матрицам, приводят только к конечным суммам, а произведение двух бесконечных нижне-треугольных матриц является бесконечным нижне-треугольным. Следующие две теоремы были впервые сформулированы и доказаны Шапиро и др. ^[1] которые говорят, что они модифицировали работу, которую нашли в статьях Джан-Карло Роты и книге Романа. ^[3]

Теорема: а. Позволять $(a(x),b(x))$ и $(c(x),d(x))$ — массивы Риордана, рассматриваемые как бесконечные нижние треугольные матрицы. Тогда произведением этих матриц будет массив, связанный с парой $(a(x)c(b(x)),d(b(x)))$ формального степенного ряда, который сам по себе является массивом Риордана.

б. Этот факт оправдывает определение умножения $*$ ' массивов Риордана, рассматриваемых как пары степенных рядов

(a(x),b(x))*(c(x),d(x))=(a(x)c(b(x)),d(b(x))

Доказательство: поскольку $a(x),c(x)$ имеют порядок 0, ясно, что $a(x)c(b(x))$ имеет порядок 0. Аналогично $b(x),d(x)\in {\mathcal {F}}_{1}$ подразумевает $d(b(x))\in {\mathcal {F}}_{1}.$ Так $(a(x)c(b(x)),d(b(x)))$ представляет собой массив Риордана. Определить матрицу $M$ как массив Риордана $(a(x),b(x)).$ По определению, это $j$ -й столбец $M_{*,j}$ представляет собой последовательность коэффициентов степенной ряд $a(x)b(x)^{j}$ . Если умножить эту матрицу справа на последовательность $(r_{0},r_{1},r_{2},...)^{T}$ получаем в результате линейную комбинацию столбцов $M$ который мы можем прочитать как линейную комбинацию степенных рядов, а именно $\sum _{\nu \geq 0}r_{\nu }M_{*,\nu }=\sum _{\nu \geq 0}r_{\nu }a(x)b(x)^{\nu }=a(x)\sum _{\nu \geq 0}r_{\nu }b(x)^{\nu }.$ Таким образом, просмотр последовательности $(r_{0},r_{1},r_{2},...)^{T}$ как кодифицировано степенным рядом $r(x),$ мы показали это $(a(x),b(x))*r(x)=a(x)r(b(x)).$ Здесь $*$ — символ, обозначающий соответствие на уровне степенного ряда матричному умножению. Мы перемножили массив Риордана $(a(x),b(x))$ с одним степенным рядом. Теперь позвольте $(c(x),d(x))$ быть еще одним массивом Риордана, рассматриваемым как матрица. Можно сформировать произведение $(a(x),b(x))(c(x),d(x))$ . $j$ -й столбец этого товара просто $(a(x),b(x))$ умноженный на $j$ -й столбец $(c(x),d(x)).$ Поскольку последний соответствует степенному ряду $c(x)d(x)^{j}$ , из вышеизложенного следует, что $j$ -й столбец $(a(x),b(x))(c(x),d(x))$ соответствует $a(x)c(b(x))d(b(x))^{j}$ . Поскольку это справедливо для всех индексов столбцов $j$ происходит в $(c(x),d(x))$ мы показали часть а. Часть Б теперь ясна. $\Box$

Теорема: Семейство массивов Риордана, наделенное произведением ' $*$ определенное выше, образует группу: группу Риордана. ^[1]

Доказательство: Ассоциативность умножения. $*$ ' следует из ассоциативности умножения матриц. Следующее примечание $(1,x)*(c(x),d(x))=(1\cdot c(x),d(x))=(c(x),d(x))$ . Так $(1,x)$ является левым нейтральным элементом. Наконец, мы утверждаем, что $(c({\bar {d}}(x))^{-1},{\bar {d}}(x))$ является левым обратным к степенному ряду $(c(x),d(x))$ . Для этого проверьте расчет $(c({\bar {d}}(x))^{-1},{\bar {d}}(x))*(c(x),d(x))$ $=((c({\bar {d}}(x))^{-1}c(d(x)),d({\bar {d}}(x)))=(1,x)$ . Как известно, ассоциативная структура, имеющая левонейтральный элемент и каждый элемент которой имеет левый инверсный элемент, является группой. $\Box$

Конечно, не все обратимые бесконечные нижние треугольные массивы являются массивами Риордана. Вот полезная характеристика массивов Риордана. Следующий результат, по-видимому, принадлежит Роджерсу. ^[4]

Теорема: бесконечный нижний треугольный массив. $D=(d_{n,k})_{n,k\geq 0}$ является массивом Риордана тогда и только тогда, когда существует последовательность, традиционно называемая $A$ -последовательность, $A=(a_{0}\neq 0,a_{1},...)$ такой, что

*_{1}:d_{n+1,k+1}=a_{0}d_{n,k}+a_{1}d_{n,k+1}+a_{2}d_{n,k+2}+\cdots =\sum _{j\geq 0}a_{j}d_{n,k+j}

Доказательство . ^[5] $\Rightarrow :$ Позволять $D$ быть массивом Риордана, происходящим из $(d(t),h(t)).$ С $d(t)\in {\mathcal {F}}_{0},$ $d_{0,0}\neq 0.$ С $h(t)$ имеет порядок 1, отсюда следует, что $(d(t)h(t)/t,h(t))$ является массивом Риордана и по свойству group существует массив Риордана $(A(t),B(t))$ такой, что $(d(t),h(t))*(A(t),B(t))=(d(t)h(t)/t,h(t)).$ Вычисление доходности левой части $(d(t)A(h(t)),B(h(t))$ и поэтому сравнение дает $B(h(t))=h(t).$ Конечно $B(t)=t$ является решением этого уравнения; это уникально, потому что $B$ обратима композиция. Итак, мы можем переписать уравнение как $(d(t),h(t))*(A(t),t)=(d(t)h(t)/t,h(t)).$

Теперь, исходя из закона умножения матриц, $n,k$ -вход левой части этого последнего уравнения равен

\sum _{j\geq 0}d_{n,j}(A(t),t)_{j,k}=\sum \limits _{j\geq 0}d_{n,j}[t^{j}]A(t)t^{k}=\sum \limits _{j\geq 0}d_{n,j}[t^{j-k}]A(t)=\sum \limits _{j\geq 0}d_{n,j}a_{j-k}=\sum \limits _{j\geq 0}a_{j}d_{n,k+j}.

С другой стороны, $n,k$ -ввод правой части приведенного выше уравнения равен

t^{[n]}{\frac {1}{t}}d(t)h(t)h(t)^{k}=t^{[n+1]}d(t)h(t)^{k+1}=d_{n+1,k+1},

так что я результаты. От $*_{1}$ мы также получаем $d_{n+1,n+1}=a_{0}d_{n,n}$ для всех $n\geq 0$ и поскольку мы знаем, что диагональные элементы ненулевые, мы имеем $a_{0}\neq 0.$ Обратите внимание, что используя уравнение $*_{1}$ можно вычислить все записи, зная записи $(d_{n,0})_{n\geq 0}.$

$\Leftarrow :$ Теперь предположим, что мы знаем о треугольном массиве уравнения $*_{1}$ для некоторой последовательности $(a_{j})_{j\geq 0}.$ Позволять $A(t)$ быть производящей функцией этой последовательности и определить $h(t)$ из уравнения $tA(h(t))=h(t).$ Проверьте, можно ли решить полученные уравнения относительно коэффициентов $h;$ и поскольку $a_{0}\neq 0$ это понятно $h(t)$ имеет порядок 1. Пусть $d(t)$ — производящая функция последовательности $(d_{0,0},d_{1,0},d_{2,0},...).$ Тогда для пары $(d(t),h(t))$ мы находим $(d(t),h(t))*(A(t),t)=(d(t)A(h(t)),h(t))=(d(t)h(t)/t,h(t)).$ Это в точности те же уравнения, которые мы нашли в первой части доказательства и, проведя его рассуждения, находим уравнения типа $*_{1}$ . С $d(t)$ (или последовательность его коэффициентов) определяет другие элементы, мы обнаруживаем, что массив, с которого мы начали, является массивом, который мы вывели. Итак, массив в $*_{1}$ представляет собой массив Риордана. $\Box$

Очевидно, $A$ -последовательность сама по себе не предоставляет всей информации о массиве Риордана. Помимо $A$ -последовательность тот $Z$ -последовательность, приведенная ниже, была изучена и оказалась полезной.

Теорема. Позволять $(d_{n,k})_{n,k\geq 0}$ — бесконечный нижний треугольный массив, диагональная последовательность которого $(d_{n,n})_{n\geq 0}$ не содержит нулей. Тогда существует единственная последовательность $Z=(z_{0},z_{1},z_{2},...)$ такой, что

d_{n+1,0}=z_{0}d_{n,0}+z_{1}d_{n,1}+z_{2}d_{n,2}+\cdots =\sum \limits _{j\geq 0}z_{j}d_{n,j},\quad n=0,1,2,3,...

Доказательство: ввиду треугольности массива заявленное уравнение эквивалентно $d_{n+1,0}=\sum _{j=0}^{n}z_{j}d_{n,j}.$ Для $n=0,$ это уравнение $d_{1,0}=z_{0}d_{0,0}$ и, как $d_{0,0}\neq 0,$ это позволяет вычислять $z_{0}$ однозначно. В общем, если $z_{0},z_{1},...,z_{n-1}$ известны, то $d_{n+1,0}-\sum _{j=0}^{n-1}z_{j}d_{n,j}=z_{n}d_{n,n}$ позволяет вычислять $z_{n}$ однозначно. $\Box$

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Шапиро, Луи В .; Гету, Сейюм; Воан, Вэнь-Цзинь; Вудсон, Леон К. (ноябрь 1991 г.). «Группа Риордан». Дискретная прикладная математика . 34 (1–3): 229–239. дои : 10.1016/0166-218X(91)90088-E .
^ «6-я Международная конференция по массивам Риордана и смежным темам» . 6-я Международная конференция по массивам Риордана и смежным темам .
^ Роман, С. (1984). Умбральное исчисление . Нью-Йорк: Академическая пресса.
^ Роджерс, генеральный директор (1978). «Треугольники Паскаля, числа Каталана и массивы восстановления». Дискретная математика . 22 (3): 301–310. дои : 10.1016/0012-365X(78)90063-8 .
^ Он, Техас; Спруньоли, Р. (2009). «Характеристика последовательностей массивов Риордана». Дискретная математика . 309 (12): 3962–3974. дои : 10.1016/j.disc.2008.11.021 .

[Shapiro_et_al_19912-1] Jump up to: ^а ^б ^с ^д ^и Шапиро, Луи В .; Гету, Сейюм; Воан, Вэнь-Цзинь; Вудсон, Леон К. (ноябрь 1991 г.). «Группа Риордан». Дискретная прикладная математика . 34 (1–3): 229–239. дои : 10.1016/0166-218X(91)90088-E .

[2] «6-я Международная конференция по массивам Риордана и смежным темам» . 6-я Международная конференция по массивам Риордана и смежным темам .

[umbral-3] Роман, С. (1984). Умбральное исчисление . Нью-Йорк: Академическая пресса.

[renewal-4] Роджерс, генеральный директор (1978). «Треугольники Паскаля, числа Каталана и массивы восстановления». Дискретная математика . 22 (3): 301–310. дои : 10.1016/0012-365X(78)90063-8 .

[SeqChar-5] Он, Техас; Спруньоли, Р. (2009). «Характеристика последовательностей массивов Риордана». Дискретная математика . 309 (12): 3962–3974. дои : 10.1016/j.disc.2008.11.021 .

[1]

[2]

[3]

[4]

[5]