当前位置: 首页> 教育> 就业 > 排列组合数

排列组合数

时间:2025/7/12 2:51:21来源:https://blog.csdn.net/qq_40052678/article/details/141991975 浏览次数:0次

排列组合数

概述

排列数:
从n个不同元素,任取个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号(或者是)表示。

组合数:
从n个不同元素中,任取 个元素组成一个集合,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。用符号来表示,组合数也常用表示

各种排列

不相邻的排列

1-n这n个自然数中选k个,这k个中任何两个数都不相邻的组合有

错位排列

我们把错位排列问题具体化,考虑这样一个问题:

n封不同的信,编号分别是1,2,3,4,5,现在要把这五封信放在编号1,2,3,4,5的信封中,要求信封的编号与信的编号不一样。问有多少种不同的放置方法?

假设我们考虑到第n个信封,初始时我们暂时把第n封信放在第n个信封中,然后考虑两种情况的递推:

前面n-1个信封全部装错;
前面n-1个信封有一个没有装错其余全部装错。
对于第一种情况,前面n-1个信封全部装错:因为前面n-1个已经全部装错了,所以第n封只需要与前面任一一个位置交换即可,总共有种情况。

对于第二种情况,前面n-1个信封有一个没有装错其余全部装错:考虑这种情况的目的在于,若n-1个信封中如果有一个没装错,那么我们把那个没装错的与n交换,即可得到一个全错位排列情况。

其他情况,我们不可能通过一次操作来把它变成一个长度为 的错排。

于是可得错位排列的递推式为。

错位排列数列的前几项为0,1,2,9,44,265。

圆排列

n个人全部来围成一圈,所有的排列数记为。考虑其中已经排好的一圈,从不同位置断开,又变成不同的队列。 所以有

部分圆排列公式

三种求组合数的方法

通过预处理

代码

#include<bits/stdc++.h>  
using namespace std;  
const int N=2005,mod=1e9+7;  
int c[N][N];  
void init(int n,int m)  
{  for(int i=0;i<=n;i++)  {  for(int j=0;j<=i;j++)  {  if(j==0) c[i][j]=1;  else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;  }  }  
}  
int main()  
{  init(2000,2000);  int n,a,b;  20.   cin>>n;  for(int i=1;i<=n;i++)  {  cin>>a>>b;  cout<<c[a][b]<<endl;  }  return 0;  
}  

随取随用,可预处理逆元和阶乘

代码

#include<bits/stdc++.h>  
#define int long long  
using namespace std;  
const int N=1e5+5,mod=1e9+7;  
int fac[N],infac[N];  
int qpow(int a,int n,int mod)  
{  int ans=1;  while(n)  {  if(n&1) ans=ans*a%mod;  a=a*a%mod;  n>>=1;  }  return ans;  
}  
void init()  
{  fac[0]=1;  infac[0]=1;  for(int i=1;i<N;i++)  {  fac[i]=fac[i-1]*i%mod;  infac[i]=infac[i-1]*qpow(i,mod-2,mod)%mod;  }  
}  
int C(int a,int b)  
{  return fac[a]*infac[b]%mod*infac[a-b]%mod;  
}  
signed main()  
{  int n;  cin>>n;  init();  //for(int i=1;i<=100;i++) cout<<fac[i]<<" "<<infac[i]<<endl;  for(int i=1;i<=n;i++)  {  int a,b;  cin>>a>>b;  cout<<C(a,b)<<endl;  }  return 0;  
}  

Lucas定理,当p为质数时,有

代码

#include<bits/stdc++.h>  
#define int long long  
using namespace std;  
int qpow(int a,int n,int mod)  
{  int ans=1;  while(n)  {  if(n&1) ans=ans*a%mod;  a=a*a%mod;  n>>=1;  }  return ans;  
}  
int C(int a,int b,int p)  
{  int res=1;  for(int i=1,j=a;i<=b;i++,j--)  {  res=res*j%p*qpow(i,p-2,p)%p;  }  return res;  
}  
int lucas(int a,int b,int p)  
{  if(a<b) return 0;  if(a<p&&b<p) return C(a,b,p);  else return lucas(a%p,b%p,p)*lucas(a/p,b/p,p)%p;  
}  
signed main()  
{  int n;  cin>>n;  for(int i=1;i<=n;i++)  {  int a,b,p;  cin>>a>>b>>p;  cout<<lucas(a,b,p)<<endl;  }  return 0;  
}
关键字:排列组合数

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: