排列与组合的应用四川成都市大弯中学 李植武摘要 在信息学奥林匹克竞赛中，多次出现了排列与组合的竞赛题目。

本文介绍了排列与组合的概念、公式，重点讲解了排列与组合的生成算法，最后通过几个竞赛题目的解决，体现了排列与组合在信息学竞赛中的应用。

关键词 排列 组合 生成 应用说明：本文中的pascal 程序在Lazarus v0.9.22 beta 下调试完成，c 程序dev-c++ 4.9.9.2下调试完成，所有程序通过相应数据测试。

一、排列与组合 1．排列及公式 (1)线排列一般地，从n 个不同元素中，取出m(m ≤n)个元素按照一定的顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个线排列；从n 个不同元素中取出m(m ≤n)个元素的所有线排列的个数，叫做从n 个不同元素中取出m 个元素的排列数，用符号 m n A 表示。

)!(!A1)-m -...(n )2)(1(mn m n n n n n A mn -=--= 规定 0！＝1。

(2)圆排列从n 个不同元素中取出m 个元素按照某种次序（如逆时针）排成一个圆圈，称这样的排列为圆排列，圆排列个数为)!(!m n m n m A mn -=。

因为从n 个不同元素中取出m 个元素排成一列的个数是mn A 。

不妨设一个排列是：a 1a 2…a m 。

而这个排列与排列a 2…a m a 1, a 3…a m a 1a 2,…, a m a 1a 2…a m-1，是一样的圆排列，共有m 个，所以一个圆排列对应m 个普通排列，所以有圆排列数mA mn。

(3)无限重排列从n 个不同元素中取r 个元素按次序排列，每个元素可以取无限次，这样的排列称为无限重排列。

显然，其排列数为n r 。

(4)有限重排列从k 个不同元素{ a 1a 2…a k }中取n 个元素按次序排列，元素a i 可以取r i次,r 1+r 2+...+r k =r ，这样的排列称为有限重排列。

实际上,这个问题与下面的问题等价：把r(r 1+r 2+...+r k =r)只彩色球放到n 个编号不同的盒子中去的方法数!!...!21k r nr r r A 。

如r=n,则排列数有!...!!!21k r r r n ⨯⨯⨯。

(5)错排问题一个排列使得所有的元素都不在原来的位置上，则称这个排列为错排。

例如有3个元素，原来位置为：1 2 3，它的错排有两种3 1 2和2 3 1。

用f[n]表示n 个元素的错排数，利用容斥原理可以推出（过程略）：f[n]=]!1)1(......!21!111[!n n n -+++-。

主要讲一下递推式。

考虑任意一个满足条件的排列a 1,a 2,a 3,…,a n ,显然有a n ≠n,不妨设n=a i ,考虑书i 的位置，它有两种情况：1)i=a n 2)i ≠a n对于1)，数i 在位置n,而数n 在位置i 上，则是n-2的错排问题，这种情况的方法数为f[n-2]。

对于２)，可以把位置n 看成位置i （位置i 上不放数i,而此时位置n 也不放数i ，所以i 和n 可以等同看待）,则问题成了n-1个数的错排问题了。

由1)与2)及i 有n-1种取值，所以有f[n]=(n-1)(f[n-2]+f[n-1])。

：2．组合及公式 (1)非重组合一般地，从n 个不同元素中，取出m(m ≤n)个元素，不允许元素重复，不考虑元素次序，叫做从n 个不同元素中取出m 个元素的一个非重组合；从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数.用符号mn C 表示.1)!(!!!)1)...(2)(1(0=-=+---==n m n m m mn mn C m n m n C m m n n n n A A C 规定组合数的两个性质：11-+-+==m nm n m n mn nm n CC CC C（2）重组合从n 个不同元素中,取出r 个允许重复的元素而不考虑其次序时，称为从n 个不同元素中取r 个允许重复的组合，简称重组合。

其组合数为)!1(!)!1(1--+=-+n r r n C r r n .这个问题，可以看作用r 个相同的标记去标明这n 个不同的对象，而每一个对象可以被标上多个标记，一个对象上最多r 个标记。

设n 个元素为{ a 1a 2…a n }，记a i 被记了k 次为a i(k),同一个元素标记不同次数，认为是不同的元素，那么第1次标记有n 种方法，有n+1个元素{ a 1a 2…a n a i(k)},第2次标记就有n+1种方法，有n+2个元素，……第r 次标记有n+r-1种方法，有n-r 个元素，而标记顺序对结果没有影响，所以有r!1)-r (n 1)n(n +⋯+种方法，即)!1(!)!1(1--+=-+n r r n C rr n 。

二、排列与组合生成算法 1.排列生成有N 本不同的书摆在书架上，设其编号分别为１，２，３，......，Ｎ，编程求解这Ｎ本书的不同摆放方案和摆放方案总数。

程序名：pailie.pas/c/cpp 输入文件：pailie.in 输出文件：pailie.out 输入文件的格式为：仅为一个数N输出文件的格式为：依次为每一行为一种方案,每个数之间用一个空格隔开，最后一行为方案数 样例 input2output 1 2 2 1 2数据规模 1=<N<=10说明，排列方案字典顺序小的在前。

分析：本题要求出所有具体方案，所以用不着排列公式来计算方案数。

生成排列方案的过程中可以统计出方案总数。

（１）按字典序生成排列法（根据上一个排列产生下一个排列）。

该算法的Ｎ—Ｓ流程图如图１。

Pascal 版参考程序： program pailie;vars,j,t,i,k,n:Longint;a:array[1..10]of longint;function fi:longint;vari:longint;begini:=n;while (i>1)and(a[i-1]>a[i]) do dec(i);fi:=i;end;function fk:longint;vark:longint;begink:=n;while (k>1)and(a[k]<a[i-1])do dec(k);fk:=k;end;procedure print;vari:longint;begininc(s);for i:=1 to n-1 do write(a[i],' ');writeln(a[n]);end;beginassign(input,'pailie.in');assign(output,'pailie.out');reset(input);rewrite(output);readln(n);for i:=1 to n do a[i]:=i;s:=0;print;i:=fi;while i>1 dobegink:=fk;t:=a[i-1];a[i-1]:=a[k];a[k]:=t;for j:=i to (n+i)div 2 dobegint:=a[n+i-j];a[n+i-j]:=a[j];a[j]:=t;end;print;i:=fi;end;writeln(s);close(input); close(output); end.（２）回溯算法产生排列用p[i]记录一个排列的第i个数，{没有用已用ifalseitrueia=][伪代码描述的产生排列的第i个数的方法Procedure try(i)BeginIf i>n then begin 输出排列；返回end;//产生了一个完整排列，输出For j=1 to n doIf not a[j] then // j这个数没有用BeginP[i]=j;A[j]=true;//占位Try(i+1);//搜索下一个数End;End;Pascal版参考程序：program pailie;varp:array[1..10] of longint;a:array[1..10] of boolean;n,tot,i:longint;fil:text;procedure print;vari:longint;begininc(tot);for i:=1 to n dowrite(fil,p[i],' ');writeln(fil);end;procedure tryy(i:longint);varj:longint;beginif i>n then begin print;exit end;for j:=1 to n doif not a[j] thenbegina[j]:=true;p[i]:=j;tryy(i+1);a[j]:=false;end;end;beginassign(fil,'pailie.in');reset(fil);readln(fil,n);close(fil);assign(fil,'pailie.out');rewrite(fil);fillchar(a,sizeof(a),false);tot:=0;tryy(1);writeln(fil,tot);close(fil);end.C语言版参考程序：# include <stdio.h>long a[15],n,s;bool f[15];FILE *fp;void shu(long a[]){long i;for (i=1;i<=n;i++)fprintf(fp,"%d ",a[i]);fprintf(fp,"\n");s++;}void pai(long i){long j,k;if (i==n+1) { shu(a); return; }for (j=1;j<=n;j++)if (f[j]) { f[j]=false; a[i]=j; pai(i+1); f[j]=true; }}int main(){long i,j,k,m;fp=fopen("pailie.in","r");fscanf(fp,"%d",&n);fp=fopen("pailie.out","w");for (i=1;i<=n;i++) f[i]=true;s=0; pai(1);fprintf(fp,"%d\n",s);fclose(fp);return 0;}2.组合生成有N本不同的书摆在书架上，设其编号分别为１，２，３，......，Ｎ，现要从其中取出Ｒ本书，编程求解这Ｎ本书的不同组合方案和方案总数。