Re: [理工] [离散]台大电机 生成函数

楼主: mi981027 (呱呱竹)   2019-12-03 03:48:29
首先先了解F_3(x) - F_2(x)这套解法的想法是什么
https://i.imgur.com/icjskyy.jpg
简单来说,10个相同物放入3个相同箱,不允许空箱的方法数,等同于:
分割整数10,"恰"使用3个整数来分割的方法数。也等同于:
分割整数10,最大只能使用3来分割,且一定要用到3的方法数
(使用Ferrers diagram作转置来思考)
那就可以用生成函数来列式了,因为现在限制最大只能使用3来分割
所以生成函数里就只需要考虑1出现次数的GF, 2出现次数的GF, 3出现次数的GF
这就是F_3(x)
可是现在规定一定要用到3
那就必须扣掉只出现1或2的情况,也就是F_2(x)
https://i.imgur.com/VSAAz0h.jpg
所以第一个问题是你的F_3(x) - F_2(x)列式列错了
第二个问题是箭头指的地方化简错了,所以让你以为这个解法可以往下做
事实上整数分割的问题(应该)是没办法用生成函数求系数的方法做出来的
(有错还请指正><)
因为根本无法化简生成函数的式子
记得小黄也有提到,这样的问题顶多就是要你写出生成函数,不太可能去求个数
那这题还是要求个数怎么办??
其实就是爆开了,这题爆开只有8个,绝对比求生成函数快多了><
作者: mistel (Mistel)   2019-12-03 08:52:00
半夜也照着把生成函数列出来结果边想着这样不是还要暴力讨论系数吗结果迷迷糊糊睡着了... 感谢mi大

Links booklink

Contact Us: admin [ a t ] ucptt.com