二项式系数 – Binomial Coefficients

二项式系数是组合数学中十分重要的基本知识,各种应用都少不了他.今天做了两个题,顺便总结下:

这个是我们了解到的最基本的形式,当k=0时,上式值为1,当k>n时,值为0;

帕斯卡三角中的每个数相当于顶上两侧数的加和,也可以用组合的思想来解释这个公式:

从n个人中选出k个人,我们先看其中的A某,如果他不在这k个人中,那么就相当于从n-1个人中挑出k个人,如果他在这k个人中,那么剩下的k-1个人就要从n-1个人中挑选.根据加法原理,总的数量就是这两种情况的和.

二项式定理,高中时候就很熟悉的东西,当x=1,y=1时候可以得到:

还有一个公式用的很多:

他可以用来证明下面的公式，

二项式系数的最大值为：

帕斯卡三角（杨辉三角）有很多性质，懒得用公式打出来了，就画了一个图：

横竖斜方向上的数字都有性质：

横：加和为2的N次方         竖：某一列从1开始到数字A的和等于A右下角的数

斜（蓝色）：从1开始到A的和，等于A下边的数。

斜（褐色）：所有斜线上的数字加和排列起来是fibonacci数列。

这里有两道题,简单看一下:

zoj 1938  Binomial Showdown

很纯的题目,就是让求组合数:下面是关键代码:

//如果没有if语句,会超时
long long qiu( long long a,long long b )
{
    long long i,sum = 1;
    if( a-b < b ) b = a-b;
    for( i = 0; i < b; i++ )
        sum *= ( a - i ),sum/=i+1;
    return sum;
}

poj 3219 Binomial Coefficients
本题是让求出组合数除2的余数，如果把结果求出来，再进行运算肯定会超时。
由于我们只是需要知道结果跟2的关系，求出n，k，n-k，的2的阶数a,b,c，如果a == b+c,显然结果是个奇数，反之是偶数：

#include<iostream>
#include<cstdio>

using namespace std;
int count( int x )
{
    int sum = 0;
    while( x )
        x /= 2,sum += x;
    return sum;
}

int main(void)
{
    int n,k;
   
    while( cin >> n >> k )
    {
        if( count(n) == count(k) + count(n-k) ) 
            cout << 1 << endl;
        else 
            cout << 0 << endl;
    }
    return 0;
}