李辰剑 2024-7-23

---

近日担任《离散数学》助教，批阅期末考卷的时候发现最后一题有许多等价答案，涉及大量组合数的推导与化简。于是我捡起了自高中以后尘封多年的组合数知识，略加推导后整理得出了这篇文章，以供日后参考。同时，也希望这篇文章能帮助到有需要的老师和同学们。

记号约定

本文假设读者有基本的组合数学知识，熟悉组合数 $C_n^k$ 的解析表达式：

$$\newcommand\C[2]{C_{ #1}^{ #2}} \C nk\equiv\binom{n}{k}=\frac{n!}{k!(n-k)!}\tag{0.1}$$

组合数/二项式系数有两种主流的记号，除了上述的 $C_n^k$，还有一种表达 $\binom{n}{k}\equiv \C nk$，后一种记号主要用在高等数学和二项式系数中。本文中主要采用前一种记号。

文中不加说明时，参数（$m,n,k…$）默认都是自然数。

研究方法：多项式

除了组合数，本文还需要读者熟悉多项式的基本用法。读者也许会有些疑惑，明明是学习组合数学，为什么需要熟悉多项式呢？事实上，组合数与多项式之间有着非常深刻的联系。

考察整幂次的二项式展开：

$$\newcommand\S[2]{\sum_{ #1=0}^{ #2}} \newcommand\Sn[1]{\sum_{ #1=0}^{n}} \newcommand\Skn{\sum_{k=0}^{n}} \newcommand\Snk\Skn (a+b)^n=\Snk \C nka^kb^{n-k} \tag{0.2}$$

你会发现，在左边全部展开后（合并同类项之前）得到的的 $2^n$ 个单项式里，恰好有 $\C nk$ 个 $a$ 的幂次为 $k$ 的项，因此等式右边对应的系数刚好就是 $\C nk$。多项式乘法展开后的合并同类项刚好是一次单项式的计数过程。当然，这样的例子还有许多。从多项式出发研究组合数将为我们提供新的视角，而且令许多代数（algebraic）方法成为可能。

多项式和组合数之间有着千丝万缕的联系，而采用多项式研究组合数的方法也将贯穿本文的始终。

第一组恒等式：横向求和

1. 全部横向和

由

$$2^n=(1+1)^n=\Snk\C nk \cdot 1^n\cdot 1^{n-k}=\Snk\C nk \notag$$

我们可以得到：

$$\label{eq:sum_C}\tag{1.1} \boxed{\Snk\C nk=2^n}$$

这是我们的第一个恒等式，我称之为横向全部和。

李辰剑 2023-6-16 定稿

一、问题引入

《戴森球计划》相信大家都很熟悉啦，它是一款科幻主题的模拟经营游戏。在《戴森球计划》中，玩家需要在宇宙中采集材料、解锁科技、进行工业生产，最终建造出一个包裹恒星的戴森球，通过戴森球大量收割恒星的太阳能。然而，《戴森球计划》中科技产品的生产和建造极其复杂（配方很复杂，供应链更复杂）；而建造整个戴森球（包裹整个恒星，物资消耗能不大吗）又需要大量物资，对生产的规模和效率提出了很高的要求。因此，玩家常常需要花费大量时间来设计、建造、调整各种科技产品的生产线，非常痛苦。这也是《戴森球计划》被许多玩家诟病“费肝”的原因。

于是我就想，能否用计算机科学中一些成熟的优化算法来帮忙设计生产线呢？我初步筛选出了三个可以用计算机算法优化的任务：

(1) 用线性规划求解最优的资源、产品分配。《戴森球计划》中的产业链很长，一些产品的生产配方较为复杂，需要经过多道生产步骤。例如，以下是低阶科技产品电动马达的生产线路图：

如何合理分配资源（例如，以合适的比例将铁矿分配到铁块和磁铁的生产中）以最大化目标产出（例如，最大化马达的生产速率）是一个麻烦的问题。但这一步骤恰好可以用线性规划（Linear Programming）模型求解。

(2) 用集成芯片设计算法优化工厂和物流的布局布线。 《戴森球计划》中的工厂输入输出和布局可以非常复杂… 其实这和集成芯片物理设计中的元件布局和布线有许多相似之处。

(3) 用非线性模型优化工厂位置和物流。这个我懂，区位条件嘛！哪颗星球铁矿多、就着重生产钢铁、马达；哪颗星球石油多，就着重搞能源工业和石油化工。如果有市场经济，每个工厂的厂长就会自己搬去离原料最近的工厂，从而最小化物流开销。——可惜《戴森球计划》中的所有生产都由玩家一人负责，因此需要玩家自己优化所有工厂的位置，相当繁琐。如果能写出一个目标函数，以工厂选址为输入变量变量、以物流成本为函数值、再对该函数进行最优化，就可以得到最优的工厂选址，从而将玩家从繁琐的工厂规划中解放出来。

虽然三个想法都很诱人，但是布局布线和非线性优化都过于复杂…… 于是我决定先尝试基于线性规划的想法(1)。也许以后可以试试另两个想法 :-)

---

李辰剑
初稿 2021-3-16
修改&完成 2022-6-23

---

Contents

• 引入
• 求解最简单的两项
• 利用递推求解所有高斯积分
• 一点点的进一步讨论
• 附录：$n\le9$时的高斯积分

引入

高斯积分是形如

$$\newcommand\dd{\mathrm d} \newcommand\lam{\lambda} \newcommand\intr{\int_0^\infty} \newcommand\ker{e^{-\lam x^2}} \intr x^n \ker\dd x \tag{1}$$

的定积分（严格来说是广义积分）。它的核心是$e^{-\lam x^2}$在$[0,+\infty)$上的积分，再辅以幂函数$x^n$作为佐料。这个式子看上去有些复杂，却在各种工程计算、数学推导中有着广泛的应用。例如，在麦克斯韦气体速率分布律

$$p_{\mathrm{M.B.}}(v)=c\cdot v^2\exp\left(-\frac{ mv^2}{2k_BT}\right)\tag{2}$$

中，为了计算出前面的归一化系数$c$，就需要对后面的部分进行积分，相当于计算$n=2$时的高斯积分。

在温度$T$下，达到热平衡的理想气体中气体分子的「速率」会满足一定的「统计规律」。
麦克斯韦气体速率分布是指：气体分子的速率为$v$的概率即为上述的$p(v)$.

又如，在大家耳熟能详的高斯分布

$$p_{\mathrm{Gaussian}}(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}\tag{3}$$

中，为了计算出前面的归一化系数$1/\sqrt{2\pi}\sigma$，也需要对后面的部分进行积分，然后调整前面的系数使得概率密度函数在全空间的积分为1.这相当于计算$n=0$时的高斯积分：

$$1=\int_{-\infty}^{+\infty}p(x)\dd x=\boxed{\cdots}\times\int e^{-\frac{(x-\mu)^2}{2\sigma^2}}\dd x=\boxed{\cdots}\times\sqrt{2\pi}\sigma\notag \\ \implies\boxed{\cdots}=\frac 1{\sqrt{2\pi}\sigma}$$

怎么感觉都是在计算归一化系数啊喂0.0

S=1/p+1/p^2+…的各种求法

StarSky 2021-9-1

---

这是我的一个B站视频的补充材料，不过您愿意的话，直接读文章也可以。

B站视频传送门：1/3+1/9+…=1/2 ？？【manim练习作|一定要看到6分10以后】

---

初中时，有一天早上我坐在马桶上考虑起了这样一个问题：

$$\label{prob_3_series} \frac13+\frac19+\cdots=?\tag{1}$$

在脑海中一通想象猜出答案$1/2$之后，我也不知道怎么证明，便没了主意。

进一步地，由于：

$$\frac12+\frac14+\cdots+\frac1{2^n}=1-\frac1{2^n}\\ \Rightarrow\frac12+\frac14+\cdots=1-\frac1{2^\infty}=1=\frac11\tag{2}$$

我猜想，会不会有

$$\frac1p+\frac1{p^2}+\cdots=\frac1{p-1},\forall (p\in\mathbb{Z})\land (p>1)\tag{3}$$

呢？

后来我去找初中数学老师，可她告诉我：

“很多年没有处理极限了，我也不记得怎么做了。”

于是只好作罢。不过她当时在草稿纸上龙飞凤舞的极限符号，倒是对我产生了很深的影响——我如今还在用她的花体写极限符号。

近日为了这个问题做视频，结果除了了高中数列的标准做法，还发现了好多不同的解法。由于并不是每个解法都适合做成动画，因此多余的解法我就写到这篇博文里了。在视频中出境的是前两个解法。

I.标准解法

高中数列中的标准解法。

结论（等比数列的求和公式） 对于等比数列$a_n=a_1q^{n-1}(n\in\mathbb N)$,前$n$项和为

$$\begin{align*} S_n&=a_1+a_2+\cdots+a_n\\ &= \left\{\begin{array}{ll} a_1\frac{1-q^n}{1-q} &q\neq1\\ na_1 &q=1. \end{array}\right. \end{align*}\tag{4}$$

证明$ q=1$的情况是显然的。下面考虑$q\neq1$的情况：

$$\begin{align*} S_n&=a_1+a_2+\cdots+a_n\\ &=a_1+a_1q+\cdots+a_1q^{n-1}\\ &=a_1(1+q+\cdots+q^{n-1}) \end{align*}\label{S_def}\tag{5}$$

于是我们需要对后面括号中的因子$(1+q+\cdots+q^{n-1})$求和。

李辰剑 2020-12-14

写在前面

自从大一学了傅里叶级数（并且没学好），大二的数理方法又错过了讲傅里叶变换的那节课（数理方法），就一直对傅里叶变换感觉懵懵懂懂，没学进去；虽然道理能搞懂、公式能照搬，但用起来总是感觉心里没底，缺乏信心；再加之傅里叶变换的具体方法和公式种类繁多，更让我摸不着头脑。由于计算物理要讲FFT, 便打算趁这个机会查缺补漏，把傅里叶变换没有搞懂的地方彻底搞懂（指我自己的问题），整理成笔记。

这系列笔记的内容应该包括：

• 从傅里叶级数到傅里叶变换的”推导“（是如何过渡过去的？）

  • 这里便会牵涉到各种不同的傅里叶公式
  • ——这也是这篇笔记的内容.因此，这个系列的第一篇其实是”(二)”出于逻辑完整性，最开始的内容应该是傅里叶方法和傅里叶级数的引入，以及级数敛散性的讨论，因此这篇过渡到傅里叶变换的笔记就是(二)了; 什么？你问我(一)和后面的内容会不会填坑？我估计大概率不会(坏笑
• 关于傅里叶级数敛散性的一些讨论 ->(一)（刘旭峰留下的坑，看了伍胜健的《数学分析II》中的相关内容才明白）
• 卷积的推导 -> (三)
• DFT 和 FFT -> (四)

从三角傅里叶级数到复傅里叶级数

在高数课本中，给出的傅里叶级数公式为：

$$\label{Fourier_series} f(x)=\frac{a_0}{2}+\sum_{n=1}^\infty (a_n\cos nx+b_n \sin nx) \tag{1}$$

简单起见，我们假设函数$f(x)$没有瑕点，级数总能收敛

其中系数由积分给出：

$$\left\{\begin{array}{l} a_n=\frac{1}{\pi}\int_\pi^\pi f(x)\cos nx \mathrm{d}x \\ b_n=\frac{1}{\pi}\int_\pi^\pi f(x)\sin nx \mathrm{d}x \\ \end{array}\right.\tag{2}$$

这种做法的合理性来自于三角函数系的正交性:

$$\left\{\begin{array}{l} \langle \cos mx|\cos nx\rangle=\pi\delta_{mn},\langle \sin mx|\sin nx\rangle=\pi\delta_{mn} \\ \langle \cos mx|\sin nx\rangle=0 \end{array}\right.\tag{3}$$

其中，内积$\langle\cdot|\cdot\rangle$是由$[-\pi, \pi]$上的定积分定义的；对正弦函数而言，参数$n$不能为$0$, 而对余弦函数而言，$n$可以为零，但此时的正交关系为$\langle\cos nx|\cos nx\rangle=\langle 1|1\rangle=2\pi$而非$\pi$.

这个结果看上去非常美丽，但仍有一些问题：

• 为什么$n=0$的项要搞特殊？强迫症很痛苦啊！
  • 进一步来说，从数学上，为什么$n=0$的项很特殊呢？(显然我并不满足那个简单的定积分公式)
  • 整个三角函数系看上去还是有点冗余/复杂. 如果能化成单参数的函数族就好了.
• 这个形式要求$f(x)$必须是以$2\pi$为周期的函数，对一般函数不太好处理.
• 这个形式很不容易推广/过渡到傅里叶变换上.

所幸我这两天找到了一个巧妙的方法, 可以解决这些问题.