不同种类不同个数集合的重复排列—

不同种类不同个数集合的重复排列——指数型母函数

本文主要是介绍不同种类不同个数集合的重复排列——指数型母函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我们知道多元素的多重集排列是这样的：

元素个数

a1 n1

a2 n2

a3 n3

……

ak nk

其中n=n1+n2+……+nk

取出所有的元素，不同的排列情况应该是 $\frac{n!}{n_1!n_2!\cdots n_k!}$

当不是取出所有元素呢？

回想母函数的方法：

1g砝码，2g砝码，3g砝码……均有无限个，那么母函数的表达式就是

$g(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)\cdots$

砝码故事的背景是所有的砝码都是”同类的“，而现在相当于是有不同种类的砝码，问排列情况。从这个角度看，指数型函数的答案应该比普通母函数的答案要大。

事实确实是这样：

$\\g(x)=(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots+\frac{x^{n_1}}{n_1!})(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots+\frac{x^{n_2}}{n_2!})\cdots(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots+\frac{x^{n_k}}{n_k!})$

最终得到：

$\\g(x)=\sum\limits_{n=0}^{\infty}a_n\frac{x^n}{n!}=a_0+a_1\frac{x}{1!}+a_2\frac{x^2}{2!}+\cdots+a_n\frac{x^n}{n!}+\cdots$

答案就是 $x^n$ 对应的 $a_n$

应用：

hdu 1521

http://acm.hdu.edu.cn/showproblem.php?pid=1521

大意：有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数

#include <iostream>
#include <cstdio>
using namespace std;
int c[15],fac[15];
double c1[15],c2[15];
int main()
{fac[0]=1;for(int i=1;i<=10;i++) fac[i]=fac[i-1]*i;int n,m;while(cin>>n>>m){for(int i=1;i<=n;i++) scanf("%d",&c[i]);for(int i=0;i<15;i++) c1[i]=c2[i]=0.0;for(int i=0;i<=c[1];i++){c1[i]=1.0/fac[i];}for(int i=2;i<=n;i++){for(int j=0;j<=m&&j<=c[i];j++){for(int k=0;k+j<=m;k++){c2[k+j]=c2[k+j]+c1[k]/fac[j];}}for(int j=0;j<=m;j++){c1[j]=c2[j];c2[j]=0;}}printf("%.0lf\n",c1[m]*fac[m]);}return 0;
}

这篇关于不同种类不同个数集合的重复排列——指数型母函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！