OEIS

[OEIS A183135] 引号序列

定义引号序列为:

给定 , 对个不同的求出字符集大小为的长度为的引号序列的个数, 模 .

OEIS 上对引号序列的定义: > the number of length 2n k-ary words (n,k>=0) that can be built by repeatedly inserting doublets into the initially empty word

这是雅礼模拟考试的一道题 (by yyt).

本文讨论生成函数暴力展开的方法 >_< 其他做法移步「6月雅礼集训 2017 Day10」quote - Galaxies

OEIS 查二维数列的方法见 Hints for Using OEIS

仿照卡特兰数, 我们来为引号序列建立状态只有一维的递推.

以下讨论中, 如未特别说明, 字符集大小默认为 .

模型转化

一个引号序列对应个元素进出栈的过程.

如: abbacc <-> a 入, b 入, b 出, a 出, c 入, c 出

但是 abbaaa 该对应以下哪一个呢? - a 入, b 入, b 出, a 出, a 入, a 出 - a 入, b 入, b 出, a 入, a 出, a 出

我们规定对应第一个. 即: 栈顶元素等于当前字符时, 选择弹栈而非压栈.

设为长度为的引号序列的个数. 考虑最后一个出栈的元素 , 设它是第个入栈的元素 (0-indexed). 它有种取值. 与是独立的, 前面的过程有种方案, 后面的过程需保证不在中途被弹出.

设为长度为的引号序列的个数, 且栈底有某个字符 , 它自始至终不能被弹出. 同样考虑 . 有种方案. 现在, 栈中只剩下 , 对于第个入栈的元素, 我们有种选择. 同样, 需要保证不在中途被弹出. 只要它不被弹出, 就不会被弹出. 因此, 有种方案.

用生成函数来表达:

解之, 得

有两根, 根据 , 我们舍去了另一个.

不知道前几天为什么觉得做到这一步就进行不下去了......

卡特兰数的生成函数为

分母有理化后, 用广义二项式定理展开根式, 进而得到闭形式. 我们来效仿这个做法.

令 , 则

还是很腌臢......值得庆幸的是, 我们并不追求一个优美的闭形式 (在 OEIS 上没找到), 只需要把它展开, 得到一个足够好算的式子.

把分子分母分别展开:

于是

又 (注意此时 )

代入, 得

上面的式子虽然不怎么漂亮, 但是计算起来挺方便, 因为二项式系数的指标并不涉及 .

撒花~