您在本页停留了

语 文
英 语
其 它
综合

  转化插入法解排列组合


  对于一些不相邻的排列组合问题,或至少一个的组合问题,可以通过转化手段用插入法解题。

  例1.马路上有编号1,2,3…8,9的九只路灯,为节约用电,可以把其中的三只路灯关掉,但不能同时关掉相邻的两只或三只,也不能关掉两端的路灯,满足条件的关灯方法有多少种?
  分析:将问题转化成3个相同的黑球不相邻的插入6个相同的白球行列之间(不包括首尾两侧),有多少种方法?
  解:因为任意相邻2个白球之间最多插1个黑球,于是,这就是从5个位置中任选3个位置的组合问题。故共有 =10种方法。

  例2.某人射击8枪,共命中4枪,并且这4枪中有且仅有3枪连中,那么对于该人射击8枪,按“中”与“不中”报告结果,不同的结果共有多少种?
  分析:把问题转化成4个相同的黑球,其中3个黑球连在一起看成一个,不相邻地插入4个相同的白球行列之间(包括首尾两侧),有多少种方法?
  解:因为任意相邻2个白球之间最多插一个黑球,于是,这就是将2个(三个连在一起的看成一个)黑球插入5个空位,有 =20种方法。

  例3.3个人坐在一排有8个座位的椅子上,若每个人左、右两边都有空位,则不同的坐法种数有多少?
  解:把问题转化成在5个相同的黑球间插入3个不同颜色的球(不包括首尾两侧),共有几种方法: =24种。

  例4.从1,2,3,…,2000这两千个自然数中,取出10个互不相邻的自然数,有多少种方法?
  分析:将问题转化成10名女学生不相邻地插入站成一列横队的1990名男学生之间(包括首尾两侧),有多少种方法?
  解:因为任意相邻2名男学生之间最多站1名女学生,队伍中的男学生首尾两侧最多也可各站1名女学生。于是,这就是1991个位置中任选10个位置的组合问题,故共有 种方法。

  例5.某中学从高中7个班中选出12名学生组成校代表队,参加市中学数学应用题竞赛活动,使代表中每班至少有1人参加的选法共有多少种?
  解:由于12个名额是不可区别的,所以将问题转化成把排成一行的12个0分成7份的方法数,这样用6块闸板插在11个间隔中,共有 =462种不同插法。