【组合数学】 普通型母函数(整数拆分问题,多重集的组合问题) | 您所在的位置:网站首页 › 如何分清排列问题和组合问题 › 【组合数学】 普通型母函数(整数拆分问题,多重集的组合问题) |
文章目录
1.母函数概念2.普通型母函数3. 整数拆分问题(多重集的组合问题)4.母函数是如何应用于多重集组合问题的?5.模板(数N的划分方案数)6.练手题目
1.母函数概念
母函数是数学中的一个概念,又称为生成函数,是计数方面的一个重要理论和工具。 母函数分为普通型母函数和指数型母函数,前者用于解决多重集的组合问题,后者用于解决多重集的排列问题。 多重集可以理解为同一个元素可以出现多次的集合 2.普通型母函数简单来说: 对于一个序列 a 0 , a 1 , a 2 , ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ a n a_0,a_1,a_2,\cdot\cdot\cdot\cdot\cdot\cdot a_n a0,a1,a2,⋅⋅⋅⋅⋅⋅an,我们称 a 0 a_0 a0+ a 1 x a_1x a1x+ a 2 x 2 a_2x^2 a2x2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + a n x n \cdot\cdot\cdot\cdot\cdot\cdot+a_nx^n ⋅⋅⋅⋅⋅⋅+anxn为该序列的普通型母函数 3. 整数拆分问题(多重集的组合问题)给定一个数N,问N有几种划分方式。 比如N=4,则有: 4 = 4; 4 = 3 + 1; 4 = 2 + 2; 4 = 2 + 1 + 1; 4 = 1 + 1 + 1 +1; 共计5种划分方式,注意1+3与3+1是同一种划分方式。 换种问法就是换零钱的方案数,砝码称重的方案数。 其实这些问题本质上就是多重集的组合问题。 模型: 给定n种物品及每种物品的数量(可以为无限个)和权值,问你权值和为X的组合方案有几种? 在砝码称重问题中,这个权值就是一种砝码的质量 在换零钱问题中,这个权值就是一种硬币的币值 在整数划分问题中,这个权值就是数的数值大小。 从模型的角度分析整数拆分问题就是: 给你n个数(1~N),每个数的权值就是其本身数值大小,每个数可以被重复取用任意次,问你数值和为N的组合方案有几种? 4.母函数是如何应用于多重集组合问题的?先看三个等式: x 4 ⋅ x 5 = x 9 x^4\cdot x^5 = x^9 x4⋅x5=x9 x 3 ⋅ x 6 = x 9 x^3\cdot x^6 = x^9 x3⋅x6=x9 x 3 ⋅ x 3 ⋅ x 3 = x 9 x^3\cdot x^3 \cdot x^3 = x^9 x3⋅x3⋅x3=x9 观察它们的指数,很轻易的就能发现上述三个等式其实暗含了三种9的划分方式(组合方案)。 用x的指数来代表权值,则: 组合数的加法化为了幂级数的乘幂相加 这句话很重要,不懂可以之后再理解。 更进一步: 给定一个4g和一个5g的砝码,问你能称重的范围及对于每一个重量称重的方案数 答案很简单,我们可以称量4g,5g,9g重量的待测物体且各自只有一个方案。 但我们也可以利用之前发现的规律来解决: ( 1 + x 4 ) ⋅ ( 1 + x 5 ) = 1 + x 4 + x 5 + x 9 (1+x^4)\cdot(1+x^5)=1+x^4+x^5+x^9 (1+x4)⋅(1+x5)=1+x4+x5+x9 首先1代表 x 0 x^0 x0,一个0g的砝码。 一个括号的内容就是一个多项式,一个多项式对应一种砝码,多项式中的每一个项代表了一种使用的情况。比如对于第一个多项式1就代表不使用这个砝码, x 4 x^4 x4代表使用。 两个多项式各含两项,相乘就得到了四个项: 1由两个1相乘而来,代表两个砝码都不使用,自然就只能称量0g的物体 x 4 x^4 x4由 x 4 x^4 x4和1相乘而来,代表使用了4g的砝码,而5g的不使用 x 5 x^5 x5由 x 5 x^5 x5和1相乘而来,代表使用了5g的砝码,而4g的不使用 x 9 x^9 x9由 x 4 x^4 x4和 x 5 x^5 x5相乘而来,代表两个砝码都使用,称量9g的物体 这样我们就得到了用一个4g和一个5g的砝码组合后的所有方案 推而广之: 我们以一个多项式代表一种砝码,多项式中的每一项代表这个砝码具体的使用情况。 对于更复杂的问题,比如有2个1g的砝码和3个2g的砝码和1个4g的砝码。 ( 1 + x 1 + x 2 ) ⋅ ( 1 + x 2 + x 4 + x 6 ) ⋅ ( 1 + x 4 ) (1+x^1+x^2)\cdot(1+x^2+x^4+x^6)\cdot(1+x^4) (1+x1+x2)⋅(1+x2+x4+x6)⋅(1+x4) 第一个多项式对应的是1g的砝码: 如果不使用该法码,我们就用 x 0 x^0 x0来表示 如果使用一次该砝码,我们就用 x 1 x^1 x1来表示 如果使用两次该砝码,我们就用 x 2 x^2 x2来表示,可以发现它和使用一次2g的砝码是一样的,因为它们都称量2g的物体。 其实上述过程就是构造母函数的过程。 结合多项式相乘的过程,结果的每一项都是在各个多项式中各自取一项相乘而来,它和我们取砝码的过程是对应的。例: 对于第一个多项式(1g的砝码),我们取 x 1 x^1 x1表示使用一个该砝码 对于第二个多项式(2g的砝码),我们取 x 2 x^2 x2表示使用一个该砝码 对于第三个多项式(4g的砝码),我们取 x 4 x^4 x4表示使用一个该砝码 那么结果就是 x 1 ⋅ x 2 ⋅ x 4 = x 7 x^1\cdot x^2\cdot x^4 =x^7 x1⋅x2⋅x4=x7代表我们可以将其用于称量7g的物体,这样我们就得到了一种7g的方案,其实还有一种7g的方案就是 x 1 ⋅ x 6 ⋅ x 0 x^1\cdot x^6 \cdot x^0 x1⋅x6⋅x0。 求完结果之后合并同类项,这样我们就得到了: 1 + x + 2 x 2 + x 3 + 3 x 4 + 2 x 5 + 4 x 6 + 2 x 7 + 3 x 8 + x 9 + 2 x 10 + x 11 + x 12 1+x+2x^2+x^3+3x^4+2x^5+4x^6+2x^7+3x^8+x^9+2x^{10}+x^{11}+x^{12} 1+x+2x2+x3+3x4+2x5+4x6+2x7+3x8+x9+2x10+x11+x12 每一项的指数就代表了砝码组合后的重量; 可以看到 x 7 x^7 x7前面的系数为2,这两个 x 7 x^7 x7分别是通过 x 1 ⋅ x 2 ⋅ x 4 x^1\cdot x^2\cdot x^4 x1⋅x2⋅x4和 x 1 ⋅ x 6 ⋅ x 0 x^1\cdot x^6 \cdot x^0 x1⋅x6⋅x0得到的。也就是说某一项前面的系数就代表了方案的个数。 由上述过程我们就得到了解决多重集组合问题的一种方法: ①构造母函数 ②展开,合并同类项,就得到了答案 理解了之后,还有一个大问题就是如何应用上述理论,将其通过代码实现出来。 5.模板(数N的划分方案数)对于一个给定的数N,我们可以通过构造下面这个母函数求其划分方案数: ( 1 + x + x 2 + x 3 + ⋅ ⋅ ⋅ + x N ) ⋅ ( 1 + x 2 + x 4 + x 6 + ⋅ ⋅ ⋅ ) ⋅ ( 1 + x 3 + x 6 + x 9 + ⋅ ⋅ ⋅ ) ⋅ ⋅ ⋅ ( 1 + x N ) (1+x+x^2+x^3+\cdot\cdot\cdot+x^N)\cdot(1+x^2+x^4+x^6+\cdot\cdot\cdot)\cdot(1+x^3+x^6+x^9+\cdot\cdot\cdot)\cdot\cdot\cdot(1+x^N) (1+x+x2+x3+⋅⋅⋅+xN)⋅(1+x2+x4+x6+⋅⋅⋅)⋅(1+x3+x6+x9+⋅⋅⋅)⋅⋅⋅(1+xN) 类比于砝码:第一个多项式对应数字1,第二个多项式对应数字2…… 我们要求的方案数就是x^N的系数 模拟多项式相乘并合并同类项的过程: c数组存放之前几个多项式相乘的结果,下标i表示某一项的指数,存放的值表示系数(系数的英文:coefficient) temp是每次多项式相乘的计算结果 c数组初始化为1,存放的其实是第一个多项式(系数全为1) long long c[150],temp[150]; for(int i=0;i long long N; long long c[150],temp[150]; while(~scanf("%lld",&N)){ for(int i=0;i |
CopyRight 2018-2019 实验室设备网 版权所有 |