組合せ数(n_C_r)の計算

組合せ数(n_C_r)の計算例です。 n 個の数から r 個を選択する場合の組合せ数を計算します。

計算では、選択する数に重複がある場合とない場合（選択する文字が同じでも順番のみが異なっている場合）に分けて計算しています。

//-----------------------------------------------------------------
// 組合せ数(nCr)の計算: list_51.c
//-----------------------------------------------------------------
#include <stdio.h>

//-----------------------------------------------------------------
unsigned long long calc_casen(int n,int r,int dup);
//-----------------------------------------------------------------

int main()
{
    int i,n;
    printf("**組合せ数(nCr)の計算\n");
    printf("個数(n): "); scanf("%d",&n);
    printf("N  C  r = 場合の数(重複なし,あり)\n");
    for(i=0;i<=n;i++){
        printf("%2d C %2d = ",n,i);
        printf("%20llu " ,calc_casen(n,i,0));
        printf("%20llu\n",calc_casen(n,i,1));
    }
    return 0;
}

//-----------------------------------------------------------------
// 組合せ数 nCr の計算[Pascalの3角形による方法]
//-----------------------------------------------------------------
unsigned long long calc_casen(int n,int r,int dup)
{
    int i,j,nn;
    unsigned long long* a=
        (unsigned long long*)calloc(n,sizeof(unsigned long long));
    unsigned long long retv;
    nn=(dup)?(n+r-1): n;
    if(nn-r<r) r=nn-r;
    if(r==0) return 1; if(r==1) return nn;
    for(i=1;i<r;i++) a[i]=i+2;
    for(i=3;i<=nn-r+1;i++){
        a[0]=i;
        for(j=1;j<r;j++) a[j]+=a[j-1];
    }
    retv = a[r-1];
    free(a);
    return retv;
}

result

**組合せ数(nCr)の計算 個数(n): N C r = 場合の数(重複なし,あり) 34 C 0 = 1 1 34 C 1 = 34 34 34 C 2 = 561 595 34 C 3 = 5984 7140 34 C 4 = 46376 66045 34 C 5 = 278256 501942 34 C 6 = 1344904 3262623 34 C 7 = 5379616 18643560 34 C 8 = 18156204 95548245 34 C 9 = 52451256 445891810 34 C 10 = 131128140 1917334783 34 C 11 = 286097760 7669339132 34 C 12 = 548354040 28760021745 34 C 13 = 927983760 101766230790 34 C 14 = 1391975640 341643774795 34 C 15 = 1855967520 1093260079344 34 C 16 = 2203961430 3348108992991 34 C 17 = 2333606220 9847379391150 34 C 18 = 2203961430 27900908274925 34 C 19 = 1855967520 76360380541900 34 C 20 = 1391975640 202355008436035 34 C 21 = 927983760 520341450264090 34 C 22 = 548354040 1300853625660225 34 C 23 = 286097760 3167295784216200 34 C 24 = 131128140 7522327487513475 34 C 25 = 52451256 17451799771031262 34 C 26 = 18156204 39602161018878633 34 C 27 = 5379616 88004802264174740 34 C 28 = 1344904 191724747789809255 34 C 29 = 278256 409894288378212890 34 C 30 = 46376 860778005594247069 34 C 31 = 5984 1777090076065542336 34 C 32 = 561 3609714217008132870 34 C 33 = 34 7219428434016265740 34 C 34 = 1 14226520737620288370