欧拉数（Genshining）

标签：right matrix Genshining sum rangle binom 欧拉 left

欧拉数

记 \(\left\langle \begin{matrix} n\\k \end{matrix} \right\rangle\) 为 \(n\) 阶排列 \(p[1:n]\) 中有 \(k\) 个 \(p[i]<p[i+1](i<n)\) 的数量。

基础公式和欧拉数·行

有 \(\left\langle \begin{matrix} n\\k \end{matrix} \right\rangle=\left\langle \begin{matrix} n\\n-k-1 \end{matrix} \right\rangle\)。显然，我们把上升改为下降，再令 \(n-k-1\to k\)，得到的排列应当构成双射。

仍然考虑增量法构造递推式。

新加最大的数，不构成上升的可能是插在上升中间或者第一个，构成的可能则是其他任何位置。那么递推公式就得出了。

\[\left\langle \begin{matrix} n\\m \end{matrix} \right\rangle=(m+1)\left\langle \begin{matrix} n-1\\m \end{matrix} \right\rangle+(n-m)\left\langle \begin{matrix} n-1\\m-1 \end{matrix} \right\rangle \]

下面使用归纳法证明其通项公式：

\[\left\langle \begin{matrix} n\\m \end{matrix} \right\rangle=\sum_{k=0}^m\binom{n+1}{k}(m-k+1)^n(-1)^k \]

考虑加法公式的右侧展开：

\[(m+1)\sum_{k=0}^m\binom{n}{k}(m-k+1)^{n-1}(-1)^k+(n-m)\sum_{k=0}^{m-1}\binom{n}{k}(m-k)^{n-1}(-1)^k\\ =\sum_{k=0}^m\binom{n}{k}[(m+1)(m-k+1)^{n-1}(-1)^k+(n-m)(m-k)^{n-1}(-1)^k]\\ =\sum_{k=0}^m\binom{n}{k}[(m-k+1)^{n}(-1)^k+\frac{k}{m-k+1}(m-k+1)^{n}(-1)^k+(n-m)(m-k)^{n-1}(-1)^k]\\ =\sum_{k=0}^m\left(\binom{n}{k}+\binom{n-1}{k}\right)(m-k+1)^n(-1)^k\\ +\left(\frac{k}{m-k+1}-\frac{k}{n-k+1}\right)(m-k+1)^n(-1)^k\\ +\sum_{k=0}^m(n-m)(m-k)^{n-1}(-1)^k\binom{n}{k}\\ =\sum_{k=0}^m\binom{n+1}{k}(m-k+1)^n(-1)^k+\frac{k(n-m)}{n-k+1}\binom{n}{k}(m-k+1)^{n-1}(-1)^k\\ +\sum_{k=0}\binom{n}{k-1}(n-m)(m-k)^{n-1}(-1)^k\\ =\sum_{k=0}^m\binom{n+1}{k}(m-k+1)^n(-1)^k+0\\ =\sum_{k=0}^m\binom{n+1}{k}(m-k+1)^n(-1)^k\\ \]

至此，我们可以用卷积

\[f=gh,g_k=(k+1)^n,h_k=\binom{n+1}{k}(-1)^k \]

计算之。

值得一提的是，还有一种有趣的计算方法：

设 \(x_1,x_2,\dots,x_n\) 是均匀分布在 \((0,1)\) 上的实随机变量。可以发现，由于 \(\forall i\neq j,P(x_i=x_j)=0\)，所以根据其大小关系得到排列是均匀的。

设 \(y_i=(x_i-x_{i-1}+1)\bmod 1\)，容易证明，\(\{y\}\) 和 \(\{x\}\) 构成双射。而 \(\sum y_i= x_n+n-k-1\in(n-k-1,n-k)\)，\(k\) 为“上升“的个数。

考虑统计概率（最后再用 \(n!\) 乘起来即可）。 只需要求得 \(\sum y_i\in(n-k-1,n-k)\) 的概率。事实上可以先统计 \(\sum y_i<n-k\) 的概率再做差分。

考虑形式上我们虽然是求概率，但是考虑扩展为“测度”

考虑这样的一列随机变量： \(z_i=\sum _{j\le i}y_j\)，若抛开 \(y_i<1\) 的限制，显然其在 \(n\) 维空间 \((0,0,\dots,0)\to (1,1,\dots,1)\) 的测度为 \(\dfrac{(n-k)^n}{n!}\)，分母是因为要求 \(z\) 有序。

如果令 \(p\) 个 \(y_j\) 强制 \(\ge1\)，发现其测度为 \(\dfrac{(n-k-p)^n}{n!}\) 。进行容斥，得出答案为：

\[\left\langle \begin{matrix} n\\k \end{matrix} \right\rangle=n!\sum_{p=0}^{n-k} \frac{(-1)^p\binom{n}{p}(n-k-p)^n}{n!}-n!\sum_{p=0}^{n-k-1} \frac{(-1)^p\binom{n}{p}(n-k-p-1)^n}{n!}\\ =\sum_{p=0}^{n-k} (-1)^p\binom{n}{p}(n-k-p)^n-\sum_{p=0}^{n-k-1} (-1)^p\binom{n}{p}(n-k-p-1)^n=\left\langle \begin{matrix} n\\n-k-1 \end{matrix} \right\rangle\\ \]

所以

\[\left\langle \begin{matrix} n\\m \end{matrix} \right\rangle=\sum_{p=0}^{m+1}(-1)^p \binom{n}{p}(m-p+1)^n-\sum_{p=0}^m(-1)^p\binom{n}{p}(m-p)^n\\ =\sum_{p=0}^{m+1}(-1)^p \binom{n+1}{p}(m-p+1)^n-\sum_{p=1}^{m+1}\binom{n}{p-1}(-1)^p(m-p+1)^n-\sum_{p=0}^m(-1)^p\binom{n}{p}(m-p)^n\\ =\sum_{p=0}^{m+1}(-1)^p \binom{n+1}{p}(m-p+1)^n \]

Worpitzky 恒等式

\[x^n =\sum_k\left\langle \begin{matrix} n\\k \end{matrix} \right\rangle\binom{x+k}{n} \]

证明:

容易得知：

\[x\binom{x+k}{n}=(k+1)\binom{x+k}{n+1}+(n-k)\binom{x+k+1}{n+1} \]

然后发现拆开右式的

\[\binom{x+k}{n} \]

就可以归纳证明。

借助此恒等式，我们可以知道一阶欧拉数和斯特林数的关系：

对 Worpitzky 恒等式两边求 \(x\) 的 \(m\) 阶有限微积分得到：

\[\Delta^m(x^n)\mid_{x=0}=\Delta^m\left(\sum_k\left\langle \begin{matrix} n\\k \end{matrix} \right\rangle\binom{x+k}{n}\right)\mid_{x=0}\\ \sum_i \binom{m}{i}i^n(-1)^{m-i}=\sum_k\left\langle \begin{matrix} n\\k \end{matrix} \right\rangle\binom{k}{n-m}\\ \sum_k\left\langle \begin{matrix} n\\k \end{matrix} \right\rangle\binom{k}{n-m}=m!{n\brace m}\\ \]

用哑元 \((z-1)^{n-m}\) 乘上两边并对 \(m\) 求和，可得出欧拉数的行生成函数。

\[\sum_k\left\langle \begin{matrix} n\\k \end{matrix} \right\rangle z^k=\sum _k{n\brace k}k!(z-1)^{n-k} \]

令两边 \(\forall k,[z^k]\text{LHS}=[z^k]\text{RHS}\)，得出

\[\left\langle \begin{matrix} n\\m \end{matrix} \right\rangle=\sum_k{n\brace k}\binom{n-k}{m}(-1)^{n-m-k}k! \]

在此处 我们发现了另一个公式：

\[\left\langle \begin{matrix} n\\m \end{matrix} \right\rangle=\sum_{k=0}^n\binom{n+1}{k+m+1}(-1)^{n-k-m}k^n \]

证明方法是把组合数用上指标范德蒙德卷积展开。

二阶欧拉数

\(\left\langle\left\langle \begin{matrix} n\\m \end{matrix} \right\rangle\right\rangle\) 定义为多重集 \(\{1,1,2,2,\dots,n,n\}\) 排列中满足以下条件的个数：

\[\sum_{i=1}^{2n-1} [p_i<p_{i+1}]=m \]

2.\(\forall a\in[1,n]\)，\(a\) 的两次出现位置之间的数都大于 \(a\)。

增量法容易知道，

\[\left\langle\left\langle \begin{matrix} n\\m \end{matrix} \right\rangle\right\rangle=(m+1)\left\langle\left\langle \begin{matrix} n-1\\m \end{matrix} \right\rangle\right\rangle+(2n-m-1)\left\langle\left\langle \begin{matrix} n-1\\m-1 \end{matrix} \right\rangle\right\rangle \]

标签：right,matrix,Genshining,sum,rangle,binom,欧拉,left
From： https://www.cnblogs.com/british-union/p/eulerian.html