交互順列

Type of permutation

組合せ 数学において、{1, 2, 3, ..., n }の交代順列（ジグザグ順列）とは、各要素が前の要素より交互に大きくなったり小さくなったりするように、これらの数を順列（配置）することです。例えば、{1, 2, 3, 4}の5つの交代順列は以下のとおりです。

• 1、3、2、4 1 < 3 > 2 < 4 なので、
• 1、4、2、3 1 < 4 > 2 < 3 なので、
• 2、3、1、4 2 < 3 > 1 < 4 なので、
• 2、4、1、3 2 < 4 > 1 < 3 なので、
• 3、4、1、2 です。3 < 4 > 1 < 2 だからです。

このタイプの順列は19世紀にデジレ・アンドレによって初めて研究されました。 ^[1]

交互順列という用語の使い方は、著者によって若干異なります。交互順列の 2 番目のエントリが 1 番目のエントリよりも大きくなることを要求する著者もいれば (上記の例のように)、交互順列を逆にすることを要求する著者もいます (つまり、2 番目のエントリが 1 番目のエントリよりも小さく、3 番目のエントリが 2 番目のエントリよりも大きくなる、など)。また、両方のタイプを交互順列という名前で呼ぶ著者もいます。

集合 {1, ..., n }の交互順列の数A _nを決定する問題は、アンドレの問題と呼ばれます。数A _nは、オイラー数、ジグザグ数、または上下数として知られています。n が偶数の場合には数A n_はセカント数として知られ、 nが奇数の場合にはタンジェント数として知られています。後者の名称は、数列の生成関数の研究に由来しています。

定義

順列c ₁ , ..., c _nは、その要素が交互に上昇と下降を繰り返す場合、 交代順列であると言われます。つまり、最初と最後の要素以外の各要素は、隣接する要素の両方よりも大きいか小さいかのいずれかになります。一部の著者は、「交代」という用語をc ₁ < c ₂ > c ₃ < ...を満たす「上向き下向き」順列のみを指して使用し、 c ₁ > c ₂ < c ₃ > ...を満たす「下向き上向き」順列を逆交代順列と呼びます。他の著者はこの慣例を逆にし、「交代」という用語を上向き下向きと下向き上向きの両方の順列を指すために使用します。

下から上への順列と上から下への順列の間には単純な一対一の対応があります。つまり、各エントリc _{i を}n + 1 - c _iに置き換えると、エントリの相対的な順序が逆になります。

慣例により、どの命名スキームでも、長さ 0 (空集合の順列) と長さ 1 (単一のエントリ 1 からなる順列) の一意の順列は交互に存在するものとみなされます。

アンドレの定理

ベルヌーイ（1742年） 『オペラ・オムニア』第4巻105ページのジグザグ数

集合 {1, ..., n }の交互順列の数A _nを決定する問題は、アンドレの問題と呼ばれます。数A _{n は}、オイラー数、ジグザグ数、上下数、またはこれらの組み合わせなど、様々な名前で知られています。特にオイラー数_という名称は、密接に関連する数列を指すこともあります。A nの最初のいくつかの値は、1、1、1、2、5、16、61、272、1385、7936、50521、...（OEISの数列A000111）です。

これらの数はカタラン数と同様の単純な再帰性を満たす。{1, 2, 3, ..., n ,  n + 1 }の交互順列（上下両方）の集合を、 最大の要素n + 1の位置k に従って分割することにより、次のことが示される。

${\displaystyle 2A_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}A_{k}A_{n-k}}$

n ≥ 1のすべてに対して。アンドレ（1881）はこの再帰性を利用して、指数関数生成関数を満たす微分方程式を与えた。

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}}$

数列A _nについて。実際、再帰式は次のようになります。

${\displaystyle 2\sum _{n\geq 1}A_{n+1}{\frac {x^{n+1}}{(n+1)!}}=\sum _{n\geq 1}\sum _{k=0}^{n}{\frac {A_{k}}{k!}}{\frac {A_{n-k}}{(n-k)!}}{\frac {x^{n+1}}{n+1}}=\int \left(\sum _{k\geq 0}A_{k}{\frac {x^{k}}{k!}}\right)\left(\sum _{j\geq 0}A_{j}{\frac {x^{j}}{j!}}\right)\,dx-x}$

ここで、とを代入する。これにより積分方程式が得られる。 ${\displaystyle j=n-k}$ ${\displaystyle {\frac {x^{n+1}}{n+1}}=\int x^{k+j}\,dx}$

${\displaystyle 2(A(x)-1-x)=\int A(x)^{2}\,dx-x,}$

これを微分すると となる。この微分方程式は変数分離法（初期条件を使用）で解くことができ、接線半角公式を用いて簡略化することで、最終結果は ${\displaystyle 2{\frac {dA}{dx}}-2=A^{2}-1}$ ${\displaystyle A(0)=A_{0}/0!=1}$

${\displaystyle A(x)=\tan \left({\frac {\pi }{4}}+{\frac {x}{2}}\right)=\sec x+\tan x}$、

正接関数と正接関数の和である。この結果はアンドレの定理として知られている。この結果の幾何学的解釈は、ヨハン・ベルヌーイの定理^[2]の一般化によって与えられる。

アンドレの定理から、級数A ( x )の収束半径はπ /2である ことが分かる。これにより、漸近展開^[3]を計算することができる。

${\displaystyle A_{n}\sim 2\left({\frac {2}{\pi }}\right)^{n+1}n!\,.}$

ザイデルのアルゴリズム

1877年フィリップ・ルートヴィヒ・フォン・ザイデルはAnの_計算を簡単にするアルゴリズムを発表しました。^[4]

${\displaystyle {\begin{array}{crrrcc}{}&{}&{\color {red}1}&{}&{}&{}\\{}&{\rightarrow }&{\color {blue}1}&{\color {red}1}&{}\\{}&{\color {red}2}&{\color {blue}2}&{\color {blue}1}&{\leftarrow }\\{\rightarrow }&{\color {blue}2}&{\color {blue}4}&{\color {blue}5}&{\color {red}5}\\{\color {red}16}&{\color {blue}16}&{\color {blue}14}&{\color {blue}10}&{\color {blue}5}&{\leftarrow }\end{array}}}$

A _nのザイデルのアルゴリズム

1. まず行0に1を入れ、kは現在埋められている行の番号を表すものとする。
2. kが奇数の場合、 k − 1行目の左端の数字をk行目の最初の位置に置き、行を左から右へ埋めていく。各要素は左の数字と上の数字の合計になる。
3. 行の最後に最後の数字を複製します。
4. kが偶数の場合は、反対方向にも同様に進みます。

^{ザイデルのアルゴリズムは実際にははるかに一般的なものであり（ドミニク・デュモン[5]}の説明を参照）、その後も何度か再発見されました。

ザイデルのアプローチと同様に、DEクヌースとTJバックホルツは数A _{2 n}の再帰方程式を与え、ベルヌーイ数 B _{2 n}とオイラー数 E _{2 n}を「整数に対する単純な演算のみを使用して電子計算機で」計算するためのこの方法を推奨した。 ^[6]

VIアーノルド^{[7]はザイデルのアルゴリズムを再発見し、その後ミラー、スローン、ヤングはザイデルのアルゴリズムを}ブストロフェドン変換という名前で普及させました。

三角形の形：

						1
					1		1
				2		2		1
			2		4		5		5
		16		16		14		10		5
	16		32		46		56		61		61
272		272		256		224		178		122		61

OEISには、1 が 1 つあるOEIS : A000657と、1 が 2 つある OEIS : A214267のみが含まれています。

次の行に補助的な 1 と 1 つの 0 を含む分布:

						1
					0		1
				−1		−1		0
			0		−1		−2		−2
		5		5		4		2		0
	0		5		10		14		16		16
−61		−61		−56		−46		−32		−16		0

これはOEIS : A239005で、 OEIS : A008280の符号付きバージョンです。主対角線はOEIS : A122045です。主対角線はOEIS : A155585です。中央の列はOEIS : A099023です。行の合計は1, 1, −2, −5, 16, 61...です。OEIS : A163747を参照してください。下記の 1, 1, 0, −2, 0, 16, 0 で始まる配列を参照してください。

秋山・谷川アルゴリズムをOEIS : A046978 ( n + 1 ) / OEIS : A016116 ( n ) に適用すると、次の結果が得られます。

1	1	⁠1/2⁠	0	− ⁠1/4⁠	− ⁠1/4⁠	− ⁠1/8⁠
0	1	⁠3/2⁠	1	0	− ⁠3/4⁠
−1	−1	⁠3/2⁠	4	⁠15/4⁠
0	−5	− ⁠15/2⁠	1
5	5	− ⁠51/2⁠
0	61
−61

1.最初の列はOEIS : A122045です。これを二項変換すると以下のようになります。

1	1	0	−2	0	16	0
0	−1	−2	2	16	−16
−1	−1	4	14	−32
0	5	10	−46
5	5	−56
0	−61
−61

この配列の最初の行はOEIS : A155585です。増加する反対角線の絶対値はOEIS : A008280です。反対角線の合計は− OEIS : A163747 ( n + 1 ) です。

2. 2列目は1 1 −1 −5 5 61 −61 −1385 1385...である。これを二項変換すると以下のようになる。

1	2	2	−4	−16	32	272
1	0	−6	−12	48	240
−1	−6	−6	60	192
−5	0	66	32
5	66	66
61	0
−61

この配列の最初の行は1 2 2 −4 −16 32 272 544 −7936 15872 353792 −707584...です。2番目の二分法の絶対値は、1番目の二分法の絶対値の2倍です。

OEIS : A046978 ( n ) / ( OEIS : A158780 ( n + 1 ) = abs( OEIS : A117575 ( n )) + 1 = 1, 2, 2, ⁠に適用される秋山・谷川アルゴリズムを考えてみましょう。3/2⁠、1、⁠3/4⁠、⁠3/4⁠、⁠7/8⁠、1、⁠17/16⁠、⁠17/16⁠、⁠33/32⁠ ...。

1	2	2	⁠3/2⁠	1	⁠3/4⁠	⁠3/4⁠
−1	0	⁠3/2⁠	2	⁠5/4⁠	0
−1	−3	− ⁠3/2⁠	3	⁠25/4⁠
2	−3	− ⁠27/2⁠	−13
5	21	− ⁠3/2⁠
−16	45
−61

絶対値がOEIS : A000111である最初の列は、三角関数の分子である可能性があります。

OEIS : A163747は第一種自動列です（主対角線はOEIS : A000004です）。対応する配列は次のようになります。

0	−1	−1	2	5	−16	−61
−1	0	3	3	−21	−45
1	3	0	−24	−24
2	−3	−24	0
−5	−21	24
−16	45
−61

最初の2つの上対角線は−1 3 −24 402... = (−1) ^{n + 1}  ×  OEIS : A002832です。反対角線の和は0 −2 0 10... = 2 ×  OEIS : A122045 ( n  + 1 ) です。

− OEIS : A163982 は、例えばOEIS : A164555 / OEIS : A027642のような、第2種の自動シーケンスです。したがって、配列は次のようになります。

2	1	−1	−2	5	16	−61
−1	−2	−1	7	11	−77
−1	1	8	4	−88
2	7	−4	−92
5	−11	−88
−16	−77
−61

主対角線（ここでは2 −2 8 −92... ）は、最初の上側の対角線（ここではOEIS : A099023 ）の2倍です。反対角線の和は2 0 −4 0... = 2 ×  OEIS : A155585 ( n + 1 ) です。OEIS : A163747  −  OEIS : A163982 = 2 ×  OEIS : A122045です。

関連する配列

奇数添え字のジグザグ数（すなわち接線数）はベルヌーイ数と密接な関係がある。その関係は次の式で表される。

${\displaystyle B_{2n}=(-1)^{n-1}{\frac {2n}{4^{2n}-2^{2n}}}A_{2n-1}}$

n > 0 の場合  。

Z _{n が}、{1, ..., n } の上下または下上（またはn < 2 の場合はその両方）の順列の数を表す場合、上記の組み合わせから、n ≥ 2の場合、 Z _n = 2 A _nとなります。Z _n の最初のいくつかの値は、1、1、2、4、10、32、122、544、2770、15872、101042、...（OEISのシーケンスA001250）です。

オイラージグザグ数はエントリンガー数と関連しており、エントリンガー数からジグザグ数が計算できる。エントリンガー数は以下のように再帰的に定義できる。^[8]

${\displaystyle E(0,0)=1}$

${\displaystyle E(n,0)=0\qquad {\mbox{for }}n>0}$

${\displaystyle E(n,k)=E(n,k-1)+E(n-1,n-k)}$。

n^{番目のジグザグ数は}、エントリンガー数E ( n , n )に等しい。

偶数添え字を持つ数A _{2 n は}、セカント数またはジグ数と呼ばれます。セカント関数が偶数でタンジェントが奇数であるため、上記のアンドレの定理から、これらはsec xのマクローリン級数の分子であることが分かります。最初のいくつかの値は1、1、5、61、1385、50521、…（OEISのシーケンスA000364）です。

正割数は、符号付きオイラー数（双曲正割のテイラー係数）と式E _{2 n}  = (−1) ⁿ A _{2 n}で関連付けられます。（nが奇数のときはE _n  = 0 です。）

同様に、奇数添え字を持つ数A _{2 n +1は、}接線数またはザグ数と呼ばれます。最初のいくつかの値は1、2、16、272、7936、…（OEISのシーケンスA000182）です。

第二種スターリング数を用いた明示的な式

オイラージグザグ数とオイラー数、ベルヌーイ数の関係は、次のことを証明するために使用できる^{[9] [10]}

${\displaystyle A_{r}=-{\frac {4^{r}}{a_{r}}}\sum _{k=1}^{r}{\frac {(-1)^{k}\,S(r,k)}{k+1}}\left({\frac {3}{4}}\right)^{(k)}}$

どこ

${\displaystyle a_{r}={\begin{cases}(-1)^{\frac {r-1}{2}}(1+2^{-r})&{\mbox{if r is odd}}\\(-1)^{\frac {r}{2}}&{\mbox{if r is even}}\end{cases}},}$

${\displaystyle (x)^{(n)}=(x)(x+1)\cdots (x+n-1)}$は上昇階乗を表し、 は第2種スターリング数を表します。 ${\displaystyle S(r,k)}$

参照

• 最長交代部分列
• ブストロフェドン変換
• フェンス（数学）、交互順列を線形拡張として持つ半順序集合

引用

1. ジェシカ・ミラー、NJAスローン、ニール・E・ヤング、「シーケンスに対する新しい演算：ブストロフェドン変換」Journal of Combinatorial Theory、シリーズA 76(1):44–54 (1996)
2. フィリップ・アンリ、ゲルハルト・ヴァナー、「ビュルギ、ベルヌーイ、オイラーとザイデル・エントリンガー・アーノルドの三角形によるジグザグ」、Elemente der Mathematik 74 (4) : 141–168 (2019)
3. Stanley, Richard P. (2010), 「交互順列の概観」, Combinatorics and graphs , Contemporary Mathematics, vol. 531, Providence, RI: American Mathematical Society, pp.  165– 196, arXiv : 0912.4240 , doi :10.1090/conm/531/10466, MR  2757798
4. Seidel, L. (1877)、「Über eine einfache Entstehungsweise der Bernoullischen Zahlen und einiger verwandten Reihen」、Sitzungsber。ミュンシュ。アカド。、4：157～ 187
5. Dumont, D. (1981)、「Matrices d'Euler-seidel」、Séminaire Lotharingien de Combinatoire、B05c
6. Knuth, DE ; Buckholtz, TJ (1967)、「正接数、オイラー数、ベルヌーイ数の計算」、Mathematics of Computation、21 (100)、アメリカ数学会: 663– 688、doi : 10.2307/2005010、JSTOR  2005010
7. Arnold, VI (1991)、「関数特異点に関連するベルヌーイ・オイラーアップダウン数、その組み合わせ論および算術」、Duke Math. J.、63 (2): 537– 555、doi :10.1215/s0012-7094-91-06323-4
8. ワイスタイン、エリック・W.「エントリンジャー・ナンバー」。 MathWorld -- Wolfram Web リソースより。 http://mathworld.wolfram.com/EntringerNumber.html
9. メンデス、アンソニー (2007). 「交互順列に関する注記」.アメリカ数学月刊誌. 114 (5): 437– 440. doi :10.1080/00029890.2007.11920432. JSTOR  27642223.
10. メズー、イシュトヴァーン;ラミレス、ホセ L. (2019)。 「r 交互順列」。数学の方程式。土井：10.1007/s00010-019-00658-5。

参考文献

• アンドレ、デジレ( 1879)、「科​​学の開発」、科学アカデミーの研究、88 : 965–967。

• André, Désiré (1881)、「Sur les permutations alternées」(PDF)、Journal de mathématiques pures et appliquées、3e série、7 : 167–184、2021年 11 月 22 日のオリジナル(PDF)からアーカイブ。

• ヘンリー、フィリップ。ゲルハルト、ワナー (2019)。 「ビュルギ、ベルヌーイ、オイラー、ザイデル・エントリンガー・アーノルドの三角形によるジグザグ」。数学の要素。74 (4): 141–168 .土井:10.4171/EM/393。。

• スタンリー、リチャード・P. (2011).列挙的組合せ論第1巻（第2版）.ケンブリッジ大学出版局.

外部リンク

• ワイスタイン、エリック・W.「交代順列」。MathWorld。
• Ross Tang、「冪級数からのオイラージグザグ数 (アップ/ダウン数) の明示的な式」A _nの簡単な明示的な式。
• 「交互順列の概観」リチャード・P・スタンリーのプレプリント

Retrieved from "https://en.wikipedia.org/w/index.php?title=Alternating_permutation&oldid=1326435941"