跳转至

# Entringer Number

## 恩特林格数

恩特林格数（Entringer number，OEIS A008281）𝐸(𝑛,𝑘)E(n,k) 是满足下述条件的 0 0 到 𝑛 n 共 𝑛 +1 n+1 个数的置换数目：

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

恩特林格数的初值有：

𝐸(0,0)=1 E(0,0)=1 𝐸(𝑛,0)=0 E(n,0)=0

有递推关系：

𝐸(𝑛,𝑘)=𝐸(𝑛,𝑘−1)+𝐸(𝑛−1,𝑛−𝑘)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)：

𝐸(0,0)𝐸(1,0)→𝐸(1,1)𝐸(2,2)←𝐸(2,1)←𝐸(2,0)𝐸(3,0)→𝐸(3,1)→𝐸(3,2)→𝐸(3,3)𝐸(4,4)←𝐸(4,3)←𝐸(4,2)←𝐸(4,1)←𝐸(4,0)E(0,0)E(1,0)→E(1,1)E(2,2)←E(2,1)←E(2,0)E(3,0)→E(3,1)→E(3,2)→E(3,3)E(4,4)←E(4,3)←E(4,2)←E(4,1)←E(4,0)

即：

1 0→1 1←1←0 0→1→2→2 5←5←4←2←0 1 0→1 1←1←0 0→1→2→2 5←5←4←2←0

按照这种方式排列的恩特林格数的优势是，与它的递推关系 𝐸(𝑛,𝑘) =𝐸(𝑛,𝑘 −1) +𝐸(𝑛 −1,𝑛 −𝑘)E(n,k)=E(n,k−1)+E(n−1,n−k) 一致，可以方便记忆和理解．

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

∞∑𝑚=0∞∑𝑛=0 𝐸(𝑚+𝑛,1 2(𝑚+𝑛+(−1)𝑚+𝑛(𝑛−𝑚)))𝑥 𝑚 𝑚!𝑥 𝑛 𝑛!=c o s⁡𝑥+s i n⁡𝑥 c o s⁡(𝑥+𝑦)∑m=0∞∑n=0∞E(m+n,1 2(m+n+(−1)m+n(n−m)))x m m!x n n!=cos⁡x+sin⁡x cos⁡(x+y)

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

𝐸(0,0)𝐸(1,1)𝐸(2,0)𝐸(3,3)𝐸(4,0)𝐸(1,0)𝐸(2,1)𝐸(3,2)𝐸(4,1)𝐸(2,2)𝐸(3,1)𝐸(4,2)𝐸(3,0)𝐸(4,3)𝐸(4,4)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)

即：

1 1 0 2 0 0 1 2 2 1 1 4 0 5 5 1 1 0 2 0 0 1 2 2 1 1 4 0 5 5

## zigzag 置换

一个 zigzag 置换（zigzag permutation）是一个 1 1 到 𝑛 n 的排列 𝑐 1 c 1 到 𝑐 𝑖 c i，使得任意一个元素 𝑐 𝑖 c i 的大小都不介于 𝑐 𝑖−1 c i−1 和 𝑐 𝑖+1 c i+1 之间．

对于 zigzag 置换的个数 𝑍 𝑛 Z n（OEIS A001250），从 𝑛 =0 n=0 开始有：

1,1,2,4,1 0,3 2,1 2 2,5 4 4,⋯1,1,2,4,10,32,122,544,⋯

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

𝑛=1:{1}𝑛=2:{1,2},{2,1}𝑛=3:{1,3,2},{2,1,3},{2,3,1},{3,1,2}𝑛=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}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}

## 交替置换与 zigzag 数

（注意和「错位排列」进行概念上的区分．）

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

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

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

𝑐 1>𝑐 2<𝑐 3>⋯c 1>c 2<c 3>⋯

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

𝑐 1<𝑐 2>𝑐 3<⋯c 1<c 2>c 3<⋯

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

对于大于 1 1 的 𝑛 n，记：

𝐴 𝑛=𝑍 𝑛 2 A n=Z n 2

定义初值：

𝐴 0=𝐴 1=1 A 0=A 1=1

这里的 𝐴 𝑛 A n 称为 zigzag 数（Euler zigzag number，OEIS A000111），从 𝑛 =0 n=0 开始有：

1,1,1,2,5,1 6,6 1,2 7 2,⋯1,1,1,2,5,16,61,272,⋯

接下来试着求解 𝐴 𝑛 A n．

从 1 1 到 𝑛 n 之中，选取 𝑘 k 个数构成子集，有 (𝑛 𝑘)(n k) 种选法．

在这个 𝑘 k 元子集中，选反交替置换 𝑢 u，有 𝐴 𝑘 A k 种选法；用全集减掉这个 𝑘 k 元子集，剩余的 𝑛 −𝑘 n−k 元子集中，选反交替置换 𝑣 v，有 𝐴 𝑛−𝑘 A n−k 种选法．

考虑 𝑛 +1 n+1 元排列 𝑤 w，将 𝑢 u 倒置作为开头，接上 𝑛 +1 n+1，再接上 𝑣 v．那么，𝑤 w 一定是 zigzag 置换，并且任意一个 𝑛 +1 n+1 元 zigzag 置换，都可以在 𝑛 +1 n+1 处截断得到对应的反交替置换 𝑢 u 和 𝑣 v，并且不同的 𝑛 +1 n+1 元 zigzag 置换对应的 𝑢 u 和 𝑣 v 不同．

因此有递推关系：

2 𝐴 𝑛+1=𝑛∑𝑘=0(𝑛 𝑘)𝐴 𝑘 𝐴 𝑛−𝑘 2 A n+1=∑k=0 n(n k)A k A n−k 2(𝑛+1)𝐴 𝑛+1(𝑛+1)!=𝑛∑𝑘=0 𝐴 𝑘 𝑘!𝐴 𝑛−𝑘(𝑛−𝑘)!2(n+1)A n+1(n+1)!=∑k=0 n A k k!A n−k(n−k)!

当 𝑛 n 为 0 0 时并不满足这个递推式，初值 𝐴 0 A 0 和 𝐴 1 A 1 都是 1 1．

可见，这是一个指数型生成函数的卷积．假设 𝐴 𝑛 A n 的指数型生成函数为 𝑦 y，就有微分方程：

2 d 𝑦 d 𝑥=𝑦 2+1 2 d y d x=y 2+1

等式右面加 1 1 是为了处理 𝑛 n 为 0 0 时的特殊情况．该方程的通解为：

𝑦=t a n⁡(1 2 𝑥+𝐶)y=tan⁡(1 2 x+C)

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

𝑦=t a n⁡𝑥+s e c⁡𝑥 y=tan⁡x+sec⁡x

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

## 恩特林格数与 zigzag 数的关系

根据恩特林格数的定义，恩特林格数 𝐸(𝑛,𝑘)E(n,k) 是首元素为 𝑘 k 的 0 0 到 𝑛 n 的交替置换个数．因此恩特林格数与 zigzag 数事实上有关系：

𝐴 𝑛=𝐸(𝑛,𝑛)A n=E(n,n)

将 𝐴 𝑛 A n 称为「zigzag 数」也有原因：记 𝐸 𝑛 E n 是欧拉数（Euler number），𝐵 𝑛 B n 是伯努利数．

当 𝑛 n 为偶数时，偶数项下标的 zigzag 数也称「正割数」𝑆 𝑛 S n 或者「zig 数」．有关系：

𝐴 𝑛=(−1)𝑛/2 𝐸 𝑛 A n=(−1)n/2 E n

前几项为（OEIS A000364）：

1,1,5,6 1,1 3 8 5,⋯1,1,5,61,1385,⋯

当 𝑛 n 为奇数时，奇数项下标的 zigzag 数也称「正切数」𝑇 𝑛 T n 或者「zag 数」．有关系：

𝐴 𝑛=(−1)(𝑛−1)/2 2 𝑛+1(2 𝑛+1−1)𝐵 𝑛+1 𝑛+1 A n=(−1)(n−1)/2 2 n+1(2 n+1−1)B n+1 n+1

前几项为（OEIS A000182）：

1,2,1 6,2 7 2,7 9 3 6,⋯1,2,16,272,7936,⋯

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

s e c⁡𝑥=𝐴 0+𝐴 2 𝑥 2 2!+𝐴 4 𝑥 4 4!+⋯sec⁡x=A 0+A 2 x 2 2!+A 4 x 4 4!+⋯t a n⁡𝑥=𝐴 1 𝑥+𝐴 3 𝑥 3 3!+𝐴 5 𝑥 5 5!+⋯tan⁡x=A 1 x+A 3 x 3 3!+A 5 x 5 5!+⋯

或者写到一起：

s e c⁡𝑥+t a n⁡𝑥=𝐴 0+𝐴 1 𝑥+𝐴 2 𝑥 2 2!+𝐴 3 𝑥 3 3!+𝐴 4 𝑥 4 4!+𝐴 5 𝑥 5 5!+⋯sec⁡x+tan⁡x=A 0+A 1 x+A 2 x 2 2!+A 3 x 3 3!+A 4 x 4 4!+A 5 x 5 5!+⋯

构成 zigzag 数的生成函数．

## 参考资料与链接

1. Alternating permutation - Wikipedia

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, Great-designer, CCXXXI, ChungZH, jifbt
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用