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

B型非交錯連接分拆的兩個計數結果

2017-04-13 03:50:32崔漢哲
上海電機學院學報 2017年1期
關鍵詞:定義

崔漢哲

(上海電機學院 數理教學部,上海 201306)

B型非交錯連接分拆的兩個計數結果

崔漢哲

(上海電機學院 數理教學部,上海 201306)

連接分拆與非交錯連接分拆是組合數學中的一類重要研究對象。對于[±n]的所有B型非交錯連接分拆組成的集合NCL(B)(n),分別計算其中包含或不包含零分塊的元素個數。找到其滿足的遞推關系,并得出生成函數的表達式。

B型非交錯連接分拆; 零分塊; 遞推式; 生成函數

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

另一方面,文獻[14]中從與組合數學有密切聯系的Coxeter群的分類角度出發,定義了A、B和D型組合對象。在此基礎上,文獻[15]中定義了B型非交錯連接分拆,研究了它們的基本性質,并與文獻[16]共同得到了一些基本的計數結果。具體而言,文獻[15]中計算了集合[±n]={1,2,…,n,-1,-2,…,-n}的所有B型非交錯連接分拆的個數。本文進一步計算集合[±n]的B型非交錯連接分拆中包含或不包含零分塊的元素個數。

1 定義與引理

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

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

對于Z的子集V,定義

若集合π以Z的若干子集為元素,則類似定義

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

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

(1) absπ∈LP(n);

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

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

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

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

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

以下B型連接分拆與非交錯連接分拆的幾個簡單性質見文獻[15],在本文的證明中將要用到。

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

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

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

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

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

下文的2個引理總結了文獻[9]、[15]中關于NCL(n)與NCL(B)(n)的一些計數結果。

則S(x)滿足方程

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

(1)

(2)

sn滿足的遞推關系為s1=1;當n≥2時,

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

(3)

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

引理2 設n∈N,記

(4)

式中,fn滿足的遞推關系為f1=2,f2=6;當n≥3時,

(5)

2 定理、推論及其證明

定理1 設n∈N,記

(6)

式中,hn滿足的遞推關系:h1=1,h2=3;當n≥3時,

(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。

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

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

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

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

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

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

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

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

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

π∈NCLZ(B)(n)

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

(8)

由此可知,π的個數為s2hn-2+s3hn-3+…+sn-1h1。

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

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

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

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

反之,給定

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

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

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

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

由此可得情況(6)中π的個數為

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

綜合上述6種情況,可知n≥3時,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)

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

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

(10)

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

(11)

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

(12)

證畢。

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

推論1 設n∈N,記

(13)

式中,gn滿足的遞推關系為g1=1,g2=3;當n≥3時,

(14)

注記 用定理1證明中推導H(x)的方法也可以直接得到推論1的結果。g1=1、g2=3易得,然后類似定理1的證明,分6種情況討論。下文只寫出每種情況對應的元素個數K,具體過程略去。

(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滿足的遞推關系以及G(x)的表達式。

[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] 崔漢哲. 非交錯連接分拆的等價描述 [J].上海電機學院學報,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型非交錯連接分拆及其計數 [J]. 上海電機學院學報,2015,18(1):42-45.

[16] 崔漢哲. B型非交錯連接分拆的一個計數結果 [J]. 上海電機學院學報,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-), 男,講師,博士,主要研究方向為泛函分析和組合數學,E-mail:cuihz@sdju.edu.cn

2095 - 0020(2017)01 -0052 - 04

O 157.1

A

猜你喜歡
定義
以愛之名,定義成長
活用定義巧解統計概率解答題
例談橢圓的定義及其應用
題在書外 根在書中——圓錐曲線第三定義在教材和高考中的滲透
永遠不要用“起點”定義自己
海峽姐妹(2020年9期)2021-01-04 01:35:44
嚴昊:不定義終點 一直在路上
華人時刊(2020年13期)2020-09-25 08:21:32
定義“風格”
成功的定義
山東青年(2016年1期)2016-02-28 14:25:25
有壹手——重新定義快修連鎖
修辭學的重大定義
當代修辭學(2014年3期)2014-01-21 02:30:44
主站蜘蛛池模板: 国产精品亚洲αv天堂无码| 国产精品任我爽爆在线播放6080 | 真实国产乱子伦视频 | 亚洲午夜天堂| 任我操在线视频| 在线免费不卡视频| 婷婷六月综合网| 亚洲视频影院| 国产自在线播放| 亚洲一区国色天香| 亚洲精品久综合蜜| 日韩黄色在线| 色久综合在线| 亚洲一区国色天香| 久久久久久久久18禁秘| h网站在线播放| 日韩无码真实干出血视频| 成人午夜久久| 欧亚日韩Av| 日韩一区精品视频一区二区| 亚洲无码一区在线观看| 亚洲第一区在线| 午夜性爽视频男人的天堂| 国产美女视频黄a视频全免费网站| 国产午夜福利亚洲第一| 欧美日韩在线亚洲国产人| 婷婷激情亚洲| 亚洲欧美另类久久久精品播放的| 亚洲精品va| 欧美一区二区三区国产精品| 久久久久亚洲Av片无码观看| 91视频精品| 国产91九色在线播放| 国产交换配偶在线视频| 亚洲美女一区| 天天操天天噜| 国产白浆一区二区三区视频在线| a毛片在线播放| 免费中文字幕一级毛片| 国产精品美女免费视频大全| 色综合天天操| 久久精品91麻豆| 国产本道久久一区二区三区| 亚洲色图欧美在线| 久久精品视频亚洲| 一级毛片免费观看不卡视频| 免费a级毛片18以上观看精品| 精品人妻一区二区三区蜜桃AⅤ| 日韩欧美中文字幕在线韩免费| 国产精品人成在线播放| 永久免费无码日韩视频| 日韩专区欧美| 国产一区二区三区在线观看免费| 久草视频中文| 黄色在线不卡| 二级特黄绝大片免费视频大片| 国产精品第一区在线观看| 日本一区二区三区精品视频| 宅男噜噜噜66国产在线观看| 在线播放91| 人妻丰满熟妇啪啪| 国产清纯在线一区二区WWW| 成人在线亚洲| 欧美精品啪啪| 在线国产毛片| 波多野结衣亚洲一区| 呦女精品网站| 色噜噜狠狠色综合网图区| 国产成人精品一区二区秒拍1o| 永久免费精品视频| 国产成人精彩在线视频50| 看看一级毛片| 日韩精品无码免费专网站| 日韩A∨精品日韩精品无码| 日韩高清一区 | 久久久精品无码一二三区| 亚洲一区二区精品无码久久久| 美女免费黄网站| 色视频国产| 人人91人人澡人人妻人人爽 | 91精品专区| 日本五区在线不卡精品|