组合数学初步

1、组合数学组合数学简介 组合数学起源于古老的数学娱乐和游戏。而在当今社会中同样发挥着重要的作用。 组合数学研究一个集合的物体进行满足一些规则的排列。具体的说，组合数学研究的是这些排列的存在性、计数和分类。 在ACM/ICPC中用到的组合数学知识有： 一一对应原理、加法乘法原理、多重集排列和组一一对应原理、加法乘法原理、多重集排列和组合、排列生成、递推关系、母函数、鸽巢原理、合、排列生成、递推关系、母函数、鸽巢原理、容斥原理、群和置换群、贝恩塞特引理和波利亚容斥原理、群和置换群、贝恩塞特引理和波利亚定理定理 一一对应原理一一对应原理 “一一对应一一对应”概念是一个在计数中极为概念是一个在计数中极为

2、基本的概念。一一对应既是单射又是满基本的概念。一一对应既是单射又是满射。射。 如我们说如我们说A A集合有集合有n n个元素个元素 |A|=n|A|=n，无非，无非是建立了将是建立了将A A中元与中元与1,n1,n元一一对应的元一一对应的关系。关系。 在组合计数时往往借助于一一对应实现在组合计数时往往借助于一一对应实现模型转换。模型转换。 比如要对比如要对A A集合计数，但直接计数有困难，集合计数，但直接计数有困难，于是可设法构造一易于计数的于是可设法构造一易于计数的B B，使得，使得A A与与B B一一对应。一一对应。 例例 在在100100名选手之间进行淘汰赛名选手之间进行淘汰赛( (即一

3、即一场的比赛结果，失败者退出比赛场的比赛结果，失败者退出比赛),),最后最后产生一名冠军，问要举行几场比赛？产生一名冠军，问要举行几场比赛？ 一一对应一一对应例例 含有含有n n个元素的集合的所有子集个数为个元素的集合的所有子集个数为2 2n n解解 一种常见的思路是按轮计场，费事。一种常见的思路是按轮计场，费事。 另一种思路是另一种思路是淘汰的选手淘汰的选手与与比赛比赛( (按场计按场计) )集集一一对应一一对应。9999场比赛。场比赛。 一一对应一一对应例：求集合例：求集合1,2,1,2,n,n的不含相邻整数的的不含相邻整数的k k元子集的个数。元子集的个数。分析：每个满足条件的分析：每个

4、满足条件的k k元子集都和一个元子集都和一个0101有序串对应，且这个有序串没有两有序串对应，且这个有序串没有两1 1相邻。相邻。这样的串含有这样的串含有k k个个1 1，每个，每个1 1前面的前面的0 0的个数的个数是不同，又与是不同，又与0,1,0,1,n-k,n-k 中选中选k k个不同的个不同的元素对应。所以结果元素对应。所以结果= =c(n-k+1,k)c(n-k+1,k) 某机要部门安装了电子锁。M(M8)工作人员每人发一张磁卡，卡上有开锁的密码特征。为了保证安全，规定至少要有N(N=0)的一个非负整数解对应。x1+x2+xk=r的一个非负整数解r1,(k-1)*的一个排列对应。例

5、例 令令S S是具有是具有4 4种元素种元素a,b,c,da,b,c,d的多重集的多重集 1010a,10a,10b,10b,10c,10c,10dd求求S S的使得的使得4 4种元素的种元素的每一种都至少出现一次每一种都至少出现一次的的10-10-组合组合的数目是多少？的数目是多少？多重集的组合多重集的组合分析：相当于求从多重集的分析：相当于求从多重集的6-组合，即组合，即数目数目=C(6+4-1,4)例例 求方程求方程 x x1 1+ x+ x2 2+ x+ x3 3+ x+ x4 4=20=20的整数解的个数？的整数解的个数？其中其中x x1 1=3, x=3, x2 2=1, x=1,

6、 x3 3=0,x=0,x4 4=5=5例例 某餐厅有某餐厅有7 7种不同的菜，为了招待朋种不同的菜，为了招待朋友，一个顾客需要买友，一个顾客需要买1414个菜，问有多少个菜，问有多少种买法？种买法？r r个无区别的球，放进个无区别的球，放进n n个有标志的盒子，个有标志的盒子，每个盒子中可多于一个，则共有每个盒子中可多于一个，则共有C(n+r-1,r)C(n+r-1,r)种方案。种方案。注：注：盒子盒子i i中放进几个球，中放进几个球，i i就被重复了几次。就被重复了几次。例如：试问例如：试问(x+y+z)(x+y+z)4 4有多少项？有多少项？分析：（分析：（x+y+z)(x+y+z)(x

7、+y+z)(x+y+zx+y+z)(x+y+z)(x+y+z)(x+y+z) )相当于相当于4 4个无区别的球放进个无区别的球放进3 3个盒子里个盒子里例如：例如：(x(x1 1+x+x2 2+ +x+xr r) )n n有多少项？有多少项？xyz 多重集的组合的应用多重集的组合的应用全排列的生成算法全排列的生成算法 就是对于给定的字符集，用有就是对于给定的字符集，用有效的方法将所有可能的全排列效的方法将所有可能的全排列无重复无遗漏无重复无遗漏地枚举出来。地枚举出来。 全排列的生成算法全排列的生成算法这里介绍全排列算法三种：这里介绍全排列算法三种：(A)(A)字典序法字典序法(B)(B)序数法

8、序数法( (C)C)邻位对换法邻位对换法先学习一种整数的表示法。先学习一种整数的表示法。n!=(n-1)(n-1)!+(n-1)!n!=(n-1)(n-1)!+(n-1)!(n-1)!=(n-2)(n-2)!+(n-2)!(n-1)!=(n-2)(n-2)!+(n-2)!.3!=23!=2* *2!+2!2!+2!所以所以 n!=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+n!=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+2+2* *2!+22!+21!11nkkk11!1!nkkkn2.9.2 2.9.2 序数法序数法0 0到到n!-1

9、n!-1之间的任一整数之间的任一整数m m可唯一表示成可唯一表示成 m=am=an-1n-1(n-1)!+a(n-1)!+an-2n-2(n-2)!+(n-2)!+a+a1 11!1!m m与序列与序列(a(an-1n-1, a, an-2n-2, , a, a1 1) )一一对应一一对应n n个元素的全排列与个元素的全排列与0,n!-10,n!-1一一对应一一对应n n个元素的全排列与个元素的全排列与(a(an-1n-1, a, an-2n-2, , a, a1 1) )一一对应一一对应2.9.2 2.9.2 序数法序数法如何求与如何求与m对应的序列对应的序列(an-1, an-2, a1)

10、？ m除以2的余数为a1,商为b1 b1除以3的余数为a2,商为b2 b2除以4的余数为a3,商为b3 bn-2除以n的余数为an-1.n个元素的全排列与(an-1, an-2, a1)一一对应2.9.2 2.9.2 序数法序数法如何求与序列如何求与序列(an-1, an-2, a1)对应的全排列？对应的全排列？ ai表示i+1所在位置右边比i+1小的数的个数 所以 0=aiiji的所有的所有i, ai, ai i=0, =0, 改变改变a aj+1j+1。组合生成算法组合生成算法（所有的）（所有的）1,2,1,2,n,n的的r-r-组合的第一个是组合的第一个是1,2,1,2,r,r，最后一个

11、是最后一个是n-r+1,n-r+2,n-r+1,n-r+2,n.,n.只要一个组合只要一个组合c c1 1c c2 2c cr r中存在中存在c cj jn-r+jn-r+j，说明说明此组合还有下一个组合。此组合还有下一个组合。求其下一个组合的步骤如下：求其下一个组合的步骤如下：1 1）求）求2 2）3 3）|maxjrncjij1iiccriijccjj,.,2,1,111iicc组合生成算法组合生成算法（r-r-组合）组合） 定义：定义：对于序列 构造一函数：,210aaa,)(2210 xaxaaxG,210aaa称函数G(x)是序列 的母函数母函数的定义母函数的定义母函数应用举例母函数

12、应用举例例例 确定苹果、香蕉、橘子和梨的确定苹果、香蕉、橘子和梨的n-n-组合个数，其中组合个数，其中在每个在每个n-n-组合中苹果的个数是偶数，香蕉的个数是组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在奇数，橘子的个数在0 0和和4 4之间，而且至少要有一个梨。之间，而且至少要有一个梨。xxxxxxxxxxxxxxxxxxxxg111111.)(1.)(.)(1 ()(522324325342母函数简单应用举例例例 某单位有某单位有8 8位男同志，位男同志，5 5位女同志，现要组织一位女同志，现要组织一个由偶数个男同志和数目不少于个由偶数个男同志和数目不少于2 2个女同志组成的小个女

13、同志组成的小组，试求有多少种组成方式？组，试求有多少种组成方式？8642)6 , 8()4 , 8()2 , 8(1)(xxCxCxCxA5432)4 , 5()3 , 5()2 , 5()(xxCxCxCxB)()()(xBxAxC例例 投掷一次筛子，出现点投掷一次筛子，出现点1 1，2 2，6 6的概率均的概率均为为1/61/6，问连续投掷两次出现点数之和为，问连续投掷两次出现点数之和为1010的概率？的概率？如果连续投掷如果连续投掷1010次，其点数之和为次，其点数之和为3030的概率？的概率？例例 确定方程确定方程的非负整数解的个数的非负整数解的个数h hn n的个数。的个数。nxxx

14、x43215243分析：令分析：令f f1 1=3x=3x1 1， f f2 2=4x=4x2 2， f f3 3=2x=2x3 3， f f4 4=5x=5x4 4，于是问题等价于求方程于是问题等价于求方程的非负整数解，其中的非负整数解，其中f f1 1是是3 3的倍数，的倍数， f f2 2是是4 4的的倍数，倍数， f f3 3是是2 2的倍数，的倍数， f f4 4是是5 5的倍数。的倍数。nffff4321母函数应用举例母函数应用举例.)1.)(1 (.)1.)(1 ()(105428463xxxxxxxxxg母函数应用母函数应用整数的拆分整数的拆分整数的拆分就是把正整数整数的拆分就

15、是把正整数n n分解成若干正分解成若干正整数的和。通常用整数的和。通常用p(n)p(n)表示表示n n的拆分数。的拆分数。如如5 5可以拆分成：可以拆分成： 5 5，4+14+1，3+23+2，1+1+31+1+3，2+2+12+2+1， 1+1+1+21+1+1+2，1+1+1+1+11+1+1+1+1等价于将等价于将n n个无区别的球放到一些无区别个无区别的球放到一些无区别的盒子中，有多少种放法？的盒子中，有多少种放法？)1)(1)(1 (63422xxxxxxx xn n系数表示系数表示n n拆分成拆分成1 1、2 2、3 3的允许重复的拆分数的允许重复的拆分数nxxxx11111111

16、32的的x xn n系数表示系数表示n n的所有拆分数的所有拆分数整数拆分举例整数拆分举例例例 若有若有1 1克、克、2 2克、克、3 3克、克、4 4克的砝码各克的砝码各1 1枚，枚，能称出几种可能的重量？能称出几种可能的重量？1098765432432222221)1)(1)(1)(1 ()(xxxxxxxxxxxxxxxg整数拆分举例整数拆分举例例例 求求1 1角、角、2 2角、角、3 3角的邮票可贴出不同数值角的邮票可贴出不同数值邮资的方案数的母函数。邮资的方案数的母函数。.)1.)(1.)(1 ()(63422xxxxxxxg以以整数拆分整数拆分为例：为例：观察以下的母函数：观察以下

17、的母函数：首先思考：首先思考：如果让你手工计算，你是怎样处理的？如果让你手工计算，你是怎样处理的？实际编程：实际编程：让计算机按照自己的思路计算即可让计算机按照自己的思路计算即可/ Author by lwg#include using namespace std;const int lmax=10000; int c1lmax+1,c2lmax+1;int main()int n,i,j,k;while (cinn)for (i=0;i=n;i+) c1i=0;c2i=0; for (i=0;i=n;i+) c1i=1; for (i=2;i=n;i+)for (j=0;j=n;j+)for

18、 (k=0;k+j=n;k+=i) c2j+k+=c1j; for (j=0;j=n;j+) c1j=c2j;c2j=0; coutc1nendl;return 0;主打例题：主打例题：HDOJ_1398 Square CoinsHDOJ_1398 Square Coins Sample InputSample Input2 2101030300 0 Sample OutputSample Output1 14 42727算法分析：算法分析：典型的利用母函数可解的题目。典型的利用母函数可解的题目。G(x)=(1+x+x2+x3+x4+)(1+x4+x8+x12+)(1+x9+x18+x27+)

19、/HDOJ_1398 Square Coins#include using namespace std;const int lmax=300;int c1lmax+1,c2lmax+1;int main(void)int n,i,j,k;while (cinn & n!=0)for (i=0;i=n;i+)c1i=1;c2i=0;for (i=2;i=17;i+)for (j=0;j=n;j+)for (k=0;k+j=n;k+=i*i)c2j+k+=c1j;for (j=0;j=n;j+)c1j=c2j;c2j=0;coutc1nn & n!=0)for (i=0;i=n;i

20、+)c1i=1;c2i=0;for (i=2; i=17; i+)for (j=0;j=n;j+)for (k=0;k+j=n; k+=elemi-1 ) c2j+k+=c1j;for (j=0;j=n;j+)c1j=c2j;c2j=0;coutc1nendl;return 0;指数型母函数的定义指数型母函数的定义定义定义 对于序列对于序列a a0 0,a,a1 1,a,a2 2, ,定义定义 称为序列称为序列aai i 的指数型母函数。的指数型母函数。例例 序列序列(0!,1!,2!,(0!,1!,2!,) )的指数型母函数为的指数型母函数为 .! 3! 2! 1)(332210 xaxax

21、aaxGexxxxxx11.1.! 3! 3! 2! 2! 1! 1! 0232指数型母函数应用举例指数型母函数应用举例例例 由由a,b,c,da,b,c,d这这4 4个字符取个字符取5 5个进行排列，要求个进行排列，要求a a的出现次数不超过的出现次数不超过2 2次，但不能不出现次，但不能不出现,b,b不不超过超过1 1次，次，c c的出现次数不超过的出现次数不超过3 3次，次，d d的出现的出现次数为偶数。求满足上述条件的排列数。次数为偶数。求满足上述条件的排列数。.! 5215! 464! 318! 25.244338325)! 4! 21)(! 3! 21)(1)(! 2! 1()(5

22、432543242322xxxxxxxxxxxxxxxxxxxGe指数型母函数应用举例指数型母函数应用举例例例 n n个有区别的球，放进个有区别的球，放进4 4个有标志的盒子，要个有标志的盒子，要求求1,21,2两盒必须含偶数个球，第两盒必须含偶数个球，第3 3盒含奇数个球。盒含奇数个球。问有多少种不同的方案？若放进问有多少种不同的方案？若放进m m个有标志的个有标志的盒子，要求无一空盒，有多少种方案？盒子，要求无一空盒，有多少种方案？.)! 3.)(! 21 (.)! 4! 21 ()(32242xxxxxxxGemexxxxG.)! 3! 2()(32指数型母函数应用举例指数型母函数应用举

23、例 有袋子里均匀地装着c种颜色的巧克力，每种巧克力均有无限多。佳佳每次从袋子里拿一块放在桌子上，如果桌子上已经有一块颜色相同的巧克力，佳佳就把两块巧克力都吃掉。佳佳一共取出n块巧克力，请问最后桌子上有m块的概率有多大？例如c=5,n=100,m=2时概率为0.6251028、1709、1085、1171、1398、2069、2152其它相关题目（比如求邮票、硬币之类的组合数、整数的不同拆分数等） 递推关系递推关系例例 古代有古代有1 1国王要奖赏他的臣子，问他要什么国王要奖赏他的臣子，问他要什么臣子说我的要求不高，臣子说我的要求不高，8 8* *8 8的棋盘上第的棋盘上第1 1格子放格子放1

24、1个麦粒，第个麦粒，第2 2格子放格子放2 2个麦粒，第个麦粒，第3 3格子放格子放2 22 2个麦个麦粒，第粒，第6464个格子放个格子放2 26363个麦粒。个麦粒。兔子问题The rabbits have powerful reproduction ability. One Pairof adult rabbits can give birth to one pair of kid rabbits everyMoth. And after m months,the kid rabbits can become adultrabbits. As we all know,when m=2,t

25、he sequence of the Number of pars of rabbits in each month is called FibonacciSequence. But when m2 ,the problem seems not so simpleYou job is to calculate atfer d months how many pairs of Rabbits are there.整数拆分举例整数拆分举例( 难一点）难一点）给定n个各不相同的球和m个不同的盒子，有多少种不同的放球方法，使得每个盒子中球数不小于k。（一个acm题）分析：设anm表示将n个不同的球放到

26、m个不同盒子的满足条件的方法数。则有 ( , ) 1ni ka n mc n i a ni m例例: :（20502050）折线分割平面）折线分割平面问题描述问题描述： 平面上有平面上有n n条折线，问这些折线最多能将平面分割条折线，问这些折线最多能将平面分割成多少块成多少块? ?样例输入样例输入1 12 2样例输出样例输出2 27 7F(nF(n)=F(n-1)+4(n-1)+1)=F(n-1)+4(n-1)+1“佐罗佐罗”的烦恼的烦恼说起佐罗，大家首先想到的除了他脸上的面具说起佐罗，大家首先想到的除了他脸上的面具，恐怕还有他每次刻下的，恐怕还有他每次刻下的“Z”Z”字。我们知道，字。我们知

27、道，一个一个“Z”Z”可以把平面分为可以把平面分为2 2部分，两个部分，两个“Z”Z”可可以把平面分为以把平面分为1212部分，那么，现在的问题是：部分，那么，现在的问题是：如果平面上有如果平面上有n n个个“Z”,Z”,平面最多可以分割为几平面最多可以分割为几部分呢？部分呢？说明说明1 1：“Z”Z”的两端应看成射线的两端应看成射线说明说明2 2：“Z”Z”的两条射线规定为平行的的两条射线规定为平行的附加思考题（还没加到附加思考题（还没加到OJOJ）：）： 如果正整数构成的集合X满足以下条件，我们称它为n-k特殊集： 集合X中每个元素均不同且不超过n 集合x的所有元素之和大于k 集合x中不包

28、含任意一对相邻的自然数给出n,k,求n-k特殊集合有多少个？如：输入6,3输出17鸽巢原理鸽巢原理 鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有两个或两个以上鸽子。”例例367人中至少有人的生日相同。例例10双手套中任取11只，其中至少有两只是完整配对的。例例参加一会议的人中至少有人认识的别的参加者的人数相等。鸽巢原理之二鸽巢原理之二鸽巢原理二鸽巢原理二m1 , m2 , , mn都是正整数，并有m1 + m2 + +mnn + 1个鸽子住进n个鸽巢，那么，或者第 1个巢中至少有m1个鸽子，或者第 2个巢中至少有m2个鸽子,或者

29、第 n个巢中至少有mn个鸽子 鸽巢原理之二鸽巢原理之二推论推论m只鸽子进n个巢，至少有一个巢里有 只鸽子nm推论推论n(m1) + 1只鸽子进n个巢，至少有一个巢内至少有m只鸽子推论推论若m1 , m2 , , mn是正整数，且 r1,则 m1, , mn至少有一个不小于rm1 + +mn n鸽巢原理的一个例子鸽巢原理的一个例子定理定理若序列S = a1 , a2 , , ann+1中的各数是不等的n 是正整数，则 S有一长度为n+1的严格增子序列或长度为n+1的减子序列12111112.(1).nnnniijiiinnjjkAAAAAAAAAAAA nii=1jikj A+ 容斥原理两个基本

30、公式容斥原理两个基本公式121211112.( 1).nnnnniijiijjkninAAANAAAANAAAAAAAAnii=1 ji kj A- 容斥原理指的就是以上两个基本公式。4.2 容斥原理两个基本公式容斥原理两个基本公式 例例3 从(0,0)到(10,5)点的路径中不通过AB,CD,EF,GH中任一条路径的路径数 4.3 应用举应用举例例(0,0)(10,5)ABCDEFGH某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。 1465 1465 不容易系列之一不容易系列之一 小于n且与n互素的数有多少个？ 如图是一个国际象棋棋盘。两个象互

31、不攻击当且仅当它们不处于同一条斜线上。在一个n*n(n=30)的棋盘上放k个互不攻击的象有多少种方法？棋盘多项式棋盘多项式我们把棋盘的形状推广到任意形状： 布子规定称为无对攻规则，任意两棋子不放在同行同列上。 令r k（C）表示k个棋子布到棋盘C上的方案数。如：r1( )=1，r1( )=2，r1( )=2，r2( )=0，r2( )=1。为了形象化起见，（ ）中的图象便是棋盘的形状。定义定义设C为一棋盘，称R(C)= rk(C) xk为C的棋盘多项式。规定 r0(C)=1，包括C=时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有

32、rk(C)=rk1(Ci)rk(Ce)，k=0)()()(1)()()(1)()(1111110eikkekkkikkkekikkkkCRCxRxCrxCrxxCrCrxCrCR例如：R( )=1+ x；R( )= xR( )+ R( )= x+ (1+ x)=1+2x；R( )= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x2 如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有： rk(C) = ri(C1) rki(C2) i=0k故R(C) = ( ri(C1) rki(C2) ) xk = ( ri(C1) xi

33、) ( rj(C2) xj )j=0nnkni=0i=0k=0 R(C) = R(C1) R(C2)利用前述的R(C)的两式，可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例例R ( ) = xR( )+R( ) = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3*R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x3* 其中有红色的格子表示禁区。 R( )=1+6x+10 x2+4x3 方案数=4!6(41)!+10(42)!4(43)! +0(44)!=4群的概念定义 ：给定(G, )，若满足下列4个条件： （1）封

34、闭性 若a,bG,则a bG （2）结合律 （3）存在单位元素 （4）存在逆元素就叫群。群的元素个数叫有限群，有限群的元素个数叫群的阶。满足交换律的群叫阿贝尔群。例 （R,+）是群。（R-0,）是群。置换群置换可视为集合1,2,n到其自身的一个一对一的函数. naaaanp321321置换的复合运算定义为123443211243432121pp4312432121pp则循环、换位 132121aaaaaaaannn置换 可表示为)(21naaa 叫做n阶循环。例如，)13245(1524354321)2)(1435(1352454321)5)(4)(3)(2)(1 (5432154321128

35、965734987654321p例如，145692378循环只与元素的相邻状况有关，而与哪个元素为首无关。定理：任何一个置换都可以表示成若干循环的乘积。定义：2阶循环(ij)叫作i和j的换位换位。定理：任何一个循环都可表示成若干 换位之积。如(123n)=(12)(13)(1n) )123(3211232131231312可用数学归纳法证明此定理。1234567821345678置换群的应用举例 佳佳最喜欢与老师和小伙伴们一起玩传球的游戏。游戏开始时所有小朋友分成两组，每组n人，围成一个圈。每个小朋友都有一个编号(1n)这个编号在其所在组是唯一的。游戏开始之前，每个小朋友都有一个球，球上有编号

36、(1.n)，并且一个组中的球不会有两个相同的编号。然后，所有小朋友必须闭上研究，游戏开始。随着老师口中的哨子发出的节奏，每个小朋友都用一只手把球传到右边，而用另一只手接左边的来球。 突然，老师的哨子停了，关键的时刻到了。小朋友马上睁开眼睛，开始与同组的小朋友进行传球，争取以最短的时间把球传到位。传到位是指一个组中的每一个小朋友手上的球的编号与他自己的编号相同。最后获胜的就是那个最先把球传到位的组 这个游戏非常有趣，小朋友们玩了许多次。聪明的佳佳总结出一条经验：总是两个人之间的对传。 现在需要你写一个程序，帮助小朋友们确定传球方法。 问题：至少需要几次对传才能将球传到位 问题：至少需要多少时间才能将球传到位。每一个时间单位一个小朋友可以不做任何动作，也可以与另一个小朋友之间进行对传 你弟弟有一项家庭作业需要你帮助完成。老师给了他一列数，需要他半这些数按升序排列。你可以每次交换两个数的位置，而一次交换的代价被定义成交换的两个数的和。写一个程序，用最小的交换代价和来帮助弟弟完成这项无聊的排序工作置换群的应用举例贝恩塞特引理设 是X=1,2,n上的置换群，G对X所划分的不同的等价类个数为)(.)()(