（应用数学专业论文）分拆与匹配中的有禁模式.pdf

摘要 近几年里，有禁分拆与有禁匹配被广泛地研究，越来越多的组合数学中的经 典结果被推广至分拆与匹配的研究中本文主要研究了几类有禁分拆与有禁匹配 的计数问题文中我们主要使用了构造双射的方法和传递矩阵法，并借助计算机 开发了一个m a p l e 软件包来生成特定序列所满足的递归方程 本文共由三章组成其组织如下： 在第一章中，我们简要叙述了一下该文的研究背景，并介绍了部分文中使用 的基本定义和常见符号 在第二章中，我们主要考虑双边对称的3 - n o n c r o s s i n g 分拆的计数问题c h e n e ta 1 首次提出了集合分拆中的k - c r o s s i n g 和k - n e s t i n g 的概念，并通过v a c i l l a t i n g t a b l e a u x 与分拆之间的一个双射来证明这两个统计量对称联合分布的性质该双 射推广了全排列和标准杨表对之间经典的r s k 对应，并同样具备r s k 对应所 具备的对称性基于该双射的对称性质和其与格路之间的关系，并借用迭代级数 的常数项理论，我们通过开发了一个针对二维平面内v a c i l l a t i n gl a t t i c ew a l k 计 数问题的m a p l e 软件包，以此得到集合m 中所有3 - n o n c r o s s i n g 分拆的个数所 满足的递归关系式该软件包适用于一类相似的v a c i l l a t i n gl a t t i c ew a l k 的计数 问题 在第三章中，我们主要考虑可通过k 次堆栈排序的分拆和匹配的计数问题 我们刻画了可通过k 次堆栈排序的分拆与匹配的主要性质一个分拆足可通过七 次堆栈排序的当且仅当它的序列表示避免2 3 ( k + 2 ) 1 模式我们计算了可通 过k 次堆栈排序的无相交分拆、无相交匹配和无嵌套匹配这三类分拆的生成函 数，并通过构造双射的方法给出了七次堆栈排序的分拆的生成函数的一个公式 该公式比m a n s o u r 和s e v e r i n i 通过核方法所得到的公式更简单直接利用经典 的传递矩阵法，我们证明了可通过k 次堆栈排序的匹配的个数的生成函数足有 理的 最后，我们在附录中给出第二章中所提到的m a p l e 软件包及该软件包应用于 h e s i t a t i n gl a t t i c ew a l k 计数问题时的初始变量 关键词：分拆，匹配，杨表，r s k 对应，堆栈排序，d 有限，p 一递归 i i a b s t r a c t a b s tr a c t i nr e c e n ty e a r s ，t h es u b j e c to fp a t t e r na v o i d a n c ei ns e tp a r t i t i o n sa n dm a t c h - i n g sh a sb e e nw i l d l ys t u d i e d m o r ea n dm o r ec l a s s i c a lc o m b i n a t o r i a lr e s u l t sh a v e b e e ne x t e n d e df o rt h ep a r t i t i o nc a s e t h em a i nr e s u l t so ft h i st h e s i sc o n s i s to f s e v e r a la p p r o a c h e st os t u d yt h ee n u m e r a t i o no fp a r t i t i o n sa n dm a t c h i n g sa v o i d i n g c e r t a i np a t t e r n s ，i n c l u d i n gt h eb i j e c t i v em e t h o d ，t h et r a n s f e rm a t r i xm e t h o d ，a n d am e t h o do fd e v e l o p i n gam a p l ep a c k a g et op r o d u c ed - f i n i t ee q u a t i o n sb a s e do n t h et h e o r yo fc o n s t a n tt e r m s t h i st h e s i si so r g a n i z e da sf o l l o w s t h ef i r s tc h a p t e ri sd e v o t e dt oa ni n t r o - d u c t i o nt os e tp a r t i t i o n sa n di t sr e l a t e dc o m b i n a t o r i a lo b j e c t s w ew i l lp r e s e n t s o m eb a s i cd e f i n i t i o n sa n dt h ec l a s s i c a ln o t a t i o n s t 1 1 er s ka l g o r i t h m ，n a m e da f t e rg d eb r o b i n s o n ，c s c h e n s t e d ，a n dd k n u t h i sp e r h a p st h em o s tb e a u t i f u la n di m p o r t a n ta l g o r i t h mi nc o m b i n a t o r i c s i i li t sm o s tb a s i cf o r m i tt r a n s f o r i n 8ap e r m u t a t i o ni n t oap a i ro fs t a n d a r dy o u n g t a b l e a u xo ft h es a m es h a p e s c h f i t z e n b e r g e r st h e o r e mf o ro r d i n a r yr s kc o r = r e s p o n d e n c en a t u r a l l ye x t e n d sf o rc h e ne t ，a l sc o r r e s p o n d e n c ef o rm a t c h i n g s a n dp a r t i t i o n s b a s e do nt h es a m es y m m e t r i cp r o p e r t y , w ec o u n tt h eb i l a t e r a l l y s y m m e t r i ck - n o n c r o s s i n gp a r t i t i o n sw h i c hn a t u r a l l ya r i s e sa sa na n a l o g u ef o ri n - v o l u t i o n si nc h a p t e r2 i no b t a i n i n gt h ea n a l o g o u sr e s u l tf o r3 - n o n c r o s s i n gp a r t i - t i o n s ，w eu s ead i f f e r e n tt e c h n i q u et od e v e l o pam a p l ep a c k a g ef o r2 一d i m e n s i o n a l v a c i l l a t i n gl a t t i c ew a l ke n u m e r a t i o np r o b l e m s t h ep a c k a g ea l s oa p p l i e st ot h e h e s i t a t i n ge a s e a sa p p l i c a t i o n s ，w ef i n ds e v e r a li n t e r e s t i n gt e l a t i o n sf o rs o m e s p e c i a lb i l a t e r a l l ys y m m e t r i cp a r t i t i o n s i nc h a p t e r3 ，w et u r nt oc o u n tt h ek - s t a c ks o r t a b l ep a r t i t i o n sa n dm a t c h i n g s a p a r t i t i o no ram a t c h i n gi ss a i dt ob ek - s t a c ks o r t a b l ei fi t sc a n o n i c a ls e q u e n c e i sk - s t a c ks o r t a b l e w es h o wt h a tap a r t i t i o ni sk - s t a c ks o r t a b l ei fa n do n l yi f i t sc a n o n i c a ls e q u e n c ei s2 3 ( k + 2 ) 1 一a v o i d i n g t h ee x p l i c i tf o r m u l a sf o rt h e g e n e r a t i n gf u n c t i o n sf o rt h en u m b e r so fk - s t a c ks o r t a b l en o n c r o s s i n gp a r t i t i o n s ， i i i a b s t r a c t n o n c r o s s i n gm a t c h i n g sa n dn o n n e s t i n gm a t c h i n g sa r eo b t a i n e d u s i n gt h et r a n s f e r m a t r i xm e t h o dw es h o wt h a tt h eg e n e r a t i n gf u n c t i o nf o rt h en u m b e ro fk s t a c k s o r t a b l em a t c h i n g si sr a t i o n a l m o r e o v e r ，w ec o n s t r u c tas i m p l eb i j e c t i o nb e t w e e n t h es e to fp a r t i t i o n so fmw i t hn om o r et h a nk + 2b l o c k sa n dt h es e to fk s t a c k s o r t a b l ep a r t i t i o n so fm ，w h i c hi n d u c e ss i m p l e rf o r m u l a sf o rt h en u m b e ro fk s t a c k s o r t a b l ep a r t i t i o n sa n df o rt h eg e n e r a t i n gf u n c t i o nc o m p a r e dw i t ht h ef o r m u l a s o fm a n s o u ra n ds e v e r i n i w ec o n c l u d et h i st h e s mw i t ht h em a p l ep a c k a g ed e v e l o p e di nc h a p t e r2a n d t h ei n i t i a lv a r i a b l e sw h e nt h ep a c k a g ea p p l i e st ot h eh e s i t a t i n gc a s e k e y w o r d s ：p a r t i t i o n ，m a t c h i n g ，t a b l e a u ，r s kc o r r e s p o n d e n c e ，s t a c ks o r t a b l e ， d f i n i t e ，p r e c u r r e n c e i v 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：琵如、墨、 o 一口7 年乡月弓日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： ，”。w j ”m - ， 一“”一“。_ 1 ”+ ? “”p 。“ ；内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长l o 年，可少于1 0 年) ：机密2 0 年( 最长2 0 年，可少于2 0 年) t 。i 。，。+ i 。，。，。! 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 京永太， 渺c 7 年乡月多日 c h a p t e r1 i n t r o d u c t i o n c h a p t e r1 i n t r o d u c t i o n 1 1b a c k g r o u n da n do v e r v i e w t h e g e n e r a le n u m e r a t i o np r o b l e mf o rp a t t e r na v o i d a n c e i np e r m u t a t i o n sa t t r a c t s i n t e n s er e s e a r c ha c t i v i t yi nt h ep a s td e c a d e r e c e n t l y , m o r ea n dm o r ea t t e n t i o n h a sb e e np a i dt ot h es t u d yo ft h ep a t t e r n si ns e tp a r t i t i o n s ，a n di ti sc u r r e n t l y a na r e ao fv e r ya c t i v er e s e a r c h m u c hw o r kh a sb e e n d o n eo na ni m p o r t a n tc l a s so fp a r t i t i o n sa v o i d i n gc e r t a i n p a t t e r n ，c a l l e dn o n c r o s s i n gp a r t i t i o n s aw e l l k n o w nr e s u l to fk r e w e r a s ( 3 1 】s t a t e s t h a tt h en u m b e ro fn o n c r o s s i n gp a r t i t i o n so f 佗】i st h e 佗一t hc a t a l a nn u m b e r g = 击( ：) t h ee n u m e r a t i o nr e s u l tw a sr e f i n e db ys a p o u n a k i sa n dt s i k o u r a s 【3 8 】i nw h i c h t h en u m b e ro ff i x e dp o i n t sw a sc o n s i d e r e d ，a n db yy a n oa n dy o s h i d a 【5 7 】i nw h i c h t h ec o n c e p to f “i n n e r ”b l o c k sw a si n t r o d u c e d m o t i v a t e db yd a v e n p o r t s c h i n z e ls e q u e n c e s ，k l a z a rf 2 5 1d e f i n e da n ds t u d i e d an o t i o no fp a t t e r na v o i d a n c ef o rs e tp a r t i t i o n s i nt h i sl a n g u a g e ，t h en o n c r o s s i n g p a r t i t i o nc a nb ee x p l i c a t e da sa b a b - f r e es e tp a r t i t i o n s ，t h e s e to fp a r t i t i o n sa v o i d - i n gt h ep a t t e r na b a b u s i n gt h eg e n e r a t i n gf u n c t i o nm e t h o d ，k l a z a re x t e n d e d t h ek n o w ne n u m e r a t i v er e s u l t sf o rs e v e r a lc l a s s e so fp a r t i t i o n s g i v e nap a t t e r n 矿= a b a bo r 仃= a b b a ，d e n o t eb yp ( 盯，l ，礼，七) t h ec a r d i n a l i t yo ft h es e tp ( a ，l ，礼，七) o fk - r e g u l a ra n dp - f r e ep a r t i t i o n so f 叫w i t hlb l o c k s u s ep ( 盯，k ) s t a n df o rt h eb i - v a r i a t eg e n e r a t i n gf l m c t i o n sp ( 仃，尼) ( z ，y ) ：= n 1 op ( o ，l ，n ，尼) z 。y n t h ee x p l i c i t f o r m u l a sf o rp ( a b b a ，k ) a r ed e t e r m i n e df o r 七= 1 ，2 ，3 ，a n dt h ee x a c tf o r m u l af o r p ( a b a b ，k ) i ss t a t e da sf o l l o w s p r o p o s i t i o n1 1 1 ( k l a z a r 【2 5 】) f o ra n yk 1 ， p ( 。鼬，七) = 互1 ，( 1 + y + y c ( 七) - - x y - - 佰万丽矿葡砀厕) ， w h e r ec ( 1 ) = 0 ，c ( 2 ) = 1a n d e ( 南) = c ( 七) ( z ，y ) = 1 + z y + ( z ) 2 + + ( z y ) 知一2 k l a z a ra l s oe n u m e r a t e dp a r t i t i o n so f n 1t h a td on o tc o n t a i nag i v e np a r t i t i o n o rag i v e ns e to fp a r t i t i o n si n 2 6 1 ap a r t i t i o n7 ro fmi sc o n t a i n e di na n o t h e r p a r t i t i o nt o fmi f n 1h a sa 缸s u b s e to nw h i c hti n d u c e s7 r g i v e nap a r t i t i o n 丌，s u p p o s et h a t 尸( 7 r ；z ，n ) i st h en u m b e ro fp a r t i t i o n so f 【i t n o tc o n t a i n i n g7 ra n d h a v i n gfp a r t s g i v e nas e t o fp a r t i t i o n sr ，d e f i n ep ( r ；f ，n ) i nas i m i l a rw a y t h e nf o rac e r t a i ns e to fp a r t i t i o n sra n dap o s i t i v ei n t e g e rj ，t h eg e n e r a t i n g f u n c t i o ni so b t a i n e da sf o l l o w s p r o p o s i t i o n1 1 2( k l a z a r 【2 6 ) p ( n ；l ，n ) y 竹= t l l a ( y ) ( 1 一y ) r ( 1 2 y ) z ( 1 一t 可) n w h e r ea ( y ) z 【可】，0 ，t = r a i n ( ，七) ，a n dk = m i n e n1 1 7 r i i 一1 乃rk = 0t h e d e n o m i n a t o ri s1 u n d e rt h en o t i o n sd e f i n e db yk l a z a r ，s a g a nf 3 7 e n u m e r a t e da n dc h a r a c - t e r i z e dt h ep a r t i t i o n sa v o i d i n ga n yp a r t i t i o no fa 3 l e ti i n ( 7 r ) d e n o t et h es e t o fp a r t i t i o n so f 礼】a v o i d i n gc e r t a i np a r t i t i o n7 r e x a c tf o r m u l a sa n dg e n e r a t i n g f u n c t i o n sf o r 移竹( 7 r ) f o rv a r i o u sp a t t e r n s7 r ，i n c l u d i n ge a c hp a r t i t i o no f 【3 】，a r e o b t a i n e d t h ee n u m e r a t i o no fa l lp a r t i t i o n so ff n lw h i c ha v o i daf a m i l yo fp a r - t i t i o n so f 【3 】，a sw a sd o n eb ys i m i o na n ds c h m i d tf o rp e r m u t a t i o n si n 【4 4 ，w a s s t u d i e db yg o y t 1 9 g i v e nap a t t e r n 仃，u s ep ( 竹；仃) t od e n o t et h en u m b e ro fs e tp a r t i t i o n so f 【n 】 w h i c ha v o i d 口t h ep a t t e r no 1i ss a i dt ob ee q u i v a l e n tt ot h ep a t t e r n 盯2w h e n e v e r p ( i t ；仃1 ) = p ( i t ；5 r 2 ) f o ra l l 礼j e l i n e ka n dm a n s o u r 2 2 】u s e df i l l i n g so ff e r r e r s d i a g r a m sa n ds t a c kp o l y o m i n o e st op r o v i d es e v e r a ln e wi n f i n i t ef a m i l i e so fp a i r s o fe q u i v a l e n tp a r t i t i o n s l a t e r ，m a n s o u ra n ds e v e r i n if 3 3 1p r o v i d e da ne x p l i c i t f o r m u l af o rt h eo r d i n a r yg e n e r a t i n gf u n c t i o no ft h en u m b e ro f ( k ，d ) 一n o n c r o s s i n g p a r t i t i o n so f 【n f o rd = l ，2 ，w h e r eas e tp a r t i t i o ni ss a i dt ob e ( k ，d ) - n o n c r o s s i n g i fi ta v o i d st h ep a t t e r n1 2 k 1 2 d i nt h em e a n t i m e ，t h es t u d yo ft h ej o i n td i s t r i b u t i o no fc e r t a i np a t t e r n si n s e tp a r t i t i o n sh a sb l o s s o m e di nm o s tr e c e n t l y t h ej o i n td i s t r i b u t i o no fn u m b e r s 2 c h a p t e r1 i n t r o d u c t i o n o fc r o s s i n g sa n dn e s t i n g so ft w oe d g e si nm a t c h i n g sw a ss t u d i e db yk l a z a r 2 7 1 k a s r a o u ia n dz e n g 【2 3 】g e n e r a l i z e dt h er e s u l tb yc o n s t r u c t i n ga ni n v o l u t i o npo n t h es e th 礼o fa l ls e tp a r t i t i o n so fms u c ht h a t ( i ) pp r e s e r v e st h es e to fl e a s t e l e m e n t so fn o n - s i n g l e t o nb l o c k s ( i nap a r t i t i o n ) ，t h es e to fl a s te l e m e n t so fn o n - s i n g l e t o nb l o c k s ，t h es e to fs i n g l e t o nb l o c k s ( h e n c ea l s ot h es e to ft h er e m a i n i n g m i d d l ee l e m e n t so fn o n - s i n g l e t o nb l o c k s ) a n dt h en u m b e ro fa l i g n m e n t s ，b u t ( i i l pi n t e r c n a n g e st h en u m b e r so fc r o s s m g sa n dn e s t i n g s t h ec o n c e p t so fk - c r o s s i n ga n dk - n e s t i n gw e r ei n t r o d u c e db yc h e ne ta 1 9 】 u n d e rt h e i rt e r m i n o l o g y , t h e ye s t a b l i s h e da ne l e g a n tb i j e c t i o nb e t w e e np a r t i t i o n s a n dv a c i l l a t i n gt a b l e a u xt os h o wt h a tt h ec r o s s i n gn u m b e r sa n dt h en e s t i n gn u m - b e r sa r ed i s t r i b u t e ds y m m e t r i c a l l yo v e ra l lp a r t i t i o n sa n dm a t c h i n g s i tw a sa l s o s h o w nt h a tt h e r ei sac l o s e dc o n n e c t i o nb e t w e e nt h el a t t i c ew a l k sa n dp a r t i t i o n s ， i n c l u d i n gm a t c h i n g s b a s e do nt h i sc o n n e c t i o n t h e ye n u m e r a t e dt h en u m b e ro f 肛 n o n c r o s s i n gm a t c h i n g s s t i l lf o l l o w i n gt h es a m ec o n n e c t i o n ，b o u s q u e t m 6 1 0 ua n d x i n 【7 】7p r o v e dt h a tt h es e q u e n c ec o u n t i n g3 - n o n c r o s s i n gp a r t i t i o n si sp - r e c u r s i v e ， a n da ne x p l i c i tr e c u r s i o nw a sg i v e n p r o p o s i t i o n1 1 3 ( b o u s q u e t - m 6 1 0 ua n d n o n c r o s s i n gp a n i t i o n si sg i v e nb yg ( 0 ) = 岛 x i n 7 】) t h en u m b e rc 3n ) 0 1 3 一 ( 1 ) = 1 ，a n df o r 礼0 ， 9 nn + 3 ) c 3 ( 几) - 2 ( 5 n 2 + 3 2 n + 4 2 ) c 3 ( n + 1 ) + ( 几十7 ) ( n + 6 ) c 3 ( 扎+ 2 ) = 0 e q u i v a l e n t l y ，t h ea s s o c i a t e dg e n e r a t i n gf u n c t i o nc ( t ) = 竹 oc 3 ( 扎) 护s a t i s f i e s t 2 ( 1 - 9 t ) ( 1 一亡) 嘉c ( 亡) + 鱿( 5 - 2 7 t + 1 8 t 2 ) u d i c ( 亡) + 1 。( 2 - 3 t ) c ( 亡) 一2 。= 。 m o t i v a t e db yt h ee n u m e r a t i v er e s u l t sf o r3 - n o n c r o s s i n gp a r t i t i o n s o n eo fo u r m a i nt a s ki sm a i n l yt oc o u n tt h eb i l a t e r a l l ys y m m e t r i c3 - n o n c r o s s i n gp a r t i t i o n s b yas i m i l a rw a yw er e p r e s e n tt h eg e n e r a t i n gf u n c t i o n sa sc e r t a i nc o n s t a n tt e r m s b u tt h et e c h n i q u e sd i f f e rt h e r e a f t e r i np r o v i n go u rr e s u l t w ed e v e l o pam a p l e p a c k a g ef o rac l a s so ft w od i m e n s i o n a lv a c i l l a t i n gl a t t i c ew a l ke n u m e r a t i o np r o b - l e m s w h i c hp r o d u c e sd f i n i t ee q u a t i o n sf o rg i v e nc o n s t a n tt e r m s t h ep a c k a g ei s a l s oe x t e n d e dt ot h eh e s i t a t i n gc a s e a sa p p l i c a t i o n s w ef i n ds e v e r a li n t e r e s t i n g r e s u l t sf o rs o m es p e c i a lb i l a t e r a l l ys y m m e t r i cp a r t i t i o n s a n o t h e rg o a lo ft h i st h e s i si st oe n u m e r a t et h ek - s t a c ks o r t a b l em a t c h i n g s a n dp a r t i t i o n s t h eo p e r a t i o no fs t a c k - s o r t i n gw a sf i r s ti n t r o d u c e db yk n u t h 2 9 ， s e e ，a l s o ，【l 】s o o na f t e r w a r d sv a r i o u se n u m e r a t i o nr e s u l t sw e r eg i v e nb ym a n y 3 c o m b i n a t o r i s t s t h en u m b e ro fi - s t a c ks o r t a b l ep e r m u t a t i o n so ni n a l s oe q u a l s t h e 礼t hc a t a l a nn u m b e rc k t h en u m b e ro f2 一s t a c ks o r t a b l ep e r m u t a t i o n so nl 州 w a sc o n j e c t u r e db yw e s t 5 0 ，a n df i r s tp r o v e db yz e i l b e r g e rf 5 8 t w ob i j e c t i v e p r o o f sh a v eb e e nf o u n db yd u l u c q ，g i r ea n dw 钨t 1 3 1a n dg o u l d e na n dw e s t 1 8 1 ar e f i n e m e n tw a so b t a i n e db yb o u s q u e t m 6 l o u | 4 1 x u 5 6 】s t u d i e dt h e g e n e r a l i z a t i o n st o1 - s t a c ka n d2 一s t a c ks o r t a b l er - p e r m u t a t i o n si nh i st h e s i sj5 6 t h o u g ht h ee n u m e r a t i o no f 缸s t a c ks o r t a b l ep e r m u t a t i o n si ss t i l lad i f f i c u l t p r o b l e m t h ee n u m e r a t i o no f 缸s t a c ks o r t a b l em a t c h i n g sa n dp a r t i t i o n st u r n e do u t t ob em u c he a s i e r i nf a c t ，k - s t a c ks o r t a b l ep a r t i t i o n sa r es h o w nt ob et h ep a r - t i t i o n sa v o i d i n gc e r t a i np a t t e r n si nt h ee s s e n c e w bf i r s tf i n dac h a r a c t e r i z a t i o n o fk s t a c ks o r t a b l ep a r t i t i o n si nt e r m so fp a t t e r na v o i d a n c e ，a n dt h e nc o n s i d e r 肛s t a c ks o r t a b l en o n c r 0 8 s i n gp a r t i t i o n s ，n o n c r o s s i n gm a t c h i n g sa n dn o n n e s t i n g m a t c h i n g s a n dw ef i n de x p l i c i tf o r m u l a sf o rt h e s en u m b e r sa n df o rt h e i rg e n e r - a t i n gf u n c t i o n sw h i c ha r ea l lr a t i o n a l f o rs m a l lk s ，w ea l s og i v et h eg e n e r a t i n g f u n c t i o n sf o rt h en u m b e ro fk s t a c ks o r t a b l en o n n e s t i n gp a r t i t i o n s u s i n gt h e t r a n s f e rm a t r i xm e t h o d ，w es h o wt h a tt h eg e n e r a t i n gf u n c t i o nf o rt h en u m b e ro f k s t a c ks o r t a b l em a t c h i n g si sr a t i o n a l ，a n df o rs m a l lkw ec a nc o m p u t ei t sg e n - e r a t i n gf u n c t i o n m o r e o v e r ，w ec o n s t r u c tas i m p l eb i j e c t i o nb e t w e e nt h es e t o f p a r t i t i o n so fi n lw i t hn om o r et h a nk + 2 b l o c k sa n dt h es e to fk s t a c ks o r t a b l ep a r - t i t i o n so fm ，w h i c hi n d u c e ss