定义

记一个排列 (P) 的升高为 (k) 当且仅当存在 (k) 个位置 (i) 使得 (P_i<P_{i+1})。

那么定义欧拉数 (leftlangleegin{matrix}n\kend{matrix}ightangle) 表示长度为 (n) 且有 (k) 个上升的排列的数量。

递推式

通过讨论 (n) 在最左边，最右边还是中间可以得出转移：

[leftlangleegin{matrix}n\kend{matrix}ightangle = (k + 1)leftlangleegin{matrix}n – 1\kend{matrix}ightangle + (n – k) leftlangleegin{matrix}n – 1\k – 1end{matrix}ightangle
]

计算

高妙的组合意义

考虑计算 (leftlangleegin{matrix}n\kend{matrix}ightangle / n!) 也就是概率，可以发现，对于 (n) 个实数的均匀分布 ((a_1, a_2, cdots, a_n) in (0, 1)^n) 产生和排列 (P) 相同的偏序关系的概率是 (frac 1{n!})，这样我们就可以将问题转化为 (a_i < a_{i + 1}) 有 (k) 个的概率。

将 (a) 进行差分，定义 (a_0 = 0, b_i = (a_i – a_{i – 1}) mod 1)，显然 (b_i in (0, 1))。

考虑 (b_i) 的实际意义，发现当 (a_{i – 1} < a_i) 时，(b_i = a_i – a_{i – 1})，否则 (b_i = 1 + a_i – a_{i – 1})，而 (a_{i – 1} < a_{i}) 有 (k + 1) 个（(a_0 = 0)），所以说 (sum b_i = n – k – 1 + a_n in (n – k – 1, n – k))。这样，问题就变为了给定 (n) 个 ((0, 1)) 之间的实数 (x_1, x_2, cdots, x_n)，求满足 (sum x_i in (n – k – 1, n – k)) 的概率，可以转化为 (sum x_i < n – k) 的概率然后差分，设其为 (F(n – k))。

使用几何概型，由于样本空间的“体积”是 (1)，所以答案就是满足条件的区域的“体积”。

设 (G(k)) 表示 (n) 个随机变量没有限制的情况下的满足 (sum x_i < k) 的区域的“体积”。

考虑容斥有多少个 (x_i > 1)，能够列出式子：

[F(k) = sum_{i = 0}^k (-1)^i inom ni G(k – i)
]

接下来只需要知道如何计算 (G(k)) 即可。

将 (n) 个变量做前缀和，设为 (t_i)，那么只需要满足 (t_i < t_{i + 1}) 且 (t_n < k) 的条件即可，由最开始的性质，可以将其对应到排列上得出概率为 (frac 1 {n!})。又因为 (G(k)) 是“体积”，所以 (G(k) = frac {k^n}{n!})，即：

[F(k) = frac 1 {n!} sum_{i=0}^k (-1)^i inom ni (k – i)^n
]

于是 (leftlangleegin{matrix}n\kend{matrix}ightangle) 可以做到计算一个 (mathcal O(n))，计算一行 (mathcal O(n log n))。

直接容斥

广告

设 (F(n, k)) 表示长度为 (n) 的排列，钦定有 (k) 个 < 的方案数。

考虑将 < 看成边，那么排列中将会形成 (n – k) 个连通块，而连通块内部必须有序，连通块之间可以任意打乱顺序，所以方案数就是 ((n – k)!egin{Bmatrix} n\n – k end{Bmatrix})。

由二项式反演：

[egin{aligned}
leftlangleegin{matrix}n\kend{matrix}ightangle &= sum_{i = k}^n (-1)^{i – k} inom ik (n – i)!egin{Bmatrix} n\n – i end{Bmatrix}\
&=sum_{i = k}^n (-1)^{i – k} inom ik sum_{j = 0}^{n – i} inom{n – i} j (-1)^{n – i – j} j^n\
&=sum_{j = 0}^{n – k} j^n (-1)^{n – k – j} sum_{i} inom ik inom {n – i}j\
&= sum_{j = 0}^{n – k} (-1)^{n – k – j} j^n inom {n + 1} {k + j + 1}
end{aligned}
]

解释一下最后一步吧，由于 (inom ik = [x^{i – k}] frac 1{(1 – x)^{k + 1}}, inom {n – i}j = [x^{n – i – j}] frac 1{(1 – x)^{j + 1}})，所以 (sum_i inom ik inom {n – i}j = [x^{n – j – k}] frac 1 {(1 – x)^{k + j + 2}} = inom {n + 1}{k + j + 1})。

同样可以直接卷积求出一行欧拉数。