球坐标下Laplace算子的公式

前几天给人找了几道微积分题目,里面有一个是计算球坐标下面的Laplace算子的表达式。这当然可以暴力用复合函数的求导来算,但是可能比较复杂。事实上可以有一种积分的办法来算出这个结果。

我们知道,在标准坐标下,Laplace算子的形式为

 \Delta u = \frac{\partial^2u}{\partial x^2} + \frac{\partial^2u}{\partial y^2} + \frac{\partial^2u}{\partial z^2}

现在计算在球坐标

\begin{cases}
x = r\sin\theta\cos\varphi \\
y = r\sin\theta\sin\varphi \\
z = r\cos\theta
\end{cases}

下Laplace算子的表达式。首先计算其Jacobi矩阵

 \frac{\partial(x, y, z)}{\partial(r, \theta, \varphi)} = \begin{pmatrix}
\sin\theta\cos\varphi & \sin\theta\sin\varphi & \cos\theta \\
r\cos\theta\cos\varphi & r\cos\theta\sin\varphi & -r\sin\theta \\
-r\sin\theta\sin\varphi & r\sin\theta\cos\varphi & 0
\end{pmatrix}^T

对应逆矩阵为

 \frac{\partial(r, \theta, \varphi)}{\partial(x, y, z)} = \begin{pmatrix}
\sin \theta\cos\varphi & \sin\theta\sin\varphi & \cos\theta \\
\frac{1}{r}\cos\theta\cos\varphi & \frac{1}{r}\cos\theta\sin\varphi & -\frac{1}{r}\sin\theta \\
-\frac{\sin\varphi}{r\sin\theta} & \frac{\cos\varphi}{r\sin\theta} & 0
\end{pmatrix}

注意到这是一个正交矩阵。

我们利用Laplace算子的积分表达式,考虑

 \begin{aligned}\frac{ \partial{u(r, \theta, \varphi)}}{\partial(x, y, z)} \cdot \frac{\partial{v(r, \theta, \varphi)}}{\partial(x, y, z)} &= \frac{\partial{u(r, \theta, \varphi)}}{\partial(r, \theta, \varphi)}\frac{\partial(r, \theta, \varphi)}{\partial(x, y, z)}^T\frac{\partial(r, \theta, \varphi)}{\partial(x, y, z)}\frac{\partial{v(r, \theta, \varphi)}}{\partial(r, \theta, \varphi)} \\ &= u_rv_r + \frac{1}{r^2}u_\theta v_\theta + \frac{1}{r^2\sin^2\theta}u_\varphi v_\varphi \end{aligned}

对于任意的$v \in C_c^\infty$,利用分部积分

 \begin{aligned}
\int \Delta u v dxdydz &= -\int \nabla u \cdot \nabla v dxdydz \\
&= -\int \left( u_r v_r + \frac{1}{r^2} u_\theta v_\theta + \frac{1}{r^2\sin^2\theta}u_\varphi v_\varphi \right) r^2\sin\theta drd\theta d\varphi \\
&= \int \left( \left (u_r r^2\sin\theta \right )_r + ( u_\theta \sin\theta )_\theta + u_{\varphi\varphi} \right) v drd\theta d\varphi \\
\end{aligned}

再根据

 \int \Delta u v dxdydz = \int \Delta u v r^2\sin\theta drd\theta d\varphi

这样就可以得到

 \begin{aligned}
\Delta u &= \frac{1}{r^2\sin\theta}\left( \left (u_r r^2\sin\theta \right )_r + ( u_\theta \sin\theta )_\theta + u_{\varphi\varphi} \right) \\
&= \frac{1}{r} \frac{\partial^2}{\partial r^2}(ru) + \frac{1}{r^2\sin \theta} \frac{\partial}{\partial \theta}\left( \sin \theta \frac{\partial u}{\partial \theta} \right) + \frac{1}{r^2\sin^2 \theta} \frac{\partial^2 u}{\partial \varphi^2}
\end{aligned}

Pólya’s Urn

Pólya’s Urn是这样一个模型:假设现在有一个盒子,里面有r个红球和g个绿球,现在不断地随机从盒子取出一个球,之后再放回去,外加放入额外的c个和取出的球颜色相同的球。现在问,盒子中绿色球的比例在最后是否会趋向与某个分布?

实际上最后这个比例会是一个参数是g/cr/c的Beta分布。

首先我们设S_n = r + g + nc是第n次操作后盒子中所有球的数目。再设G_n, R_n分别是第n次操作后盒子中绿色球、红色球的数目。以及令X_n = G_n / S_n, \mathcal F_n = \sigma(G_k, S_k, 0 \leq k \leq n)。计算条件期望

 \begin{aligned}
\mathbb E[G_{n+1} | \mathcal F_n] &= \frac{G_n}{S_n}(G_n + c) + \frac{R_n}{S_n}G_n \\
&= (c + S_n) X_n = S_{n+1} X_n
\end{aligned}

可以看出\mathbb E[X_{n+1}|\mathcal F_n] = X_n\{X_n\}是一个鞅。再由于0\leq X_n \leq 1,我们知道X_n几乎处处收敛到一个随机变量X。现在考虑其分布。

首先可以计算出在第n步及以前,有m \leq n次取出绿色球的概率,并且写为紧凑的形式如下

 \begin{aligned}
&\mathbb P\left[ X_n = \frac{mc + g}{nc + g + r} \right] \\&= \frac{n!}{m!(n-m)!}\cdot \frac{\displaystyle\prod_{k=0}^{m-1}(k + g/c) \prod_{k=0}^{n - m - 1}(k + r/c)}{\displaystyle\prod_{k=0}^{n - 1}(\frac{g+r}{c} + k)}\\&= \frac{\Gamma(n + 1)}{\Gamma(m + 1)\Gamma(n - m + 1)}\cdot \frac{\Gamma(m + g/c)\Gamma(n - m + r/c)}{\Gamma(n + (g + r)/c)\text{B}(r/c, g/c)}
\end{aligned}

其中\Gamma\text{B}分别是Gamma函数和Beta函数。

接下来利用Stirling公式\Gamma(x) = \sqrt{2\pi/x} (x/e)^x (1 + O(1/x)),可以得到

 \frac{\Gamma(x + a)}{\Gamma(x + b)} = x^{a - b} \left( 1 + O\left( \frac{1}{x} \right) \right)\text{ as } x \to \infty

那么对于固定的\alpha, \beta, m满足0 < \alpha < \beta < 1以及\alpha n < m < \beta n,可以有

 \begin{aligned}
&\mathbb P\left[ X_n = \frac{mc + g}{nc + g + r} \right] \\&= \frac{1}{\text{B}(r/c, g/c)} n^{1 - (g + r)/c} (n - m)^{r/c - 1} m^{g/c - 1} \left( 1 + O\left( \frac{1}{n} \right) \right)\\
&= \frac{1}{n \text{B}(r/c, g/c)} \left (1 - \frac{m}{n} \right )^{r/c - 1} \left( \frac{m}{n} \right)^{g/c - 1} \left( 1 + O\left( \frac{1}{n} \right) \right)
\end{aligned}

对于所有满足\alpha n < m < \beta nm求和

 \lim_{n\to \infty} \mathbb P[\alpha \leq X_n \leq \beta] = \frac{1}{\text{B}(r/c, g/c)}\int_{\alpha}^\beta (1 - x)^{r/c - 1}x^{g/c - 1} dx

最后可以得到X的分布是\text{Beta}(g/c, r/c)

三维空间中的旋转:旋转矩阵、欧拉角

考虑这样一个问题:如何计算三维空间中一个点绕着某一条向量旋转一个特定角度之后的坐标?旋转矩阵、欧拉角和四元数都是用来解决这个问题的方法。关于四元数的内容可以看平面等距变换、三维空间的旋转和四元数

接下来我们来讨论一下旋转矩阵和欧拉角这两个方法,并且我们选取右手坐标系作为我们的坐标系。

旋转矩阵

首先,对于一个三维空间的点 P(x, y, z),要将其绕 z 轴旋转 \theta 角度是可以很简单地用旋转矩阵来表示的

 \begin{equation}
R_z(\theta) =
\begin{bmatrix}
\cos \theta & -\sin \theta & 0 \\
\sin \theta & \cos \theta & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\end{equation}

类似地,绕另外两个坐标轴旋转的矩阵可以表示如下(注意 R_y 有些不同)

 \begin{equation}
R_x(\theta) =
\begin{bmatrix}
1 & 0 & 0 \\
0 & \cos \theta & -\sin \theta \\
0 & \sin \theta & \cos \theta \\
\end{bmatrix}
\end{equation}

\begin{equation}
R_y(\theta) =
\begin{bmatrix}
\cos \theta & 0 & \sin \theta \\
0 & 1 & 0 \\
-\sin \theta & 0 & \cos \theta \\
\end{bmatrix}
\end{equation}

对于这三个特殊的旋转轴我们已经有了解决方案了,那么对于任意的轴 p 要怎么办呢?我们可以将这个旋转分解:

  • 将整个坐标轴旋转,使得旋转轴 pz 轴重合
  • 再将点 Pz 轴旋转 \theta
  • 再将整个坐标轴旋转回原位

3d-angle-rotation-matrix

如图,我们可以用两个角 \phi\psi 表示一个旋转轴的位置(这里认为旋转轴是个单位向量

 \begin{equation}
\left \{ \begin{aligned}
x &= \sin \phi \cos \psi \\
y &= \sin \phi \sin \psi \\
z &= \cos \phi
\end{aligned} \right.
\end{equation}

这样整个旋转就可以表示如下(最先进行的旋转它对应的旋转矩阵在最右侧)

R_z(\psi)R_y(\phi)R_z(\theta)R_y(-\phi)R_z(-\psi)

或者利用 R(-\alpha) = R^{-1}(\alpha) = R^T(\alpha),可以改写为

R_z(\psi)R_y(\phi)R_z(\theta)R_y^T(\phi)R_z^T(\psi)

经过化简,就可以得到最终的旋转矩阵

\begin{equation}
\begin{bmatrix}
\cos \theta + x^2(1 - \cos \theta) & xy(1 - \cos \theta) - z\sin \theta & xz(1 - \cos \theta) + y\sin \theta \\
yx(1 - \cos \theta) + z\sin \theta & \cos \theta + y^2(1 - \cos \theta) & yz(1 - \cos \theta) - x\sin \theta \\
zx(1 - \cos \theta) - y\sin \theta & zy(1 - \cos \theta) + x\sin \theta & \cos \theta + z^2(1 - \cos \theta)
\end{bmatrix}
\end{equation}

我们将旋转矩阵左乘需要旋转的向量就可以得到旋转后的结果了!

旋转矩阵一个很方便的地方是它可以沿着任意轴任意角度的旋转,但是,旋转矩阵缺点是它需要有 9 个元素来表示一个旋转,而且矩阵的乘法也比较慢。

欧拉角

euler-angle

欧拉角是用三个旋转角度 \alpha, \beta, \gamma 来标示旋转的。如图,图中蓝色坐标系是起始的坐标系,红色的坐标系是最后旋转完成的坐标系。整个旋转分为三个步骤:

  • 将坐标系绕 z 轴旋转 \alpha
  • 将旋转后坐标系绕自己本身的 x 轴(也就是图中的 N 轴)旋转 \beta
  • 将旋转后坐标系绕自己本身的 z 轴旋转 \gamma

由于绕不同的轴旋转所得到的欧拉角是不同的,所以欧拉角在使用的时候必须要先指明旋转的顺序,这里使用的是“zxz”的顺序。

欧拉角表示的旋转转换成旋转矩阵就是

 \begin{equation} R_z(\alpha)R_x(\beta)R_z(\gamma) \end{equation}

需要注意,这里的后面两次旋转并不是在原本固定的坐标系下的旋转。在旋转矩阵中,每一次旋转的叠加都是在左边乘上对应的旋转矩阵,然而,在这里乘法的顺序是相反的。

这可以这样来理解,假设最原始的固定的坐标系是 C_0

  • 假设有一个和 C_0 重合坐标系 C_3,先将 C_3C_0z 轴旋转 \gamma
  • 假设有一个和 C_0 重合坐标系 C_2,将 C_2 和前一步旋转后的 C_3 一起绕 C_0x 轴旋转 \beta
  • 假设有一个和 C_0 重合坐标系 C_1,将 C_1 和前一步旋转后的 C_2, C_3 一起绕 C_0z 轴旋转 \alpha

然后我们仅看这三个坐标系的关系:C_0 绕自己的 z 轴旋转 \alpha 角就可以和 C_1 重合;C_1 绕自己的 x 轴旋转 \beta 角可以和 C_2 重合,这是因为 C_1C_2 在最后一步是一起旋转的,它们的相对位置不会改变;同样可以知道 C_2 绕自己的 z 轴旋转 \gamma 角就可以和 C_3 重合。

在这里 C_1, C_2 相当于是前面欧拉角旋转的前两步得到的坐标系。

这样的话从 C_0C_3 的变换就相当于之前欧拉角的旋转变换,因此按照这个过程,旋转矩阵就是按照上面的顺序相乘了。

反演魔术:反演原理及二项式反演

首先我来说说什么是反演(inversion),对于一个数列\{f_n\}来说,如果我们知道另外一个数列\{g_n\},满足如下条件

 g_n = \sum_{i=0}^n a_{ni}f_i

反演过程就是利用 g_0, g_1, \cdots, g_n 来表示出 f_n

 f_n = \sum_{i = 0}^n b_{ni}g_i

本质上来说,反演其实是一个解线性方程组的过程,但是你观察后发现,这个矩阵实际上是一个三角矩阵,那必然存在着快捷的方法。对于使得这两个反演公式成立的这些系数应该满足什么条件呢?我们现在就来探讨一番!

我们首先讨论一下在什么情况下能够比较容易建立反演公式,之后介绍二项式反演以及它的两个应用,其中一个是错位排列问题

Read More

特殊多项式在整点上的线性插值方法

首先我来解释一下题目是什么东西,假如给你一个 k 次多项式 P(x),并且已知了 P(0), P(1), \cdots, P(k),要求计算出 P(n), n \in \mathbb N 的值,由于已经知道了 k + 1 个点值,那么要插值出系数是可以在 \mathcal O(k^2) 完成,如果使用 FFT 的话是可以在 \mathcal O(k \log^3 k) 的时间内完成的[1],但是对于这个特别的问题,我们有一个 \mathcal O(k) 的算法!这好像是杜教先提出来的,然后还有这篇文章

Read More

Catalan 数列及其应用

卡特兰数(Catalan number)是组合数学中一个重要的计数数列,在很多看似毫不相关地方都能见到它的身影

这篇文章介绍卡特兰数的几个应用以及它的推导过程,从组合推理和生成函数两个方面来推导出 Catalan 数的公式

带限制条件的路径总数

首先我们来看一个问题:

在一个平面直角坐标系中,只能往右或往上走一个单位长度,问有多少种不同的路径可以从左下角 (1, 1) 走到右上角 (n, n),并且要求路径不能经过直线 y = x 上方的点,下图中的路径都是合法的(图片来源 Wikipedia)

450px-Catalan_number_4x4_grid_example.svg

如果没有限制条件,那么从左下角走到右上角一共有 2n 步,有 n 步是往右,另外 n 步是往上,那么路径方案数就是 2n 步中选择 n 步往右,一共有 {2n} \choose {n} (即 C_{2n}^n)种方案

那么我们考虑一下这里面有多少种方案是不合法的

首先对于每一种不合法的方案,它的路径一定与 y = x + 1 有交。我们找到它与 y = x + 1 的第一个交点,然后将这个点后面部分的路径关于 y = x + 1 做一个对称。由于原来路径到达 (n, n),新的对称之后的路径就会到达 (n - 1, n + 1)。这样我们把每一种不合法方案都对应到了一条从 (1, 1)(n - 1, n + 1) 的路径,现在再来看是否每一条这样的路径都能对应到一种不合法方案,如果是,那么这就建立了一个一一映射的关系,也就是它们的方案总数相同。这是肯定的,因为每一条这样的路径必定与 y = x + 1 有交,那么对称回去,就得到一条不合法方案

由于从 (1, 1)(n - 1, n + 1) 的路径有 {n - 1 + n + 1} \choose {n - 1} 条,那么合法的方案就是

 C_n = {{2n} \choose {n}} - {{2n} \choose {n - 1}} = \frac{1}{n + 1} {{2n} \choose {n}}

我们把这个方案数记为 C_n,这就是著名的 Catalan 数

Read More

Codeforces 上的一些组合计数问题

Codeforces 15E. Triangles

Problem:给出一个有规律的金字塔(如图),黑色的边是可以走路径,要求求出包含 H 点的简单回路(不经过一个顶点两次)的条数,并且这个回路围住的部分不可以包含灰色的三角形,答案对 10^9+9 取模,其中 n \leq 10^6,并且一定是一个偶数

5945210be972aa5fe947f3b8a3a0378a4cade844

Example:当 n = 2 时,一共有 10 种方案,其中 5 种是这样,另外的是顺时针顺序地走

5E-triangles

Solution:首先第 1 层是最特殊的,因为这里没有灰色的三角形,然后注意到灰色的部分把整个金字塔分成了左部和右部

5E-triangles-level1

路径现在可以分成三个部分

  • 在第一层移动,这一共 10 种(见样例)
  • 进入左部或右部后直接回到 H
  • 进入左部(右部)后经过 E 点进入右部(左部)

对于第二种情况,在第一层的部分走法可以是(只有逆时针部分,实际上有 8 种)

  • A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow C \rightarrow A
  • A \rightarrow B \rightarrow D \rightarrow \text{LeftPart} \rightarrow E \rightarrow F \rightarrow C \rightarrow A
  • A \rightarrow B \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A
  • A \rightarrow B \rightarrow D \rightarrow E \rightarrow \text{RightPart} \rightarrow F \rightarrow C \rightarrow A

对于第三种情况,在第一层(原来图中的两层现在算一层,也就是下面的 n 是题目中 n\frac{1}{2})的部分走法有 2 种,左部到右部和右部到左部

现在要统计的就是在左部和右部内有多少种方案,因为左部右部对称,所以答案是一样的,我们来考虑左部

S_n 表示在有 n 层的金字塔中,走左部的方案数,因为走进左部后每一层都会遇到凹进去的部分,这部分只要枚举一下走了多远可以统计出第 n 层一共有 2\sum_{i=1}^{n-2} 2^i + 1 = 2^n - 3 这么多的情况

然后要走到第 n 层后就是 \prod_{i=2}^{n} (2^i - 3) 种情况,然后走回去的路径有 4 种选择,因此

 S_n = \sum_{i=2}^{n} 4\prod_{j=2}^i (2^j - 3)

答案是 2S_n^2 + 8S_n + 10 Read More

牛顿迭代法在多项式运算的应用

总算是快把 FFT 和生成函数的各种东西补了好多,膜拜策爷的论文和 Picks 的博客 QAQ

这篇文章大概就是说如何用牛顿迭代法来解满足 G(F(z)) \equiv 0 \pmod {z^n}F(z)

然后这东西可以比较方便地计算 \sqrt{A(z)}e^{A(z)},也就是多项式开根、求指数对数之类鬼畜的东西,在生成函数计数中十分有用

顺便一提,这里说的“多项式”实际上你可以直接理解为生成函数或者形式幂级数

Read More

多项式的多点求值与快速插值

多项式的多点求值(multi-point evaluation)是给出一个多项式 A(x),和 n 个点 x_0, x_1, \cdots, x_{n-1},要求求出 A(x_0), A(x_1), \cdots, A(x_{n-1})

相反的,多项式的插值(interpolation)是给出 n+1 个点 (x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n),求出一个 n 次多项式,使得这些点都在这个多项式上

这两个问题实际上是在多项式的点值表示(point-value representation)和系数表示(coefficient representation)之间转换的方法,在快速傅里叶变换中由于带入值的特殊性质,可以在 \mathcal O(n\log n) 的之间内将两种东西互相转换,但是,如果是任意给定点要求求值或者插值,就没有比较好的性质可以利用,但是仍然有比较快速的方法来计算它们

Read More