组合数学:生成函数求解重复字母字符串问题
首先,设$a(x)$表示选0个或1个a的方案数,$b(x)$表示选0个或1个b的方案数,$c(x)$表示选0个或1个c的方案数。则有:
$$a(x)=(1+x)$$
$$b(x)=(1+x)$$
$$c(x)=(1+x)$$
因为可以重复选择,所以四个字母的选法可以表示为:
$$(a(x)+b(x)+c(x))^4$$
展开得到:
$$ \begin{aligned} &(a(x)+b(x)+c(x))^4\ =&a^4(x)+4a^3(x)b(x)+6a^2(x)b^2(x)+4a(x)b^3(x)+b^4(x)&+4a^3(x)c(x)+12a^2(x)b(x)c(x)+12a(x)b^2(x)c(x)+4b^3(x)c(x)+4a^3(x)c^2(x)&+12a^2(x)b(x)c^2(x)+12a(x)b^2(x)c^2(x)+4b^3(x)c^2(x)+6a^2(x)c^3(x)+12a(x)b(x)c^3(x)+6b^2(x)c^3(x)+c^4(x) \end{aligned}$$
我们只需要将其中包含至少两个a的项找出来,并将它们的系数相加即可。注意到,$a^4(x)$和$a^3(x)b(x)$不符合条件,因为它们不含有至少两个a。因此,我们只需要考虑下面这些项:
$$ \begin{aligned} &6a^2(x)b^2(x)+4a(x)b^3(x)+4a^3(x)c(x)+12a^2(x)b(x)c(x)\ &+12a(x)b^2(x)c(x)+4a^3(x)c^2(x)+12a^2(x)b(x)c^2(x)+12a(x)b^2(x)c^2(x)\ &+6a^2(x)c^3(x)+12a(x)b(x)c^3(x) \end{aligned}$$
它们的系数分别为6,4,4,12,12,4,12,12,6,12。因此,我们可以得到组成不同字符串的方案数为:
$$6+4+4+12+12+4+12+12+6+12=82$$
因此,由生成函数的方法,我们得到了答案为82。
原文地址: https://www.cveoy.top/t/topic/oVPz 著作权归作者所有。请勿转载和采集!