9
Oct
“十字架”组合计数问题浅试
By 苏剑林 | 2022-10-09 | 20160位读者 | 引用
16
Sep
生成函数法与整数的分拆
By 苏剑林 | 2014-09-16 | 31525位读者 | 引用我们在高中甚至初中，都有可能遇到这样的题目：
设$x,y,z$是非负整数，问$x+y+z=2014$有多少组不同的解？（不同顺序视为不同的解）
难度稍高点，可以改为
设$x,y,z$是非负整数，$0\leq x\leq y\leq z$，问$x+y+z=2014$有多少组不同的解？
这些问题都属于整数的分拆问题（广为流传的哥德巴赫猜想也是一个整数分拆问题）。有很多不同的思路可以求解这两道题，然而，个人认为这些方法中最引人入胜的（可能也是最有力的）首推“生成函数法”。
关于生成函数，本节就不多作介绍了，如果缺乏相关基础的朋友，请先阅读相关资料了解该方法。不少数论的、离散数学的、计算机科学的书籍中，都介绍了生成函数法（也叫母函数法）。本质上讲，母函数法能有诸多应用，是因为$x^a\times x^b=x^{a+b}$这一性质的成立。
最近评论