Boustrophedon transformation

Inom matematik är boustrophedontransformen en procedur som kartlägger en sekvens till en annan . Den transformerade sekvensen beräknas av en "additions"-operation, implementerad som om den skulle fylla en triangulär array på ett boustrophedon ( sickzag - eller serpentinliknande) sätt - i motsats till ett "Raster Scan" sågtandsliknande sätt.

Definition

Boustrophedon-transformationen är en numerisk, sekvensgenererande transformation, som bestäms av en " additions" -operation.

Figur 1. Boustrophedon-transformen: Börja med den ursprungliga sekvensen (i blått), lägg sedan till siffror enligt pilarna och läs slutligen av den transformerade sekvensen på andra sidan (i rött, med b = a $b_ {0}=a_{0}}$ ).

Generellt sett, givet en sekvens: $(a_{0},a_{1},a_{2},\ldots )$ , ger boustrophedontransformen en annan sekvens: $(b_{0},b_{1},b_{2},\ldots )$ , där $b_{0}$ troligen definieras som ekvivalent med $a_{0}$ . Hela transformationen i sig kan visualiseras (eller föreställas) som konstruerad genom att fylla ut triangeln som visas i figur 1 .

Boustrophedon triangel

För att fylla i den numeriska likbenta triangeln ( Figur 1 ), börjar du med inmatningssekvensen, $(a_{0},a_{1},a_{2}, \ldots )$ , och placera ett värde (från inmatningssekvensen) per rad, med hjälp av boustrophedon scan ( zigzag - eller serpentin -liknande) tillvägagångssätt.

Triangelns övre hörn kommer att vara ingångsvärdet $a_{0}$ , motsvarande utdatavärdet $b_{0}$ , och vi numrerar denna översta rad som rad 0.

De efterföljande raderna (som går ner till basen av triangeln) numreras i följd (från 0) som heltal – låt $k$ beteckna numret på raden som för närvarande fylls. Dessa rader är konstruerade enligt radnumret ( $k$ ) enligt följande:

• För alla rader, numrerade $k\in \mathbb {N}$ , kommer det att finnas exakt $(k+1)$ värden i raden.
• Om $k$ är udda, sätt sedan värdet $a_{k}$ på den högra änden av raden.
  • Fyll i det inre av denna rad från höger till vänster, där varje värde (index: $(k,j)$ ) är resultatet av "addition" mellan värdet till höger (index : $(k,j+1)$ ) och värdet uppe till höger (index: $(k-1,j+1 )$ ).
  • Utgångsvärdet $b_{k}$ kommer att vara på den vänstra änden av en udda rad (där $k$ är udda ).
• Om $k$ är jämnt, sätt sedan inmatningsvärdet $a_{k}$ på radens vänstra ände.
  • Fyll i det inre av denna rad från vänster till höger, där varje värde (index: $(k,j)$ ) är resultatet av "addition" mellan värdet till vänster ( index: $(k,j-1)$ ) och värdet längst upp till vänster (index: $(k-1,j- 1)$ ).
  • Utdatavärdet $b_{k}$ kommer att vara på den högra änden av en jämn rad (där $k$ är jämn ).

Se pilarna i figur 1 för en visuell representation av dessa "tilläggs"-operationer.

För en given, ändlig ingångssekvens: $(a_{0},a_{1},...a_{N})$ , av $N$ värden, kommer det att finnas exakt $N$$[0,N)$ i triangeln, så att $k$ är ett heltal i intervallet: (exklusivt) . Den sista raden är med andra ord $k=N-1$ .

Återkommande förhållande

En mer formell definition använder en återfallsrelation . Definiera talen $T_{k,n}$ (med k ≥ n ≥ 0) med

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

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

${\text{med }}$

$\quad k,n\in \mathbb {N }$

$\quad k\geq n>0$ .

Sedan definieras den transformerade sekvensen av $b_{n}=T_{n,n}$ (för $T_{2,2}$ och större index).

Enligt denna definition, notera följande definitioner för värden utanför begränsningarna (från förhållandet ovan) på $(k,n)$ par:

${\begin{aligned}T_{0,0}\,{\overset {\Delta }{=}}&\,a_{0}\,{\overset {\Delta }{=}} \,b_{0}\\\\T_{k,0}\,{\overset {\Delta }{=}}&\,a_{k}\,\iff k\,{\text{är jämnt} }\\T_{k,0}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\text{är udda}}\\\\T_{ 0,k}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\text{är jämnt}}\\T_{0,k}\,{ \overset {\Delta }{=}}&\,a_{k}\,\iff k\,{\text{är udda}}\\\end{aligned}}$

Speciella fall

₀ I fallet a = 1, a _n = 0 ( n > 0), kallas den resulterande triangeln $T_{k,n}$ –Entringer–Arnold-triangeln och talen kallas Entringer-tal (sekvens A008281 i OEIS ).

kallas talen i den transformerade sekvensen b _{n Euler upp/ned-tal.} Detta är sekvens A000111 på On-Line Encyclopedia of Integer Sequences . Dessa räknar upp antalet alternerande permutationer på n bokstäver och är relaterade till Euler-talen och Bernoulli-talen .

Algebraisk definition(er)

Med utgångspunkt från den geometriska designen av boustrophedon-transformen kan algebraiska definitioner av sambandet från ingångsvärden ( $a_{i}$ ) till utdatavärden ( ${\displaystyle b_{i}})$ definieras för olika algebras ("numeriska domäner").

Euklidiska (verkliga) värden

I den euklidiska ( $\mathbb {E} ^{n}$ ) algebra för Real ( $\mathbb {R} ^{1}$ )-värderade skalärer, transformerade boustrophedonen Real -value ( b _n ) är relaterat till ingångsvärdet, ( a _n ) , som:

${\begin{aligned}b_{n}&=\summa _{k=0}^{n}{\binom {n} {k}}a_{k}E_{nk}\\\end{aligned}}$ ,

med det omvända förhållandet (ingång från utgång) definierat som:

${\begin{aligned}a_{n}&=\summa _{k=0}^{n }(-1)^{nk}{\binom {n}{k}}b_{k}E_{nk}\end{aligned}}$ ,

där ( E _n ) är sekvensen av "upp/ner"-tal – även känd som sekant- eller tangenttal .

Den exponentiella genererande funktionen

Den exponentiellt genererande funktionen för en sekvens ( a _n ) definieras av

$EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.$

Den exponentiellt genererande funktionen för boustrophedontransformen ( b _n ) är relaterad till den för den ursprungliga sekvensen ( a _{n )} av

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

Den exponentiella genererande funktionen för enhetssekvensen är 1, så att upp/ned-talen är sek x + tan x .

•   Millar, Jessica; Sloane, NJA; Young, Neal E. (1996). "En ny operation på sekvenser: Boustrouphedon-transformen". Journal of Combinatorial Theory, serie A . 76 (1): 44–54. arXiv : math.CO/0205218 . doi : 10.1006/jcta.1996.0087 . S2CID 15637402 .
•   Weisstein, Eric W. (2002). CRC Concise Encyclopedia of Mathematics, andra upplagan . Chapman & Hall/CRC. sid. 273. ISBN 1-58488-347-2 .