Entringer Number
恩特林格数
恩特林格数(Entringer number,OEIS A008281)𝐸(𝑛,𝑘)
是满足下述条件的 0
到 𝑛
共 𝑛 +1
个数的置换数目:
- 首元素是 𝑘
; - 首元素的下一个元素比首元素小,再下一个元素比前一个元素大,再下一个元素比前一个元素小……后面相邻元素的大小关系均满足这样的规则。
恩特林格数的初值有:
𝐸(0,0)=1
𝐸(𝑛,0)=0
有递推关系:
𝐸(𝑛,𝑘)=𝐸(𝑛,𝑘−1)+𝐸(𝑛−1,𝑛−𝑘)
Seidel–Entringer–Arnold 三角
恩特林格数的一个适当排列的数字三角,称为 Seidel–Entringer–Arnold 三角(Seidel–Entringer–Arnold triangle,OEIS A008280)。该三角是按照「牛耕」顺序(ox-plowing order)排列的恩特林格数 𝐸(𝑛,𝑘)
:
𝐸(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)
即:
10→11←1←00→1→2→25←5←4←2←0
按照这种方式排列的恩特林格数的优势是,与它的递推关系 𝐸(𝑛,𝑘) =𝐸(𝑛,𝑘 −1) +𝐸(𝑛 −1,𝑛 −𝑘)
一致,可以方便记忆和理解。
恩特林格数有一个指数型生成函数:
∞∑𝑚=0∞∑𝑛=0𝐸(𝑚+𝑛,12(𝑚+𝑛+(−1)𝑚+𝑛(𝑛−𝑚)))𝑥𝑚𝑚!𝑥𝑛𝑛!=cos𝑥+sin𝑥cos(𝑥+𝑦)
这个生成函数的系数分布事实上是上面的 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)
即:
110200122114055
zigzag 置换
一个 zigzag 置换(zigzag permutation)是一个 1
到 𝑛
的排列 𝑐1
到 𝑐𝑖
,使得任意一个元素 𝑐𝑖
的大小都不介于 𝑐𝑖−1
和 𝑐𝑖+1
之间。
对于 zigzag 置换的个数 𝑍𝑛
(OEIS A001250),从 𝑛 =0
开始有:
1,1,2,4,10,32,122,544,⋯
例如,前几个 𝑛
的交替置换有:
𝑛=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}
交替置换与 zigzag 数
(注意和「错位排列」进行概念上的区分。)
对于大于 1
的 𝑛
,每个 zigzag 置换翻转过来仍旧为 zigzag 置换,可以两两配对,所以必然为偶数。
这里再给出一种配对的方法:将 zigzag 置换分为交替置换(alternating permutation)和反交替置换(reverse alternating permutation)。
交替置换的首元素大于第二个元素,大小关系为:
𝑐1>𝑐2<𝑐3>⋯
反交替置换的首元素小于第二个元素,大小关系为:
𝑐1<𝑐2>𝑐3<⋯
如果将 1
和 𝑛
位置互换,2
和 𝑛 −1
位置互换,以此类推,即可将交替置换与反交替置换两个集合互换。因此,交替置换与反交替置换的个数相等,恰好为 zigzag 置换的一半。
对于大于 1
的 𝑛
,记:
𝐴𝑛=𝑍𝑛2
定义初值:
𝐴0=𝐴1=1
这里的 𝐴𝑛
称为 zigzag 数(Euler zigzag number,OEIS A000111),从 𝑛 =0
开始有:
1,1,1,2,5,16,61,272,⋯
接下来试着求解 𝐴𝑛
。
从 1
到 𝑛
之中,选取 𝑘
个数构成子集,有 (𝑛𝑘)
种选法。
在这个 𝑘
元子集中,选反交替置换 𝑢
,有 𝐴𝑘
种选法;用全集减掉这个 𝑘
元子集,剩余的 𝑛 −𝑘
元子集中,选反交替置换 𝑣
,有 𝐴𝑛−𝑘
种选法。
考虑 𝑛 +1
元排列 𝑤
,将 𝑢
倒置作为开头,接上 𝑛 +1
,再接上 𝑣
。那么,𝑤
一定是 zigzag 置换,并且任意一个 𝑛 +1
元 zigzag 置换,都可以在 𝑛 +1
处截断得到对应的反交替置换 𝑢
和 𝑣
,并且不同的 𝑛 +1
元 zigzag 置换对应的 𝑢
和 𝑣
不同。
因此有递推关系:
2𝐴𝑛+1=𝑛∑𝑘=0(𝑛𝑘)𝐴𝑘𝐴𝑛−𝑘
2(𝑛+1)𝐴𝑛+1(𝑛+1)!=𝑛∑𝑘=0𝐴𝑘𝑘!𝐴𝑛−𝑘(𝑛−𝑘)!
当 𝑛
为 0
时并不满足这个递推式,初值 𝐴0
和 𝐴1
都是 1
。
可见,这是一个指数型生成函数的卷积。假设 𝐴𝑛
的指数型生成函数为 𝑦
,就有微分方程:
2d𝑦d𝑥=𝑦2+1
等式右面加 1
是为了处理 𝑛
为 0
时的特殊情况。该方程的通解为:
𝑦=tan(12𝑥+𝐶)
代入第 0
项为 1
之后,可以得到特解:
𝑦=tan𝑥+sec𝑥
正切函数是奇函数,正割函数是偶函数,两者之和构成 zigzag 数的生成函数。
恩特林格数与 zigzag 数的关系
根据恩特林格数的定义,恩特林格数 𝐸(𝑛,𝑘)
是首元素为 𝑘
的 0
到 𝑛
的交替置换个数。因此恩特林格数与 zigzag 数事实上有关系:
𝐴𝑛=𝐸(𝑛,𝑛)
将 𝐴𝑛
称为「zigzag 数」也有原因:记 𝐸𝑛
是欧拉数(Euler number),𝐵𝑛
是伯努利数。
当 𝑛
为偶数时,偶数项下标的 zigzag 数也称「正割数」𝑆𝑛
或者「zig 数」。有关系:
𝐴𝑛=(−1)𝑛/2𝐸𝑛
前几项为(OEIS A000364):
1,1,5,61,1385,⋯
当 𝑛
为奇数时,奇数项下标的 zigzag 数也称「正切数」𝑇𝑛
或者「zag 数」。有关系:
𝐴𝑛=(−1)(𝑛−1)/22𝑛+1(2𝑛+1−1)𝐵𝑛+1𝑛+1
前几项为(OEIS A000182):
1,2,16,272,7936,⋯
于是对于在 𝑥 =0
处的泰勒展开,可以给出正割数和正切数:
sec𝑥=𝐴0+𝐴2𝑥22!+𝐴4𝑥44!+⋯
tan𝑥=𝐴1𝑥+𝐴3𝑥33!+𝐴5𝑥55!+⋯
或者写到一起:
sec𝑥+tan𝑥=𝐴0+𝐴1𝑥+𝐴2𝑥22!+𝐴3𝑥33!+𝐴4𝑥44!+𝐴5𝑥55!+⋯
构成 zigzag 数的生成函数。
参考资料与链接
- Alternating permutation - Wikipedia
本页面最近更新:2023/12/16 23:29:25,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Tiphereth-A, Great-designer, CCXXXI, ChungZH, jifbt
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用