組み合わせと配列の表現:pascal三角形と母関数

楊輝三角と母関数はいずれも異なる問題の組合せ結果を表現することができ、楊輝は表を打つのに有利で、演算が速く、母関数は組合せの思想と過程をよりよく体現することができる.C(n,m)=A(n,m)/m!=n!/(n-m)!/m!,次のnおよびmについて:
3 2
5 3
9 5
10 5
16 8
20 10
約束:1<=m<=n<=20.
楊輝三角:

#include <iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
LL fac[21][21];  
void init(){
    for(int i=0;i<21;i++){
        fac[i][0]=fac[i][i]=1;
        for(int j=1;j<i;j++){
            fac[i][j]=fac[i-1][j-1]+fac[i-1][j];
        }
    }
}
int main()
{
	freopen("cin.txt","r",stdin);
    freopen("cout.txt","w",stdout);
    int n,m;
    init();
    while(cin>>n>>m){
        cout<<fac[n][m]<<endl;
    }
    return 0;
}

結果:
3
10
126
252
12870
184756
親関数はC(n,m)=A(n,m)/m!=n!/(n-m)!/m! g(x)=(1+x+x^2+......)^n

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
//C(n,m)=A(n,m)/m!  g(x)=(1+x+x^2+……)^n
LL c1[21],c2[21];
int main()
{
    freopen("cin.txt","r",stdin);
    freopen("cout.txt","w",stdout);
    int n,m;
    while(cin>>n>>m){
        int i,j,k;
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        c1[0]=c1[1]=1;
        for(i=1;i<n;i++){
            for(j=0;j<=n;j++)c2[0+j]+=c1[j];
            for(j=0;j<n;j++)c2[1+j]+=c1[j]; //    x   ，     ，         。
            for(j=0;j<=n;j++){
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        for(i=0;i<=20;i++) cout<<c1[i]<<" "; cout<<endl;
        cout<<c1[m]<<endl;
    }
    return 0;
}

結果:
1 3 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3
1 5 10 10 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10
1 9 36 84 126 126 84 36 9 1 0 0 0 0 0 0 0 0 0 0 0
126
1 10 45 120 210 252 210 120 45 10 1 0 0 0 0 0 0 0 0 0 0
252
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 0 0 0 0
12870
1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1
184756
では配列A(n,m)については上にmを乗じるだけ!できます.intとlong longで表現する階乗範囲は限られており、int:13!  LL: 20!.次のコードテストで得られます.
    LL n,m,i;
    for(m=1,i=2;;i++){
        n=m;
        m*=i;
        if(m    }
    printf("The max number is %I64d.",i-1);
へへへ、これは私たちがn<=20を約束した理由です.