组合数学第二章母函数与递推关系习题解答

母函数与递推关系习题

母函数与递推关系习题 1、 有n 阶台阶，一人从下往上走，每次走一或两级，求他走这n 级台阶的方法数。 2、 {1,2,3,}n S n = 的一个子集为交替的：如果按递增次序列出该子集的元素时，它们的 奇偶性为：奇、偶、奇、偶、 。空集也算作交替的。求n S 的交替自己的树木。 3、 某人有n 元钱，他一天买一样东西，或一元钱的甲、或二元钱的乙、或二元钱的丙，问他用完这n 元钱有多少种方法？ 4、 求{,,}S a b c =∞?的n 排列数，要求在排列中a 与a 不相邻。 5、 设40n n i a i == ∑，0n ≥，求n a 。 6、 求1003102-?? ???。 7、 平面上有n 条直线，其中任意两条都相交于一点，但没有三条相交于同一点，求这n 条直线将平面分成的区域数。 8、 空间中有n 个平面，其中任意两个都有唯一交线，任意三个都有唯一一个交点，但没有四个相交于同一点。求这n 个平面将空间分成的区域数。 9、 在平面上画一个圆，然后再依次画n 条与圆都相交的直线，其中当k 是大于1的奇数时，第k 条直线只与前面(1)k -条直线中的一条在圆内相交，当k 是偶数时，第k 条直线与前面(1)k -条直线都在圆内相交，又没有三条直线在圆内相交于同一点。求这n 直线将圆分成的区域数。 10、 求{1,2,3}S =∞?的k 排列的个数，要求在排列中同一元素至多连续出现两次。 11、 将一个凸(1)n +边形用它的对角线划分成三角形，要求所用的对角现在多边形内部无交点，求划分的方法数。 12、 设一克、三克、七克重的砝码分别有1枚、3枚、2枚。问用这些砝码能称出哪些重量？称每一重量又各有几种方案？ 13、 有两种拆分：（1）1{1,12,3,14,}S =∞??∞?? ；（2）23{1,2,3,}S =? 。证明对 同一正整数n ，这两种拆分的拆分数相等。 14、 证明：周长为2n ，边长为整数的三角形的个数等于将n 拆分成恰好三项的拆分数。

组合数学-第十节：递推关系

第4章 递推关系 递推关系几乎在所有的数学分支中都有重要作用，对于组合数学更是如此，这是因为每个组合问题都有它的组合结构，而在许多情况下递推关系是刻画组合结构的最合适的工具。如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系等，是递推关系中的几个基本问题。 本章首先讨论递推关系的建立问题，然后对一些常见的递推关系作比较深入的讨论，并给出其解法。 4.1 递推关系的建立 在3.3节中讨论集合{}1,2,n 的错排数n D 时，我们建立了关于n D 的递推关系 ()()()1212 130,1n n n D n D D n D D --?=-+≥??==?? （4.1.1） 并由此推出了 ()()11120 n n n D nD n D -?=+-≥??=?? （4.1.2） 等式（4.1.1）和等式（4.1.2）都是递推关系的例子，等式（4.1.1）给出了n 元错排数n D 同1n -元错排数及2n -元错排数2n D -之间的关系，这样，由初值1D 和2D 就可以计算出3D ，由2D 和3D 又可以计算出4D ，如此可以逐次计算出错排数序列123,,D D D 。而等式（4.1.2）给出了n 元错排数n D 同1n -元错数1n D -之间的关系，这样由初始值1D 就唯一地确定了错排数序列。 定义4.1.1 给定一个数的序列()()()0,1,,H H H n ，若存在整数0n ，使当0n n ≥时，可以用等号（或大于号，小于号）将()H n 与其前面的某些项()()0H i i n ≤<联系起来，这样的式子就叫做递推关系。 下面通过几个例子来看看如何建立递推关系，至于递推关系的求解，将在后面的几节中讨论。 例1（Hanoi 塔问题） 现有A ，B ，C 三根立柱以及n 个大小不等的中空圆盘，这些圆盘自小到大套在A 柱上形成塔形，如图4.1.1所示。要把n 个从A 柱上搬到C 柱上，并保持原来的顺序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一根立柱上，且不允许大盘压在小盘上。问至少要搬多少次？

组合数学教学大纲

《组合数学》课程教学大纲 课程编码：LX113900 课程名称：组合数学 英文名称：Combinational Mathematic s 适用专业：计算机科学与技术 先修课程：无 学分：3 总学时：48 一、课程简介 该课程是为计算机类学生开设的一门选修课程。主要讲授排列与组合、母函数及其应用、递推关系、容斥原理、抽屉原理、polya定理等内容。通过该课程的学习，能使学生系统掌握组合数学的基本知识、基本理论和基本方法；培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，运用组合数学的思想和方法分析和解决实际问题的能力。 This course’s main contents include permutation and combination, generating function and its application, recursive relation, including excluding principle, drawer principle and Ramsey theorem, Ploya theorem. 二、本课程与其它课程的联系 本课程无先修课程,与计算机科学与技术专业的后续课程如算法设计与分析以及编译原理等课程有一定的联系,排列组合及递推关系与算法设计与分析中的算法复杂性分析有密切关系,为复杂性分析提供了基础知识,容斥原理和抽屉原理在编译原理中有其重要作用。 三、课程内容及要求 （一）排列与组合（6学时） 主要内容：两个基本法则；排列与组合及其计算；排列与组合的生成算法；Striling近似公式。 基本要求：理解排列与组合的概念；掌握组合的主要性质；熟练掌握排列数

母函数

第二章 母函数及其应用 问题：对于不尽相异元素的部分排列和组合，用第一章的方法是比较麻烦的（参见表2.0.1）。 新方法：母函数方法，问题将显得容易多了。其次，在求解递推关系的解、整数分拆以及证明组合恒等式时，母函数方法是一种非常重要的手段。 表2.0.1 条件 组合方案数 排列方案数 对应的集合 相异元素，不重复 ()! !!r n r n C r n -?= ()! ! r n n P r n -= {}n e e e S ,,, 21= 相异元素，可重复 r r n C 1-+ r n S ＝{,,21e e ?∞?∞ n e ?∞, } 不尽相异元素（有限重复） 特例 r ＝n 1 ! !!!m n n n n 21 S ＝{11e n ?，22e n ?， …，m m e n ?}, n 1＋n 2＋…＋n m ＝n n k ?1, (k ＝1,2,…, m ) r ＝1 m m 所有n k ?r r r m C 1-+ r m 至少有一个n k 满足1?n k < r 母函数方法的基本思想是把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转化为多项式或幂级数之间的运算。 2.1 母 函 数 （一）母函数 （1）定义 定义2.1.1 对于数列{}n a ，称无穷级数()∑∞ =≡0 n n n x a x G 为该数列的（普通型）母函 数，简称普母函数或母函数。 （2）例 例2.1.1 有限数列C (n ,r )，r ＝0,1,2, …,n 的普母函数是()n x +1。 例2.1.2 无限数列{1，1，…，1，…}的普母函数是 +++++=-n x x x x 2 111 （3）说明 ● n a 可以为有限个或无限个； ● 数列{}n a 与母函数一一对应，即给定数列便得知它的母函数；反之，求得母函数则数 列也随之而定；

递推关系的求解及其应用-组合数学

《组合数学》课程结课作业 题目递推关系的求解及其应用 院系控制与计算机工程学院专业班级 学生姓名 学号 2018年5月

摘要 递推关系作为数学的一种思维，充分的展现了生活中许多事物现象变化所遵循的规律。所有的事物都不是单一存在的，而是和某些东西相互依存的。比如在求解排列组合、数列中都会用到递推关系的思想与方法。本论文将围绕着递推思维及求解在数列、排列组合上的应用展开讨论。本论文阐述递推关系不是单一的个体，它与生成函数、线性关系、数列组合综合使用，并到达解决问题的思想。也说明学科之间是一个统一的整体。 关键词：递推关系;求解方法;递推思维;应用 1 绪论 递推关系几乎在所有的数学领域中都占据着重要的比例和广泛应用,在物理学上也有着深刻的影响，是数学运算中的一个强有力的工具。因此不管是在教学中还是生活中，都可能要用递推关系来解决所碰到的问题，或与其他学科相结合形成性学科的过程中用递推关系，比如递推关系可和数列、线性规划与矩阵相结合形成要实现这一目的新学科，把所学的知识串连在一起，形成一种新的思维。首要的关键是用递推方法来探究这一过程，搭建一桥梁。在此基础上才能用所学的递推理论和方法进行分析和应用，从而才能解决实际理论的问题，是我们所学的知识更上一个台阶。 通常情况下递推关系的求解比较困难，仅局限于使用递推关系的一些定义很多问题是不能解决的，并且所涉及的领域也很广。递推关

系的研究还可以追溯到斐波纳契关系： 它是比萨的数学家Leonardo 在1202年给出的。在他所著的《Liber baci 》一书中，讨论一个一年之内能有多少对兔子的问题，都用到了递推关系的思想。比如常见的线性递推数列，生成函数都是数学中的重要概念,也是解决数学问题的重要工具之一。本文主要介绍线性递推数列通项公式的求解方法及利用生成函数来求解递推关系，以及递推关系的推广。 2 线性递推关系 数列n a 必须有连续个k 项满足),,,(21n k n k n k n x x x f x -+-++=，满足此式的数列则叫它为数列n x 的一个递推关系式。由递推关系式及满足k 个 初始值可以确定的一个数列n x 叫做递推数列。因此，无论是牵涉到递推数列的证明题，解析题，还是需要建立递推关系式的综合题，那么解决递推数列的核心是求通项公式，也是最基本的步骤。 2.1 线性递推数列的相关认识 定义1 如果已知数列n a 的第1项（或前几项），且数列n a 的任意 一项与它的前一项1-n a （或前几项）间的关系可以用一个式子来表示， 对于任意的自然数n ，由递推关系),,,(21n k n k n k n a a a f a -+-++=所确定的数列n a 则叫做递推数列[] 1。 例2.1 求解递推关系17-=n n a a 其中9812=≥a n 且。 解：这是n n a a 71=+其中0≥n 且982=a 的另一种描述形式。于是解具有形式).7(0n n a a =因为),7(98202a a ==于是,20=a 而且),7(2n n a =是唯

排列组合与数列递推关系

例析排列、组合、概率问题中的递推数列 一、a n =p ·a n －1+q 型 【例1】 某种电路开关闭合后，会出现红灯或绿灯闪动，已知开关第一次闭合后，出 现红灯和绿灯的概率都是12，从开关第二次闭合起，若前次出现红灯的概率是1 3 ，出现绿灯 的概率是23；若前次出现绿灯，则下次出现红灯的概率是35，出现绿灯的概率是2 5 ，记开关 第n 次闭合后出现红灯的概率为P n 。 (1)求：P 2；(2)求证：P n <1 2(n ≥2)；(3)求lim n n P →∞ 。 解析：(1)第二次闭合后出现红灯的概率P 2的大小决定于两个互斥事件：即第一次红 灯后第二次又是红灯；第一次绿灯后第二次才是红灯。于是P 2=P 1·13+(1－P 1)·35=7 15 。 (2)受(1)的启发，研究开关第N 次闭合后出现红灯的概率P n ，要考虑第n －1次闭合后出现绿灯的情况，有 P n =P n －1·13+(1－P n －1)·35=－415P n －1+3 5 ， 再利用待定系数法：令P n +x =－415(P n －1+x )整理可得x =－9 19 ∴{P n －919}为首项为(P 1－919)、公比为(－4 15)的等比数列 P n －919=(P 1－919)(－415)n －1=138(－415)n －1，P n =919+138(－415 )n － 1 ∴当n ≥2时，P n <919+138=1 2 (3)由(2)得lim n n P →∞ =9 19。 【例2】 A 、B 两人拿两颗骰子做抛掷游戏，规则如下:若掷出的点数之和为3的倍数时，则由原掷骰子的人继续掷；若掷出的点数不是3的倍数时，由对方接着掷.第一次由A 开始掷.设第n 次由A 掷的概率为P n ， (1)求P n ；⑵求前4次抛掷中甲恰好掷3次的概率. 解析：第n 次由A 掷有两种情况： ① 第n －1次由A 掷，第n 次继续由A 掷，此时概率为12 36P n －1； ② 第n －1次由B 掷，第n 次由A 掷，此时概率为(1－12 36 )(1－P n －1)。 ∵两种情形是互斥的 ∴P n =1236P n －1+(1－1236)(1－P n －1)(n ≥2)，即P n =－13P n －1+23(n ≥2) ∴P n －12=－13(P n －1－12)，(n ≥2)，又P 1=1 ∴{P n －12}是以12为首项，－1 3为公比的等比数列。 ∴P n －12=12(－13)n －1，即P n =12+12(－13)n － 1。 ⑵2881 。 二、a n +1=p ·a n +f (n )型 【例3】 (传球问题)A 、B 、C 、D 4人互相传球，由A 开始发球，并作为第一次传球，经过5次传球后，球仍回到A 手中，则不同的传球方式有多少种？若有n 个人相互传球k 次后又回到发球人A 手中的不同传球方式有多少种？ 分析：这类问题人数、次数较少时常用树形图法求解，直观形象，但若人数、次数较多时树形图法则力不从心，而建立递推数列模型则可深入问题本质。 4人传球时，传球k 次共有3k 种传法。设第k 次将球传给A 的方法数共有a k (k ∈N *)种传法，则不传给A 的有3k －a k 种，故a 1=0，且不传给A 的下次均可传给A ，即 a k +1=3k －a k 。两边同除以3k +1得a k +13k +1=－13·a k 3k +1 3 ， 令b k =a k 3k ，则b 1=0，b k +1－14=－13(b k －14)，则b k －14=－14(－13)k － 1 ∴a k =3k 4+3 4 (－1)k 当k =5时，a 5=60. 当人数为n 时，分别用n －1，n 取代3，4时，可得a k =(n －1)k n +n －1 n (－1)k 。 【例4】 (环形区域染色问题)将一个圆环分成n (n ∈N *，n ≥3)个区 域，用m (m ≥3)种颜色给这n 个区域染色，要求相邻区域不使用同一种 颜色，但同一颜色可重复使用，则不同的染色方案有多少种？ 分析：设a n 表示n 个区域染色的方案数，则1区有m 种染法，2区有m －1种染法，3，……，n －1，n 区各有m －1种染色方法，依乘法 原理共有m (m －1)n － 1种染法，但是，这些染中包含了n 区可能和1区染 上相同的颜色。而n 区与1区相同时，就是n －1个区域涂上m 种颜色合乎条件的方法。 ∴a n =m (m －1)n － 1－a n －1，且a 3=m (m －1)(m －2) a n －(m －1)n =－[a n －1－(m －1)n － 1] a n －(m －1)n =[a 3－(m －1)3](－1)n － 3 ∴a n =(m －1)n +(m －1)(－1)n (n ≥3) 用这个结论解：2003年高考江苏卷：某城市在中心广场建一个花圃，花圃分为6个部分如图，现要栽种4种不同颜色的花且相邻 部分不能同色，由不同的栽种方法有 种。 只需将图变形为圆环形，1区有4种栽法。不同的栽法数为 N =4a 5=120。 三、a n +1=a n ·f (n )型 【例5】 (结草成环问题)现有n (n ∈N *)根草，共有2n 个草头，现将2n 个草头平均分成n 组，每两个草头打结，求打结后所有草能构成一个圆环的打结方法数。 分析：将2n 个草头平均分成n 组，每两个草头打结，要 使其恰好构成圆环，不同的连接方法总数m 2=a n 。 将草头编号为1，2，3，……，2n －1，2n 。 草头1可以和新草头3，4，5，……，2n －1，2n 共2n －2个新草头相连，如右图所示。 假设1和3相连，则与余下共n －1条相连能成圆环的方法数为a n －1。 ∴a n =(2n －2)a n －1，(n ≥2，n ∈N *)，a 1=1，得a n a n －1 =2n －2 1 2 3 n n -1 (1) 2 3 4 5 6 1 2 3 4 5 6 3 4 …… 1 6 2n -1 2n

母函数的概念与性质

1绪论 母函数又可译为发生函数或生成函数.母函数方法是现代离散数学领域中的重要方法.它是联结离散数学与连续数学的桥梁.它是解决组合计数问题的一个重要工具之一. 母函数方法是一种既简单又有用的数学方法，是一个古老方法.他源于De Moivre 在1720前后的工作，1748年欧拉在研究关于划分的问题中发展了这一方法.拉普拉期于18世纪末及19世纪初期对其进行了广泛的论述.其探究主要与概率论相关.尽管这一方法有其悠久的历史，但是正如我们将要看到的那样，这一方法有着广泛的应用. 当代计算机科学家克努特（D.E.Knuth）在其名著《The art of computer programming,voll》中作了这样的论述：“…当运用母函数时，通常无需担心级数的收敛性，因为我们只是在探求得到某个问题的解的可能途径，一旦当我们用任何手段发现了解，尽管这些手段也许不严格，就有可能独立的验证这个解…例如有时很容易用数学归纳法来证明，我们甚至不必提到它是利用母函数发现的.此外，可以证明我们对母函数所做的绝大多数——如果不是所有的话——运算都能严格论证其可行而无须顾及级数的收敛性.”这段引文最后的断言是通过把母函数作为形式幂级数而得以实现的. 一般情况下，母函数中的x只是一个抽象符号，并不需要对它赋予具体数值.因而不需要考虑它的收敛性.此时的变量x只是一种形式变元.对这种级数可以把它看成形式幂级数，可以按通常方式定义其加法、乘法、形式微分等运算，从而构成一个代数体系. 母函数有多种类型，这里仅讨论最常见的两种：普通母函数和指数母函数.下面分别进行讨论.

2母函数基本概念 定义2.1. 对于数列{}0n n a ≥，称函数 120120 ()k k k f x a x a a x a x ≥==+++∑ 为数列{}0n n a ≥的普通型母函数（简称普母函数）． 定义2.2. 对于数列{}0n n a ≥，称函数1 2 01 2 ()! 1! 2! k k k x x x f x a a a a k ≥= =+++∑ 为数列{}0n n a ≥的指数型母函数（简称指母函数）． 数列与母函数可以互求.已知母函数，可求出其对应的数列；已知数列，可求出其对应的母函数. R 上的母函数的全体记为[]R x ????.在集合[]R x ????中适当定义加法和乘法运算，可使它成为一个整环，任何一个母函数都是这个环中的元素. 定义2.3. 设0 ()k k k A x a x ∞ == ∑与0 ()k k k B x b x ∞ == ∑是R 上的两个母函数.若对任意0k ≥， 有k k a b =.则称()A x 与()B x 相等.记作()()A x B x =. 定义 2.4. 设α为任意实数. []0 ()k k k A x a x R x ∞ =??=∈?? ∑,则()0 ()k k k A x a x αα∞ == ∑称作α 与()A x 的数乘积. 定义2.5. 设0 ()k k k A x a x ∞ == ∑与0 ()k k k B x b x ∞ == ∑是R 上的两个母函数. （1）将()A x 与()B x 相加定义为0 ()()()k k k k A x B x a b x ∞ =+=+∑，并称()()A x B x +为() A x 与() B x 的和，把运算“+”称作加法. （2）将()A x 与()B x 相乘定义为011 00 ()()()k k k k k A x B x a b a b a b x ∞ -=?=+++∑ ，并称()() A x B x ?为()A x 与()B x 的积，把运算“?”称作乘法. 3母函数的性质