组合数学讲义习题讲解1

1,Combinatorics(习题讲解),2,n节点二叉树的构造方法数,设有n个实数a1a2an，以a1，a2，an为节点可构成各不相同的n节点二叉树（如a1，a2，a3可构成5棵不相同的3节点二叉树）；注意在二叉树中，左子树中的节点值均小于根节点值，右子树中的节点值均大于根节点值。试证明：以a1，a2，an为节点构成的不相同的n节点二叉树的棵数为n+1阶Catalan数。设不相同的n节点二叉树的棵数为bn。显然b1=1,b2=2。,3,n节点二叉树的构造方法数,a1，a2，an各节点均可作为n节点二叉树的根。按根节点的不同把n节点二叉树分为n类：以a1为根，此时其左子树必为空，（左子树中的节点值均小于根节点值）此时其右子树中的节点恰有n-1个，该右子树的不同构造方法数为bn-1，因此以a1为根的不同n节点二叉树数目为bn-1。以a2为根，此时其左子树中有且仅有a1，即只有一种情况；而右子树中的节点恰有n-2个，该右子树的不同构造方法数为bn-2，因此以a2为根的不同n节点二叉树数目为bn-2。,4,n节点二叉树的构造方法数,以a3为根，此时其左子树中恰有a1和a2，其不同构造方法数为b2；而右子树中的节点恰有n-3个，该右子树的不同构造方法数为bn-3，因此以a3为根的n节点二叉树数目为b2bn-3。以ak为根，此时其左子树中有a1。ak-1，其不同构造方法数为bk-1；而右子树中的节点有n-k个，该右子树的不同构造方法数为bn-k，因此以ak为根的n节点二叉树数目为bk-1bn-k。,5,n节点二叉树的构造方法数,以an为根，此时其右子树必为空，（右子树中的节点值均大于根节点值）此时其左子树中的节点恰有n-1个，该左子树的不同构造方法数为bn-1，因此以an为根的不同n节点二叉树数目为bn-1。故总的方法数bn=bn-1+bn-2+b2bn-3+bk-1bn-k+bn-1令ck+1=bk(k1)，有cn+1=cn+cn-1+c3bn-2+ckcn-k+1+cn由于c2=b1=1，再令c1=1，c0=0。于是有cn+1=c0cn+1+c1cn+c2cn-1+c3bn-2+ckcn-k+1+cnc1+cn+1c0符合n+1阶Catalan数的非线性递归方程。得证。,6,矩阵连乘的方法数问题,为什么要研究这样的问题？e.g.设有矩阵M1,M2,M3,M4，其维数分别是1020,2050,501和1100，现要求出这4个矩阵相乘的结果。我们知道，若矩阵A的维数是pq，矩阵B的维数是qr，则A与B相乘后所得矩阵AB的维数是pr。按照矩阵相乘的定义，求出矩阵AB中的一个元素需要做q次乘法（及q-1次加法）。这样，要计算出AB就需要做pqr次乘法。,7,矩阵连乘的方法数问题,由于矩阵连乘满足结合律，故计算矩阵连乘的方式可以有多种。例如，我们可以按M1(M2(M3M4)的方式去计算，也可以按(M1(M2M3)M4的方式去计算，所得结果是相同的。但是值得注意的是，按前一方式计算需要做125,000次乘法，而按后一方式计算只需要做2,200次乘法。由此可见，矩阵连乘的运算次序对于所需要的计算量(所需乘法次数)有着极大的影响。(可用动态规划法解决本问题)(为简单起见，且由于加法比同样数量的乘法所用时间要少得多,故这里暂不考虑加法的计算量。),8,矩阵连乘的方法数问题,矩阵M1,M2,M3,M4的维数分别是1020,2050,501和1100M3M4：50*1*100=5,000,所得结果为50100矩阵；M2(M3M4)：20*50*100=100,000,所得结果为20100矩阵；M1(M2(M3M4)：10*20*100=20,000,结果为10100矩阵。故M1(M2(M3M4)方式计算需要5,000+100,000+20,000=125,000次乘法M2M3：20*50*1=1000,所得结果为201矩阵；M1(M2M3)：10*20*1=200,所得结果为101矩阵；(M1(M2M3)M4：10*1*100=1000,结果为10100矩阵。故(M1(M2M3)M4方式计算只需1,000+200+1,000=2,200次乘法,9,矩阵连乘的方法数问题,看看矩阵连乘加括号的方法数到底有多少？M1M2MiMi+1Mn考虑最后一次乘法的所在位置：可以是M1(M2MiMi+1Mn)也可以是(M1M2)(M3MiMi+1Mn)也可以是也可以是(M1M2Mi)(Mi+1Mn)也可以是也可以是(M1M2MiMi+1Mn-1)Mn即最后一次乘法的所在位置共有n-1个，按这n-1个位置分类：,10,矩阵连乘的方法数问题,设n个矩阵连乘加括号方法数为an，则a1=1，a2=1，a3=2,类型M1(M2MiMi+1Mn)中的方法数共有an-1种;类型(M1M2)(M3MiMi+1Mn)中的方法数共有an-2种;类型(M1M2Mi)(Mi+1Mn)中的方法数共有aian-i种;类型(M1M2MiMi+1Mn-1)Mn中方法数共有an-1种故an为上述n-1类的总和：an=an-1+an-2+aian-i+an-1令a0=0，则上式可写为an=a0an+a1an-1+a2an-2+aian-i+an-2a2+an-1a1+ana0恰好是n阶Catalan数所满足的方程。,11,n边凸多边形的三角形划分方法数,把n边凸多边形(n3)划分成n-2个三角形，可按如下方式考虑：设n+1边凸多边形的三角形划分方法数为an+1并令bn=an+1(n2)由于n+1边凸多边形的每条边必在某个三角形中，故点1与点n+1的连线P也必在某个三角形中，其所对的顶点可以是点2，或点3,或点k，或点k+1，或点n。以连线P所对的顶点进行分类：对点2，或点3,，或点n。当连线P所对的顶点是点2时,点n+1，点1，点2构成的三角形已确定，而由点2,点3,点n,点n+1构成另一个n边凸多边形，故属于此类（连线P对点2）的三角形划分方法数为an=bn-1；,12,n边凸多边形的三角形划分方法数,当连线P所对的顶点是点3时，点n+1，点1，点3构成的三角形已确定（此时点1，点2，点3构成的三角形也已随之确定），而由点3,点4,点n,点n+1构成一个n-1边凸多边形，属于此类的三角形划分方法数为an-1=bn-2；，一般地，当连线P所对的顶点是点k时，点n+1，点1，点k构成的三角形已确定，该三角形的一边是由点1,点2,点k构成的k边凸多边形(该k边凸多边形三角形划分方法数为ak=bk-1)；而该三角形的另一边是由点k,点k+1,点n,点n+1构成的n-k+2边凸多边形（该n-k+2边凸多边形三角形划分方法数为an-k+2=bn-k+1）；故属于此类的三角划分方法数为bk-1*bn-k+1,13,n边凸多边形的三角形划分方法数,当连线P所对的顶点是点k+1时，点n+1，点1，点k+1构成的三角形已确定，该三角形的一边是由点1,点2,点k,点k+1构成的k+1边凸多边形（该k+1边凸多边形三角形划分方法数为ak+1=bk）；而该三角形的另一边是由点k+1,点n,点n+1构成的n-k+1边凸多边形（该n-k+1边凸多边形三角形划分方法数为an-k+1=bn-k）；故属于此类的三角划分方法数为bk*bn-k，最后，当连线P所对的顶点是点n时，,14,n边凸多边形的三角形划分方法数,当连线P所对的顶点是点n时，点n，点n+1，点1构成的三角形已确定，该三角形的一边是由点1,点2,点n构成的n边凸多边形，故属于此类的三角形划分方法数为an=bn-1；按连线P所对的顶点进行分类后得各类方法数：对点2为bn-1，对点3为bn-2,，对点k为bk-1*bn-k+1，对点k+1为bk*bn-k，对点n为bn-1；故总和为bn-1+bn-2+bk-1*bn-k+1+bk*bn-k+bn-1；由于b0,b1均无定义(而b2=a3=1为凸3边形即三角形划分方法数)；故定义b0=0,b1=1,于是n+1边凸多边形三角划分方法数an+1即bn=b0bn+b1bn-1+b2bn-2+bk-1*bn-k+1+bk*bn-k+bn-1b1+bnb0,15,n边凸多边形的三角形划分方法数,n+1边凸多边形三角划分方法数an+1即bn=b0bn+b1bn-1+b2bn-2+bk-1*bn-k+1+bk*bn-k+bn-1b1+bnb0且边界条件有：b0=0,b1=1,b2=1，刚好满足n阶Catalan数条件故bn是n阶Catalan数。因此n边凸多边形三角划分方法数an即bn-1为n-1阶Catalan数。,16,给了n个数据元素，问这n个数据元素依次进出栈的情况有多少种？Eg:1个数据元素：进出。2个数据元素：进进出出，进出进出。3个数据元素：进进进出出出，进进出出进出，进进出进出出，进出进进出出，进出进出进出。4个数据元素：进进进进出出出出进进出出进进出出进进进出进出出出进进出出进出进出进进进出出进出出进出进进进出出出进进进出出出进出进出进进出进出出进进出进进出出出进出进进出出进出进进出进出进出出进出进出进进出出进进出进出出进出进出进出进出进出（需满足：自左向右，“进”的个数不少于“出”的个数）,思考题,17,n个数据元素进出栈方法数,考虑最后一个出栈的元素：可以是第一个进栈的元素，如进进进出出出(n=3时)也可以是第二个进栈的元素，如进出进进出出(n=3时)，也可以是第k个进栈的元素，也可以是第n个（最后一个）进栈的元素，如进进出出进出(n=3时)计算方法：按最后一个出栈的元素分类计算，再把各类总加。,18,n个数据元素进出栈方法数,设n个数据元素进出栈方法数为an。第1类：最后一个出栈的元素是第1个进栈的元素：第1个元素进栈后一直未动，等其后的n-1个元素进出栈执行完毕后才出来，这n-1个元素进出栈方法数为an-1第2类：最后一个出栈的元素是第2个进栈的元素：第2个元素最后出栈，说明第1个元素在第2个元素进栈前已经出栈，之后第2个元素进栈且一直未动，直到其后的n-2个元素进出栈执行完毕才出来，这n-2个元素进出栈方法数为an-2第3类：最后一个出栈的元素是第3个进栈的元素：,19,n个数据元素进出栈方法数,第3类：最后一个出栈的元素是第3个进栈的元素：第3个元素最后出栈，说明第1、