Równanie P-rekurencyjne

Dalsze informacje: funkcja holonomiczna

W matematyce równanie P-rekurencyjne jest liniowym równaniem sekwencji , w którym sekwencje współczynników można przedstawić jako wielomiany . Równania P-rekurencyjne to liniowe równania rekurencyjne (lub liniowe relacje rekurencyjne lub liniowe równania różnicowe) ze współczynnikami wielomianowymi. Równania te odgrywają ważną rolę w różnych dziedzinach matematyki, szczególnie w kombinatoryce . Ciągi będące rozwiązaniami tych równań nazywane są holonomicznymi , P-rekurencyjnymi lub D-skończonymi.

Od końca lat 80. opracowano pierwsze algorytmy do znajdowania rozwiązań tych równań. Siergiej A. Abramov, Marko Petkovšek i Mark van Hoeij opisali algorytmy znajdowania rozwiązań wielomianowych, wymiernych, hipergeometrycznych i d'Alembertowskich.

Definicja

Niech ${\textstyle \mathbb {K}}$ będzie polem charakterystycznym zero (na przykład ${\textstyle \mathbb {K} =\mathbb {Q}}$ ), ${\textstyle p_{k}(n)\in \mathbb {K} [n]}$ wielomiany dla ${\textstyle k=0,\dots ,r}$ , ${\ textstyle f \ in \ mathbb {K} ^ {\ mathbb {N}}}$ sekwencja i ${\ textstyle y \ in \ mathbb {K} ^ {\ mathbb {N}}}$ nieznana sekwencja . Równanie

$${\ Displaystyle \ suma _ {k = 0} ^ {r} p_ {k} (n) \, y (n + k) =f(n)}$$

nazywa się liniowym równaniem rekurencyjnym ze współczynnikami wielomianowymi (wszystkie równania rekurencyjne w tym artykule mają tę postać). Jeśli ${\ textstyle p_ {0}}$ i ${\ textstyle p_ {r}}$ są niezerowe, to ${\ textstyle r}$ nazywamy rzędem równania. Jeśli $zero,$ równanie nazywamy jednorodnym, w przeciwnym razie nazywamy je niejednorodnym.

Można to również zapisać jako ${\ textstyle Ly = f}$ gdzie ${\ textstyle L = \ suma _ {k = 0} ^ {r} p_ {k} N ^ {k}}$ jest liniowym operatorem powtarzania ze współczynnikami wielomianu, a ${\ textstyle N \, y (n) =$ operatorem przesunięcia, tj. $)$ .

Rozwiązania w formie zamkniętej

Niech ${\ textstyle \ suma _ {k = 0} ^ {r} p_ {k} (n) \, y (n + k ) = f (n)}$ lub równoważnie ${\ textstyle Ly = f}$ być równaniem rekurencyjnym ze współczynnikami wielomianowymi. Istnieje kilka algorytmów obliczających rozwiązania tego równania. Algorytmy te mogą obliczać rozwiązania wielomianowe, wymierne, hipergeometryczne i d'Alembertowskie. Rozwiązanie jednorodnego równania jest dane przez jądro liniowego operatora powtarzalności: ${\ textstyle \ ker L = \ {y \ in \ mathbb {K} ^ { \mathbb {N} }\,:\,Ly=0\}}$ . Jako podprzestrzeń przestrzeni sekwencji to jądro ma a podstawa . Niech ${\ textstyle \ {y ^ {(1)}, y ^ {(2)}, \ kropki, y ^ {(m)} \}}$ być podstawą ${\textstyle \ ker L}$ , to suma formalna ${\ textstyle c_ {1}y ^ {(1)} + \ kropki + c_ {m} y ^ {(m)}} dla$ dowolnych stałych ${\ textstyle c_ {1}, \dots ,c_{m}\in \mathbb {K} }$ nazywamy ogólnym rozwiązaniem problemu jednorodnego ${\textstyle Ly=0}$ . Jeśli ${\ textstyle {\ tylda {y}}}$ jest szczególnym rozwiązaniem ${\ textstyle Ly=f}$ , tj. ${\ textstyle L {\ tylda {y}} = f}$ , a następnie ${\ textstyle c_ {1} y ^ {(1)} + \ kropki +c_{m}y^{(m)}+{\tylda {y}}}$ jest również rozwiązaniem problemu niejednorodnego i nazywa się go ogólnym rozwiązaniem problemu niejednorodnego.

Rozwiązania wielomianowe

Główny artykuł: Wielomianowe rozwiązania równań P-rekurencyjnych

Pod koniec lat 80. Siergiej A. Abramow opisał algorytm, który znajduje ogólne wielomianowe rozwiązanie równania rekurencyjnego, tj. ${\ textstyle y (n) \ in \ mathbb {K} [n]}$ fa ${\ textstyle f (n) \ in \ mathbb {K} [n]$ . On (a kilka lat później Marko Petkovšek ) dał stopień związany z rozwiązaniami wielomianowymi. W ten sposób problem można po prostu rozwiązać, rozważając układ równań liniowych . W $. {n})_{n\w \mathbb {N}}})$ rozwiązać wydajniej, rozważając szeregów potęgowych równania określonej podstawie potęgowej ( .

Inne algorytmy znajdowania rozwiązań bardziej ogólnych (np. rozwiązania wymierne lub hipergeometryczne) również opierają się na algorytmach obliczających rozwiązania wielomianowe.

Racjonalne rozwiązania

Główny artykuł: algorytm Abramowa

W 1989 Siergiej A. Abramow wykazał, że ogólne racjonalne rozwiązanie, tj. ${\ textstyle y (n) \ in \ mathbb {K} (n)}$ , z wielomianem po prawej stronie ${\textstyle f (n) \ in \mathbb {K} [n]}$ , można znaleźć za pomocą pojęcia uniwersalnego mianownika. Uniwersalnym mianownikiem jest wielomian ${\ textstyle u}$ takie, że mianownik każdego racjonalnego rozwiązania dzieli się ${\ textstyle u}$ . Abramov pokazał, jak ten uniwersalny mianownik można obliczyć, używając tylko pierwszego i ostatniego wielomianu współczynnika ${\ textstyle p_ {0}}$ i ${\ textstyle p_ {r}}$ . Zastępując ten uniwersalny mianownik nieznanym mianownikiem $,$ można znaleźć, obliczając wszystkie wielomianowe rozwiązania przekształconego równania.

Rozwiązanie hipergeometryczne

Główny artykuł: algorytm Petkovška

Sekwencja nazywana jest ${\ textstyle y (n + 1) / y (n) \ w \ mathbb {K} (n)}$$,$$jeśli$ dwóch kolejnych wyrazów jest funkcją tj / . Dzieje się tak wtedy i tylko wtedy, gdy sekwencja jest rozwiązaniem równania rekurencyjnego pierwszego rzędu ze współczynnikami wielomianu. Zbiór ciągów hipergeometrycznych nie jest podprzestrzenią przestrzeni ciągów, ponieważ nie jest domknięty na dodawanie.

W 1992 roku Marko Petkovšek $podał$ algorytm umożliwiający uzyskanie ogólnego hipergeometrycznego rozwiązania równania rekurencyjnego, w którym prawa strona sumą ciągów hipergeometrycznych. Algorytm wykorzystuje postać normalną funkcji wymiernej Gospera-Petkovška. Przy tej konkretnej reprezentacji ponownie wystarczy rozważyć wielomianowe rozwiązania przekształconego równania.

Inne i bardziej efektywne podejście jest zasługą Marka van Hoeij. Rozważając pierwiastki pierwszego i ostatniego wielomianu współczynnikowego i $textstyle p_ {r}}$${\$ – zwanych osobliwościami – można krok po kroku zbudować rozwiązanie wykorzystując fakt, że sekwencja hipergeometryczna ${\ textstyle y (n)}$ ma reprezentację formy

$${\ Displaystyle y (n) = c \ ,r(n)\,z^{n}\,\Gamma (n-\xi _{1})^{e_{1}}\Gamma (n-\xi _{2})^{e_{2 }}\cdots \Gamma (n-\xi _{s})^{e_{s}}}$$

dla niektórych ${\ textstyle c \ in \ mathbb {K}, z \ w {\overline {\mathbb {K}}},s\in \mathbb {N}, r(n)\in {\overline {\mathbb {K}}}(n),\xi _{1}, \dots ,\xi _{s}\in {\overline {\mathbb {K}}}}$ z ${\ textstyle \ xi _ {i} - \ xi _ {j} \ notin \ mathbb {Z}}$ dla ${\ textstyle i \ neq j}$ i ${\ textstyle e_ {1}, \ kropki, e_ {s} \ w \ mathbb {Z}}$ . Tutaj ${\ textstyle \ Gamma (n)}$ oznacza funkcję Gamma i $K}}}}$ { algebraiczne zamknięcie pola ${\ textstyle \ mathbb {K}}$ . Wtedy $}$$}$ muszą być osobliwościami równania ( tj. ${\ textstyle p_ {r}}$ ). Ponadto można obliczyć granice wykładników mi $\ textstyle e_ {i}}$ . Dla ustalonych wartości ${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}} można zrobić$ ansatz, który daje kandydaci na ${\ textstyle z}$ . $za$ określonego $wykonać$ ansatz, aby uzyskać funkcję wymierną Abramova. Rozważając wszystkie możliwości otrzymuje się ogólne rozwiązanie równania rekurencyjnego.

Rozwiązania D'Alemberta

Sekwencja nazywana jest d'alembertowską, jeśli $y$$\ textstyle y = h_ {1} \ suma h_ {2} \ suma \ cdots \ suma h_ {$ dla niektórych ciągów hipergeometrycznych ${\ textstyle h_ {1}, \ kropki, h_ {k}}$ i ${\ textstyle y = \ suma x}$ oznacza, że ${\ textstyle \ Delta y = x}$ gdzie ${\ textstyle \ Delta}$ oznacza operator różnicy, tj. ${\ textstyle \ Delta y = Ny -y=y(n+1)-y(n)}$ . Dzieje się tak wtedy i tylko wtedy, gdy istnieją operatory rekurencji liniowej pierwszego rzędu ${\ textstyle L_ {1}, \ kropki, L_ {k}}$ z racjonalnymi współczynnikami takimi, że ${\ textstyle L_ {k} \ cdots L_ {1} y = 0}$ .

1994 Abramov i Petkovšek opisali algorytm, który oblicza ogólne d'Alembertowskie rozwiązanie równania rekurencyjnego. Algorytm ten oblicza rozwiązania hipergeometryczne i rekurencyjnie zmniejsza kolejność równania rekurencyjnego.

Przykłady

Podpisane macierze permutacji

Liczbę macierzy permutacji ze $znakiem o rozmiarze$ sekwencją y $\ textstyle y (n) \ in \ mathbb {Q} ^ {\$ . Macierz permutacji ze znakiem to macierz kwadratowa, która ma dokładnie jeden niezerowy wpis w każdym wierszu iw każdej kolumnie. Wpisy niezerowe mogą być ${\ textstyle \ pm 1}$ . Sekwencja jest określona przez liniowe równanie rekurencyjne ze współczynnikami wielomianowymi

$${\ Displaystyle y (n) = 4 (n-1) ^ {2} \, y (n- 2)+2\,y(n-1)}$$

i wartości początkowe ${\ textstyle y (0) = 1, y (1) = 2}$ . Stosując algorytm do znajdowania rozwiązań hipergeometrycznych można znaleźć ogólne rozwiązanie hipergeometryczne

$${\ Displaystyle y (n) = c \, 2 ^ {n} n!}$$

dla pewnej stałej ${\ textstyle c}$ . Biorąc również pod uwagę wartości początkowe, sekwencja ${\textstyle y(n)=2^{n}n!}$ opisuje liczbę macierzy permutacji ze znakiem.

Inwolucje

Liczba inwolucji $textstyle$ z elementami $n} jest określona$

$${\ Displaystyle y (n) = (n-1) \, y (n-2) + y (n-1).}$$

Stosując na przykład algorytm Petkovška można zobaczyć, że nie ma rozwiązania wielomianowego, wymiernego ani hipergeometrycznego dla tego równania rekurencyjnego.

Aplikacje

Funkcja jeśli $fa$$gdzie$ K ${\ textstyle \ mathbb {K} (n, k)}$ oznacza funkcje wymierne w ${\ textstyle n}$ i ${\ textstyle k}$ . Suma hipergeometryczna jest skończoną sumą postaci ${\ textstyle f (n) = \ suma _ {k} F (n, k)}$ gdzie ${\ textstyle F (n, k)}$ jest hipergeometryczny. Kreatywny algorytm teleskopowy Zeilbergera może przekształcić taką hipergeometryczną sumę w równanie rekurencyjne ze współczynnikami wielomianowymi. To równanie można następnie rozwiązać $zamkniętej$ aby uzyskać na przykład liniową kombinację rozwiązań hipergeometrycznych, która jest nazywana rozwiązaniem w postaci .