交互順列

組合せ 数学において、集合 {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 番目のエントリが最初のエントリよりも大きいことを要求する著者もいれば (上記の例のように)、交互順列を逆にすることを要求する著者もいます (つまり、2 番目のエントリが最初のエントリよりも小さく、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 からなる順列) の一意の順列は交互に存在するものとみなされます。

集合 {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_{nk}}$

全ての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_{nk}}{(nk)!}}{\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=nk}$${\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!\,.}$

奇数添え字のジグザグ数（つまり、正接数）はベルヌーイ数と密接な関係がある。その関係は次式で与えられる。

${\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）。

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

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

${\displaystyle E(n,0)=0\qquad {\mbox{n>0の場合}$

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

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 )。

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

${\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)}$は上昇階乗を表し、 は第二種スターリング数を表します。 ${\displaystyle S(r,k)}$

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

• アンドレ、デジレ(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 版)。ケンブリッジ大学出版局。

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