组合数学
10
面心—面心 （3）20个 （20个面，10个轴，2个转动）（10个轮换，每个轮换3根火柴，3根火柴颜色必须相同，才有不动图象,故无不动图象）
棱中—棱中 （1）2（2）14 15个 （火柴有方向，无不动图象） 方案数：
L=((30！/10！10！10！)*230+24*(6！/2！2！2！)*26)/60
6.由b、r、g三种颜色的5颗珠子镶成的圆环，共有几种不同的方案? 解： 正5边形的运动群 绕心转 ±72 (5) 2个 ±144 (5) 2个 翻转 180 (1)(2) 5个 不动 (1)5 1个
不同方案数为m=(35+4·31+5·33)/10=39
11.在正四面体的每个面上都任意引一条高，有多少方案？
解： 除了绕顶点-对面的中心轴旋转均不会产生不变的图象外,绕其他轴的旋转相当于正4面体的面3着色。
正4面体的转动群用面的置换表示： 顶点-对面的中心：(1)(3) 2*4= 8个； 棱中-棱中： (2) 3个； 不动： (1)4 1个； 可得不同的方案数为M=[34+0·8·32+3·32]/12=9
12.一幅正方形的肖像与一个立方体的面一样大，6副相同的肖像贴在立方体的6个面上有多少种贴法？
解： 除了绕面心—面心轴旋转任何度数均不会产生不变的图象外，绕其他轴的旋转都相当于正六面体的面4着色。
正6面体的转动群用面的置换表示：
不动 (1) 1个 面心-面心 ±90。 (1)2(4)1 6个 180。 (1)2(2)2 3个
顶点-顶点 ±120。 (3)2 8个 棱中-棱中 180。 (2)3 6个
参照讲义4.6例4可得不同的方案数为
M=[4+0·6·4+0·3·4+8·4+6·4]/24=192
14.足球由正5边形与正6边形相嵌而成。一个足球由多少块正5边形与正6边形组成？ 把一个足球所有的正6边形都着以黑色，正5边形则着以其它各色，每个5边形的着色都不同，有多少种方案？ 解： 5边形面心与体心连一直线从另一5边形面心穿出。该直线为对称轴。欠角=360。–(108。+2·120。)=12。;720。/12。=60(个顶点);60·3/2=90(条棱);60/5=12(个5边形);60·2/6=20(个6边形)
16
6
3
4
2
36
2
。
。
。
1
1
2
组合数学
一个顶点通过一个转动可与任一顶点重合，重合的方式只有1种，故转动群的阶为60。因为5边形着色均不同，所以除不变置换的任意旋转都不会产生不变图象，12个5边形着不同颜色共12!种方案。所以共有12!/60=7983360种方案。
附（例题）：用相同的火柴棍搭一个足球，有多少方案？ 解：相当于对棱（火柴棍）二着色（不能照搬）。 置换群为：
不动
。
5边形面心—面心72倍数 18圈
6边形面心—面心120倍数 30圈
棱中—棱中（6边形边界）18030/2=15，故15个转动） 方案数：
l=(290+24*218+20*230+0)/60=
**火柴有方向，棱中—棱中转动时无不动图象*****
16.用8个相同的骰子垛成一个正6面体，有多少方案？
解： 相当于正六面体每个角上放一个骰子。骰子按讲义4.6中关于正立方体的不同旋转均不会产生重合现象，共24种方案。因此本题相当于正六面体的顶点24着色。但绕顶点-顶点的对称轴旋转不会产生重合的图象。
参照习题11可得不同的方案数为M=[248+6·242+3·244+0·8·244+6·244]/24=4586595984。
17.正六面体的6个面和8个顶点分别用红、蓝两种颜色的珠子嵌入。试问有多少种不同的方案数?(旋转使之一致的方案看作是相同的)。
解： 本题相当于把讲义4.6例4例5合并起来,8个顶点6个面共14个元素的置换群。
面心-面心 ±90。 (1)2(4)1(4)2 6个
。224
180 (1)(2)(2) 3个
顶点-顶点 ±120。 (3)2(1)2(3)2 8个 棱中-棱中 180 (2)(2) 6个 不动 (1)6(1)8 1个 方案数为：[6·25+3·28+8·26+6·27+214]/24 =776
★★★★★★
[定义] 凸多面体与一个顶点相关的面角之和与360。的差称为该顶点的欠角。 [定理]凸多面体各顶点欠角的和为720。(用欧拉定理证) 用正5边形搭成的正多面体:
(5-2)·180。/5=108。,360。-3·108。=36。。 720/36=20(个顶点)
一个顶点3条棱，重复度为2：20·3/2=30条棱 一个顶点相关3个面,重复度为5：20·3/5=12个面
用正3角形搭成的面最多的正多面体:
。
。
。
。
。
（1）1个
18
（5） 24个（12个5边形，6个轴，4个转动） （3）
30
90
20个（20个6边形，10个轴，2个转动）
44
（1）（2）
2
15个 （60个5边形的棱，90-60=30，
34
17
组合数学
360-5·60=60。
720/60=12(个顶点)
一个顶点关联5条棱,重复度为2：12·5/2=30条棱。 一个顶点关联5个面,重复度为3：12·5/3=20个面 正三角形可组成正四、八、20面体。 正4面体：4个顶点、6条棱、4个面； 正8面体：6个顶点、12条棱、8个面； 正20面体：12个顶点、30条棱、20个面。
足球：
欠角=360–(108+2·120)=12 720/12 =60(个顶点) 60·3/2=90(条棱) 60/5=12(个5边形)
60·2/6=20(个6边形) (正20面体砍去12个顶点)
第六章：
/*
单纯表格法与改善的单纯表格法的区别在于前者计算所有的Pj，j＝1 , 2 , … , n+m．后者先算B，P0，再算CBB，找出一个满足λj＝cj－CBBAj＞0的Aj，只计算Pj＝ BAj,两者都通过计算λ＝min{ αi/αij｜αij ＞0}来确定退出基Ak，通过行变换将Pj变成ek，同时用同样的行变换将B变成B'－1，P0变成P0，从而进入下一轮迭代．
*/
*在改善的单纯形表格法中，因为每次的高斯消元均对P0和B-1进行操作，这样每次先进行高斯消元后，均可进行CB*B-1的计算，进而应用 入j= Cj- (CB*B-1)*Aj，得到每个入的值，对于MAX要判断全部为<=0，对于MIN要判断全部为>=0
*用大M法时，求最大值时M<0; 求最小值时M>0。
－1
－1
－1
－1
－1
。
。
。
。
。
。
。。。
’
18
组合数学
Moni ：
按照字典序法、递增进位制法、递减进位制法和邻位对换法分别求全排列817249365之后的第99个全排列。 原中介数 99对应进位制数 新中介数 对应排列 字典序法 70501301 4011 70510320 817329645 递增进位制法 37510100 4011 37514111 857239461 递减进位制法 00101573 130 00102023 124639857 邻位对换法 00144503 130 00144633 712948365
a，b，c，d，e构成的n位字符串中要求同一字符不能连续出现3次，这样的字符串有多少个?在所有这样的串中同一字符连续出现2次的情况一共出现了多少次? 解：(1)设所求的字符串数为Un个，按最后两个字符是否相同进行分类： 相同： 4Un-2 不相同：4Un-1
即：Un=4Un-1+4Un-2
特征方程为：x2-4x-4=0 两个特征根为：α=2+2
2 β=2-2
2
初值：U1=5；U2=25；U3=120 -?U0=5/4 设Un=Aαn+Bβn A+B=5/4 Aα+Bβ=5 解得：A=5(2+Un=5(2+
2)/16 B=5(2-n
2)/16
n
2)/16α+5(2-2)/16β
(2) 设在所有这样的串中同一字符连续出现2次的情况一共出现了Vn次, 按最后两个字符是否相同进行分类： 相同： 4Vn-2+4Un-2 不相同：4Vn-1
即：Vn=4Vn-1+4Vn-2+4Un-2
-? Vn-4Vn-1-4Vn-2=4Un-2 (1) 特征方程为：（x2-4x-4）2=0 两个特征根为：α=2+2
2(2重根)； β=2-2
2(2重根)。
初值：V1=0;V2=5;V3=40;V4=280 可设Vn=（En+F）αn+(Gn+H) β
n
(2)
n-1
将(2)代入(1)得： （En+F）αn+(Gn+H) βn -4{[E（n-1）+F]α（n-2）+H] βn-2 }= 4(Aαn-2+Bβn-2)
n-1
+[G（n-1）+H] β }-4{[E（n-2）+F]α
n-2
+[G
19
组合数学
4Eα
n-1
+8Eα
n-1
n-2
=4Aα
n-2
n-2
n-2
4Gβ+8Gβ=4Bβ 求出：E=G=5/32
由V1=0 和V0=0(推出)，求出：F=-5 Vn=(5/32*n-5
n
2/64;H=5
n
2/64.
2/64)α+(5/32*n+52/64)β
3、求下列有禁区的棋盘布子的方案数。
解：禁区的棋盘多项式为：
（1+3x+x）(1+4x+2x)=1+10x+37x+62x+47x+16x+2x
2
2
2
2
3
4
5
6
方案数：=6！-10*5！+37*4！-62*3！+47*2！-16*1！+2*0！
=720-1200+888-372+94-16+2 =116
4、证明：在平面直角坐标系中，33个整点中必有9个整点的重心仍是整点。 证：先证明9个整点中必有3个整点的重心的仍是整点。（证明方法请参照第三章习题17解答）
33个整点中必有9个3点组，每组的重心仍是整点。而这9个重心中必有3个的重心仍是整点，从而就证明了33个整点中必有9个整点的重心仍是整点。 附：第三章习题17
17. 在平面直角坐标系中至少任去多少个整点才能保证存在3个点构成的三角形的重心是整点？
解 设(x，y)是整点，每个分量模3后有 如下表的结果：
若有３个点模３后的结果落在上表中的同 一格中，则这３个点的重心是整点． 若有３点占满一行，则３点重心是整点； 有３点占满一列，则３点重心是整点； 若存在一组均匀分布，则有3点重心是整点．
由上表可知，若只有8个点，也不能保证有３点的重心是整点．（因为若每个格子都有 ２点，则只占有４个格子，无法保证上面的要求）
20