2019-03-29
这是著名的卡特兰数问题,你百度一下“卡特兰数”有很多资料.现把我收集的资料加上我的注释,解释如下:
我们来看一种图形化的方法证明这个等式我们把对n个5角的和n个1元的排队理解为在一个n * n的方格中从一个顶点走向对角的过程.过程中的每个顶点代表一个拿1元的或者5角的.向右走n次(代表5角的),向上走n次(代表1元的).题意可以得出在任何一个人断开其前面的拿5角的必须大于或等于拿一元的人.也就是只在图中实线部分,而不超过对角线的线路:
每次沿着实线走,所以,只要求出从方格左下角到右上角路径的个数即可. 我们把表格补全,考虑每一条不合法的路径,如
在这条路径上,必然有一个地方连续两次向上,即从图上蓝点处开始,而且这个点必然在如图所示的绿线上.我们以这个点为起点,把到左上角整条路经取反,也就是对称上去,得到一条新路径,但是超出了表格.我们知道,这条路径包括n + 1次向上和n – 1次向下,也就是在一个(n + 1) * (n - 1)的方格中.由此我们知道,一条不合法路径必然对应一个(n + 1) * (n - 1)方格中的路径.同样地,对于(n + 1) * (n - 1)方格中任意一条路径,以这条路径与绿线的第一个交点为起点到方格的右上方全部取反,即可得到一个在n * n方格中的不合法路径.
我们通过这样的方法确定了每条不合法路径与一个(n + 1) * (n - 1)方格中路径的一一对应关系,因此,方格中不合法路径总数为C(2n, n - 1),而所有路径总数为C(2n, n),两式相减即为原组合等式.
这是著名的卡特兰数问题,你百度一下“卡特兰数”有很多资料.现把我收集的资料加上我的注释,解释如下:
我们来看一种图形化的方法证明这个等式我们把对n个5角的和n个1元的排队理解为在一个n * n的方格中从一个顶点走向对角的过程.过程中的每个顶点代表一个拿1元的或者5角的.向右走n次(代表5角的),向上走n次(代表1元的).题意可以得出在任何一个人断开其前面的拿5角的必须大于或等于拿一元的人.也就是只在图中实线部分,而不超过对角线的线路:
每次沿着实线走,所以,只要求出从方格左下角到右上角路径的个数即可. 我们把表格补全,考虑每一条不合法的路径,如
在这条路径上,必然有一个地方连续两次向上,即从图上蓝点处开始,而且这个点必然在如图所示的绿线上.我们以这个点为起点,把到左上角整条路经取反,也就是对称上去,得到一条新路径,但是超出了表格.我们知道,这条路径包括n + 1次向上和n – 1次向下,也就是在一个(n + 1) * (n - 1)的方格中.由此我们知道,一条不合法路径必然对应一个(n + 1) * (n - 1)方格中的路径.同样地,对于(n + 1) * (n - 1)方格中任意一条路径,以这条路径与绿线的第一个交点为起点到方格的右上方全部取反,即可得到一个在n * n方格中的不合法路径.
我们通过这样的方法确定了每条不合法路径与一个(n + 1) * (n - 1)方格中路径的一一对应关系,因此,方格中不合法路径总数为C(2n, n - 1),而所有路径总数为C(2n, n),两式相减即为原组合等式.