跳转至

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 数的生成函数。

参考资料与链接

  1. Alternating permutation - Wikipedia