本文共 1402 字，大约阅读时间需要 4 分钟。

1.4圆周排列

• n个取r个在圆周上排列数以$Q(n,r)$

• 圆周排列与排列不同之处在于圆周排列头尾相邻,
• a,b,c,d
• abcd,dabc,cdab,bcda是不同的排列,但属同一个圆周排列

• 例1-25
• 5男,3女围一圆,则$Q(8,8)=7!=5040$
• 若男生$B_1$不和女生$G_1$相邻多少方案?
• 若3女不相邻,多少方案?
• 方法1
  • 先将G1排除,7人围一圆桌,然后G1插入,如图1-10
  • G1插入有5种选择,故B1和G1不相邻方案数

• 方法2
  • 先求B1和G1相邻而坐的方案数

• 若3女不相邻,
  • 5男围圆桌,然后3女依次插入

• 例1-26
• n对夫妻一圆桌,每对夫妻相邻而坐
• 夫妻相邻而坐但可交换位置
• $(n-1)!\times 2^n$

• 例1-27
• (1)12人分两桌,每桌6,圆桌
• (2)12对夫妻平分两圆桌
  • 每对夫妻必须相邻而作

1.5 排列的生成算法

• 若说以前讨论了排列的个数,这节则将这些排列一一罗列出

• 有时要在计算机上模拟各种排列状态下出现的情况加以分析,
• 若干排列的生成算法

1.5.1序数法

1.6允许重复的组合与不相邻的组合

1.6.1允许重复的组合

• A = { 1 , 2 , 3 } A=\{1,2,3\} A={
  1,2,3},取两个作允许重复的组合
  • {1,2},{1,3},{2,3}外
  • 还{1,1},{2,2},{3,3}
• 允许重复的组合的模型是$r$个球无标志
  • $n$盒子有区别
  • 取出$r$个球放进盒子,每盒子许多于一球
• 不允许重复的组合模型是$n$球有标志,$r$盒无区别
  • 取$r$个球放进盒子,每盒一个球

• 定理1-2
• $n$个不同元素中取$r$个作允许重复的组合
  • 有n种球，但每种都很多哦
• 为$C(n+r-1,r)$

• 只证允许重复的组合和从$n+r-1$个不同元素中取$r$个作不允许重复的组合一一对应

• 先证从n个元素中取r个作允许重复的组合,和从n+r-1个不同元素中取r个作不允许重复的组合对应.

  不失一般性,假定n个元素为1,2,…,n,从中取r个允许重复的组合a1,a2,…,a.由于允
  许重复,假定
  a1≤a2≤…≤ar
  从(a1,a2,…,a,)引出(a1,a2+1,a3+2,…,ar+r-1),a1,a2+1,a3+2,…,a,+r-1互不
  相同,而且a+ァー1≤n+r-1.这就证明了每一个1到n取r个作允许重复的组合(a1,a2,…,
  a,),对应一个从1到n+r-1取r个作不重复的组合(a1,a2+1,…,a,+r-1)
  反过来每一个从1到n+rー1中取r个作不重复的组合(ん1,h,…,b),对应一个从1到n
  取r个作允许重复的组合,假定
  b<b2<b<…・<b≤m+rー1
  令
  b3-2
  于是有
  即从1到n+rー1取r个作不允许重复组合(b,…,b)对应于一个从1到n取r个作允许
  重复组合.

1.9 Stirling公式

• 组合数学中经常遇到n!的计算,
• 随着n增长,n!的增长极快。

转载地址：https://cyj666.blog.csdn.net/article/details/104976871 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！