首先是那个经典的骨牌问题。
一个 2×n 的网格,求在这上面用 1×2 的骨牌密铺的方案数。
显然这玩意是斐波那契数列。
但是这样推就会推错:
观察到只有横着铺和竖着铺两种,因此可以认为是若干个横着铺的里面插着竖着铺的。
构造横着的 EGF:F(x)=ex,构造竖着的 EGF:G(x)=2ex−e−x。
然后两个 EGF 的卷积等价于将两者归并起来,因此 设 H(x)=F(x)G(x) ,则 [xn]H(x) 即为答案。
然后把 F(x) 和 G(x) 卷一下,惊奇的发现 [xn]H(x)=2n−1!
这显然推错了,而且非常荒谬。
蒟蒻刚学生成函数,对于一些概念还是近乎一头雾水,这里面应该也是部分概念搞错导致的,但蒟蒻还是不能理解,因此在这里求教。