Entringer Number

恩特林格数

恩特林格数（Entringer number，OEIS A008281） 是满足下述条件的 到 共 个数的置换数目：

• 首元素是 ；
• 首元素的下一个元素比首元素小，再下一个元素比前一个元素大，再下一个元素比前一个元素小……后面相邻元素的大小关系均满足这样的规则。

恩特林格数的初值有：

有递推关系：

Seidel-Entringer-Arnold 三角

恩特林格数的一个适当排列的数字三角，称为 Seidel-Entringer-Arnold 三角（Seidel-Entringer-Arnold triangle，OEIS A008280）。该三角是按照“牛耕”顺序（ox-plowing order）排列的恩特林格数 ：

即：

按照这种方式排列的恩特林格数的优势是，与它的递推关系 一致，可以方便记忆和理解。

恩特林格数有一个指数型生成函数：

这个生成函数的系数分布事实上是上面的 Seidel-Entringer-Arnold 三角的简单拉伸变形：

即：

zigzag 置换

一个 zigzag 置换（zigzag permutation）是一个 到 的排列 到 ，使得任意一个元素 的大小都不介于 和 之间。

对于 zigzag 置换的个数 （OEIS A001250），从 开始有：

例如，前几个 的交替置换有：

交替置换与 zigzag 数

（注意和“错位排列”进行概念上的区分。）

对于大于 的 ，每个 zigzag 置换翻转过来仍旧为 zigzag 置换，可以两两配对，所以必然为偶数。

这里再给出一种配对的方法：将 zigzag 置换分为交替置换（alternating permutation）和反交替置换（reverse alternating permutation）。

交替置换的首元素大于第二个元素，大小关系为：

反交替置换的首元素小于第二个元素，大小关系为：

如果将 和 位置互换， 和 位置互换，以此类推，即可将交替置换与反交替置换两个集合互换。因此，交替置换与反交替置换的个数相等，恰好为 zigzag 置换的一半。

对于大于 的 ，记：

定义初值：

这里的 称为 zigzag 数（Euler zigzag number，OEIS A000111），从 开始有：

接下来试着求解 。

从 到 之中，选取 个数构成子集，有 种选法。

在这个 元子集中，选反交替置换 ，有 种选法；用全集减掉这个 元子集，剩余的 元子集中，选反交替置换 ，有 种选法。

考虑 元排列 ，将 倒置作为开头，接上 ，再接上 。那么， 一定是 zigzag 置换，并且任意一个 元 zigzag 置换，都可以在 处截断得到对应的反交替置换 和 ，并且不同的 元 zigzag 置换对应的 和 不同。

因此有递推关系：

当 为 时并不满足这个递推式，初值 和 都是 。

可见，这是一个指数型生成函数的卷积。假设 的指数型生成函数为 ，就有微分方程：

等式右面加 是为了处理 为 时的特殊情况。该方程的通解为：

代入第 项为 之后，可以得到特解：

正切函数是奇函数，正割函数是偶函数，两者之和构成 zigzag 数的生成函数。

恩特林格数与 zigzag 数的关系

根据恩特林格数的定义，恩特林格数 是首元素为 的 到 的交替置换个数。因此恩特林格数与 zigzag 数事实上有关系：

将 称为“zigzag 数”也有原因：记 是欧拉数（Euler number）， 是伯努利数。

当 为偶数时，偶数项下标的 zigzag 数也称“正割数” 或者“zig 数”。有关系：

前几项为（OEIS A000364）：

当 为奇数时，奇数项下标的 zigzag 数也称“正切数” 或者“zag 数”。有关系：

前几项为（OEIS A000182）：

于是对于在 处的泰勒展开，可以给出正割数和正切数：

或者写到一起：

构成 zigzag 数的生成函数。