Catalan数的一些结论

第 39卷第 3期 2005年 9月 华 中师范大学学 报(自然科学版 ) J()URNAI OF CENTRAI CHINA NORM AL UNIVERSITY(Nat．Sci．) VO1．39 NO．3 Sept． 2005 文章编号 ：1000—11 90(2005)03—0298 03 Catalan数的一些结论 王春香，毛经中，朱善聪 (华 中师范大学 数学与统计学学 院，武汉 430079) 摘 要 ：Catalan数是指 个 1和 个 0构成 2n项 a。，a 2。⋯ 。a 2 ，其部分和恒满 足 a。+n 2+⋯+a ≥ ， 一1，2，⋯。2 的排列．这类排列的个数为cata1an数，记为c 一 ( )( ≥0)，给出了 Catalan数的有关性质及其相关 的结论 ，以及有关 的例子． 关键词 ：Catalan数 ；排列 ；一一对应 中图分类号 ：O157．5 文献标识码 ：A 1 引言 在 组 合 数 学 中 比 较 熟 悉 的 一 个 数 列 是 Fibanocci数列，它的重要性体现在其广泛的应用． 但 是还 有 一个 Catalan数列 ，也 应 用 极 为广 泛． Catalan数首先是由欧拉在精确计算对凸多边形的 不同的三角剖分的计数问题时得到的，在他之后的 数学家卡特朗在研究乘法结合方式 问题时也引出 了 Catalan数．(参见文献 [1])．例如 ：考虑一类 ，z 个 1和 ，z个 0构成 2，z项 a ，a ，⋯，a 其部分和恒 满足 口 +d：+⋯+d ≥ ，k一1，2，⋯ ，2n的排列 ， 这类排列的个数为 Catalan数，记为 c， 一_l_ · l⋯I(，z≥0)．当然Catalan数列还有其它的描述 方式 ，例如 ：在非组合代数中，设给出 ，z个不同的实 数 。， ，⋯， ，试计算这 ，z个数的连乘积的计算 方式有多少种?此处认为 。 。和 。 。是不同的计 算 方式．为解决这个 问题令f(n)示不 同的计 算 方式．显然 -厂(2)一2，f(3)===12，可知有递归关系式 n 1 ／t1 如下：-厂(，z)一∑l }f(k)f(n一点)，它表示在进行 ^一 1 ＼ 最后一次乘法运算时，其前面一个因子总是某 k个 数 的连乘积 ，而后一个 因子则为其余 ，z—k个数的 连乘积．这 ，z个数的连乘积 的计算方式 数也 为 C 一 l_【2 n)(，z≥o)．当catalan数作为数列的第，z 项时，就得到一个 Catalan数列．其初始条件 为 C 一 1，及递归关系式为 C 一 c c一 (，z≥ 2)． 2 主要结论 对于以下两个定理，本文给出一个与文献 [2， 3]中不一样的证明方法． 定理 1_2]，z个“1”和 ，z个“0”组成的 2，z位 的二 进 制数，要求从左到右扫描 ，“1”的累计数 不小 于 “0”的累计数 ，这样 的二 进制数 的个数 为著名 的 catalan数C， 一—l_( 1(，z≥o)． 证 明 令 ， 为 ，z个“1”和 ，z个“0”组成 的符合 二进制数的个数．，z个“1”和 ，z个“O”组成的二进制 数可 以看作是一种类型 (1型)为 ，z个元素和另一 种类型(0型)的 ，z个元素的两种不同元素的排列 ， 这样的排列个数为(2 n)一署 ，从(2 n)中减去 ＼，z／ ： ＼，z／ 不符合要求的个数即为所求的 考虑 ，z个“1”和 ”个“0”组成 的不符 合要求 的二进 制数．不符合要 求 的数应为 ：从左到右扫描时 ，必然存在一个最小 的 k使得在这 k位上首先出现“0”的类计 数多于 “1，，的类计数．特别地 ，k是一个奇数 ，而在 k之前 的 k 1位数中，有相等个数的“1，，和“0”，而且这第 k位上是“0”，现在把这前 k位 中每一位上 的数进 行交换 ，“1”换成“0”，“O”换成“1”，并且保持剩下的 数不变．结果这样 的二进制数是一个有 ，z+1个“1” 收稿 日期 ：2004—1 2—25． 基金项 目：国家 自然科学基 金资助项 目(10371048)． 作者简介 ：王春香 (1971一 )，女 ，湖北鄂 州人 ，讲师 ，主要从 事图论与组合的教学与研究． 维普资讯 http://www.cqvip.com 第 3期 王春香 等 ：Catalan数 的一些结 论 299 和 ～1个“0”的二进制数．即一个不合要求的二进 制数对应一个由 +1个“1”和 一1个“0”组成 的 一 个排列 ，这个过程是可逆的：任何一个由 ／'l+1个 “1”和 一1个“0”组成的 2 位数 ，由于“1”的个数 比“0”的个数 多 2个 ，2 是偶数，因此必在某个奇 位数上出现“1”的类计数超过“0”的类计数 ，同样对 它们进行交换 ，并使其余的不动 ，使之成为由 个 “1”和 个“0”组成的 2 位数，这时“0”的类计个数 多于“1”的类计个数 ，是一个不符合要求的二进制 数．从而不符合要求 的二进制数与 ”+1个“1”和 一 1个“0”组成 的排列一一对应 ，这样 的排 列个数 为 因此有 f 2 1一 l + 1／ (2n)! (2n) ! ( ～ 1)1 1 f 2n 1 l j’ 即 A， 一C 定理 2 个+1和 个 一1构成的 2 项 ＆ ， ＆2，⋯ ，＆2 ，其部分和满足 ＆l，＆2，⋯ ，“! ≥0(正一1，2， ⋯ ， )的数列的个数等于第 个 Catalan数． 证明 由定理 1即可证． 从这两个定理显然可得到以下推论： 推论 l 个 1和 个 0构成 2 项 “ ，“。，⋯， ＆z 其部分和恒满足 ＆ +＆ +⋯+“ ≥ ，正一1，2， ⋯ ，2 的排列，这类排列的个数为 Catalan数． 3 应用 以下计数问题都与 Catalan数有关． 命 题 l(唱票问题)甲、乙各 张选票的方式 数 (要求任一时刻所公布的甲的票数都不少于乙的 票数)为 Catalan数 c ． ’ 证明 若将选甲、乙的票分别计为 1，0，则问题 即是将 ”个 1和 ”个 0排成--7'I，求使得前边 k个 数字 中恒有 ＆1+＆2+⋯+＆ ≥ ，正：1。2，⋯ ，2n 的数列 的个数．由推 论 1即可知唱票 的方 式数为 Catalan数 一 ． 命题 2(特定非负整数解问题)求方程 + +⋯+ 一”的非负整数解l满足∑ ，≥正，正：1， 2，⋯ ．，2)组数为 Catalan数 一 ． 证 明 将 每 组 解 中 的 各 个 分 别 换 成 ¨1⋯10，然后依序连在一起 即对应一个 个 1和 r ， 个 0排列而成的序列．例如 ： 一3时， 3=1+1+1(可写为 101010) =1+2+0(可写为 101100) _-2+1+0(可写为 110100) 一 2+0+1(可写为 11O010) =3+0+0．(可写为 l11000) 可 以证明这个写法是一一对应的． 而右边是 由 个 1和 ”个 0组成 的序列 n ， 2，⋯，＆2女(正：1，2，⋯ ， )其部分和恒满足 “ +d 2+ ⋯ +＆ ≥ ，正一1，2，⋯ ，2 ． 由推论 1可知非负整数解组数为Catalan致 命题 3(路径问题)如图 1，从原点 O(0，0)到点 (”， )的路径数(要求中途所经过的点(“，6)满足关 系式 ＆≤6)为第 个 Catalan数． 图 1 从原点 (J到点 的路径数为 证 明 因为要求 中途所经过的任一点 (“，6)满 足 关系式 “≤6，故问题转化成从 (0，0)点出发 ，途 经对角线 OA及对角线上方的点到达( ， )点的途 经数．把沿 y轴正方向走一格记 为 1，沿 X 轴正方 向走一格记为 0．由(0，0)到 ( ， )需要走 2 步，也 即每一条路径对应一个 由 个 1和 ”个 0组成 的 序 列，且“途 中所经过的点(n，6)满足 “≤6”的条件 一 一 一 卅 一 L．． ㈤ I． I． A 维普资讯 http://www.cqvip.com 300 华中师范大学学报(自然科学 版) 第 39卷 转化为“对任一时刻的 k，部分和满足 a +a z+⋯ 厶 +口 ≥ ，k一1，2，⋯，2n”．从而每一条可行性路径 厶 对应一个推论 1所要求的数列，并且这种对应是一 一 对应．故这样的路径数为 Catalan数． 当然还有许多与 Catalan数有关的例子 ，见文 献[4-6]，在此不一一给予证明 ，现在列举如下 ： (1)设有 +1个点的凸多边形 ，用 内部不交 的对角线(共 一2条)将 它剖分成 为 一1个三角 形 ，不同的剖分方式数 Catalan数 C ． (2)设 2 个 点均匀地 分布在 一个 圆的圆周 上 ，能用 条不相交的弦把这些点全配成对，则这 种配对的方法数是 Catalan数 C ． (3)有 2 个人在售票处前站 队买票．入场 门 票是 50美分 ，而 个人恰有这样的钱数．其它 个 人每个人恰有一美分钞票 不巧开始时售票处没有 零钱．如果到第一个位置为止，有 50美分 的人数不 少于有 1美元的人数 ，就称这 2 个人 的序列是可 行的，在这种情况下，能对每个需要找零钱的人找 给零钱，这种可行的序列数为 Catalan数c ． (4)给定不 同高度 的 2 个人．把这些人排列 成两行 ，每行是 个人，使得第一行的任何一个人 高于第二行对应的人，这样排列的方法有 Catalan 数 C 种． 参考文献 ： [1] 康庆德 形形色色的计数[M]．石家庄：河北教育出版社， 1993． Ez] 卢开澄．组合数学(第二版)I-M]．北京：清华大学出版社， 1991． [3] Brualdi R A．Introductory、Combination[M]．New Jersey： Prentice Hall PTR．199． E4] 孙淑玲．组合数学[M]．合肥：中国科技大学出版社，1999． [5] 李有林．一个与 Catalan数有关的计数问题[J]．兰州大学学 报 (自然科学版 )，2003，39(3)：8～10． [6] 毛经中．组合数学基础[M]．武汉：华中师范大学出版社， 1 990． Some results of Catalan number WANG Chun—xiang，MAO Jing—zhong，ZHU Shan—cong (School of Mathematics and Statistics，Central China Normal University，W uhan 430079) Abstract：Catalan number is a kind of permutation，which can be formed by 1 and 0 and the number of 1 or 0 is ，respectively，its partial sum satisfying that口I+口2+⋯ +口 ≥ ，忌一 1，2，⋯ ，2 ．It is known that the number of this kind of permutation have the e— qua¨ty c 一；雨1(2 n)( ≥。)．In thiS paper,they improVe a kind c。n i。n。f catalan number problem and some theorems．They introduce the property and result of Catalan number and some examples． Key words：Catalan number；permutation；one to one correspondence 维普资讯 http://www.cqvip.com