Бустрофедонның өзгеруі - Википедия - Boustrophedon transform

Жылы математика, бустрофедонды түрлендіру бұл картаны бейнелейтін процедура жүйелі басқасына. Трансформацияланған дәйектілік «толтыру» операциясымен есептеледі, ол a-ны толтырғандай орындалады үшбұрышты жиым ішінде бустрофедон (зигзаг - немесе серпентин тәрізді) тәсіл - а «Растрлық сканерлеу» ара тісі тәрізді.

Анықтама

The бустрофедонды түрлендіру - санымен анықталатын, тізбекті тудыратын түрлендіру «қосу» жұмыс.

1-сурет. Бустрофедонды түрлендіру: Бастапқы тізбектен бастаңыз (көк түсте), содан кейін көрсеткілермен көрсетілген сандарды қосыңыз, ал екінші жағында трансформацияланған ретті оқыңыз (қызылмен,

{ displaystyle b_ {0} = a_ {0}}

).

Жалпы, бірізділік берілген: ${ displaystyle (a_ {0}, a_ {1}, a_ {2}, ldots)}$ , Бустрофедонды түрлендіру тағы бір дәйектілікті береді: ${ displaystyle (b_ {0}, b_ {1}, b_ {2}, ldots)}$ , қайда ${ displaystyle b_ {0}}$ баламасы анықталған болуы мүмкін ${ displaystyle a_ {0}}$ . Трансформацияның барлығын үшбұрышты толтыру арқылы салынған етіп бейнелеуге (немесе елестетуге) болады. 1-сурет.

Бустрофедон үшбұрышы

Санды толтыру үшін Үшбұрыш (1-сурет), сіз кіріс кезегінен бастайсыз, ${ displaystyle (a_ {0}, a_ {1}, a_ {2}, ldots)}$ және бустрофедонды сканерлеу көмегімен бір жолға бір мәнді (енгізу кезегінен) орналастырыңыз (зигзаг - немесе серпантин сияқты) тәсіл.

Үшбұрыштың жоғарғы шыңы кіріс мәні болады ${ displaystyle a_ {0}}$ , шығыс мәніне балама ${ displaystyle b_ {0}}$ , және біз осы жоғарғы қатарды 0 қатарымен санаймыз.

Келесі жолдар (үшбұрыштың табанына дейін төмендейді) біртіндеп (0-ден) бүтін сандар ретінде нөмірленеді - болсын ${ displaystyle k}$ қазіргі уақытта толтырылған жолдың нөмірін белгілеңіз. Бұл жолдар жол нөміріне сәйкес тұрғызылған ( ${ displaystyle k}$ ) келесідей:

Барлық жолдар үшін нөмірленген ${ displaystyle k in mathbb {N}}$ , дәл болады ${ displaystyle (k + 1)}$ жолдағы мәндер.
Егер ${ displaystyle k}$ $к$ тақ болса, мәнін қойыңыз ${ displaystyle a_ {k}}$ $а_ {к}$ жолдың оң жағында
- Осы жолдың ішін оңнан солға толтырыңыз, мұнда әр мән (индекс: ${ displaystyle (k, j)}$ ) оңға мән арасындағы «қосу» нәтижесі (индекс: ${ displaystyle (k, j + 1)}$ ) және жоғарғы оң жақтағы мән (индекс: ${ displaystyle (k-1, j + 1)}$ ).
- Шығу мәні ${ displaystyle b_ {k}}$ тақ жолдың сол жағында болады (қайда ${ displaystyle k}$ болып табылады тақ ).
Егер ${ displaystyle k}$ $к$ тең, содан кейін кіріс мәнін қойыңыз ${ displaystyle a_ {k}}$ $а_ {к}$ қатардың сол жағында.
- Осы жолдың ішін солдан оңға қарай толтырыңыз, мұнда әр мән (индекс: ${ displaystyle (k, j)}$ ) мәні оның сол жағындағы «қосу» нәтижесі болып табылады (индекс: ${ displaystyle (k, j-1)}$ ) және оның жоғарғы сол жағындағы мән (индекс: ${ displaystyle (k-1, j-1)}$ ).
- Шығу мәні ${ displaystyle b_ {k}}$ жұп қатардың оң жағында болады (қайда ${ displaystyle k}$ болып табылады тіпті ).

Ішіндегі көрсеткілерді қараңыз 1-сурет осы «қосу» операцияларының визуалды көрінісі үшін.

Берілген, ақырлы кіріс тізбегі үшін: ${ displaystyle (a_ {0}, a_ {1}, ... a_ {N})}$ , of ${ displaystyle N}$ мәндер дәл болады ${ displaystyle N}$ үшбұрыштағы жолдар, ${ displaystyle k}$ аралықтағы бүтін сан: ${ displaystyle [0, N)}$ (эксклюзивті). Басқаша айтқанда, соңғы қатар ${ displaystyle k = N-1}$ .

Қайталану қатынасы

Неғұрлым формалды анықтамада а қайталану қатынасы. Сандарды анықтаңыз ${ displaystyle T_ {k, n}}$ (бірге к ≥ n ≥ 0) бойынша

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

{ displaystyle T_ {k, n} = T_ {k, n-1} + T_ {k-1, k-n}}

{ displaystyle { text {with}}}

{ displaystyle quad k, n in mathbb {N}}

{ displaystyle quad k geq n> 0}

.

Содан кейін түрлендірілген реттілік анықталады ${ displaystyle b_ {n} = T_ {n, n}}$ (үшін ${ displaystyle T_ {2,2}}$ және одан жоғары индекстер).

Осы анықтамаға сәйкес шектеулерден тыс мәндерге (жоғарыдағы қатынастардан) келесі анықтамаларға назар аударыңыз ${ displaystyle (k, n)}$ жұп:

${ displaystyle { begin {aligned} T_ {0,0} , { overset { Delta} {=}} & , a_ {0} , { overset { Delta} {=}} , b_ {0} T_ {k, 0} , { overset { Delta} {=}} & , a_ {k} , iff k , { text {жұп}} T_ {k, 0} , { overset { Delta} {=}} & , b_ {k} , iff k , { text {тақ}}} T_ {0, k} , { overset { Delta} {=}} & , b_ {k} , iff k , { text {жұп}} T_ {0, k} , { overset { Delta} {=}} & , a_ {k} , iff k , { text {тақ}}} соңы {тураланған}}}$

Арнайы істер

Жағдайда а₀ = 1, а_n = 0 (n > 0), алынған үшбұрыш деп аталады Зайдель – Entringer – Арнольд үшбұрышы^[1] және сандар ${ displaystyle T_ {k, n}}$ деп аталады Автордың нөмірлері (жүйелі A008281 ішінде OEIS ).

Бұл жағдайда түрлендірілген реттіліктегі сандар б_n Эйлердің жоғары / төмен сандары деп аталады.^[2] Бұл бірізділік A000111 үстінде Он-лайн тізбегінің энциклопедиясы. Олардың саны ауыспалы ауыстырулар қосулы n әріптерімен байланысты Эйлер сандары және Бернулли сандары.

Алгебралық анықтама

Геометриялық жобасынан құрылыс бустрофедонды түрлендіру, кіріс мәндерінен тәуелділіктің алгебралық анықтамалары ( ${ displaystyle a_ {i}}$ ) мәндерді шығару үшін ( ${ displaystyle b_ {i}}$ ) әр түрлі үшін анықталуы мүмкін алгебралар («сандық домендер»).

Евклидтік (нақты) мәндер

Евклидте ( ${ displaystyle mathbb {E} ^ {n}}$ Алгебра нақты үшін ( ${ displaystyle mathbb {R} ^ {1}}$ ) бағаланған скалярлар, бустрофедон түрлендірілген Нақты -мән $(б n)$ кіріс мәнімен байланысты, $(а n)$ , сияқты:

${ displaystyle { begin {aligned} b_ {n} & = sum _ {k = 0} ^ {n} { binom {n} {k}} a_ {k} E_ {nk} end { тураланған}}}$ ,

кері қатынаспен (шығудан кіріс) келесідей анықталады:

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

қайда $(E n)$ «жоғары / төмен» сандар тізбегі болып табылады - және де белгілі секант немесе тангенс сандар.^[3]

Экспоненциалды генерациялау функциясы

The экспоненциалды генерациялау функциясы реттілік (а_n) арқылы анықталады

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

Бустрофедон түрлендіруінің экспоненциалды генерациялау функциясы (б_n) бастапқы дәйектілікпен байланысты (а_n) арқылы

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

Бірлік реттілігінің экспоненциалды генерациялау функциясы 1-ге тең, сондықтан жоғары / төмен сандардың секх + күңгіртх.

Әдебиеттер тізімі

^ Вайсштейн, Эрик В. «Зайдель-Антрингер-Арнольд үшбұрышы». Қайдан MathWorld - Wolfram веб-ресурсы. http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html
^ Вайсштейн, Эрик В. «Эйлерия нөмірі». Қайдан MathWorld - Wolfram веб-ресурсы. http://mathworld.wolfram.com/EulerianNumber.html
^ Вайсштейн, Эрик В. «Бустрофедонның өзгеруі». Қайдан MathWorld - Wolfram веб-ресурсы. http://mathworld.wolfram.com/BoustrophedonTransform.html

Миллар, Джессика; Слоан, Н.Ж.А .; Young, Neal E. (1996). «Тізбектегі жаңа операция: Буструфедон трансформасы». Комбинаторлық теория журналы А. 76 (1): 44–54. arXiv:математика.CO/0205218. дои:10.1006 / jcta.1996.0087.
Вайсштейн, Эрик В. (2002). CRC Математиканың қысқаша энциклопедиясы, екінші басылым. Чэпмен және Холл / CRC. б. 273. ISBN 1-58488-347-2.

[1] Вайсштейн, Эрик В. «Зайдель-Антрингер-Арнольд үшбұрышы». Қайдан MathWorld - Wolfram веб-ресурсы. http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html

[2] Вайсштейн, Эрик В. «Эйлерия нөмірі». Қайдан MathWorld - Wolfram веб-ресурсы. http://mathworld.wolfram.com/EulerianNumber.html

[3] Вайсштейн, Эрик В. «Бустрофедонның өзгеруі». Қайдан MathWorld - Wolfram веб-ресурсы. http://mathworld.wolfram.com/BoustrophedonTransform.html

[1]

[2]

[3]