999精品在线视频,手机成人午夜在线视频,久久不卡国产精品无码,中日无码在线观看,成人av手机在线观看,日韩精品亚洲一区中文字幕,亚洲av无码人妻,四虎国产在线观看 ?

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

2017-04-13 03:50:32崔漢哲
關(guān)鍵詞:定義

崔漢哲

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

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

崔漢哲

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

連接分拆與非交錯(cuò)連接分拆是組合數(shù)學(xué)中的一類(lèi)重要研究對(duì)象。對(duì)于[±n]的所有B型非交錯(cuò)連接分拆組成的集合NCL(B)(n),分別計(jì)算其中包含或不包含零分塊的元素個(gè)數(shù)。找到其滿(mǎn)足的遞推關(guān)系,并得出生成函數(shù)的表達(dá)式。

B型非交錯(cuò)連接分拆; 零分塊; 遞推式; 生成函數(shù)

組合數(shù)學(xué)中,連接分拆(linked partitions)與非交錯(cuò)連接分拆(noncrossing linked partitions)作為一類(lèi)重要的內(nèi)容被研究。它們最早由Dykema[1]在經(jīng)典非交換概率論的T—變換研究時(shí)引入,之后被廣泛應(yīng)用于非交換概率論的其他方面以及算子代數(shù)的研究中[2-7]。同時(shí),不同學(xué)者從多角度研究了連接分拆與非交錯(cuò)連接分拆作為組合對(duì)象的豐富性質(zhì),如代數(shù)結(jié)構(gòu)[8]、計(jì)數(shù)性質(zhì)、與其他組合對(duì)象的聯(lián)系[10-13]等。

另一方面,文獻(xiàn)[14]中從與組合數(shù)學(xué)有密切聯(lián)系的Coxeter群的分類(lèi)角度出發(fā),定義了A、B和D型組合對(duì)象。在此基礎(chǔ)上,文獻(xiàn)[15]中定義了B型非交錯(cuò)連接分拆,研究了它們的基本性質(zhì),并與文獻(xiàn)[16]共同得到了一些基本的計(jì)數(shù)結(jié)果。具體而言,文獻(xiàn)[15]中計(jì)算了集合[±n]={1,2,…,n,-1,-2,…,-n}的所有B型非交錯(cuò)連接分拆的個(gè)數(shù)。本文進(jìn)一步計(jì)算集合[±n]的B型非交錯(cuò)連接分拆中包含或不包含零分塊的元素個(gè)數(shù)。

1 定義與引理

在集合{1,2,…,n,-1,-2,…,-n}上定義全序關(guān)系1<2<…

對(duì)于a∈Z,定義絕對(duì)值映射abs∶Z→N為

對(duì)于Z的子集V,定義

若集合π以Z的若干子集為元素,則類(lèi)似定義

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

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

(1) absπ∈LP(n);

(2) 由V∈π可得-V∈π;

(3)π中至多有一個(gè)元素W滿(mǎn)足W=-W。此時(shí),稱(chēng)W為π的零分塊。

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

π|S={V∩S|V∈π,V∩S≠?}

稱(chēng)其為將π限制到S后所得的連接分拆。最后,將NCL(B)(n)中所有包含零分塊的元素組成的集合記為NCLZ(B)(n)。本文目的為計(jì)算|NCLZ(B)(n)|和|NCL(B)(n)NCLZ(B)(n)|。

以下B型連接分拆與非交錯(cuò)連接分拆的幾個(gè)簡(jiǎn)單性質(zhì)見(jiàn)文獻(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)。

下文的2個(gè)引理總結(jié)了文獻(xiàn)[9]、[15]中關(guān)于NCL(n)與NCL(B)(n)的一些計(jì)數(shù)結(jié)果。

則S(x)滿(mǎn)足方程

S2(x)+(x-1)S(x)+x=0

(1)

(2)

sn滿(mǎn)足的遞推關(guān)系為s1=1;當(dāng)n≥2時(shí),

sn=sn-1+s1sn-1+s2sn-2+…+sn-1s1

(3)

注:本文中的生成函數(shù)與文獻(xiàn)[9]中稍有不同,略去了常數(shù)項(xiàng)1。因此,式(1)以及方程的解是改寫(xiě)后的結(jié)果。下同。

引理2 設(shè)n∈N,記

(4)

式中,fn滿(mǎn)足的遞推關(guān)系為f1=2,f2=6;當(dāng)n≥3時(shí),

(5)

2 定理、推論及其證明

定理1 設(shè)n∈N,記

(6)

式中,hn滿(mǎn)足的遞推關(guān)系:h1=1,h2=3;當(dāng)n≥3時(shí),

(7)

證明 由NCLZ(B)(1)={{{1,-1}}}可知h1=1。

由NCLZ(B)(2)={{{1,-1},{2},{-2}},{{1},{-1}{2,-2}},{{1,2,-1,-2}}}可知h2=3。

設(shè)π∈NCLZ(B)(n)且n≥3。將元素-n所在分塊記為V,將在[±n]的全序之下的V中最小元記為v。分以下6種情況討論。

(1)v=-n。此時(shí),V={n}且{n}與{-n}同時(shí)為單點(diǎn)塊。由性質(zhì)2可知,n與-n在π中均為單覆蓋。于是,π|[±(n-1)]∈NCLZ(B)(n-1),且π|[±(n-1)]可以是NCLZ(B)(n-1)中的任意元素,故π的個(gè)數(shù)為hn-1。

(2)v=n。此時(shí)V={n,-n}恰為π中的零分塊。由非交錯(cuò)條件可知,π|[n-1]∈NCL(n-1),且π|[n-1]可以是NCL(n-1)中的任意元素,π的個(gè)數(shù)為sn-1。

(3)v=-1。此時(shí),n∈-V且V(-V)不為零分塊。由非交錯(cuò)條件可知,此時(shí)π中沒(méi)有零分塊,即π?NCLZ(B)(n)。由題設(shè),此情況可略去不計(jì)。

(4)v=1。此時(shí),π|[±(n-1)]∈NCLZ(B)(n-1),且π|[±(n-1)]可以是NCLZ(B)(n-1)中的任意元素,故π的個(gè)數(shù)為hn-1。

(5)v∈{2,3,…,n-1}。此時(shí),由非交錯(cuò)條件可知,π|{1,2,…,v}為NCL(v)中任意元素,而π|{v,v+1,…,n,-v,-v-1,…,-n}為{v,v+1,…,n,-v,-v-1,…,-n}上的一個(gè)包含零分塊的B型非交錯(cuò)連接分拆,且滿(mǎn)足v~-n(-v~n),于是進(jìn)一步有

π|{v,v+1,…,n -1,- v,- v -1,…,-(n-1)}∈NCLZ(B)(n-v)

且可以是NCLZ(B)(n-v)中的任意元素。

反之,對(duì)于{1,2,…,v}的一個(gè)非交錯(cuò)連接分拆π1,以及{v,v+1,…,n,-v,-v-1,…,-n}上的一個(gè)包含零分塊的B型非交錯(cuò)連接分拆π2滿(mǎn)足v~π2(-n)(-v~π2n),可以相應(yīng)得到

π∈NCLZ(B)(n)

且-n所在分塊在[±n]的全序之下的最小元為v。具體構(gòu)造如下:

(8)

由此可知,π的個(gè)數(shù)為s2hn-2+s3hn-3+…+sn-1h1。

(6)v∈{-2,-3,…,1-n}。此時(shí),-v,n∈-V且V(-V)不為零分塊。由非交錯(cuò)條件可知,

π|{1,2,…,-v,-1,-2,…,v}∈NCLZ(B)(-v)

{σ∈NCLZ(B)(-v)|v~σ(-v)}

且可以是該集合中的任意元素。而π|{v,v-1,…,-n}為{v,v-1,…,-n}的非交錯(cuò)連接分拆且滿(mǎn)足v~-n,因此,π|{v,v-1,…,-n∈NCL(n+v)。

反之,給定

NCLZ(B)(-v){σ∈NCLZ(B)(-v)|v~σ(-v)}

中元素與集合{v,…,-n}上滿(mǎn)足v~-n的非交錯(cuò)連接分拆,類(lèi)似情況(5)中的構(gòu)造,可以得到滿(mǎn)足情況(6)條件的[±n]上包含零分塊的B型非交錯(cuò)分拆。而由對(duì)稱(chēng)性、非交錯(cuò)條件以及映射abs,類(lèi)似情況(2)中的討論,可知集合

{σ∈NCLZ(B)(-v)|v~σ(-v)}=

{σ∈NCL(B)(-v)|v~σ(-v)}?NCL(-v)

由此可得情況(6)中π的個(gè)數(shù)為

sn-2(h2-s2)+sn-3(h3-s3)+…+s1(hn-1-sn-1)

綜合上述6種情況,可知n≥3時(shí),fn的遞推式如下:

hn=2hn-1+sn-1+(s2hn-2+s3hn-3+…+sn-1h1)+sn-2(h2-s2)+sn-3(h3-s3)+ …+s1(hn-1-sn-1)

(9)

結(jié)合s1=1與s2=3,將式(9)改寫(xiě)為

hn=hn-1+sn-1+2(s1hn-1+s2hn-2+…+sn-1h1)-(s1sn-1+s2sn-2+…+sn-1s1)

(10)

再由生成函數(shù)的定義可將式(10)改寫(xiě)為

(11)

最后,將引理1中S(x)的已知結(jié)果代入式(11),整理后即得

(12)

證畢。

由定理1以及引理2可直接計(jì)算NCL(B)(n)中不包含零分塊的元素個(gè)數(shù)。

推論1 設(shè)n∈N,記

(13)

式中,gn滿(mǎn)足的遞推關(guān)系為g1=1,g2=3;當(dāng)n≥3時(shí),

(14)

注記 用定理1證明中推導(dǎo)H(x)的方法也可以直接得到推論1的結(jié)果。g1=1、g2=3易得,然后類(lèi)似定理1的證明,分6種情況討論。下文只寫(xiě)出每種情況對(duì)應(yīng)的元素個(gè)數(shù)K,具體過(guò)程略去。

(1)K=gn-1;

(2)K=0;

(3)K=sn-1;

(4)K=gn-1;

(5)K=s2gn-2+s3gn-3+…+sn-1g1;

(6)K=g2sn-2+g3sn-3+…+gn-1s1。

由此,同樣可得gn滿(mǎn)足的遞推關(guān)系以及G(x)的表達(dá)式。

[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 Communication in Probability, 2012, 17(5):489-500.

[6] POPA M. A Fock space model for addition and multiplication of c-free random variables [J].Proceed-ings of the American Mathematical Society, 2014, 142(6): 2001-2012.

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

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

[9] 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.

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

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

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

[13] YAN S H F, ZHOU R. Refined enumeration of corners in tree-like tableaux[J]. arXiv,2017:1701.07216.

[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.

[16] 崔漢哲. B型非交錯(cuò)連接分拆的一個(gè)計(jì)數(shù)結(jié)果 [J]. 上海電機(jī)學(xué)院學(xué)報(bào),2016,19(2):121-124.

[17] STANLEY R P. Enumerative combinatorics[J]. Cambridge Studies in Advanced Mathematics. 1999,62(2):178,291.

[18] SLOANE N J. The on-line encyclopedia of integer sequences (OEIS) [EB/OL]. [2016-08-26].http://oeis.org/search?q=A006138&language=english &go=Search.

Two Enumerative Results for Noncrossing Linked Partitions of Type B

CUIHanzhe

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

Linked partitions and non-crossing linked partitions are both important combinatoric objects. We calculate the cardinal numbers of the sets that consist of non-crossing linked partitions of type B on [±n] with or without zero blocks. Their recurrence formulas and generating functions are obtained.

noncrossing linked partitions of type B; zero block; recurrence formula; generating functions

2016 -12 -25

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

2095 - 0020(2017)01 -0052 - 04

O 157.1

A

猜你喜歡
定義
以愛(ài)之名,定義成長(zhǎng)
活用定義巧解統(tǒng)計(jì)概率解答題
例談橢圓的定義及其應(yīng)用
題在書(shū)外 根在書(shū)中——圓錐曲線第三定義在教材和高考中的滲透
永遠(yuǎn)不要用“起點(diǎn)”定義自己
海峽姐妹(2020年9期)2021-01-04 01:35:44
嚴(yán)昊:不定義終點(diǎn) 一直在路上
定義“風(fēng)格”
成功的定義
山東青年(2016年1期)2016-02-28 14:25:25
有壹手——重新定義快修連鎖
修辭學(xué)的重大定義
主站蜘蛛池模板: 另类综合视频| 视频二区欧美| 国产尤物视频在线| 国产精品自拍露脸视频| 在线免费观看AV| 东京热高清无码精品| 亚洲精品成人福利在线电影| 美女一区二区在线观看| 谁有在线观看日韩亚洲最新视频| 自慰网址在线观看| 人妻丝袜无码视频| 精品国产成人a在线观看| 亚洲视频免| 四虎永久在线精品影院| 久久人体视频| 日韩成人午夜| 日韩资源站| www.亚洲一区二区三区| 伦伦影院精品一区| 全色黄大色大片免费久久老太| 免费aa毛片| 97人妻精品专区久久久久| 国产主播在线一区| 久久中文字幕av不卡一区二区| 丰满人妻中出白浆| 国产精品网址在线观看你懂的| 亚洲国产精品成人久久综合影院| 99热精品久久| 色悠久久综合| 黄色网在线| 亚洲无码视频图片| 国产成人1024精品| 国产91精选在线观看| 97视频在线精品国自产拍| 欧美成人aⅴ| 亚洲精品无码高潮喷水A| 综合色88| 尤物特级无码毛片免费| 91精品情国产情侣高潮对白蜜| 亚洲国产成人精品一二区| 日韩精品欧美国产在线| 欧美三级日韩三级| 婷婷午夜天| 男女性色大片免费网站| 2022国产91精品久久久久久| 国产成人精品一区二区免费看京| 成人福利在线免费观看| 国产在线拍偷自揄拍精品| 1769国产精品免费视频| 亚洲综合狠狠| 深夜福利视频一区二区| 亚洲高清无码久久久| 国产乱子伦手机在线| 精品福利一区二区免费视频| 伊人激情久久综合中文字幕| 呦女精品网站| 伊人色综合久久天天| 婷婷99视频精品全部在线观看| 女同国产精品一区二区| 色老头综合网| 四虎永久免费在线| 欧美精品一区在线看| 在线免费看片a| 国产成人午夜福利免费无码r| 欧美人人干| 又黄又爽视频好爽视频| 呦系列视频一区二区三区| 在线观看视频99| 无码免费的亚洲视频| 99热这里只有免费国产精品| 久久视精品| 日本三级欧美三级| 四虎国产永久在线观看| 精品视频一区二区三区在线播| 久久久噜噜噜| 国产乱子伦视频在线播放| 国产欧美日韩18| 精品无码国产自产野外拍在线| 日韩欧美综合在线制服| 奇米影视狠狠精品7777| 欧美a级完整在线观看| 乱人伦中文视频在线观看免费|