排列组合是数学中的一个分支。在计算机编程方面也有非常多的应用,主要有排列公式和组合公式。错排公式、母函数、Catalan Number(卡特兰数)等。
一、有关组合数学的公式
1、排列公式 P(n,r)=n!/r!
2、组合公式 C(n,r)=n!/(r!*(n-r)!) C(n,r)=C(n-1,r)+C(n-1,r-1)
3、错排公式 d[1]=0; d[2]=1;
d[n]=(n-1)*(d[n-1]+d[n-2])
4、卡特兰数
前几项:1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,208012…
公式 C(n)=C(2n,n)/(n+1)
5、母函数
在数学中,某个序列的母函数是一种形式幂级数,其每一项的系数能够提供关于这个序列的信息。使用母函数解决这个问题的方法称为母函数方法。
母函数可分为非常多种,包含普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每一个序列都能够写出以上每一个类型的一个母函数。构造母函数的目的通常是为了解决某个特定的问题,因此选用何种母函数视乎序列本身的特性和问题的类型。(百度百科)
母函数模板(针对n的分解):
/******************************
题目大意:求分解整数n的个数q(n)
例:
5 = 5;
5 = 4 + 1;
5 = 3 + 1 + 1;
5 = 3 + 2;
5 = 2 + 2 + 1;
5 = 2 + 1 + 1 + 1;
5 = 1 + 1 + 1 + 1 + 1;
sum(5) = 7;不区分顺序,
(3+2)与(2+3)为同一个
*******************************/
int main()
{
int a[350],b[350],i,j,k,n;
while(cin>>n&&n)
{
for(i=0;i<=n;i++){
a[i]=1;
b[i]=0;
}
for(i=2;i<=n;i++){
for(j=0;j<=n;j++)
for(k=0;k+j<=n;k+=i)
b[k+j]+=a[j];
for(j=0;j<=n;j++){
a[j]=b[j];
b[j]=0;
}
}
发表评论