一类计数问题的解答模式.docVIP

一类计数问题的解答模式 江苏省无锡市第一中学李广修(214031) 两个经典问题: 问题1 (参见文1)，如图1,墙上挂着两串 礼物A i (i=1，2,…，5)和B j（j=1,2,…，6）， 每次从某一串的最下端摘取一件礼物，这样摘 了11次，可将礼物全部摘完，那么对于这11 件礼物共有多少种不同的摘取顺序？ 问题2(参见文2)，如图2，求从点A顺着纵线或横线走（在纵线与横线交点处可以改变方向）到点B的最短路径数. 我们来分析这两个问题的共性:(1)都是计数型问题.(2)都含有“阵线分明”的两类元素.在问题1中，两类元素是A类礼物和B类礼物，它们各自串在一起；在问题2中两类元素是横线段和纵线段.(3)每类元素有确定的顺序.在问题1中，摘取礼物之前每类礼物顺序已定，每次都是从某串礼物的最下端摘起；在问题2中，所有的横线段具有从左至右的顺序，所有的纵线段具有从上至下的顺序.（4）在两类元素合并操作时，一类元素在整体中的“位次”确定以后（他们的先后“位次”不改变），另一类元素在整体中的“位次”也就随之唯一确定. 我们将这类计数问题称为分类有序混排计数问题. 我们再来分别解答这两个问题： 问题1解答：将一排11个空格 ，从 左至右依次记为第1格，第2格，…，第11格，对摘取的礼物作如下放置：第1次摘取的礼物，放置于第1个空格中，第2次摘取的礼物放置于第2个空格中，…，第11次摘取的礼物放置于第11个空格中.例如，摘取礼物顺序是B1，B2，B3，A1，B4， A2，B5，A3 ，A4，A5，B6时，我们用 来表示. 这样放置摘取礼物的方法，使得放置礼物Ai(i=1,2,…，4)格子的序号比放置礼物A i＋1格子的序号小,放置礼物Bj（j=1,2,…，5）格子的序号比放置礼物Bj＋1格子的序号小.所以,当A类礼物按某种方式在11个空格中放置以后,B类礼物的放置方式也就唯一确定了.不同放置礼物顺序数，就是在11个空格中放置A类礼物的不同方法数,也就是摘取11件礼物的不同顺序数，即＝462. 问题2解答：我们第i列6条横线段记为x i（i=1，2，…，8），第j行的纵条线段记为yj（j=1，2，…，5）.例如图3中从点A到点B的一种最短路径（由粗线条所连接的折线）表示为x1y1x2x3y2y3x4x5y4x6x7x8y5 .这样的表示，使得所有最短路径和xi（i=1，2，…，8）与yj（j=1，2，…，5）某个排序对应，又xi的排序确定之后，yj的排序也唯一确定了，即确定某个A到B的最短路径.由于xi要在xi＋1前（i=1，2，…，7），故它的不同排序数有=1287种,从而，从点A到点B的最短路径数为1287. 由上面的解答，我们可以概括出分类有序混排计数问题的解答模式:首先，辨别它是有序混排问题；其次，弄清楚问题中两类元素各有多少个参加“排位”. 最后，计算出“排位”数.其中，弄清楚问题中两类元素各有多少个参加“排位”是关键也是难点，需要通过对几个具体“排位”观察、概括，才能获得参与“排位”的两类元素数目.比如对于问题2，要经过几次具体最短路径走法的“比划”，才可能发现每次“排位”x i与yi的一个“排位”. 分类有序混排计数问题的求解模式的应用： 问题3：甲、乙两队各出7名队员按事先确定好的顺序出场参加围棋擂台赛.双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，…，直到有一方队员全被淘汰为止，这时另一方就获得了胜利.这样，就形成一种比赛过程.那么所有可能出现的比赛过程有多少种？ 解：这是一个分类有序混排计数问题. 记甲队1至7号队员分别为A1，A 2，…，A 7；乙队1至7号队员分别为B1，B2，…，B7.假设在比赛结束后，让两个队队员这样排成一行：从左至右依次为第一场比赛被淘汰的队员，第二场比赛被淘汰的队员，…，最后一场比赛被淘汰的队员（只能是A 7或B7)，接下来排未被淘汰的队员. 假如未被淘汰的队员仅剩一人，则让这名队员排在最右边；假如未被淘汰的队员有多名，这多名队员必是同一个队的，让这些队员按事先确定好的顺序排位.显然，这样排队，使得甲乙两队14名队员都排在其中，并且A i＋1在A i的右边(i=1,2,…，6)（A i＋1和A i不一定相邻）；Bi＋1在Bi的右边(i=1,2,…，6)（Bi＋1和Bi不一定相邻）.假如排在甲队队员A i、A i＋1(i=1,2,…，6)之间有乙队队员，则这些乙队队员是被甲队队员A i＋1所淘汰的.假如排在乙队队员Bi、Bi＋1(i=1,2,…，6)之间有甲队队员，则这些甲队员是被乙队队员Bi＋1所淘汰的.排在最左边的某个队队员以及与之连排在一起