부스트로페돈 변환

수학에서, 부스트로피돈 변환은 한 시퀀스를 다른 시퀀스에 매핑하는 과정이다. 변환된 시퀀스는 "래스터 스캔" 톱톱과 같은 방식과는 반대로, 마치 삼각 배열을 보스트로페돈(지그재그 또는 뱀처럼) 방식으로 채우는 것처럼 구현되는 "추가" 연산에 의해 계산된다.

정의

부스트롭헤돈 변환은 "추가" 연산에 의해 결정되는 수리적, 시퀀스 생성 변환이다.

Generally speaking, given a sequence: ${\displaystyle (a_{0},a_{1},a_{2},\ldots )}$, the boustrophedon transform yields another sequence: ${\displaystyle (b_{0},b_{1},b_{2},\ldots )}$, where ${\displaystyle b_{0}}$ is likely defined equivalent to ${\displaystyle {}_{}}$${\$ 전체 변환 자체는 그림 1과 같이 삼각형을 채움으로써 구성되는 것으로 시각화(또는 상상)할 수 있다.

보스트로페돈 삼각형

숫자 Isosceles 삼각형(${\displaystyle {}_{}}$ 1)을 채우려면 입력 시퀀스$({\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$a 1, a ${\displaystyle {2\mathrm{}}_{}}$, …${\displaystyle }$)로 시작하고$,$ 보스트로페돈 스캔(지그재그 또는 서펜타인 유사) 접근법을 사용하여 입력 $시퀀스(a_{0},a_{1},a_{2},\ldots$)를 한 줄에 한 값(입력 시퀀스로부터)을 배치하십시오.

삼각형의 위쪽 꼭지점은 ${\displaystyle {입력\mathrm{}}_{}}$ 값 $0{\displaystyle {}_{}}$ ${\$ 출력 값 ${\displaystyle {b\mathrm{}}_{}}$ $0{\displaystyle {}_{}}$ ${\$과 같으며$,$ 이 위쪽 행에 행 0으로 번호를 매긴다.

후속 행(삼각형의 밑부분까지 내려감)은 연속적으로 (0부터) 정수로 번호가 매겨진다. $k{\displaystyle }$ ${\displaystyle k}$은 현재 채워지고 있는 행의 수를 나타낸다$$. 이러한 행은 다음과 같이 행 번호(${\displaystyle }$ ${\displaystyle k}$)에 따라 생성된다.

• 번호가 매겨진 $모든{\displaystyle }$ 행에 대해 ${\displaystyle k\mathbb{}}$N$${\$displaystyle k\in \mathb {N}$ $\},$ 행에 ${\displaystyle \mathrm{정확히}}{\displaystyle }$( k${\displaystyle }$+ ${\displaystyle 1}$) ${\displaystyle (k+1)$값이$$ 있을 것이다.
• $k{\displaystyle }$ ${\displaystyle k}$이(가) 홀수인 경우 ${\displaystyle k_{}}$ ${\$ 값을 행의 오른쪽 끝에$$ 놓으십시오.
  • Fill-out the interior of this row from right-to-left, where each value (index: ${\displaystyle (k,j)}$) is the result of "addition" between the value to right (index: ${\displaystyle (k,j+1)}$) and the value to the upper right (index: ${\displaystyle (k-1,j+1)}$).
  • 출력$$ 값 $b{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$는 홀수 행의 왼쪽 끝에 위치한다($여기$서 k ${\displaystyle k}$은(는) 홀수).
• $k{\displaystyle }$ ${\displaystyle k}$이(가) 짝수인 경우 ${\displaystyle {입력}_{}}$ 값을 $k{\displaystyle {}_{}}$ ${\$ 행의 왼쪽 끝에$$ 놓으십시오.
  • Fill-out the interior of this row from left-to-right, where each value (index: ${\displaystyle (k,j)}$) is the result of "addition" between the value to its left (index: ${\displaystyle (k,j-1)}$) and the value to its upper left (index: ${\displaystyle (k-1,j-1)}$).
  • 출력$$ 값 $b{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$는 짝수 행의 오른쪽 끝에 위치한다($k{\displaystyle }$ ${\displaystyle k}$은 짝수).

이러한 "추가" 작업의 시각적 표현은 그림 1의 화살표를 참조하십시오.

주어진 한정된 입력 시퀀스의 경우:${\displaystyle }$( ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$.${\displaystyle }$. ${\displaystyle N_{}}$) ${\displaystyle (a_{0},a_{1},...$$n{\displaystyle }$ ${\displaystyle N}$ 값$$ 중 $a_{N}$은$($는) 삼각형 내에 $정확히{\displaystyle }$$$N$${\$displaystyle$k}이(가$){\displaystyle }$ [${\displaystyle 0}$, ${\displaystyle N}$)$${\$displaystyle [0,N)}($전용) 범위의 정수인 경우처럼$$ N {\$displaystystyle N}$ 행이$$ 있을 것이다. 즉, 마지막 행은 $k{\displaystyle }$= ${\displaystyle N}$- ${\displaystyle 1}$ ${\displaystyle k=N-1}$이다$.$

재발관계

보다 공식적인 정의는 재발 관계를 사용한다. 숫자 $T{\displaystyle {}_{}}$ ${\displaystyle k_{}}$, ${\displaystyle n_{}}$ ${\$을($$를) 정의하십시오(k with n with 0).

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

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

${\displaystyle {\text{}}}$

$\displaystyle \quad k,n\in \mathb {N} }$

> ${\displaystyle \quad k\geq$ n$>0$

변환된 시퀀스는 $b{\displaystyle {}_{}}$ ${\displaystyle n_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$, ${\displaystyle n_{}}$ ${\$로 정의된다.$T_{n,n}}($$T{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle 2_{}}$ ${\$개 이상의$$ 지수)

이 정의에 따라${\displaystyle }$(${\displaystyle k}$, ${\displaystyle n}$) ${\displaystyle (k,n)}$ 쌍에$$ 대한 제한 밖의 값(위의 관계에서)에 대해 다음 정의를 기록해 두십시오.

${\displaystyle {\reasoned}T_{0,0}\,{\overset {\Delta }{=}{=}&\,a_{0}\,{\delta }}}{=}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}T_{k,0}\,{\overset {\Delta }{}}{=}&\,a_{k}\,\iff k\,{\textis even}\\\T_{k,0}\,{\overset {\Delta }{}}{=}}&\,b_{k}\,\iff k\,{\text is old}\\\\\T_{0,k}\,{\overset {\Delta }{}}{=}},b_{k}\,\iff k\,{\textis even}\\\T_{0,k}\,{\overset {\Delta }{}}{=}&\,a_{k}\,\iff k\,{\textis old}\\ended}}}}}$

특수 케이스

사례 a₀ = 1, a_n = 0(n > 0)에서 결과 삼각형을 세이델-엔트링거-아놀드 삼각형이라고^[1] 하고 숫자 $T{\displaystyle {}_{}}$ ${\displaystyle {k,}_{}}$ ${\displaystyle n_{}}$ ${\$을 엔트링거 번호(OEIS에서 순서 A008281)라고 한다$$.

이 경우 변환된 시퀀스 b의_n 숫자를 오일러 위/아래 숫자라고 한다.^[2] 이것은 온라인 정수 백과사전 A000111의 순서다. 이것들은 n글자에 대한 교번 순열의 수를 열거하고 있으며 오일러 번호와 베르누이 숫자와 관련이 있다.

대수적 정의

보스트로페돈 변환의 기하학적 설계로부터 빌딩, 입력 값(${\displaystyle i_{}}$ ${\$에서 출력 값(${\displaystyle b_{}}$ i ${\$까지의 관계에 대한 대수적 정의는 다른 알헤브라에 대해 정의할 수 있다("수적 도메인").

유클리드(실제) 값

유클리드(${\displaystyle {}^{}}$ {n ${\$에 대한 대수(${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$ ${\$^1}{$1})$ $$값 스칼라에서, 부스트로페돈 변환된 Real-값(b_n)은 다음과 같이 입력값(a_n)과 관련이 있다.

== n( k) - k ${\$n}$a_{k}e_{n-k}\end$

다음과 같이 정의된 역방향 관계(출력으로부터 분리):

= = n(- ) - k (n ) - k ${\$=0$}-1)^{n-k}{n-k}b}{k}$E_{$n-k-k}\{$n-k$}end$}}{n-k}}}}}{$n-end}{$n-end

여기서 (E_n)는 "위/아래" 번호의 순서로서, 이차 또는 접선 번호라고도 한다.^[3]

지수생성함수

시퀀스 (a_n)의 지수 생성 함수는 다음과 같이 정의된다.

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

Boustrophedon 변환 (b_n)의 지수 생성 함수는 다음과 같이 원래 시퀀스 (a_n)의 지수 생성 함수와 관련이 있다.

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

단위 시퀀스의 지수 생성 함수는 1이므로 위/아래 번호의 지수 생성 함수는 sec x + tan x이다.

참조

• Millar, Jessica; Sloane, N.J.A.; Young, Neal E. (1996). "A New Operation on Sequences: the Boustrouphedon Transform". Journal of Combinatorial Theory, Series A. 76 (1): 44–54. arXiv:math.CO/0205218. doi:10.1006/jcta.1996.0087.
• Weisstein, Eric W. (2002). CRC Concise Encyclopedia of Mathematics, Second Edition. Chapman & Hall/CRC. p. 273. ISBN 1-58488-347-2.