• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      B型非交錯(cuò)連接分拆的一個(gè)計(jì)數(shù)結(jié)果

      2016-06-25 06:51:58崔漢哲

      崔漢哲

      (上海電機(jī)學(xué)院 數(shù)理教學(xué)部, 上海 201306)

      B型非交錯(cuò)連接分拆的一個(gè)計(jì)數(shù)結(jié)果

      崔漢哲

      (上海電機(jī)學(xué)院 數(shù)理教學(xué)部, 上海 201306)

      摘要連接分拆與非交錯(cuò)連接分拆是組合數(shù)學(xué)中的重要研究對(duì)象。以遞推式的形式計(jì)算集合[±n]上分塊個(gè)數(shù)為給定偶數(shù)2k的所有B型非交錯(cuò)連接分拆的數(shù)目,并得到其雙重生成函數(shù)。

      關(guān)鍵詞B型非交錯(cuò)連接分拆; 遞推式; 雙重生成函數(shù)

      連接分拆(linked partitions)與非交錯(cuò)連接分拆(non-crossing linked partitions)是組合數(shù)學(xué)中的一類重要研究對(duì)象,最早在算子代數(shù)的研究中被發(fā)現(xiàn)。它們?cè)谟?jì)算經(jīng)典非交換概率論中T—變換的形式冪級(jí)數(shù)系數(shù)時(shí)起到了重要作用[1],在非交換概率論的其他方面也有廣泛應(yīng)用[2-6]。與此同時(shí),不同學(xué)者從組合數(shù)學(xué)的多個(gè)角度也探究了它們作為組合對(duì)象的豐富性質(zhì),如計(jì)數(shù)性質(zhì)[7]、代數(shù)結(jié)構(gòu)[8]、與其他組合對(duì)象的聯(lián)系[9-13]等。

      另一方面,文獻(xiàn)[14]中從一類和組合數(shù)學(xué)有密切關(guān)系的重要代數(shù)結(jié)構(gòu)——Coxeter群的分類角度出發(fā),定義了一大類組合對(duì)象的A、B和D型。根據(jù)此觀點(diǎn),文獻(xiàn)[15]中將傳統(tǒng)的A型非交錯(cuò)連接分拆推廣到B型,研究了它們的基本性質(zhì)并得到一些基本的計(jì)數(shù)結(jié)果,即計(jì)算了集合[±n]={1,2,…,n,-1,-2,…,-n}上所有B型非交錯(cuò)連接分拆的個(gè)數(shù)。在此基礎(chǔ)上,本文進(jìn)一步考慮如下問題: 對(duì)于集合[±n]上的B型非交錯(cuò)連接分拆,在分塊個(gè)數(shù)為給定正整數(shù)的情況下,它們的個(gè)數(shù)是多少?記[±n]上所有分塊個(gè)數(shù)為偶數(shù)2k的B型非交錯(cuò)連接分拆的個(gè)數(shù)為a(n,k),本文將給出a(n,k)滿足的遞推式及其雙重生成函數(shù)的具體表達(dá)式。

      1定義與引理

      集合{1,2,…,n,-1,-2,…,-n}在偏序關(guān)系1<2<…

      對(duì)于a∈Z,定義絕對(duì)值映射abs∶Z→N為absa∶=|a|。對(duì)于Z的子集V,記-V為將V中所有元素取相反數(shù)得到的集合,記absV為將V中所有元素取絕對(duì)值得到的集合。若集合π以Z的若干子集為元素,則定義-π為{-V|V∈π},absπ為{absV|V∈π}。

      連接分拆與非交錯(cuò)連接分拆的定義見文獻(xiàn)[8]中的定義2、3,本文不再贅述。[n]的所有連接分拆組成的集合記為L(zhǎng)P(n)。[n]的所有非交錯(cuò)連接分拆組成的集合記為NCL(n)。為敘述完整,本文先給出B型連接分拆和B型非交錯(cuò)連接分拆的定義。

      定義1[15][±n]的一個(gè)B型連接分拆(linked partition of type B)是指以[±n]的若干子集為元素的集合π,且滿足以下條件:

      (1) 這些子集的并為[±n];

      (2) 若V∈π,則-V∈π;

      (3)π中至多有一個(gè)元素W滿足W=-W,此時(shí)稱W為π的零分塊;

      (4) absπ∈LP(n)。

      [±n]的所有B型連接分拆組成的集合記為L(zhǎng)P(B)(n)。對(duì)于π∈LP(B)(n),稱π的元素為塊或分塊。若i,j∈[±n]屬于π中的同一分塊,則記i~πj(當(dāng)上、下文意義明確時(shí),可將下標(biāo)省略)。若π中分塊彼此非交錯(cuò),即不存在以下情況:a,b,c,d∈[±n],a、c屬于π的某一分塊,b、d屬于π的另一分塊,且在[±n]的全序關(guān)系之下有a

      以下B型非交錯(cuò)連接分拆的幾個(gè)簡(jiǎn)單性質(zhì)在定理的證明中會(huì)用到。具體證明見文獻(xiàn)[15]。

      性質(zhì)1若π∈LP(B)(n),p∈[±n],則p在π中為單覆蓋或雙重覆蓋,且

      (1)p在π中為單覆蓋?-p在π中為單覆蓋?absp在absπ中為單覆蓋;

      (2)p在π中為雙重覆蓋?-p在π中為雙重覆蓋?absp在absπ中為雙重覆蓋。

      性質(zhì)2±1,±n在π∈LP(B)(n)中均為單覆蓋。

      性質(zhì)3若π∈NCL(B)(n),則absπ∈NCL(n)。

      對(duì)于π∈NCL(B)(n),其分塊個(gè)數(shù)有兩種情況: ①π包含零分塊,其分塊個(gè)數(shù)為奇數(shù);②π不包含零分塊,其分塊個(gè)數(shù)為偶數(shù)。本文考慮π不包含零分塊的情形。

      以下引理總結(jié)了文獻(xiàn)[7]中關(guān)于NCL(n)相應(yīng)的計(jì)數(shù)結(jié)果,在定理的證明中將會(huì)用到。

      引理1記b(n,k)為NCL(n)中分塊個(gè)數(shù)為k(1≤k≤n)的元素個(gè)數(shù),其雙重生成函數(shù)為

      (1+x-t x)B2(x,t)+

      (x-1)B(x,t)+x t=0

      (1)

      由此可解得

      B(x,t)=

      (2)

      注: 此處的生成函數(shù)B(x,t)與文獻(xiàn)[7]中的定義略有不同,本文省略了常數(shù)項(xiàng),故B(x,t)滿足的方程與最后的解是改寫后的結(jié)果。

      2定理及其證明

      定理1記a(n,k)為NCL(B)(n)中分塊個(gè)數(shù)為2k的元素個(gè)數(shù),其雙重生成函數(shù)為

      (3)

      其中,B(x,t)見引理1。

      證明先推導(dǎo)a(n,k)的遞推式,再由此解出雙重生成函數(shù)。

      根據(jù)定義容易得到如下邊界條件: 當(dāng)k>n時(shí),

      a(n,k)=b(n,k)=0

      a(n,n)=1

      此時(shí)的π∈NCL(B)(n)只有一種可能,即由2n個(gè)單點(diǎn)塊組成。

      為方便本文推導(dǎo),再令

      a(n,0)=b(n,0)=0

      另外,當(dāng)π∈NCL(B)(n)的分塊個(gè)數(shù)為2時(shí),有π={{1,…,j,-j-1,…,-n},{j+1,…,n,-1,…,-j}}(1≤j≤n)。因此,有初值條件a(n,1)=n,類似可得b(n,1)=1,其中,b(n,k)見引理1。

      以下設(shè)n≥3,k≥2,π∈NCL(B)(n)且分塊個(gè)數(shù)為2k(1≤k≤n)。將π中-n所在分塊記為V,考慮在[±n]的全序之下的V中最小元,記為v,以下分6種情況討論。

      (1)v=-n,即{n}與{-n}同時(shí)為單點(diǎn)塊。由性質(zhì)2可見,n與-n在π中均為單覆蓋。于是,將π限制到[±(n-1)]可以是NCL(B)(n-1)中的任意元素,且分塊個(gè)數(shù)為2(k-1)。故此時(shí)π的個(gè)數(shù)為

      K=a(n-1,k-1)

      (4)

      (2)v=n即{n,-n}為π中的零分塊。此時(shí)π中分塊個(gè)數(shù)應(yīng)為奇數(shù),與題設(shè)矛盾。因此,該情況不出現(xiàn),無(wú)需討論。

      K=b(n-1,k)

      (5)

      (4)v=1。此時(shí),π∈{σ∈NCL(B)(n)|1~-n(-1~n)}?NCL(B)(n-1)且分塊個(gè)數(shù)為2k,因此,π的個(gè)數(shù)為

      K=a(n-1,k)

      (6)

      (5)v∈{2,3,…,n-1}。將v記成i,分以下兩種情形討論。

      ①i在π中為單覆蓋。此時(shí)由非交錯(cuò)條件可知

      (7)

      b(i-1,k-u-1)]

      (8)

      綜合上述兩種情形,情況5中π的總個(gè)數(shù)為

      b(i,k-u)-b(i-1,k-u-1)]

      (9)

      (6)v∈{-2,-3,…,1-n}。將v記成i,類似情況5,也分以下2種情形討論。

      ①i在π中為單覆蓋。此時(shí)由非交錯(cuò)條件可知

      (10)

      a(i-1,k-u-1)]

      (11)

      綜合上述兩種情形,情況6中π的總個(gè)數(shù)為

      a(i,k-u)-a(i-1,k-u-1)]

      (12)

      綜合上述6種情況,得到n≥3,k≥2時(shí),a(n,k)的遞推式如下:

      a(n,k)=a(n-1,k-1)+b(n-1,k)+

      [b(i-1,k-u)+b(i,k-u)-

      b(i-1,k-u-1)]+

      a(i,k-u)-a(i-1,k-u-1)]

      (13)

      通過(guò)變換下標(biāo),結(jié)合定理證明的邊界條件和初值條件,可將式(13)等號(hào)右側(cè)第4、5項(xiàng)的雙重和式簡(jiǎn)單變形為

      b(i,k-1-u)

      再用邊界條件,可知

      b(1,k-u)]=b(n-1,k-1)+a(n-1,k-1)

      A(x,t)=(x t+2x2t+…+nxnt+…)+x2t2+

      x t[A(x,t)-xt]+x[B(x,t)-(xt+

      x2t+…+xnt+…)]+x[A(x,t)-

      (x t+2x2t+…+nxnt+…)]+

      2xA(x,t)B(x,t)+2[A(x,t)B(x,t)-

      x2t2]-x t[B(x,t)-x t]-x t[A(x,t)-

      x t]-2xtA(x,t)B(x,t)=

      x t+xA(x,t)+(2+2x-2x t)·

      A(x,t)B(x,t)+xB(x,t)-x tB(x,t)

      最后利用式(2)可解出

      證畢。

      參考文獻(xiàn)

      [1]DYKEMA K J.Multilinear function series and transforms in free probability theory[J].Advances in Mathematics,2007,208(1): 351-407.

      [2]POPA M.Non-crossing linked partitions and multiplication of free random variables[J].arXiv,2008: 0812.2064.

      [3]NICA A.Non-crossing linked partitions,the partial order onNC(n),and the S-transform[J].Proceedings of the American Mathematical Society,2010,138(4): 1273-1285.

      [4]POPA M,Wang J C.On multiplicative conditionally free convolution[J].Transactions of the American Mathematical Society,2011,363(12): 6309-6335.

      [5]ARIZMENDI O,VARGAS C.Product of free random variables and k-divisible non-crossing partitions[J].Electronic Communicatious in Probability,2012,17(5): 489-500.

      [6]POPA M,VINNIKOV V,WANG J C.On the multiplication of operator-valued c-free random variables[J].arXiv,2015: 1509.08853.

      [7]CHEN W Y C,WU S Y J,YAN C H.Linked partitions and linked cycles[J].European Journal of Combinatorics,2008,29(6): 1408-1426.

      [8]崔漢哲.非交錯(cuò)連接分拆的等價(jià)描述[J].上海電機(jī)學(xué)院學(xué)報(bào),2012,15(6): 409-413.

      [9]KASRAOUI A.Ascents and descents in 01-fillings of moon polyominoes[J].European Journal of Combinatorics,2010,31(1): 87-105.

      [10]KIM J S.Front representation of set partitions[J].SIAM Journal on Discrete Mathematics,2009,25(1): 447-461.

      [11]CHEN W Y C,WANG C J.Noncrossing linked partitions and large(3, 2)-Motzkin paths[J].Discrete Mathematics,2012,312(11): 1918-1922.

      [12]CHEN W Y C,LIU L H,WANG C J.Linked partitions and permutation tableaux[J].arXiv,2013: 1305.5357.

      [13]CHEN W Y C,GUO P L,PANG S X M.Vacillating hecke tableaux and linked partitions[J].Mathematische Zeitschrift,2015,281(3): 661-672.

      [14]REINER V.Non-crossing partitions for classical reflection groups[J].Discrete Mathematics,1997,177(1/3): 195-222.

      [15]崔漢哲.B型非交錯(cuò)連接分拆及其計(jì)數(shù)[J].上海電機(jī)學(xué)院學(xué)報(bào),2015,18(1): 42-45.

      Enumerative Result for Non-crossing Linked Partitions of Type B

      CUI Hanzhe

      (Department of Mathematics and Physics, Shanghai Dianji University, Shanghai 201306, China)

      AbstractBoth linked partitions and non-crossing linked partitions are important combinatoric objects. We find a recurrence formula satisfied by the number of all non-crossing linked partitions of type B with block number 2k on [±n]. Its doubly-generating function is also obtained.

      Keywordsnon-crossing linked partition of type B; recurrence formula; doubly-generating function

      收稿日期:2016-02-29

      作者簡(jiǎn)介:崔漢哲(1980-),男,講師,博士,主要研究方向?yàn)榉汉治龊徒M合數(shù)學(xué),E-mail: cuihz@sdju.edu.cn

      文章編號(hào)2095-0020(2016)02-0121-04

      中圖分類號(hào)O 157.1

      文獻(xiàn)標(biāo)識(shí)碼A

      博乐市| 新和县| 平顺县| 新密市| 岱山县| 石棉县| 康定县| 佛坪县| 巴马| 高雄县| 澳门| 福泉市| 遂昌县| 滁州市| 鹤壁市| 安远县| 富蕴县| 延安市| 隆昌县| 诸城市| 平罗县| 高尔夫| 涞水县| 布拖县| 泸溪县| 乐亭县| 施甸县| 中江县| 镇康县| 磴口县| 高雄县| 金乡县| 洪泽县| 武定县| 本溪市| 阜新市| 天镇县| 崇左市| 军事| 松滋市| 龙胜|