本篇用来记录学习过程中遇到的有趣的数列和他们的性质。

[TOC]

多边形数

三角形数

详见： OEIS A000217

就是用小石块堆叠成三角形需要的个数。如下图：

前几项：1、3、6、10、15、21、28、36、45、55、66、78、91、105、120、136、153、171……

通项公式

第 $n$ 个三角数 $a(n) = C_{n+1}^2 = \frac{n(n+1)}{2}$ 即自然数的前缀和。

特殊的三角形数

55、5,050、500,500、50,005,000……
第11个三角形数（66）、第1111个三角形数（617,716）、第111,111个三角形数（6,172,882,716）、第11,111,111个三角形数（61,728,399,382,716）都是回文式的三角形数，但第111个、第11,111个和第1,111,111个三角形数不是。

性质

任何自然数是最多三个三角形数的和
两个相继的三角形数之和是平方数
三角形数测试：$n = \frac{\sqrt{8X+1}-1}{2}$ ，如果n是整数，那么 $x$ 就是第 $n$ 个三角形数。如果 $n$ 不是整数，那么 $x$ 不是三角形数。这个检验法是基于恒等式 $8T_n + 1 = S_{2n+1}$

正方形数

详见：OEIS A000290

也称平方数，堆成正方形用的石块数。

前几项：1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144……

通项公式

\[a(n) = n^2\]

递推式： $\begin{align*} a_n &= 2a_{n-1}-a_{n-2} + 2 \\ n^2 &= 2(n-1)^2-(n-2)^2+2 \end{align*}$ 连续整数的和：完全平方数还可以表示成 $n^2=1+1+2+2+…+n−1+n−1+n$。例如，$4^2 = 16 = 1 + 1 + 2 + 2 + 3 + 3 + 4$。可以将其解释为在边长为 $3 $ 的矩形上添加宽度为 $1$ 的一行和一列，即得到边长为 4 的矩形。这对于计算较大的数的完全平方数非常有用。例如：$ 52^2 = 50^2 + 50 + 51 + 51 + 52 = 2500 + 204 = 2704$。

###　性质

奇自然数的前缀和。即 $a(n) = \sum_{i=1}^{n}(2i-1) = n(n+1)-n = n^2$
四平方和定理说明所有正整数均可表示为最多四个平方数的和。特别的，三个平方数之和不能表示形如 $4k(8m + 7)$ 的数。若一个正整数可以表示因子中没有形如 $4k + 3$ 的素数的奇次方，则它可以表示成两个平方数之和。
平方数必定不是完全数。
奇数的平方除以4余1，偶数的平方则能被4整除。
一个平方数是两个相邻三角形数之和。两个相邻平方数之和为一个中心正方形数。所有的奇数平方数同时也是中心八边形数。
在十进制中，平方数只能以 00，1，4，6，9 或 25 结尾：

若一个数以 0 结尾，它的平方数以 00 结尾，且其他数字也构成一个平方数；
若一个数以 1 或 9 结尾，它的平方数以 1 结尾，且其他数字构成的数能被 4 整除；
若一个数以 2 或 8 结尾，它的平方数以 4 结尾，且其他数字构成一个偶数；
若一个数以 3 或 7 结尾，它的平方数以 9 结尾，且其他数字构成的数能被 4 整除；
若一个数以 4 或 6 结尾，它的平方数以 6 结尾，且其他数字构成一个奇数；
若一个数以 5 结尾，它的平方数以 25 结尾，且前面的一位或两位数字数字必定为 0，2，06，56 之一，25前面的数是普洛尼克数。

每4个连续的自然数相乘加 1，必定会等于一个平方数，即 $a(a+1)(a+2)(a+3)+1=(a+3a+1)$。
平方数必定是3的倍数或者3的倍数+1。平方数必定是4的倍数或者4的倍数+1。
是否在相继正方形数之间存在一个素数这一命题，对9000000以内的数目是正确的。
除了000以外，平方数末3位数若相同，必为444：如38=1444，462=213444。
除了0000以外，平方数末4位数不可能相同。

五边形数

详见：五边形数 OEIS A000326 ，广义五边形数 OEIS A001318

前几项：1, 5, 12, 22, 35, 51, 70, 92, 117, 145……

通项公式

\[a(n) = \frac{n(3n - 1)}{2}\]

性质

奇偶排列是“奇奇偶偶”。
第 $n$ 个五边形数是第 $3n-1$ 个三角形数 $\frac{1}{3}$。
前 $n$ 个五边形数的算术平均数是第 $n$ 个三角形数。 $\frac{1}{n}\sum_{i=1}^{n}\frac{i(3i-1)}{2} = \frac{3}{2}\frac{n(n+1)(2n+1)}{6}-\frac{1}{2}\frac{n(n+1)}{2} = \frac{n(n+1)}{2}$
五边形数测试：$n = \frac{\sqrt{24X+1}+1}{6}$ 若 $n$ 是自然数，则 $x$ 是五边形数，而且恰为第 $n$ 个五边形数。若 $n$ 不是自然数，则 $x$ 不是五边形数。
费马多边形数定理：任何整数都可以表示为不超过5个五边形数的和。大多数的整数都可以表示不超过3个五边形数的和。在小于 $10^6$ 的整数中，只有6个整数需用5个五边形数的和来表示：9, 21, 31, 43, 55, 89 (OEIS:A133929) 210个整数需用4个五边形数的和来表示：4, 8, 9, 16, 19, 20, …, 20250, 33066 (OEIS:A003679)

广义五边形数

通项公式

\[p_n = \frac{n(3n \pm 1)}{2} \quad (n=0,\pm1, \pm2,\pm 3,...)\]

前几项：0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117…… (OEIS:A001318)

广义五边形数与整数分拆有重要关系。具体看之前的整数分拆文章。

性质

第 $n \quad (n>2)$ 个五边形数的外层有 $5(n-1)$ 个点，所以内部点有 $\begin{align*} \frac{n(3n-1)}{2}-5(n-1) &= \frac{3n^2-11n+10}{2}\\ &= \frac{(3n-5)(n-2)}{2}\\ &= \frac{3(n-2)^2-(n-2)}{2} \end{align*}$ 依然是一个广义五边形数。
所有的整数都可以表示成不超过3个广义五边形数的和。
若三角形数可以被3整除，则除以3之后的数必为广义五边形数。

多边形数

六边形数

七边形数

第 $n$ 个 $s$ 边形的公式： $a(n) = \frac{n[(s-2)n-(s-4)]}{2}$ 费马多边形数定理指出每个数最多是 $n$ 个 $n$ 边形的和。

斐波那契数列

向日葵的条纹个数一般都符合斐波那契数列（bilibili）。 $a_n = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]$ 其中 $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$ 恰好是黄金比例分割。因为有 $\lim_{n\rightarrow\infty}\frac{a_{n+1}}{a_n} = \varphi$ 自然中大多数的相邻叶子间的角度都符合黄金角（约等于$137.51^{\circ}$），此时符合平面最密堆积。

有趣的性质

最后一位数字，每60个数一循环最后两位数字，每300个数一循环最后三位数字，每1500个数一循环最后四位数字，每15000个数一循环最后五位数字，每150000个数一循环 ……
每第三个数可被2整除每第四个数可被3整除每第五个数可被5整除每第六个数可被8整除 ……. 这些除数本身也构成斐波那契数列
除了n=4之外，所有的 Fibonacci primes （Fibonacci数列中的素数拿出来）的序号都是素数。但是并不是所有素数序号的斐波那契数都是素数。

$\begin{array}{l}{1+1+4=6=2 \times 3} \\ {1+1+4+9=15=3 \times 5} \\ {1+1+4+9+25=40=5 \times 8} \\ {1+1+4+9+25+64=104=8 \times 13} \\ {F_{1}^{2}+F_{2}^{2}+\cdots+F_{n}^{2}=F_{n} F_{n+1}}\end{array}$ Proof1：

<img src="..\images\TIM截图20191211151804.png" alt="TIM截图20191211151804" style="zoom: 67%;" />

面积是所有前面的斐波那契数的平方之和，证得上述结论。

Proof2： $\begin{align*} F_1^2 &= F_2F_1 \quad(F_1=F_2=1) \\ F_2^2 &= F_2(F_3-F_1)=F_2F_3-F_1F_2 \\ F_3^2 &= F_3(F_4-F_2)=F_3F_4-F_2F_3 \\ &...\\ F_n^2 &= F_n(F_{n+1}-F_{n-1}) = F_nF_{n+1}-F_nF_{n-1} \\ \\ 所以： &F_{1}^{2}+F_{2}^{2}+\cdots+F_{n}^{2}=F_{n} F_{n+1} \end{align*}$

\[F_{1}+F_{2}+\cdots+F_{n} =F_{n+2}-1\]
Proof： $\begin{aligned}\quad F_{1} &=F_{3}-F_{2} \\ F_{2} &=F_{4}-F_{3} \\ & \cdots \cdots \\ F_{n-1} &=F_{n+1}-F_{n} \\F_{n}&=F_{n+2}-F_{n+1} \\ \\ \therefore F_{1}+F_{2}+&\cdots+F_{n} =F_{n+2}-1 \end{aligned}$
\[F_{1}+F_{3}+F_{5}+\cdots+F_{2 n-1} =F_{2 n}\]
Proof： $\begin{align*} \\ \\ \because F_{1}&=F_{2} \\ F_{3}&=F_{4}-F_{2} \\ F_{5}&=F_{6}-F_{4} \\ &\cdots \cdots \\ F_{2 n-1}&=F_{2 n}-F_{2 n-2} \\ \therefore F_{1}+F_{3}+F_{5}+&\cdots+F_{2 n-1} =F_{2 n} \end{align*}$

分圆问题

一个圆上取 $n$ 个点，问两两点连成得直线段最多把圆分成多少份？

前几项： $1,2,4,8,16,31$

先考虑 $n$ 个点可以连成多少条直线段，明显是 $C_n^2 = \frac{n(n-1)}{2}$ 条。
再考虑会产生多少个交点，对于上述问题求最多能分成多少个区域，容易知道任意三条直线都不交于一点时可以保证最多。从 $n$ 个点的角度考虑，每四个点形成的四元组形成两条直线段，有一个交点，所以共有 $C_n^4=\frac{n(n-1)(n-2)(n-3)}{4!}$ 个交点。
再把中间的交点都看作一个顶点，每个交点周围都有四条边，$C_n^2$ 条直线交于 $C_n^4$ 个点共被分割成 $C_n^2+2C_n^4$ 条边。
加上圆上的点，现在共有 $n+C_n^4$ 个点。加上圆被分割成的圆弧，共有 $n+C_n^2+2C_n^4$ 条边。
根据欧拉公式 $V-E+F=2$ 可以算出面的个数 $\begin{align*} F &= E-V+2 \\ &= (n+C_n^2+2C_n^4)-(n+C_n^4)+2 \\ &= C_n^2+C_n^4+2 \end{align*}$
去掉圆外的区域共有 $C_n^2+C_n^4+1$ 个面。也等于 $C_{n-1}^4+C_{n-1}^3+C_{n-1}^2+C_{n-1}^1+C_{n-1}^0$ ，这也解释了为什么 $n<6$ 时和 $2$ 的幂有关系。

卡特兰数（Catalan number）

序列 $1,2,3,..,n$ 共有多少种出栈顺序

可以按照栈是否为空，将一个出栈问题划分成多个更小的出栈问题。设第一次栈为空时共有 k 个元素出栈，即 1 的出栈序号（1是第一个被放进去的），此时序列被分成两个序列，一部分是在 $1$ 之前出栈的元素，序号为 $1$~$k-1$ 共 $k-1$ 个元素。在 $1$ 之后的元素，序号为 $k+1$ ~ $n$ 共 $n-k$ 个元素。设 $f(n)$ 表示 $n$ 个元素出栈序列种类数，则 $\begin{align*} f(n) &= f(k-1)f(n-k) \quad \quad (k\in [1,n]) \\ &= \sum_{k=1}^{n} f(k-1)f(n-k) \\ &= f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(0) \end{align*}$

n 个节点构成的二叉树的所有情形

一个根节点将数分成左子树和右子树，若左边有 k-1 个，则右边有 n-k 个。设 n 个节点的树共有 $f(n)$ 中情况，则 $f(n) = f(k-1)f(n-k) = \sum_{k=1}^{n} f(k-1)f(n-k)$ 依然是上述递推式

假设 $f(0) = 1$ ，就可以推出以后的序列 $1,2,5,14,42,132,429,1430,4862,…$

正 n 边形划分成不重叠的三角形的方案数

设正 n 边形的顶点为 $v_1,v_2,…,v_n$ ，以 $v_1v_n$ 为边找到一点 $v_k$ 可以将多边形划分成两个新的多边形，设 n 边形的总划分数为 $f(n)$ ，则 $f(n) = f(k-1)f(n-k) = \sum_{k=1}^{n} f(k-1)f(n-k)$ 依然是这个递推式

一个矩形地图，从 $(0,0)$ 点到 $(n,n)$ 点且不穿过 $y=x$ 这条直线的所有方案数。

可以转化成出栈问题，同时也可以直接用组合数的方法表示成两个组合数的差。将 $y=x$ 下移一个单位，此时不能经过 $y=x-1$ 这条直线，此时 $(0,0)$ 点关于这条直线的对称点是 $(1,-1)$ ，所以不经过 $y=x-1 $ 的所有方案数就是从 $(0,0)$ 到 $(n,n) $的总方案数减去从 $(1,-1)$ 到 $(n,n)$ 的总方案数 $\begin{align*} f(n) &= C_{2n}^{n} - C_{2n}^{n-1} \\ &= \frac{1}{n+1} C_{2n}^{n} \\ &= \frac{(2n)!}{(n+1)!n!} \\ &= \prod_{k=2}^{n} \frac{n+k}{k} \end{align*}$

2n 个括号（一半左括号，一半右括号）的匹配问题共有多少种方式

有一点可以确定，对任意一个位置，左括号数量一定不少于右括号数量，所以可以将问题转化为上一题的格路问题，依然可以是卡特兰数的表达形式。

有n个人围在圆桌参加晚宴，他们两两直接想通过握手相互认识。但是可能影晌别人所以他们的手不能有交叉，那么一共有多少种握手的方式？

错排问题

请问 n 对男女来跳舞，先跳了一曲，下一曲必须换舞伴，请问有多少种不同的换法?

信封放信，没有一封信是装对的方案数

分成两种情况。

若当前数列是$1$ ~ $n$ 有序的，可以把第 n 个数字与前面的任意一个交换，n-1 中交换方式，剩下的 n-2 个数字又可以看作一个新的有序数列，所以得到 $(n-1)D_{n-2}$ 个错排。
若前 n-1 位数字已经是错排序列，现在多一个 n ，那么第 n 个数字可以和前 n-1 个数字中的任意一个交换，这样可以得到 $(n-1)D_{n-1}$ 个错排

所以的出递推式 $D_n = (n-1)(D_{n-1}+D_{n-2}) \quad \quad (D_0=1, D_1 = 0,D_2 = 1)$ 可以看到得到的递推关系是 非常系数递推关系 ，下面提供一种解法 $\begin{aligned} D_{n}-n D_{n-1} &=-\left[D_{n-1}-(n-1) D_{n-2}\right] \\ &=(-1)^{2}\left[D_{n-2}-(n-2) D_{n-3}\right] \\ &=\cdots \\ &=(-1)^{n-1}\left(D_{1}-D_{0}\right) \\ &= (-1)^n\end{aligned}$ 设生成函数 $\begin{aligned} G_{e}(x)=& D_{0}+\frac{D_{1}}{1 !} x+\frac{D_{2}}{2 !} x^{2}+\frac{D_{3}}{3 !} x^{3} +\cdots \end{aligned}$ 前几项有 $\begin{aligned} \frac{x}{1!}D_1 &= \frac{x}{1!}(1D_0 + (-1)^1) \\ \frac{x}{2!}D_2 &= \frac{x}{2!}(2D_1 + (-1)^2) \\ \frac{x}{3!}D_3 &= \frac{x}{3!}(3D_2 + (-1)^3) \\ \cdots \\ \frac{x}{n!}D_n &= \frac{x}{n!}(nD_{n-1} + (-1)^n) \\ \cdots \end{aligned}$ 将上式相加得到 $G_{e}(x) - D_0 = xG_{e}(x) + e^{-x} - 1$

\[\begin{align*} G_{e}(x) &= xG_{e}(x) + e^{-x} \\ &= \frac{e^{-x}}{1-x} \\ &= (1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+...)(1+x+x^2+..) \\ &= \sum_{n=0}^{\infty} (1-1+\frac{1}{2!}-\cdots \pm \frac{1}{n!} ) \cdot n! x^n \end{align*}\]

所以 $\begin{aligned} D_n &= (1-1+\frac{1}{2!}-\cdots \pm \frac{1}{n!} ) \cdot n! \\ &= n!-n!+\frac{n!}{2!}-\cdots \pm \frac{n!}{n!} \\ &= \sum_{k=0}^{n} (-1)^k C_n^k (n-k)! \end{aligned}$