数学问题当中的一些基本计数问题

一些基本的计数方法

三大原理：加法原理、乘法原理、容斥原理

容斥原理：奇数个集合为正，偶数个集合为负

有重复元素的全排列。有k个元素，其中第i个有ni个，求全排列的的个数

（n1+n2+......+nk)!/(n1! n2! ......nk!)

可重复选择的组合。有n个不同的元素，每个元素可以选多次，一共选K个，有多少种方法

C(n+k-1,n-1)=C(n+k-1,k)

1.加法原理的应用：

UVA11538链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2533

解题思路:

1. 计数问题, 有三种相对摆放方式: 水平, 竖直, 对角线. 根据加法原理即可, 并且没有交集.

水平和竖直是一样的, 只要n*m矩形旋转90度. 所以结果是: n*m*(m-1)+n*m*(n-1);

以水平为例，放白后有nm种，放黑后有（m-1)种

2. 对角线复杂些, 先来确定对角线的长度: 1,2,3,...,n-2,n-1,n,n,n,...,n,n,n-1,n-2,...,2,1;

其中n的个数是m-n+1 (其中假设m>n);

结果: 2*(2*∑i*(i-1) + (m-n+1)*n*(n-1)) 其中累加的范围是(1<=i<=n-1); (对角线有两条，所以要乘以2）

化简得: 2*n*(n-1)*(3*m-n-1)/3

3. 综上所述: n*m*(n+m-2)+2*n*(n-1)*(3*m-n-1)/3

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    long long n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        if(n>m)  swap(n,m);
        cout<<n*m*(m-1)+n*m*(n-1)+2*n*(n-1)*(3*m-n-1)/3<<endl;
    }
    return 0;
}

2.加法问题的一类变形

UVA11401 链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2396

解题思路，分段法，f [n] 记录最长的那条边不超过n的放法数，假设c[n] 为最长边为n的放法数 f [n] = f [n-1] + c[n] 。

假设最长边为z，其它为 x,y;

则 z-x < y < z

当 x=1 时， z-1<y<z 0 种方案，

当 x=2 时， z-2<y<z 1 种方案，

......................................................

当 x=z-1时， 1<y<z z-2种方案

所以总计 (z-1)*(z-2)/2 种方案

但是其中包含了x与y想等的情况，因为 x取值为 [ z/2+1 , z-1 ] 区间内可能 x,y相等，共 (z-1)- (z/2+1)+1=z/2-1 种方案

而且x,y与 y,x认为为两个，重复计算了，所以除以2

所以 c[n]= [ (z-1)*(z-2)/2 -(z/2-1) ] / 2

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000000+10;
long long f[maxn];
int main()
{
    f[3]=0;
    for(long long x=4;x<=1000000;x++)
        f[x]=f[x-1]+((x-1)*(x-2)/2-(x-1)/2)/2;
    int n;
    while(cin>>n)
    {
        if(n<3)  break;
        cout<<f[n]<<endl;
    }
    return 0;
}