《一类计数问题的解答模式》由会员分享，可在线阅读，更多相关《一类计数问题的解答模式（4页珍藏版）》请在金锄头文库上搜索。
1、1图 1 A5A4A3A1A2B6B3B4B5B2B1BA图 2一类计数问题的解答模式江苏省无锡市第一中学李广修(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
2、中，两类元素是 A 类礼物和 B 类礼物，它们各自串在一起；在问题 2 中两类元素是横线段和纵线段.(3)每类元素有确定的顺序.在问题 1 中，摘取礼物之前每类礼物顺序已定，每次都是从某串礼物的最下端摘起；在问题 2 中，所有的横线段具有从左至右的顺序，所有的纵线段具有从上至下的顺序.（4）在两类元素合并操作时，一类元素在整体中的“位次”确定以后（他们的先后“位次”不改变） ，另一类元素在整体中的“位次”2A2A1 A5A4A3B3 B6B5B4B1 B2BA图 3也就随之唯一确定.我们将这类计数问题称为分类有序混排计数问题. 我们再来分别解答这两个问题：问题 1 解答：将一排 11 个空格
3、，从左至右依次记为第 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 i1 格子的序号小,放置礼物 Bj（j =1,2,，5）格子的序号比放置礼物 Bj1 格子的序号小.所以,当 A 类礼物按某种方式在 11 个空格中放置以后,B 类
4、礼物的放置方式也就唯一确定了.不同放置礼物顺序数，就是在 11 个空格中放置 A 类礼物的不同方法数,也就是摘取 11 件礼物的不同顺序数，即 462. 51C问题 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 的排序也唯一确定了，即确定3A1B2 A4A
5、3A2 B5B1 B3 B4 B7B6 A6 A7A5某个 A 到 B 的最短路径.由于 xi 要在 xi1 前（i=1，2，7） ，故它的不同排序数有 =1287 种 ,从而，从点 A 到点 B 的最短路径数为 1287. 813C由上面的解答，我们可以概括出分类有序混排计数问题的解答模式: 首先，辨别它是有序混排问题；其次，弄清楚问题中两类元素各有多少个参加“排位”. 最后，计算出“排位”数.其中，弄清楚问题中两类元素各有多少个参加“排位”是关键也是难点，需要通过对几个具体“排位”观察、概括，才能获得参与“排位”的两类元素数目.比如对于问题 2，要经过几次具体最短路径走法的“比划” ，才可
6、能发现每次“排位”x i 与 yi 的一个“排位”. 分类有序混排计数问题的求解模式的应用：问题 3：甲、乙两队各出 7 名队员按事先确定好的顺序出场参加围棋擂台赛.双方先由 1 号队员比赛，负者被淘汰，胜者再与负方2 号队员比赛，直到有一方队员全被淘汰为止，这时另一方就获得了胜利.这样，就形成一种比赛过程.那么所有可能出现的比赛过程有多少种？解：这是一个分类有序混排计数问题. 记甲队 1 至 7 号队员分别为 A1，A 2，A 7；乙队 1 至 7 号队员分别为 B1， B2， ， B7.假设在比赛结束后，让两个队队员这样排成一行：从左至右依次为第一场比赛被淘汰的队员，第二场比赛被淘汰的队员
7、，最后一场比赛被淘汰的队员（只能是 A 7 或 B7)，接下来排未被淘汰的队员. 假如未被淘汰的队员仅剩一人，则让这名队员排在最右边；假如未被淘汰的队员有多名，这多名队员必是同一个队的，让这些队员按4A1B2 A4A3A2 B5B1 B3 B4 B7B6 A6 A7A5A1B2 A4A3A2 B5B1 B3 B4 B7B6 A6 A7A5事先确定好的顺序排位.显然，这样排队，使得甲乙两队 14 名队员都排在其中，并且 A i1 在 A i 的右边(i=1,2, ，6)（A i1 和 A i 不一定相邻） ；B i1 在 Bi 的右边(i=1,2,，6)（ Bi1 和 Bi不一定相邻）.假如排在
8、甲队队员 A i、 A i1 (i=1,2,，6)之间有乙队队员，则这些乙队队员是被甲队队员 A i1 所淘汰的.假如排在乙队队员Bi、B i1 (i=1,2,，6)之间有甲队队员，则这些甲队员是被乙队队员 Bi 1 所淘汰的.排在最左边的某个队队员以及与之连排在一起的该队队员，是被另一个队的 1 号队员所淘汰的. 例如， 表示乙队第 1、2 名队员被甲队第 1 名队员所淘汰，甲队第 1、2 名队员被乙队第 3 名队员所淘汰，甲队第 6、7 名队员还未上场就已经获得胜利.这样的排队方式和甲、乙两队的比赛过程一一对应，从而所有可能出现的比赛过程有 =3432 种. 41C参考文献周士藩. 逐点累加法例析.中学数学月刊.2006.6赵红玲. 矩形格中的最短路径与杨辉三角.数学教学.2004.2(本文载于数学教学2007 年 4 期)
