Transformacja bustrofedonowa

W matematyce transformata bustrofedona jest procedurą, która odwzorowuje jedną sekwencję na drugą. Przekształcona sekwencja jest obliczana za pomocą operacji „dodawania”, realizowanej tak, jakby wypełniała trójkątną tablicę w sposób bustrofedonowy ( zygzakowaty lub serpentynowy) - w przeciwieństwie do piłokształtnego „skanowania rastrowego” .

Definicja

Transformacja bustrofedonowa jest cyfrową transformacją generującą sekwencję, która jest określana przez operację „dodawania” .

Rysunek 1. Transformacja bustrofedonu: zacznij od oryginalnej sekwencji (na niebiesko), następnie dodaj liczby zgodnie ze strzałkami, a na końcu odczytaj przekształconą sekwencję po drugiej stronie (na czerwono, gdzie ${\ displaystyle b_ {0}=a_{0}}$ ).

Ogólnie rzecz biorąc, biorąc pod uwagę sekwencję: ${\ Displaystyle (a_ {0}, a_ {1}, a_ {2}, \ ldots)}$ , ​​transformacja bustrofedonu daje inną sekwencję: ${\ Displaystyle (b_ {0}, b_ {1}, b_ {2}, \ ldots)}$ , ​​gdzie ${\ Displaystyle b_ {0}}$ jest prawdopodobnie zdefiniowany jako odpowiednik ${\ displaystyle a_ {0}}$ . Całość samej transformacji można zwizualizować (lub wyobrazić sobie) jako skonstruowaną przez wypełnienie trójkąta, jak pokazano na rysunku 1 .

Trójkąt Boustrofedonski

Aby wypełnić liczbowy trójkąt równoramienny ( ryc. 1 ), zaczynasz od sekwencji wejściowej ${\ Displaystyle (a_ {0}, a_ {1}, a_ {2}, \ldots )}$ i umieść jedną wartość (z sekwencji wejściowej) w każdym wierszu, używając metody skanowania bustrofedonem ( podobnego do zygzaka lub serpentyny ).

Górny wierzchołek trójkąta będzie wartością wejściową, ${$ wartości wyjściowej $\ displaystyle a_ {0} }$ a ten górny wiersz numerujemy jako wiersz 0. za

Kolejne wiersze (schodzące do podstawy trójkąta) są numerowane kolejno (od 0) jako liczby całkowite - niech $oznaczają$ aktualnie wypełnianego wiersza. Wiersze te są konstruowane zgodnie z numerem wiersza ( ${\ displaystyle k}$ ) w następujący sposób:

• $wartości$ wierszy będą dokładnie ${\ Displaystyle (k + 1)}$ rzędzie.
• Jeśli $.$$nieparzysta$ , umieść wartość prawym końcu
  • Wypełnij wnętrze tego wiersza od prawej do lewej, gdzie każda wartość ( indeks: ${\ Displaystyle (k, j)}$ ) jest wynikiem „dodania” między wartością po prawej (indeks: : ${\ Displaystyle (k, j + 1)}$ ) i wartość w prawym górnym rogu (indeks: ${\ Displaystyle (k-1, j + 1) )}$ ).
  • Wartość wyjściowa $nieparzysta$ na lewym końcu nieparzystego rzędu (gdzie k $displaystyle k}$ jest ).
• Jeśli $.$$parzysta$ , umieść wartość wejściową lewym końcu
  • Wypełnij wnętrze tego wiersza od lewej do prawej, gdzie każda wartość (indeks: ${\ Displaystyle (k, j)}$ ) jest wynikiem „dodania” między wartością po lewej stronie ( indeks: ${\ Displaystyle (k, j-1)}$ ) i wartość w lewym górnym rogu (indeks: ${\ Displaystyle (k-1, j- 1)}$ ).
  • Wartość wyjściowa $jest$ znajdować $się$ na prawym końcu parzystego rzędu ( ) .

Patrz strzałki na rysunku 1, aby uzyskać wizualną reprezentację tych operacji „dodawania”.

Dla danej, skończonej sekwencji wejściowej: $Displaystyle (a_ {0}, a_ {1}, ... a_ {N})}$ , ${\ Displaystyle N}$$wartości ,$ w trójkącie będzie dokładnie rzędów $}$ liczbą całkowitą z zakresu: ) $\ displaystyle k$ . Innymi słowy, ostatni wiersz to ${\ Displaystyle k = N-1}$ .

Relacja powtarzalności

Bardziej formalna definicja używa relacji rekurencyjnej . Zdefiniuj liczby (z k ≥ n ≥ 0) przez ${\ Displaystyle T_ {k, n}}$

${\ Displaystyle T_ {k, 0} = a_ {k}}$

${\ Displaystyle T_ {k, n} = T_ {k, n-1} + T_ {k-1, kn}}$

${\ Displaystyle {\ tekst {z}}}$

${\ Displaystyle \ quad k, n \ w \ mathbb {N } }$

${\ Displaystyle \ quad k \ geq n> 0}$ .

$_$ przekształcona $_$ ( _

Zgodnie z tą definicją zwróć uwagę na następujące definicje wartości poza ograniczeniami (z powyższej relacji) dla par ${\ displaystyle (k, n)} :$

${\ Displaystyle {\ rozpocząć {wyrównane} T_ {0,0} \, {\ overset {\ Delta} {=}} & \, a_ {0} \, {\ overset {\ Delta}} {=}} \,b_{0}\\\\T_{k,0}\,{\overset {\Delta }{=}}&\,a_{k}\,\iff k\,{\text{jest parzysta} }\\T_{k,0}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\tekst{jest nieparzysty}}\\\\T_{ 0,k}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\text{jest parzysta}}\\T_{0,k}\,{ \overset {\Delta }{=}}&\,a_{k}\,\iff k\,{\text{jest nieparzysty}}\\\end{wyrównany}}}$

Przypadki specjalne

₀ W przypadku a = 1, a _n = 0 ( n > 0), powstały trójkąt nazywany jest trójkątem Seidela – Entringera – Arnolda , a liczby nazywane są liczbami Entringera ${\ displaystyle T_ {k, n}}$ (sekwencja A008281 w OEIS ).

W tym przypadku liczby w przekształconym ciągu b _n nazywane są liczbami Eulera góra/dół. To jest sekwencja A000111 w On-Line Encyclopedia of Integer Sequences . Wyliczają one liczbę naprzemiennych permutacji na n literach i są powiązane z liczbami Eulera i liczbami Bernoulliego .

Definicje algebraiczne

$a$$)$ relacji między wartościami wejściowymi ( ) wartościami wyjściowymi ( można zdefiniować dla algebry („dziedziny liczbowe”).

Wartości euklidesowe (rzeczywiste).

$W$ euklidesowej ( $algebrze$ rzeczywistej ( ) o boustrofedon wartość rzeczywistą ( b _n ) odnosi się do wartości wejściowej ( a _n ) jako:

${\ Displaystyle {\ rozpocząć {wyrównane} b_ {n} & = \ suma _ {k = 0} ^ {n} {\ binom {n} {k}}a_{k}E_{nk}\\\end{wyrównane}}}$ ,

z odwrotną zależnością (wejście od wyjścia) zdefiniowaną jako:

${\ Displaystyle {\ rozpocząć {wyrównane} a_ {n} & = \ suma _ {k = 0} ^ {n }(-1)^{nk}{\binom {n}{k}}b_{k}E_{nk}\end{wyrównane}}}$ ,

gdzie ( E _n ) jest sekwencją liczb „góra/dół” — znanych również jako liczby sieczne lub styczne .

Wykładnicza funkcja generująca

Wykładnicza funkcja generująca ciągu ( a _n ) jest zdefiniowana przez

${\ Displaystyle EG (a_ {n}; x) = \ suma _ {n = 0} ^ {\ infty} a_ {n} {\ Frac {x ^ {n}} {n!}}.}$

Wykładnicza funkcja generująca transformaty bustrofedonu ( b _n ) jest powiązana z funkcją pierwotnej sekwencji ( a _n ) przez

${\ Displaystyle EG (b_ {n}; x) = (\ sec x + \ tan x) \, EG (a_ {n}; x).}$

Wykładnicza funkcja generująca ciągu jednostek wynosi 1, więc liczba w górę/w dół to sec x + tan x .

•   Millar, Jessica; Sloane, NJA; Młody, Neal E. (1996). „Nowa operacja na sekwencjach: transformacja Boustrouphedon”. Dziennik teorii kombinatorycznej, seria A. 76 (1): 44–54. arXiv : math.CO/0205218 . doi : 10.1006/jcta.1996.0087 . S2CID 15637402 .
•   Weisstein, Eric W. (2002). CRC Zwięzła encyklopedia matematyki, wydanie drugie . Chapman & Hall/CRC. P. 273. ISBN 1-58488-347-2 .