（运筹学与控制论专业论文）排列、匹配和部分有向自回避路的统计量.pdf

i i i i ii lli ii l l ll li ll li 19 0 4 6 3 2 e 倪s tc h m an 0 r m a lu n i v e r s s t a t i s t i c so np e r m u t a t i o n sa n d m a t c h i n g s a n dp a r t i a l l yd i r e c t e ds e l f - a v o i d i n gw a l k s d e p a r t m e n t o fm a t h e m a t i c s m a j o r i t y ：o p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s d i r e c t i o n ：c o m b i n a t o r i c s s u p e r v i s o r ： c a n d i d a t e ： r u o x i ad l l j i n x i ax i e a p r i l ，2 011s h a n g h a i 华东师范大学学位论文原创性声明 郑重声明：本人所呈交的学位论文 7 1 + 1 ，则称序对( 仉，7 r i + 1 ) 构成一个下降( d e s c e n o 同 样的，如果7 r i 死+ 1 ) ，所有上升做成的集合为a ( 7 r ) = ii 丌i i ，均有巧 死) 中的元素我们用r l m ( 7 r ) 表示丌的从右往左最小数的个数如排列7 r = 8 1 2 4 6 3 7 5 从右往左最 小数分别为5 ，3 ，2 和1 ，则r l r n ( 7 r ) = 4 排列7 r = 7 r 1 7 r 2 丌n 中，给定乃，着存在k 满足k 乃 孤，则称序列 七一1 7 r k 一) 构成一个( 3 1 2 ) 一型；若存在k 满足k 歹且仉一1 乃 7 r 七，则称序列( 巩一l 巩一乃) 2 华东师范大学排列、匹配和部分有向自回避路的统计量 构成一个( 1 3 - 2 ) 一型例如排列可= 7 2 8 9 6 3 4 1 5 中( 3 1 2 ) 一型有( 7 2 6 ) ，( 7 2 - 3 ) ，( 7 2 4 ) ，( 7 2 5 ) ，( 6 “) 和( 6 3 - 5 ) ，( 1 3 - 2 ) 一型有( 2 8 - 6 ) ，( 2 8 - 3 ) ，( 2 蹦) 和( 2 8 - 5 ) 对于排列7 r = 7 r 1 丌2 ，称( i ，7 r t ) 为该排列的一条弧( a r c ) 对于弧0 ，丌j ) 和( k ，砜) ，如 果k 码 矾，称0 ，乃) 和( k ，矾) 形成一个嵌套( n e s t i n g ) ；如果 j 乃 孤，称u ，乃) 和( k ，孤) 形成一个交叉( c r o s s i n g ) 我们用 n e s ( 7 r ) 表示7 r 的所有嵌套的个数，用c r s 何) 表示7 r 的所有交叉的个数 我们也可以用图表示一个排列，例如7 r = 4 2 5 1 9 8 6 7 3 对应于下图： 图1 ：排列的图形表示 按照定义，图1 中形成嵌套的弧有( 1 ，4 ) 和( 2 ，2 ) ，( 5 ，9 ) 和( 6 ，8 ) ，( 9 ，3 ) 和( 8 ，7 ) ，( 9 ，3 ) 和 ( 7 ，6 ) ，从而n e s ( 7 r ) = 4 同样，形成交叉的弧有( 1 ，4 ) 和( 3 ，5 ) ，( 3 ，5 ) 和( 5 ，9 ) ，( 9 ，3 ) 和( 4 ，1 ) ， 从而c r s ( 7 r ) = 3 定义1 设7 r 6 n ，7 r 的一个因子慨一是一个极小子集合 口，口+ l ，h ( 1 口b 佗) 中元素的有亭排列满足小于伍l 大于b l 的元素只能映射到小于a ( 大fb l 的元素 例3 搠f 3 1 4 2 7 5 6 9 8 有3 个因子，分别为3 1 4 2 ，7 5 6 和9 & 1 3 匹配及其统计量 【叫的一个分拆( p a r t i t i o n ) 是集合m 的一些非空不交子集合，且这些集合的并恰为 【叫例如【9 】的一个分拆为 1 ，2 ，5 ) ， 3 ，4 ，7 ，9 ) ， 6 ，8 ) ) 我们称这些子集合为块c a l o c k ) 【2 叫的一个匹配( m a t c h i n g ) 是【2 叫的由n 个2 - 元块组成的分拆可将这n 个块记为 ( i l ，j 1 ) ，( i 2 , 如) ，( i n ，矗) ，其中对任意1 r n ，4 j f r 我们用朋n 表示【2 叫的所有 匹配的集合 3 华东师范大学 排列、匹配和部分有向自回避路的统计量 给定匹配中的两个块嘛，矗) 和( 缸，矗) 如果i r i 5 五 j r ，则称它们形成了一个嵌套 ( n e s t i n g ) 如下图所示： 孑弋、 i ti s tj t 如果i r i 矗 矗 矗，则称它们形成了一个交叉( c r o s s i n g ) 如下图所示： t rt s3 t3 l 同排列中的定义类似，给定一个匹配m ，我们用n e s ( m ) 表示m 的所有嵌套的个数，用 c 璐( m ) 表示m 的所有交叉的个数 定义2 设m 朋伽m 的一个压 - y - f f a c t o o 是一个极小子集合 口，口+ 1 ，6 ) ( 1 口 6 2 n ) 中元素构成的一个子匹配；满足其中所有元素都只与该区问j 内元素匹配，且小于口 t 大于b ) 的元素只能5 小于a ( 大于b ) 的元素匹配 例4 下面的匹配有3 个因子： 这3 个因子分男： 为 ( 1 ，3 ) ，( 2 ，4 ) ， ( 5 ，9 ) ，( 6 ，8 ) ，( 7 ，1 0 ) ) 和 ( 1 1 ，1 2 ) ) 八 l l1 2 1 4 部分有向自回避路 m a r t i nr u b e y 在文章【2 6 】中给出下而的定义： 定义3 部分有向自回避路( p a r t i a l l yd i r e c t e ds e l f - a v o i d i n gw a &称p d s a w ) , 是指在直角坐 标平面上从原点出发、只走单位东步、北步和南步的一条路径其中要求路径不能两次经 过同一个点将满足上述条件但夹在直线y = z 和直线可= 一z 之间、终止于秒= 一z 的路 径称为对称部分有向自回避路( s y m m e t r i c p a r t i a l l yd i r e c t e ds e l f - a v o i d i n gw a l t , 简称s p d s a w ) ； 4 华东师范大学排列、匹配和部分有向自回避路的统计量 将满足上述条件但夹在z 一轴和直线掣= 一z 之间、终止于可= 一z 的路径称为非对称部分 有向白回避路( a s y n v n e t r i cp a r t i a l l yd i r e c t e ds e l f - a v o i d i n gw a l k , 筒称a s p d s a w ) 特别地，长为2 佗的一条d y c k 路( o y c kp a t h ) 是直角坐标平面上从原点( o ，o ) 出发、只走 单位东步和南步、最终到达点( n ，一n ) 的一条路d y c k 路显然是a s p d s a w 我们用 r 表示东步步数为扎的所有s p d s a w 的集合； a 表示东步步数为礼的所有a s p d s a w 的集合； 巩表示东步步数为n 的所有d y e k 路的集合 同时，设p r ，我们用en 和s 分别表示p 的东步、北步和南步，用e ( p ) ，n ( p ) 和 s ( p ) 分别表示p 的东步、北步和南步的个数，用啦( p ) 和s t ( p ) 分别表示p 的第i ( i 【叫) 列中北步和南步的个数这些记号在a s p d s a w 中也是有相同意义的 s p d s a w 的一个方格( s q u a r e ) 指由s p d s a w 和可= 一z 围成的区域中一个完整单位方 形区域；s p d s a w 的一个拐角( c o m e r ) 是由一个东步和紧跟其后的南步形成的尖角；s p d s a w 的一个子路( s u b p a t h ) 是指开始并终止于直线可= 一z 且起点和终点之间没有其他点在 可= 一z 上的一段路径 定义4 设p 是一条s p d s a w , p 的一个因子( f a c t o r ) 是指从点( 口，一口) 出发、到点( b ，一b ) 结束的p 的一条子路。满足以t 两个条件： 点( 口，一n ) 之后的所有东步都在直线可= z 一2 a 之百 点( b ，一b ) 之后厅晰有东步都在直线可= z 一2 b 之百 同理我们定义a s p d s a w 的因子为从点( 口，一口) 出发、到点( b ，- b ) 结束且点( n ，一n ) 之 后的所有东步都在直线可= 一口之下、点( b ，一b ) 之后的所有东步都在直线! ，= 一b 之下的一 条路径 对于p r ，我们用s q r ( p ) 表示p 的方格的个数，用咖( p ) 表示p 的拐角的个数，用 s b p ( p ) 表示p 的子路的个数，同时用f a c ( p ) 表示p 的因子的个数a s p d s a w 的方格、拐 角、子路和因子的定义及他们个数的表示方法也类似定义 供s 给定一条s p d s a w , 设为p ： 5 华东师范大学排列、匹配和部分有向自回避路的统计量 可知e ( p ) = 8 ，n ( p ) = 7 ，s ( p ) = 1 5 ，n 2 ( p ) = 1 ，n 4 ( p ) = 5 ，n r ( p ) = 1 ，s 2 ( p ) = 3 ，s 4 ( p ) = 3 ，s s ( p ) = 5 ，s s ( p ) = 4 以及s q r ( p ) = 1 7 ，e m ( p ) = 4 ，s b p ( p ) = 3 ，而f a e ( p ) = z 6 m n ( q ) = g ( p ) = 而1 萎c - 1 ) ( ( 0 ；) 一( n 羔1 ) ) g ( 妁 而该式恰为著名的t o u c h a r d r i o r d a n 公式，是长为2 n 且口的次数表示交叉个数的匹配 的生成函数，从而得知有n 个e 及c 个n 的s p d s a w 与长为2 n 且交叉个数为c 的匹配具有 一一对应关系 r o b e r tj m a r s h 和p a u lm a r t i n 在文章【2 3 】中给出了上述结论的一个组合证明以下给出 一个例子 首先，将s p d s a w 中包含的最大的d y c k 路称为该s p d s a w 的基底d y c k 路例如下图 中粗线描绘的d y c k 路即为给定的s p d s a w 的基底： 图2 ：s p d s a w 的d y c k 基底 7 华东师范大学 排列、匹配和部分有向自回避路的统计量 引用下面三条变换规则： 在基底d y c k 路中： 在基底d y c k 路之外的区域： 一 么 一 供6 给定一条s p d s a w , 利用i 面的三条规则将唯一得到一个匹配： 图3 ：s p d s a w 到匹配的映射 注在上述文章中，s p d s a w 被称为悬垂路( o v e r h a n gp a t h ) 更进一步地，m a r t i nr u b e y 在【2 6 】中借助赋权的d y c k 路给出了二者之间更细致的对应 关系的双射证明 8 华东师范大学排列、匹配和部分有向自回避路的统计量 定理1 设p r ，m 朋m 存在双射f ：r _ 朋m 使得f ( p ) = m 且具有下列性质的 s p d s a wp ： n ( v ) = n ， p 和直线g = 一蕾所围区域的面积为奇数偶数) 8 n ( p ) = m 一1 一一对匝于具有t 列性质的匹配m ： n e s ( m ) = c r s t m ) 为奇数i 偶数) 。 1 与m 匹j 酉已 而且该双射保持因子的对应关系。即p 的最后一个因子被映射成m 的第一个因子 2 2 排列和非对称部分有向自回避路 关于排列和a s p d s a w , 一个显然的结论是6 n 中排列的个数与e 的个数为n 的所有 a s p d s a w 的条数都为仃! 。二者之问具有一一对应关系，其中n 的个数对应于排列中嵌套的 个数，或对应于排列中( 3 1 2 ) 一型的个数【8 】我们用r 表示长为几的排列的生成函数，这个 生成函数由l a u r e nw i l l i a m s 在【3 0 】中给出： r ( g ) = eq n 骼( p ) = 三伽e 瑚七一1 c 一1 h 七一啦产( q k - i + g 二1 ) 、) 七= 1 t = 0 。 类似于上节的结论，m a r t i nr u b e y 以赋权的双色m o t z k i n 路为中间桥梁得到以下结论： 定理2 设p ，丌6 伽存在双射夕：a _ 瓯，使得g ( p ) = 7 r 且具有下列性质的 a s p d s & 孵p ： 华东师范大学 排列、匹配和部分有向自回避路的统计量 n ( p ) = n ， s n ( 尸) = m 一一对应于具有t 列性质的排列霄： n c s ( 7 r ) = n ， 1 被映射到砚 而且该双射保持因子的对应关系即p 的最后一个因子被映射成耳的第一个因子 2 3 排列中逆序数和主指标的对称分布关系 逆序数和主指标是排列中两个相当重要的统计量，在很多文献中都对它们以及它们之间 的关系进行了研究一个已知的结论是排列中逆序数和主指标具有对称分布关系，以下我们 简单介绍【2 7 】中给出的双射 妒：6 n 叫6 n 令加= u 1 瓯，定义序列饥，其中讯是( l 0 1 ，w k 的一个排 列 首先令饥= u 1 假定饥已经被定义，1 k 岫= & 我们分割m 得到6 1 8 , 每个厢问仍然 只有一个元素，故讹= 6 8 3 重复上面的过程? 1 0 7 s ：63i8 9 4i71l2 拍：36 4891725 得到妒( u ) = 3 6 4 8 9 1 7 2 5 且m a jc w ) = i n v ( 妒( u ) ) = 1 8 首先在假定妒是一个双射的前提下用归纳法证明m a j c w ) = i n o c t ) ) 令孤= u 1 忱魄对后进行归纳证明i n v ( 7 七) = m a j 0 7 k ) 首先有i n v ( 吖o ) = m a j ( ) = 0 假定对于某个k 【t _ ，k - i - 1 ，故k d c w ) ，现在需要证明i n v c - y 七十1 ) = 七+ 姗( 饥) 不难发现此时讯 的任何一个间隔c 中的最后一个数字是该间隔中最大的一个数字我们用孝c 表示隔间c 中元素的个数，则进行循环移位之后，则会新增( 椤一1 ) 个逆序又每个间隔中有且只有 一个数字大于魄+ 1 ，所以当把魄+ 1 置于讯的末端，再次新增的逆序数恰为讯中间隔的个数 i c i ，于是， ( 孝c 一1 ) + l c l = k ， c 说明i a v c - y k + 1 ) = k + 曲( 饥) 最后证明妒是一个双射为此，定义妒设i ，= v l 瓯我们希望找到唯一 一个t u = u l ( - o n 6 n 满足妒p ) = y 令矗一l = h 一1 且= v n 现在假定以和 u 七+ l ，已经确定，1 k 佗如果民的第一个数字大于( 或小于) 峨+ 1 ，则在以中每个 比吣l 大( 或小) 的数字前进插入隔板，这样便形成瓯的各个间隔，将其的元素在间隔内向 华东师范大学 排列、匹配和部分有向自回避路的统计量 左循环移动一位，从而得到的最后一个数字即为峡，去掉该数字得到以一1 很容易看出，上述 过程完全是从u 得到的过程的逆，可见妒是一个双射 例8 取y 为例7 中妒0 ) ，利用上述过程旨在得到u ? 得到= 6 8 3 9 4 1 7 2 5 36 4 89l i 36 l 4 89i1 l 6 l3l8i 9i4 i7 i 6l38 9i4i1 l6i8i9i3i4 i6i8l9 3 l 6 i 8i3 i6l8 6 725 蛐= 5 7i2 蛐= 2 1 = 7 = 1 姚= 4 咄= 9 忱= 3 1 0 2 = 8 h 1 = 6 第三节关于非对称部分有向自回避路的主要结论 本节主要介绍两个新的双射x l 和x 2 ，其中x l 用来描述a s p d s a w 和排列的六组统计量 之问的一一对应关系，x 2 在x l 的基础上问接证明了排列中逆序数和主指标的对称分布关系 3 1 双射) ( 1 x 1 ：a 一瓯设p ，将p 的各列从左往右分别编号为f n ，l r l 一1 ，1 1 从l i 开始，自下 往上依次在半格和方格中按照从小到大的顺序填入集合m 中的数字，设2 l 的最上面一个方 格中填入k 1 假设2 1 ，1 2 ，i ( 1 i 7 r t 一1 ，即( 死一1 ，死) 是霄中的一个上升特别地，z 1 必贡献一个拐 角，恰好对应于上升( r o ，7 r 1 ) 从而c r n ( p ) = 箍c ( 丌) 1 i 中有s i ( p ) 个s ，则在7 r i 一1 和仉之间还 有s i ( p ) 一1 个元素没有使用，且这s i ( p ) 一1 个元素贡献s i ( p ) 一1 个( 1 3 - 2 ) 一型不难得到 m a x s i ( p ) 一1 ，o ) = r 时，排列中共有r 个( 1 3 - 2 ) 型 而且，如果毛中e 的后面紧跟有t i 个n 说明比死一1 小、比死大的元素有t i 个，则它们 在7 r 中贡献t i 个( 3 1 2 ) 一型综合各列，如果路中共有t 个n ，排列中就有t 个( 3 1 2 ) 一型 另外，如果l i 中e 开始于直线y = 一z ，则可以肯定的是死是我们还没有用过的数字中 最小的那一个因此，s b p ( p ) = c 时，霄中从右往左最小数字也有c 个，即r l m ( 7 r ) = c 最后，假设从( a ，一a ) 到( b ，一b ) 的路径是p 的一个因子，该因子经过平移，实际上为从 ( o ，o ) 到( b a ，- ( b 一口) ) 的一条a s p d s a w , 这条a s p d s a w 对应集合【b 一口】的一个排列由 此，不难理解p 的这个因子恰好对应7 r 中长为b a 的一个因子 设k 扎，7 - 6 七，7 r g n ，我们说7 r 是避免7 的o a v o i d i n g ) 是指7 r 中没有与7 型相同 的子排列几。吼，死。( i 1 主2 丌。或7 r 2 7 r l t o 时，k 为所求的a s p d s a w 贡献0 个方格 2 假定我们已经得到了q 一1 ，即已经考虑完z n 一件2 ( i = 2 ，3 ，n ) ，且此时得到的排列 为前。1 希1 竹1 ： 如果r l - 1 一1 瓤i + - - 1 1 ， 将丌f 1 1 - 1 ；i 口1 整体移动到一1 和赤 之间，其中t 和s 是满足1 7 r 1 瓤i + - 1 1 ，喀 疵a 7 r f l 或7 奔 7 r f l 一， 将丌f 1 7 r ；- 1 ，f 1 捆绑并整体移动到1 和，霹 之间，其中s 是满足丌f 1 ，分1 一1 或一1 7 r i - 1 7 毒；或； - l 7 中1 时， 保持排列不变化并记录c i = 0 重复操作，直到考虑完z 1 通过上述步骤，可得到唯一确定的数组c = ( c 1 ，c 2 ，c ，1 ) 我们用 q 0 = 1 ，2 ，n ) 表示1 - i + 1 中方格数，从而唯一确定一条a s p d s a w 我们用p i ( i = 1 ，2 ，n ) 表示每步操作时的排列，其中p 1 为给定的排列7 r 锐u 考虑饲1 0 中的排列一。我们进行如- f 操作： 7 1 1 7 r 2 7 t o p 1 ：_ 6 4 3 5 1 8 9 2 7 叫c 1 = 0 7 r 1 丌2 丌3 一矿：_ 4 6 3 5 1 8 9 2 7 叫c 2 = 1 7 r 4 7 r 1 丌3 一矿：6 _ 3 4 5 1 8 9 2 7 叫c 3 = 1 7 r 1 7 r 4 7 1 5 一p 4 ：3 4 5 6 1 8 9 2 7 叫c t = 1 丌6 7 1 1 7 1 5 叫p 5 ：1 3 4 5 6 8 9 2 7 叫c 5 = 4 7 r 7 讹 7 r 1 _ + p 6 ：1 3 4 5 6 8 9 2 7 - - - - - bc 6 = 0 7 i 7 7 r s 7 r 1 一p 7 ：3 4 5 6 8 9 1 2 7 叫c 7 = 1 丌9 丌1 7 r s 一p s ：8 9 1 2 3 4 5 6 7 _ c s = 4 7 1 1 丌9 7 r l o p 9 ：1 2 3 4 5 6 7 8 9 一c 9 = 2 利用数组c = ( 0 ，1 ，1 ，1 ，4 ，0 ，1 ，4 ，2 ) ，我们可以确定傩删中每歹愤献的方格魏从而确定 每个e 的位置所得结果与例9 中的p _ 致且显然有m a j ( 7 r ) = 1 4 = s q r ( p ) 定理6 对任意的p ，设x z ( p ) = 丌，则7 r 6 n 且s q r ( p ) = n 坷( 7 r ) 为证明定理6 ，我们首先要证明一个引理： 1 8 华东师范大学排列、匹配和部分有向自回避路的统计量 引理7 对任意t ，i h i ，排列矿= 7 r i 丌；的子排列7 r i 赶7 r 。i + l 最多只有一个下降? 如 果这个子排列有下降那么丌i 7 r | + 1 证明 我们用归纳法证明这个引理首先，初始条件成立，因为p 1 中，砧7 r i 畦最多只有一个下 降；且如果有下降，必有7 r 砣现在考虑矿 ( i ) 畦 7 r 时， 如果砖 以 7 r i ， 保持排列不变，p 2 = p 1 ，子排列r ，t 1 - 1 1r ，- - - 2 1r ，- - - 3 1 中没有下降； 如果以 以 7 r ；， 将丌 移动到以和砖之间，得到矿= 砖丌 以以畦，子排列以丌 以中有一食下降 ( 以，丌 ) 且砣 以； 如果畦 7 r ； 以， 保持排列不变，矿= p 1 ，子排列丌i 以砖中有一个下降( 以，以) 且丌 伍) 耐 以时， 如果以 7 r ； 砣， 将丌i 移动到砣和以之问，得到矿= 以霄i 砖以畦，子排列畦丌 以中没有下降； 如果7 r 砖 畦， 保持排列不变，p 2 = p 1 ，子排列7 r i 砣以中有一个下降( 丌 ，砣) 且耐 砖； 如果7 r 以 砖， 将丌i 移动到以和以之间，得到矿= 面丌 砧以畦，子排列以万i 以中有一个下降 ( 仃i ，砖) 且以 以 可见矿时结论成立现在假设矿- 1 = 7 r f l 毋1 行1 ( 1 7 r _ 1 ， 保持排列不变，矿= 矿一，子排列7 r f l 1 砗 中没有下降；图示如下： 如果_ 1 布 7 r f l ， 我们可以找到满足操作条件的s ( 1 7 r - 1 q i + - 1 1 ， j 保持排列不变，= 矿，子排列丌 _ 1 希1 ，毒i 中有一个下降( ，喀 ) 且，中1 瓤i + - 1 1 图示如下： 伍) 子排列7 r i _ 1 希1 一1 中有一个下降时，7 r 1 设该下降为( 7 r i ，吒i + - 1 1 ) ，1 亡 主一1 ，得到- 1 丌 - 1 一1 瓤i + - - 1 1 如果7 卤 1 7 r f l - l 7 r 件i - 1 1 ， 满足映射条件的8 = t ，将丌 - 1 ，分1 - 1 移动到- 1 和辑 之间，得到矿= 诉 - 1 希1 - 1 丌喜 竹1 ，子排列，去；1 万f 1 - 1 喀 中没有下降； 图示如下： p 华东师范大学排列、匹配和部分有向自回避路的统计量 f + j j 如果祀- 1 ； 寸1 。 瓤i + - 1 1 ， 我们可以找到满足操作条件的8 ( 1 7 r f l 巧i + - - - 1 吒i + - - 1 1 ， 保持排列不变，p i = ，子排列，中1 1 喀i 喀；r f l 有一个下降( ，去i ) 且 7 r f l 瓤i + 1 1 l ，图示如下： 如果疵_ 1 7 r - 1 - 1 7 奔i ，去i ， 我们可以找到满足操作条件的s 寸1 - 1 7 r 本 布 ， 满足映射条件的s = ，将竹1 希1 - 1 移动到_ 1 和， 之间，得到矿= 喀i 疵- 1 万f 1 疵_ 1 ，去 竹1 ，子排列； _ 1 寸1 - 1 q i + - - 中有一个下 降( 采t - 1 ， ) 且，去i ，吉 图示如下： 综上所述，结论成立在矿中，由于吆 咯1 = 0 ，故排列7 r 砖碟没有下降，这个排 列即为自然序1 2 几 定理6 的证明以下只要说明映射的每一步恰使主指标减少s 或没有发生改变即可。此时每 步记录的方格数恰好等于主指标的减少量 丌f 1 疵_ 1 ，当 时，子排列丌f 1 ，中1 - 1 中必有一个下降，因为本1 ( i ) 如果子排列征_ 1 希1 砰1 中没有下降，则矿一1 中必有一1 以i l ，甭则i - + 1 1 寸1 ，卤 ，疤磊也应该一起被移动，矛盾由引理7 ，子排列i - + 1 。w 卧i - ：一1 中没有下 降此时矿一1 中有7 中1 i - 十1 1 ，瓤i 一1 瓤i + - 1 1 ，操作后，中有疵一1 7 去 ，其 余下降保持不变可见操作只破坏了下降( i - - 1 ，i - - + 1 1 ) ，此时 m a j - 1 ) 一m 萄0 ) = s ； ( i ) 如果一1 i - - + 1 1 ，则唯一一个下降属于子排列i - - + 1 1 i - + 1 2 ，设为( ，i + - - 1 1 ) ，s + 1 t i 此时，一1 中有一1 i - - + 1 1 ，_ 1 巧i + - - 1 1 ，操作后，p i 中有一1 i - + 1 l ，_ 1 瓤i + - 1 1 ，操作后，中有- 1 _ 1 或- 1 7 r 1 砖i 或7 吉i - 1 前- 1 时， m a j ( p i - 1 ) 一m a jp i ) = 0 结合定理3 及定理6 ，我们可以得到如下结论： 推论8 g 删( 霄) = g n 嘲( 引 r 6 n，r 6 f i 第四节关于对称部分有向自回避路的进一步探讨 4 1 双射砂 类似于4 i 节方法，我们寻找匹配和s p d s a w 之问的双射，目的是在一个双射中同时给 出二者更多的统计量之间的一一对应关系 妒：r 一朋n 设p r ，将p 的各列从左往右依次编号为k ，j n 一1 ，2 1 从z 1 开始，自下 往上依次给每个半格和方格的分割线按照从小到大的顺序填入【2 叫中