ブストロフェドン変換

数学において、ブストロフェドン変換は、あるシーケンスを別のシーケンスにマッピングする手順です。変換されたシーケンスは、「ラスタースキャン」の鋸歯状方式ではなく、ブストロフェドン（ジグザグまたは蛇行状）方式で三角形配列を埋めるかのように実装された「加算」演算によって計算されます。

ブストロフェドン変換は、加算などのバイナリ演算によって決定される数値シーケンス生成変換です。

一般的に言えば、シーケンス が与えられた場合、ブストロフェドン変換により別のシーケンス が生成されます。ここで、 はと同等に定義されている可能性があります。変換自体の全体は、図 1に示すように三角形を埋めることによって構築されると視覚化 (または想像) できます。 ${\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 )}$

三角形の一番上の頂点は入力値 （出力値 に相当）となり、この一番上の行を行 0 として番号付けします。 ${\displaystyle a_{0}}$${\displaystyle b_{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})}$${\displaystyle N}$${\displaystyle N}$${\displaystyle k}$${\displaystyle [0,N)}$${\displaystyle k=N-1}$

より正式な定義では、再帰関係を使用します。k ≥ n ≥  0 の 数値を次のように 定義します。${\displaystyle T_{k,n}}$

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

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

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

${\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{is even}}\\T_{k,0}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\text{is odd}}\\\\T_{0,k}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\text{is even}}\\T_{0,k}\,{\overset {\Delta }{=}}&\,a_{k}\,\iff k\,{\text{is odd}}\\\end{aligned}}}$

a ₀ = 1、a _n = 0 ( n > 0)の場合、結果として得られる三角形はザイデル・エントリンガー・アーノルド三角形^[1]と呼ばれ、その数はエントリンガー数( OEISのシーケンスA008281 )と呼ばれます。 ${\displaystyle T_{k,n}}$

この場合、変換された数列b _nの数はオイラーアップ/ダウン数と呼ばれます。^[2]これは、オンライン整数数列百科事典の数列 A000111 です。これらはn文字の交互順列の数を列挙し、オイラー数とベルヌーイ数に関連しています。

ブストロフェドン変換の幾何学的設計に基づいて、入力値 ( ) から出力値 ( ) への関係の代数的定義を、さまざまな代数(「数値領域」) に対して定義できます。${\displaystyle a_{i}}$${\displaystyle b_{i}}$

実数 ( ) 値のスカラーに対するユークリッド ( ) 代数では、ブストロフェドン変換された実数値( b _n )は入力値( a _n )と次のように関係します。 ${\displaystyle \mathbb {E} ^{n}}$${\displaystyle \mathbb {R} ^{1}}$

${\displaystyle {\begin{aligned}b_{n}&=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}E_{n-k}\\\end{aligned}}}$、

逆の関係（入力から出力）は次のように定義されます。

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

ここで、( E _n )は「上/下」の数列であり、セカント数またはタンジェント数としても知られています。^[3]

数列（a _n） の指数生成関数は次のように定義される。

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

ブストロフェドン変換の指数生成関数（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, NJA; Young, Neal E. (1996). 「シーケンスに対する新しい操作: Boustrouphedon 変換」. Journal of Combinatorial Theory, Series A. 76 ( 1): 44–54. arXiv : math.CO/0205218 . doi :10.1006/jcta.1996.0087. S2CID  15637402.
• ワイスタイン、エリック W. (2002)。CRC簡潔数学百科事典、第 2 版。チャップマン & ホール/CRC。p. 273。ISBN 1-58488-347-2。