Entringer Number

恩特林格數

恩特林格數（Entringer number，OEIS A008281）\(E(n,k)\) 是滿足下述條件的 \(0\) 到 \(n\) 共 \(n+1\) 個數的置換數目：

首元素是 \(k\)；
首元素的下一個元素比首元素小，再下一個元素比前一個元素大，再下一個元素比前一個元素小……後面相鄰元素的大小關係均滿足這樣的規則。

恩特林格數的初值有：

\[ E(0,0)=1 \]

\[ E(n,0)=0 \]

有遞推關係：

\[ E(n,k)=E(n,k-1)+E(n-1,n-k) \]

Seidel–Entringer–Arnold 三角

恩特林格數的一個適當排列的數字三角，稱為 Seidel–Entringer–Arnold 三角（Seidel–Entringer–Arnold triangle，OEIS A008280）。該三角是按照「牛耕」順序（ox-plowing order）排列的恩特林格數 \(E_(n,k)\)：

\[ \begin{aligned} & E(0,0) \\ & E(1,0) \rightarrow E(1,1) \\ & E(2,2) \leftarrow E(2,1) \leftarrow E(2,0) \\ & E(3,0) \rightarrow E(3,1) \rightarrow E(3,2) \rightarrow E(3,3) \\ & E(4,4) \leftarrow E(4,3) \leftarrow E(4,2) \leftarrow E(4,1) \leftarrow E(4,0) \end{aligned} \]

即：

\[ \begin{aligned} & 1 \\ & 0 \rightarrow 1 \\ & 1 \leftarrow 1 \leftarrow 0 \\ & 0 \rightarrow 1 \rightarrow 2 \rightarrow 2 \\ & 5 \leftarrow 5 \leftarrow 4 \leftarrow 2 \leftarrow 0 \end{aligned} \]

按照這種方式排列的恩特林格數的優勢是，與它的遞推關係 \(E(n,k)=E(n,k-1)+E(n-1,n-k)\) 一致，可以方便記憶和理解。

恩特林格數有一個指數型生成函數：

\[ \sum_{m=0}^\infty\sum_{n=0}^\infty E\left(m+n,\frac{1}{2}\left(m+n+{(-1)}^{m+n}(n-m)\right)\right)\frac{x^m}{m!}\frac{x^n}{n!}=\frac{\cos x+\sin x}{\cos (x+y)} \]

這個生成函數的係數分佈事實上是上面的 Seidel–Entringer–Arnold 三角的簡單拉伸變形：

\[ \begin{array}{ccccc} E(0,0) & E(1,1) & E(2,0) & E(3,3) & E(4,0) \\ E(1,0) & E(2,1) & E(3,2) & E(4,1) & \\ E(2,2) & E(3,1) & E(4,2) & & \\ E(3,0) & E(4,3) & & & \\ E(4,4) & & & & \end{array} \]

即：

\[ \begin{aligned} & 1\quad 1\quad 0\quad 2\quad 0\\ & 0\quad 1\quad 2\quad 2\\ & 1\quad 1\quad 4\\ & 0\quad 5\\ & 5 \end{aligned} \]

zigzag 置換

一個 zigzag 置換（zigzag permutation）是一個 \(1\) 到 \(n\) 的排列 \(c_1\) 到 \(c_i\)，使得任意一個元素 \(c_i\) 的大小都不介於 \(c_{i-1}\) 和 \(c_{i+1}\) 之間。

對於 zigzag 置換的個數 \(Z_n\)（OEIS A001250），從 \(n=0\) 開始有：

\[ 1, 1, 2, 4, 10, 32, 122, 544, \cdots \]

例如，前幾個 \(n\) 的交替置換有：

\[ \begin{aligned} n=1: & \{1\}\\ n=2: & \{1,2\}, \{2,1\}\\ n=3: & \{1,3,2\}, \{2,1,3\}, \{2,3,1\}, \{3,1,2\}\\ n=4: & \{1,3,2,4\}, \{1,4,2,3\}, \{2,1,4,3\}, \{2,3,1,4\}, \{2,4,1,3\}, \\ & \{3,1,4,2\}, \{3,2,4,1\}, \{3,4,1,2\}, \{4,1,3,2\}, \{4,2,3,1\} \end{aligned} \]

交替置換與 zigzag 數

（注意和「錯位排列」進行概念上的區分。）

對於大於 \(1\) 的 \(n\)，每個 zigzag 置換翻轉過來仍舊為 zigzag 置換，可以兩兩配對，所以必然為偶數。

這裏再給出一種配對的方法：將 zigzag 置換分為交替置換（alternating permutation）和反交替置換（reverse alternating permutation）。

交替置換的首元素大於第二個元素，大小關係為：

\[ c_1>c_2<c_3>\cdots \]

反交替置換的首元素小於第二個元素，大小關係為：

\[ c_1<c_2>c_3<\cdots \]

如果將 \(1\) 和 \(n\) 位置互換，\(2\) 和 \(n-1\) 位置互換，以此類推，即可將交替置換與反交替置換兩個集合互換。因此，交替置換與反交替置換的個數相等，恰好為 zigzag 置換的一半。

對於大於 \(1\) 的 \(n\)，記：

\[ A_n=\frac{Z_n}{2} \]

定義初值：

\[ A_0=A_1=1 \]

這裏的 \(A_n\) 稱為 zigzag 數（Euler zigzag number，OEIS A000111），從 \(n=0\) 開始有：

\[ 1, 1, 1, 2, 5, 16, 61, 272, \cdots \]

接下來試着求解 \(A_n\)。

從 \(1\) 到 \(n\) 之中，選取 \(k\) 個數構成子集，有 \(\dbinom{n}{k}\) 種選法。

在這個 \(k\) 元子集中，選反交替置換 \(u\)，有 \(A_k\) 種選法；用全集減掉這個 \(k\) 元子集，剩餘的 \(n-k\) 元子集中，選反交替置換 \(v\)，有 \(A_{n-k}\) 種選法。

考慮 \(n+1\) 元排列 \(w\)，將 \(u\) 倒置作為開頭，接上 \(n+1\)，再接上 \(v\)。那麼，\(w\) 一定是 zigzag 置換，並且任意一個 \(n+1\) 元 zigzag 置換，都可以在 \(n+1\) 處截斷得到對應的反交替置換 \(u\) 和 \(v\)，並且不同的 \(n+1\) 元 zigzag 置換對應的 \(u\) 和 \(v\) 不同。

因此有遞推關係：

\[ 2A_{n+1}=\sum_{k=0}^n \dbinom{n}{k} A_k A_{n-k} \]

\[ 2(n+1)\frac{A_{n+1}}{(n+1)!}=\sum_{k=0}^n \frac{A_k}{k!}\frac{A_{n-k}}{(n-k)!} \]

當 \(n\) 為 \(0\) 時並不滿足這個遞推式，初值 \(A_0\) 和 \(A_1\) 都是 \(1\)。

可見，這是一個指數型生成函數的卷積。假設 \(A_n\) 的指數型生成函數為 \(y\)，就有微分方程：

\[ 2\frac{\mathrm{d}y}{\mathrm{d}x}=y^2+1 \]

等式右面加 \(1\) 是為了處理 \(n\) 為 \(0\) 時的特殊情況。該方程的通解為：

\[ y=\tan\left(\frac{1}{2}x+C\right) \]

代入第 \(0\) 項為 \(1\) 之後，可以得到特解：

\[ y=\tan x+\sec x \]

正切函數是奇函數，正割函數是偶函數，兩者之和構成 zigzag 數的生成函數。

恩特林格數與 zigzag 數的關係

根據恩特林格數的定義，恩特林格數 \(E(n,k)\) 是首元素為 \(k\) 的 \(0\) 到 \(n\) 的交替置換個數。因此恩特林格數與 zigzag 數事實上有關係：

\[ A_n=E(n,n) \]

將 \(A_n\) 稱為「zigzag 數」也有原因：記 \(E_n\) 是歐拉數（Euler number），\(B_n\) 是伯努利數。

當 \(n\) 為偶數時，偶數項下標的 zigzag 數也稱「正割數」\(S_n\) 或者「zig 數」。有關係：

\[ A_n=(-1)^{n/2}E_n \]

前幾項為（OEIS A000364）：

\[ 1, 1, 5, 61, 1385, \cdots \]

當 \(n\) 為奇數時，奇數項下標的 zigzag 數也稱「正切數」\(T_n\) 或者「zag 數」。有關係：

\[ A_n=\frac{(-1)^{(n-1)/2}2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1} \]

前幾項為（OEIS A000182）：

\[ 1, 2, 16, 272, 7936, \cdots \]

於是對於在 \(x=0\) 處的泰勒展開，可以給出正割數和正切數：

\[ \sec x=A_0+A_2\frac{x^2}{2!}+A_4\frac{x^4}{4!}+\cdots \]

\[ \tan x=A_1x+A_3\frac{x^3}{3!}+A_5\frac{x^5}{5!}+\cdots \]

或者寫到一起：

\[ \sec x+\tan x=A_0+A_1x+A_2\frac{x^2}{2!}+A_3\frac{x^3}{3!}+A_4\frac{x^4}{4!}+A_5\frac{x^5}{5!}+\cdots \]

構成 zigzag 數的生成函數。

參考資料與鏈接

Alternating permutation - Wikipedia

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用