求看一下哪里证伪了
查看原帖
求看一下哪里证伪了
555065
ChrysanthBlossom楼主2024/5/2 12:35

首先是那个经典的骨牌问题。

一个 2×n2 \times n 的网格,求在这上面用 1×21 \times 2 的骨牌密铺的方案数。

显然这玩意是斐波那契数列。

但是这样推就会推错:

观察到只有横着铺和竖着铺两种,因此可以认为是若干个横着铺的里面插着竖着铺的。

构造横着的 EGF:F(x)=exF(x)=e^x,构造竖着的 EGF:G(x)=ex−e−x2G(x)=\dfrac{e^x-e^{-x}}{2}。

然后两个 EGF 的卷积等价于将两者归并起来,因此 设 H(x)=F(x)G(x)H(x)=F(x)G(x) ,则 [xn]H(x)[x^n]H(x) 即为答案。

然后把 F(x)F(x) 和 G(x)G(x) 卷一下,惊奇的发现 [xn]H(x)=2n−1[x^n]H(x)=2^{n-1}!

这显然推错了,而且非常荒谬。

蒟蒻刚学生成函数,对于一些概念还是近乎一头雾水,这里面应该也是部分概念搞错导致的,但蒟蒻还是不能理解,因此在这里求教。

2024/5/2 12:35
加载中...