1.4圆周排列

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

 

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

 

 

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

1.6.1允许重复的组合

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

 

• 定理1-2
• 在$n$n个不同元素中取$r$r个作允许重复的组合,
• 为$C(n+r-1,r)$C(n+r−1,r)

 

• 只证允许重复的组合和从$n+r-1$n+r−1个不同元素中取$r$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个作允许
  重复组合.