tablica Riordana

(Właściwa) tablica Riordana ${\ displaystyle h(t)}$ nieskończoną dolną trójkątną macierzą , zbudowaną z dwóch szeregów potęg , $)$${\ Displaystyle d (t)}$ rzędu 0 i rzędu 1, w taki sposób, że ${\ Displaystyle d_ {n, k} = [t ^ {n}] d (t) h (t) ^ {k}}$ .

Tablica Riordana jest elementem grupy Riordana. Został stworzony przez matematyka Louisa W. Shapiro i nazwany na cześć matematyka Johna Riordana .

Badanie tablic Riordana to rozwijająca się dziedzina, na którą wpływ mają inne dziedziny, takie jak kombinatoryka , teoria grup, teoria macierzy, teoria liczb, prawdopodobieństwo, ciągi i szeregi, grupy Liego i algebry Liego, grupy Liego i algebry Liego , wielomiany , teoria grafów , sieci , hipoteza Beala , hipoteza Riemanna , ciągi unimodalne , tożsamości kombinatoryczne , krzywe eliptyczne , aproksymacja numeryczna , asymptotyka i analiza danych. Tablice Riordana to także potężna koncepcja jednocząca, łącząca ważne narzędzia: funkcje generujące , systemy algebry komputerowej, języki formalne, model ścieżki i tak dalej.

Szczegóły poniżej.

Formalny szereg potęgowy $\ Displaystyle a (x) = a_ {0} + a_ {1}x+a_{2}x^{2}+\cdots =\suma _{j\geq 0}a_{j}x^{j}\in \mathbb {C} [[x]]}$ to mówi się $,$ że ma porządek jeśli ${\ Displaystyle a_ {0} =... = a_ {r-1} = 0 \ neq a_ {r}.}$ Napisz ${\ displaystyle {\ mathcal {F}} _ {r}}$ dla potęgi formalnej seria rzędów ${\ Displaystyle r.}$ Szereg potęgowy $\ Displaystyle a (x)$ 0 ma multiplikatywną odwrotność (tj. ${\ Displaystyle 1/a (x)} jest szeregiem potęgowym, jeśli ma rząd$ is a power series) iff it has order 0, i.e. iff it lies in ${\mathcal {F}}_{0}$; it has a composition inverse that is there exists a power series ${\bar {a}}$ such that ${\bar {a}}(a(x))=x$ iff it has order 1, i.e. iff it lies in ${\mathcal {F}}_{1}.$

Jak wspomniano, tablica Riordana jest zwykle definiowana jako para szeregów potęgowych ${\ Displaystyle (a (t), b (t)} \ in {\ mathcal {F}} _ {0} \ razy {\ mathcal {F}} _ {1}.} Część „tablica” w$ nazwie wynika z faktu, że kojarzy się z ${\ Displaystyle (a (t), b (t))}$ tablica liczb zespolonych zdefiniowana przez ${\ Displaystyle d_ {n, k}: = [t ^ {n}] a (t) b (t)^{k},}$$= \ mathbb {Z} _ {\ geq 0}.}$${\ Displaystyle [t ^ {n}] ...}$ Tutaj oznacza współczynnik ${\ displaystyle t ^ {n}}$ w ${\ displaystyle \ cdots}$ } . Tak więc kolumna $składa$ się po prostu z sekwencji współczynników szeregu potęgowego ${\ Displaystyle a (t) b (t) ^ {k};}$ w szczególności kolumna 0 określa i jest określona przez szereg potęgowy ${\ Displaystyle a (t).}$ Jako ${\ Displaystyle a (t)}$${\ Displaystyle b (t) = a (t) ^ {- 1} a (t) b (t).}$ t ) $)}$ Ponieważ ${\ Displaystyle b (t) = b_ {1} t + b_ {2} t ^ {2} + \ cdots}$ ma kolejność 1, ${\ Displaystyle b (t) ^ {k}}$ ma porządek $i$ ma ${\ Displaystyle a (t) b (t) ^ {k}.}$ Wynika z tego, że tablica ${\ Displaystyle d_ {n, k}}$ jest nieskończonym trójkątem wykazującym postęp geometryczny ${\ Displaystyle (d_ {k, k}) _ {k \ geq 0}=(a_{0}b_{1}^{k})_{k\geq 0}}$ na jego głównej przekątnej. Wynika z tego również, że mapa asocjacyjna z parą szeregów potęgowych ${\ Displaystyle (a (t), b (t)} \ in {\ mathcal {F}} _ {0} \ razy {\ mathcal {F}} _ {1}} jego trójkątna tablica jest iniekcyjna$ .

Przykładem tablicy Riordana jest para szeregów potęgowych ${\ Displaystyle ({\ Frac {1} {1-x}}, {\ Frac {x} {1-x}}) = (\ suma _ {j \ geq 0} x ^ {j}, \ suma _ {j\geq 0}x^{j+1})\w {\mathcal {F}}_{0}\times {\mathcal {F}}_{1}.}$ Nie jest trudno pokazać, że ta para generuje nieskończoną trójkątną tablicę współczynników dwumianowych, zwaną także macierzą Pascala ${\ Displaystyle d_ {n, k} = {n \ wybierz k}$

${\ Displaystyle P = \ lewo ({\ rozpocząć {tablica} {cccccc} 1&&&&&&\ cdots \\ 1&1&&&&&&\\1&2&1&&&&\\ 1&3&3&1&&&\\1&4&6&4&1&&\\&&&\cdots &&&\cdots \end{tablica}}\right)}$

Dowód. Jeśli ${\ Displaystyle q (x) = \ suma _ {j \ geq 0} q_ {j} x ^ {j}}$ to szereg potęgowy z powiązanym ciągiem współczynników ${\ Displaystyle (q_ {0}, q_ {1}, q_ {2}, ...),}$ mnożenie Cauchy'ego szeregów potęgowych, ${\ Displaystyle q (x) {\ Frac {x} {1-x}} = \ suma _ {j \ geq 0} (0 + q_ {0} + q_ {1} + \ cdots + q_ {j-1 })x^{j}.}$ Zatem ten drugi szereg ma jako ciąg współczynników ${\ Displaystyle (0, q_ {0}, q_ {0} + q_ {1}, q_ {0} + q_ {1} + q_ {2}, ....)}$ i stąd ${\ Displaystyle [t ^ {n}] q (x) {\ Frac {x} {1-x}} = q_ {0} + \ cdots + q_ {n-1}.} Napraw$ dowolne ${\ Displaystyle k \ w \ mathbb {Z} _ {\ geq 0}.}$ Jeśli ${\ Displaystyle q_ {n} = {n \ wybierz k},}$ tak, że ${\ Displaystyle (q_ {n}) _ {n \ geq 0}}$ reprezentuje kolumnę ${ \displaystyle k}$ tablicy Pascala, wtedy ${\ Displaystyle \ suma _ {j = 0} ^ {n-1} q_ {j} = \ suma _ {j = 0} ^ {n-1} j \ wybierz k} = {n \ wybierz k + 1 }.}$ Ten argument pozwala zobaczyć przez indukcję na ${\ displaystyle k}$ , że ${\ Displaystyle {\ Frac {1} {1-x}} ({\ Frac {x} {1-x}}) ^ {k}}$ ma kolumnę $Pascala$ jako sekwencję współczynników. ${\ Displaystyle \ Pudełko}$

Udowodnimy kilka często używanych faktów na temat tablic Riordana. Zauważ, że zasady mnożenia macierzy zastosowane do nieskończonych macierzy trójkątnych prowadzą tylko do skończonych sum, a iloczyn dwóch nieskończonych macierzy trójkątnych jest nieskończenie trójkątny. Następne dwa twierdzenia zostały odkryte zasadniczo przez Shapiro i współpracowników, którzy twierdzą, że zmodyfikowali pracę znalezioną w artykułach Gian-Carlo Roty i księdze Romana

Twierdzenie. A. Niech ${\ Displaystyle (a (x), b (x)}}$ i ${\ Displaystyle (c (x), d ( x))}$ będą tablicami Riordana, postrzeganymi jako nieskończone dolne macierze trójkątne. Wtedy iloczyn tych macierzy jest tablicą powiązaną z parą ${\ Displaystyle (a (x) c (b (x)), d (b (x)})}$ formalnego szeregu potęgowego, który sam jest tablicą Riordana.

B. Fakt $ten$ uzasadnia zdefiniowanie mnożenia Riordana postrzeganych jako pary szeregów potęgowych przez

${\ Displaystyle (a ( x),b(x))*(c(x),d(x))=(a(x)c(b(x)),d(b(x))}$

Dowód. Ponieważ $x), c (x)} mają rząd$ have order 0 it is clear that $a(x)c(b(x))$ has order 0. Similarly $b(x),d(x)\in {\mathcal {F}}_{1}$ implies ${\ Displaystyle d (b (x)} \ w {\ mathcal {F}} _ {1}.}$ Więc ${\ Displaystyle (a(x)c(b(x)),d(b(x)))}$ jest tablicą Riordana. Zdefiniuj macierz $tablicę$ Riordana ${\ Displaystyle (a (x), b (x)).}$ Z definicji jest to sekwencja współczynników potęgi ${\ Displaystyle j}$ -ta kolumna ${\ Displaystyle M_ {*, j}}$ seria ${\ Displaystyle a (x) b (x) ^ {j}.}$ Jeśli pomnożymy tę macierz od prawej strony przez sekwencję ${\ displaystyle (r_ {0}, r_ {1}, r_ {2},...) ^ {T}}$ otrzymujemy w rezultacie liniową kombinację kolumn ${\ displaystyle M}$ , którą możemy odczytywać jako liniową kombinację szeregów potęgowych, mianowicie ${\ Displaystyle \ suma _ {\ nu \ geq 0} r _ {\ nu} M_ {*, \ nu} = \ suma _ {\ nu \ geq 0} r_ {\ nu} a (x) b (x) ^ {\nu }=a(x)\sum _{\nu \geq 0}r_{\nu }b(x)^{\nu }.} Zatem oglądanie$ sekwencji ${\ Displaystyle (r_ {0}, r_ {1}, r_ {2},...) ^ {T}}$ skodyfikowane przez szereg ${\ Displaystyle r (x)}$ pokazaliśmy ${\ Displaystyle (a (x), b (x)} * r (x) = a (x) r (b (x)).}$ Tutaj ${\ Displaystyle *}$ jest symbolem wskazującym zgodność na poziomie szeregu potęg z mnożeniem macierzy. Pomnożyliśmy $_$ _ Niech teraz ${\ Displaystyle (c (x), d (x))}$ będzie kolejną tablicą Riordana widzianą jako macierz. Można utworzyć iloczyn $), b (x)} (c (x), d (x)).}$${\ Displaystyle j}$ J -ta kolumna tego iloczynu to po prostu ${\ Displaystyle (a (x), b (x)}}$ pomnożone przez -tą kolumnę ${\ Displaystyle j}$${\ Displaystyle (c (x), d (x)).}$ Ponieważ ten ostatni odpowiada szeregowi potęg ${\ Displaystyle c (x) d (x) ^ {j}, }$ wynika z powyższego, $-ta$ kolumna $\ Displaystyle (a (x), b (x)} (c (x), d (x))}$$c (b (x)) d (b (x)) ^ {j}.}$ odpowiada za Ponieważ dotyczy to wszystkich indeksów kolumn $x$ w ${\ Displaystyle (c (x), d (x)}}$ pokazaliśmy część a. Część b jest teraz jasna. ${\ Displaystyle \ Pudełko}$

Twierdzenie. Rodzina tablic Riordana obdarzona produktem $zdefiniowanym$ powyżej tworzy grupę: grupę Riordana

Dowód. Łączność mnożenia $.$ mnożenia macierzy Następna nuta ${\ Displaystyle (1, x) * (c (x), d (x)) = (1 \ cdot c (x), d (x)) = (c (x), d (x)).}$ Więc ${\ Displaystyle (1, x)}$ jest lewy element neutralny. Wreszcie twierdzimy, że ${\ Displaystyle (c ({\ bar {d}} (x)) ^ {- 1}, {\ bar {$ jest lewą odwrotnością szeregu potęgowego ${\ Displaystyle (c (x), d (x)).}$ W tym celu sprawdź obliczenie ${\ Displaystyle (c ({\ bar {d}} (x)) ^ {- 1}, {\ bar {d}} (x)} * (c (x), d (x))}$ $\ Displaystyle = ((c ({\ bar {d }}(x))^{-1}c(d(x)),d({\bar {d}}(x)))=(1,x).}$ Jak dobrze wiadomo, grupą jest struktura asocjacyjna, w której istnieje lewy neutralny element i dla każdego elementu lewa odwrotność. ${\ Displaystyle \ Pudełko}$

Oczywiście nie wszystkie odwracalne nieskończone dolne trójkątne tablice są tablicami Riordana. Oto użyteczna charakterystyka tablic, które są Riordana. Poniższy wynik wydaje się być spowodowany przez Rogersa

Twierdzenie. Nieskończona dolna $_$ sekwencja tradycyjnie nazywana $\$ , $neq 0, a_ {1}, ...) }$ takie, że

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

Dowód. $\ Rightarrow:}$$tablicą$ Niech będzie Riordana wynikającą z ${\ Displaystyle (d (t), h (t)).}$${\ Displaystyle d (t) \ w {\ mathcal {F}} _ {0},}$ re $d_{0,0}\neq 0.$ Since ${\ Displaystyle h (t)}$ ma rząd 1, wynika z tego, że ${\ Displaystyle (d (t) h (t) / t, h ( t)}}$ jest tablicą Riordana i według właściwości group istnieje tablica Riordana ${\ Displaystyle (A (t), B (t))}$ taka, że ${\ Displaystyle (d (t), h (t)} * (A (t), B (t)) = (d (t) h (t) / t, h (t)).} Obliczanie lewej$ ręki plony boczne ${\ Displaystyle (d (t) A (h (t)), B (h (t))}$ i tak porównanie daje ${\ Displaystyle B (h (t)) = h (t).}$ Oczywiście ${\ Displaystyle B (t) = t}$ jest rozwiązaniem tego równania; jest wyjątkowy ponieważ ${\ displaystyle B}$ jest odwracalną kompozycją. Więc możemy przepisać równanie jako ${\ Displaystyle (d (t), h (t)} * (A (t), t) = (d (t) h (t) / t, h (t)).}$

Teraz z prawa mnożenia macierzy, wpis po lewej stronie tego ostatniego równania to ${\ displaystyle n, k}$

${\ Displaystyle \ suma _ {j \ geq 0} d_ {n, j} (A (t), t) _ {j, k} = \ suma \ limity _ {j \ geq 0} d_ {n, j} [t^{j}]A(t)t^{k}=\sum \limits _{j\geq 0}d_{n,j}[t^{jk}]A(t)=\sum \limits _{j\geq 0}d_{n,j}a_{jk}=\sum \limits_{j\geq 0}a_{j}d_{n,k+j}.}$

Z drugiej strony rhs powyższego równania to ${\ displaystyle n, k}$

${\ Displaystyle 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},}$

tak, że wyniki. ∗ ${\ Displaystyle * _ {1}}$ otrzymujemy również $a_ {0} d_ {n n$${\ Displaystyle n \ geq 0} a$ ponieważ wiemy, że elementy ukośne są niezerowe, mamy $\ Displaystyle a_ {0} \ neq 0.}$ Zauważ, że używając równania ${\ Displaystyle * _ {1}}$ można obliczyć wszystkie wpisy znając wpisy ${\ Displaystyle (d_ {n, 0}) _ {n \ geq 0}.}$

${\ Displaystyle \ Leftarrow:} Teraz załóżmy$$,$ że znamy trójkątną tablicę równań sekwencji ${\ Displaystyle (a_ {j}) _ {j \ geq 0}.}$ Niech ${\ Displaystyle A (t)}$ będzie funkcją generującą tej sekwencji i zdefiniuj ${\ displaystyle h (t) )}$ z równania ${\ Displaystyle t A (h (t)) = h (t).}$ Sprawdź, czy możliwe jest rozwiązanie otrzymanych równań dla współczynników ${\ Displaystyle h;}$ i ponieważ $ma$ się, że ${\ Displaystyle h (t)}$ porządek 1. Niech re $Displaystyle d ( t)}$ będzie funkcją generującą ciągu ${\ Displaystyle (d_ {0,0}, d_ {1,0}, d_ {2,0},...).}$ Następnie dla pary ${\ Displaystyle ( ( d(t),h(t))}$ znajdujemy ${\ Displaystyle (d (t), h (t)} * (A (t), t) = (d (t) A (h (t)), h (t)) = (d (t) h ( t)/t,h(t)).}$ To są dokładnie te same równania, które znaleźliśmy w pierwszej części dowodu i przechodząc przez jego rozumowanie, znajdujemy równania takie jak w ${\ displaystyle * _ {1}$ } Ponieważ $,$ lub sekwencja jej współczynników) określa inne wpisy, stwierdzamy, że tablica, od której zaczęliśmy, jest tablicą Tak więc tablica w $tablicą$ Riordana ${\ Displaystyle \ Pudełko}$

Oczywiście $sama$ nie dostarcza wszystkich informacji o tablicy Riordana. Oprócz $-$ jest to $.$ , która okazała się zaskakująco użyteczna

Twierdzenie. Niech ${\ Displaystyle (d_ {n, k}) _ {n, k \ geq 0}}$ będzie nieskończoną dolną trójkątną tablicą, której przekątna sekwencja ${ \displaystyle (d_{n,n})_{n\geq 0}}$ nie zawiera zer. Wtedy istnieje unikalny ciąg ${\ Displaystyle Z = (z_ {0}, z_ {1}, z_ {2},...)}$ takie, że

${\ Displaystyle 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 ${\ displaystyle n = 0,1,2,3,...}$

Dowód. Dowód jest prosty: przez trójkątność tablicy, żądane równanie jest równoważne ${\ Displaystyle d_ {n + 1,0} = \ suma _ {j = 0} ^ {n} z_ {j} d_ {n, j}.} Dla n = , {\ Displaystyle$ n $n=0,$ this equation is $d_{1,0}=z_{0}d_{0,0}$ and, as ${\ Displaystyle d_ {0,0} \ neq 0,}$ pozwala na $unikalne$ . Ogólnie jeśli ${\ Displaystyle z_ {0}, z_ {1}, ..., z_ {n-1}}$ znane już wtedy ${\ Displaystyle d_ {n + 1,0} - \ suma _ {j = 0} ^ {n-1} z_ {j} d_ {n, j} = z_ {n} d_ { n, n}$$}$ obliczyć . ${\ Displaystyle \ Pudełko}$

Niedawno ukazała się książka, która powinna być cennym źródłem dalszych informacji.