从一个诡异的数组开始

发表于

标签： 数学

1, 2, 4, 8, 16，31……

当我打开一个b站视频
https://www.bilibili.com/video/av17442695/
看到当用直线连接圆上各点时(n=1,2,3,4,5)所划分的区域数目构成数列是1, 2, 4, 8, 16，31……，你能求出通项公式吗？
单看前四项，肯定会以为是2的n次方，但是第5个为什么是奇数？


很遗憾，我毫无头绪。可能脑子离开数学太久了吧。看到评论区贴上知乎的答案后，仔细阅读并思考后有感而发写下本文。
b站原作者的答案
https://www.bilibili.com/video/av19849697/?from=search&seid=1097064019385868872
视频制作是作者自制的python库，在GitHub上开源
https://github.com/3b1b/manim
b站有大神的教程：
https://www.bilibili.com/read/cv17444
下面我主要引述知乎大神的答案进行解释：
知乎链接：https://www.zhihu.com/question/49249958/answer/116348707?utm_source=qq&utm_medium=social
作者：匡世珉
他提供非常好的几何解释。
首先研究一条线是怎么划分圆？

线a从左往右画的时候，碰到别的线（如图中的绿线）就将绿线与圆划分的区域再划分两个子区域（+1），依次类推直线之间的交点都会把圆的区域多划分一份。当直线a继续画，到达右边的终点时，线a也会圆多划分一份。
所以，总份数应该是 1+『圆内部的交点数量』+『直线段的数量』。
1代表是圆本身为一份。
直线段的数量，则从圆上n个点中任选2个点连接直线的直线数量:具体公式暂时不知道怎么在md写，可以查看知乎链接。
那圆内部的交点数量怎么求呢？我们可以把圆内部的每个交点看成是某个圆内接四边形的对角线交点，于是在n个点中，任意四个点的组合都对应了圆内部的某个交点。

所以求圆内部的交点数相当于是求『n个点中选4个点有几种选法』

通项公式还可以有各种数学方法求出。
但是，存在两个巧合:1.为什么，n较少时为什么是2的n次幂？
2.当n等于10时，巧合区域为256？

解答这个问题，就要提到杨辉三角；
百度百科
https://baike.baidu.com/item/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92/215098?fr=aladdin

杨辉三角形的构造方法：
每一个数被复制了两份，分别加进了左下角与右下角的两个数中。

下一行的和是上一行的两倍，而由于第一行的和是1，所以每一行的和就都是2的幂啦！
另一种表现形式：

这里，我也是第一次见，直接引用知乎作者的介绍：

所以，当n=6时，即可转化为图中绿色的组合数求和，重新写回数字形式


把两个15再转化为10和5

现在一眼就明白为什么当n=6，它是31，因为它缺少右边的1。
同理，当n=10，刚好是上一列的一半，所以就是256。

第一次看到杨辉三角时，还是在廖雪峰老师的python（不好意思，中途弃学了）https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/0014317799226173f45ce40636141b6abc8424e12b5fb27000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def triangles(n):
    # 创建初始值为1的数组
    L = [1]
    while True:
        # yield是生成器函数专属关键词，函数进行到这里中断，再执行时从中断处再进行
        yield L
        # 重新声明这个数组，用循环计算下一列中间部分的数值（每列首尾都为1），长度正好是上一列的长度-1
        L = [L[x]+L[x+1] for x in range(len(L)-1)]
        # insert(0,1)在数组的开头插入1，insert(index,object),JS对应的方法是splice(0,0,1)
        # splice(par1,pa2,par3) par1是起始位置，par2是删除项数(0就可以替换)，par3是object
        L.insert(0,1)
        # append和JS的append用法相同
        L.append(1)
        # 判断推出条件
        if len(L)>n:
            break
for l in triangles(8):
    print(l)

附一个fib函数

1
2
3
4
5
6
7
def fib(max):
    n, a, b = 0, 0, 1
    while n < max:
        yield b
        a, b = b, a + b
        n = n + 1
    return 'done'

注：

1
2
3
t = (b, a + b) # t是一个tuple
a = t[0]
b = t[1]

再附廖老师的关于yield文章
https://www.ibm.com/developerworks/cn/opensource/os-cn-python-yield/

这篇文章写的比较杂乱，也有很多不足，请多包涵。