基础组合数学-526互联

加法原理、乘法原理等是组合数学中的基础

加法原理

将集合S划分为S_1,S_2,S_3,......,S_m,则|S|=|S₁|+|S₂|+|S₃|+......+|S_m|

乘法原理

定义集合S是元素序列(a,b)的集合，对于元素a有P种选择，元素b有Q种选择，则S的大小为P*Q

排列

一.不可重复排列数

从n种不同的物品中不重复的选出r个物品，P(n,r)=n!/(n-r)!

二.可重复排列数

从n种不同的物品中可重复的选出r个物品，P(n,r)=n^r

组合

C(n,r)=n!/r!(n-r)!

性质1：C(n,r)=C(n,n-r)

性质2：C(n,r)=C(n-1,r)+C(n-1,r-1) 杨辉三角的递推写法就用到了这项定理

性质3：C(n,0)+C(n,1)+C(n,2)+C(n,3)+......+C(n,n)=2^n 这个性质体现了组合数与二进制数的关系

下面给出杨辉三角的递推写法的代码

#include<bits/stdc++.h>
using namespace std;
int n,a[25][25];
int main(){
	cin>>n;
	a[1][1]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			a[i][j]=a[i-1][j]+a[i-1][j-1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cout<<a[i][j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

多重集的排列和组合

一.无限多重集的排列

设集合S是一个多重集，它有k个不同的元素，P(|S|,r)=k^r

二.有限多重集的排列

设集合S是一个多重集，它有k个不同的元素,每个元素的个数分别是n₁,n₂,n₃,......,n_k,那么S的大小为n=n₁+n₂+n₃+......+n_k,则P(|S|,r)=n!/n₁!n₂!n₃!......n_k!