鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？

——张丘建《算经》

这里从最最简单的算法开始一步一步讲如何优化，主要涉及的还是数学，Roger Bacon曾在《Opus Majus》写到

It is impossible to know things of this world unless you know mathematics.

——Roger Bacon《Opus Majus》

虽然这篇 post 会一直讲百鸡问题，但是主要还是想以此记录一些在解决某些问题是可能用到的数学思维，并不是只为了做百鸡问题。当然，我的数学也不怎么样qwq不过至少在这道题上，应用数学之后的算法在时间上的减少是比较明显的。

这篇 post 由以下几个部分构成

• 一个糟糕的实现
• 稍好一点的实现
• 再略微优化一点点
• 更好的算法
• 考虑多变量时的情况
• 总结

Continue reading 从百鸡问题到数学思维 →

第二个谬误的思考方式是在估计和进度安排中使用的工作量单位: 人月。成本的确随开发产品的人数和时间的不同有着很大的变化, 进度却不是如此。因此我认为用人月作为衡量一项工作的规模是一个危险和带有欺骗性的神话。 它暗示着人员数量和时间是可以相互替换的。……从而，添加更多的人手，实际上是延长了而不是缩短了时间。

——人月神话

Continue reading Congested network笔记(4) →

在上一篇 Congested network笔记(2) 的最后，我们把问题变成了变分不等式的求解，那么这两个变分不等式在什么情况下存在解，且解唯一呢？

$$\left\{\begin{align}\frac{\partial\mathcal{Z(F)}}{\partial\underline{\mathcal{F}}}\cdot(\mathcal{F}-\underline{\mathcal{F}})&\ge 0&\forall \mathcal{F}\in S&\text{  最优解}\\
\mathcal{C}(\mathcal{F}^*)\cdot(\mathcal{F}-\mathcal{F}^*)&\ge 0&\forall \mathcal{F}\in S&\text{ 均衡解}\end{align}\right.$$

Continue reading Congested network笔记(3) →

在上一篇 Congested network笔记(1) 里，我们提到了均衡解和优化解。其中均衡解是指对每一个流量的花费最少，即user-optimal，用户最优。优化解则是站在全局的角度考虑，提出的系统最优。

Continue reading Congested network笔记(2) →

人类天性是自私的，而经济行为植根于此"事实"之上。博弈论看似也反映了此种假设。在博弈论最初的形式中，博弈论数学描述"理性的"行为，本质上是将"理性"和"自私"当作同义词。但按照今天的解释，博弈论并非假设人类总是表现得自私——或理性。博弈论告诉你如果人类确实表现得自私或理性，会是怎么样的情形。

——A BEAUTIFUL MATH
John Nash, Game Theory
AND THE MODERN QUEST FOR A CODE OF NATURE

Continue reading Congested network笔记(1) →

前几天在《Discrete Mathematics and its Applications》上看到了这三道题，均要求使用生成函数求解，题目如下：

1. a_k = a_k-1 + 2a_k-2 + 2^k, a₀ = 4, a₁ = 12
2. a_k = 4a_k-1 - 4a_k-2 + k², a₀ = 2, a₁ = 5
3. a_k = 2a_k-1 - 3a_k-2 + 4^k + 6, a₀ = 20, a₁ = 60

昨天在StackExchange^[1]上询问之后，今天花了一早上的时间做了一遍，下面就是完整的步骤和总结。

• Problem 1

$\left\{\begin{array}{l}{a}_k=a_{k-1}+2a_{k-2}+2^k\\ a_0=4\\ a_1=12\end{array}\right.$

我们首先令f(x)为序列{ak}的生成函数，即

$\mathit{\text{f}}\left(x\right)=\sum _{k\ge 0}{a}_k{x}^k$

然后我们对递推关系式（也就是上面大括号中的第一个式子）中的每一项都乘以xk，得

$a_k{x}^k=a_{k-1}{x}^k+2a_{k-2}{x}^k+2^k{x}^k$

接着对每一项都取k从2开始的和

$\sum _{k\ge 2}{a}_k{x}^k=\sum _{k\ge 2}{a}_{k-1}{x}^k+\sum _{k\ge 2}2a_{k-2}{x}^k+\sum _{k\ge 2}{2}^k{x}^k$

$\text{=}\sum _{k\ge 2}{a}_{k-1}{x}^k+2\sum _{k\ge 2}{a}_{k-2}{x}^k+\sum _{k\ge 2}{2}^k{x}^k$

在这之后我们将对每一项都进行变形，变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。

$\sum _{k\ge 2}{a}_k{x}^k=\left(\sum _{k\ge 2}{a}_k{x}^k+a_{1}x+a_0\right)-a_{1}x-a_0$

$\text{=}\sum _{k\ge 0}{a}_k{x}^k-a_{1}x-a_0$

$\text{=}\mathit{\text{f}}\left(x\right)-4x-12$


$\sum _{k\ge 2}{a}_{k-1}{x}^k=x\sum _{k\ge 2}{a}_{k-1}{x}^{k-1}$

$\text{=}x\sum _{k\ge 1}{a}_k{x}^k$

$\text{=}x\left(\sum _{k\ge 0}{a}_k{x}^k-a_0\right)$

$\text{=}x\left(\mathit{\text{f}}\left(x\right)-4\right)$


$\sum _{k\ge 2}{a}_{k-2}{x}^k=x^2\sum _{k\ge 2}{a}_{k-2}{x}^{k-2}$

$\text{=}{x}^2\sum _{k\ge 0}{a}_k{x}^k$

$\text{=}{x}^2\mathit{\text{f}}\left(x\right)$


$\sum _{k\ge 2}{2}^k{x}^k=\sum _{k\ge 0}{2}^k{x}^k-2x$

$\text{=}\frac{1}{1-2x-1}-2x-1$

现在我们将变形后的式子替换回去

$\mathit{\text{f}}\left(x\right)-4x-12=x\left(\mathit{\text{f}}\left(x\right)-4\right)+2x^2\mathit{\text{f}}\left(x\right)+\frac{1}{1-2x}-2x-1$
合并同类项，然后分解分式多项式得

$\mathit{\text{f}}\left(x\right)=\frac{2}{3}\text{·}\frac{1}{{\left(1-2x\right)}^2}+\frac{38}{9}\text{·}\frac{1}{1-2x}-\frac{8}{9}\text{·}\frac{1}{1+x}$

根据生成函数与序列{ak}的关系，可得

$a_k\text{=}\frac{2}{3}\mathit{\text{C}}\left(2+k-1,2-1\right)2^k+\frac{38}{9}\text{·}{2}^k-\frac{8}{9}\text{·}{\left(-1\right)}^k$

$\text{=}\frac{2}{3}\left(1+k\right)2^k+\frac{38}{9}\text{·}{2}^k-\frac{8}{9}\text{·}{\left(-1\right)}^k$

$\text{=}\frac{44}{9}\text{·}{2}^k+\frac{2}{3}k\text{·}\frac{k}{3}-\frac{8}{9}\text{·}{\left(-1\right)}^k$
至此，我们解出了满足递推关系和初始条件的解

$\left\{\begin{array}{l}{a}_k=4a_{k-1}-4a_{k-2}+k^2\\ a_0=2\\ a_1=5\end{array}\right.$

我们首先令f(x)为序列{ak}的生成函数，即

$\mathit{\text{f}}\left(x\right)=\sum _{k\ge 0}{a}_k{x}^k$

然后我们对递推关系式（也就是上面大括号中的第一个式子）中的每一项都乘以xk，得

$a_k{x}^k=4a_{k-1}{x}^k-4a_{k-2}{x}^k+k^2{x}^k$

接着对每一项都取k从2开始的和

$\sum _{k\ge 2}{a}_k{x}^k=\sum _{k\ge 2}4a_{k-1}{x}^k-\sum _{k\ge 2}4a_{k-2}{x}^k+\sum _{k\ge 2}{k}^2{x}^k$

$\text{=}4\sum _{k\ge 2}{a}_{k-1}{x}^k-4\sum _{k\ge 2}{a}_{k-2}{x}^k+\sum _{k\ge 2}{k}^2{x}^k$

在这之后我们将对每一项都进行变形，变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。

$\sum _{k\ge 2}{a}_k{x}^k=\left(\sum _{k\ge 2}{a}_k{x}^k+a_{1}x+a_0\right)-a_{1}x-a_0$

$\text{=}\sum _{k\ge 0}{a}_k{x}^k-a_{1}x-a_0$

$\text{=}\mathit{\text{f}}\left(x\right)-5x-2$


$\sum _{k\ge 2}{a}_{k-1}{x}^k=x\sum _{k\ge 2}{a}_{k-1}{x}^{k-1}$

$\text{=}x\sum _{k\ge 1}{a}_k{x}^k$

$\text{=}x\left(\sum _{k\ge 0}{a}_k{x}^k-a_0\right)$

$\text{=}x\left(\mathit{\text{f}}\left(x\right)-2\right)$


$\sum _{k\ge 2}{a}_{k-2}{x}^k=x^2\sum _{k\ge 2}{a}_{k-2}{x}^{k-2}$

$\text{=}{x}^2\sum _{k\ge 0}{a}_k{x}^k$

$\text{=}{x}^2\mathit{\text{f}}\left(x\right)$

最后的这个k2的和式处理稍微复杂一些

$\sum _{k\ge 2}{k}^2{x}^k=\sum _{k\ge 0}{k}^2{x}^k-x$

$\text{=}x\sum _{k\ge 0}{k}^2{x}^{k-1}-x$

$\text{=}x\sum _{k\ge 0}kk{x}^{k-1}-x$

化简到这一步之后，下面我们对和式积分，然后再求导



$\text{=}x{\left(x\sum _{k\ge 0}k{x}^{k-1}\right)}^{\text{'}}-x$

再来一次

$\text{=}x{\left(x{\left(\sum _{k\ge 0}{x}^k\right)}^{\text{'}}\right)}^{\text{'}}-x$

到了这一步之后就简单了

$\text{=}x{\left(x{\left(\frac{1}{1-x}\right)}^{\text{'}}\right)}^{\text{'}}-x$

$\text{=}x{\left(\frac{x}{{\left(1-x\right)}^2}\right)}^{\text{'}}-x$

$\text{=}\frac{x\left(1+x\right)}{{\left(1-x\right)}^3}-x$

现在我们将变形后的式子替换回去

$\mathit{\text{f}}\left(x\right)-5x-2=4x\left(\mathit{\text{f}}\left(x\right)-2\right)-4x^2\mathit{\text{f}}\left(x\right)+\frac{x\left(1+x\right)}{{\left(1-x\right)}^3}-x$

合并同类项，然后分解分式多项式得

$\mathit{\text{f}}\left(x\right)=\frac{2}{{\left(1-x\right)}^3}+\frac{5}{{\left(1-x\right)}^2}+\frac{13}{1-x}+\frac{6}{{\left(1-2x\right)}^2}-\frac{24}{1-2x}$

根据生成函数与序列{ak}的关系，可得

$a_k\text{=}2\mathit{\text{C}}\left(3+k-1,3-1\right)+5\mathit{\text{C}}\left(2+k-1,2-1\right)+13+6\mathit{\text{C}}\left(2+k-1,2-1\right)2^k-24\text{·}{2}^k$

$\text{=}2\frac{\left(2+k\right)\left(1+k\right)}{2}+5\left(1+k\right)+13+6\left(1+k\right)2^k-24\text{·}{2}^k$

展开、合并同类项

$\text{=}\left(2+13+5\right)+\left(6\text{·}{2}^k-24\text{·}{2}^k\right)+\left(3k+5k\right)+6k\text{·}{2}^k+k^2$

$\text{=}20-18\text{·}{2}^k+8k+6k\text{·}{2}^k+k^2$

至此，我们解出了满足递推关系和初始条件的解

Problem 3的和处理方式前面的Problem 1十分相似，这里不再给出解答。