趙明澤 李慧蘭

( 山東師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，250358，濟(jì)南 )

1 引 言

對稱群中的置換已經(jīng)被應(yīng)用于多個(gè)研究領(lǐng)域，如計(jì)算機(jī)科學(xué)、財(cái)務(wù)分析和交通模擬等.由于Hopf代數(shù)結(jié)構(gòu)的穩(wěn)定性往往揭示了組合數(shù)學(xué)中深層次的性質(zhì)和聯(lián)系，所以Hopf代數(shù)逐漸成為代數(shù)組合學(xué)的重要研究內(nèi)容之一.自1979年Joni等人[1]在研究置換的離散結(jié)構(gòu)時(shí)發(fā)現(xiàn)這些離散結(jié)構(gòu)具有天然的Hopf代數(shù)結(jié)構(gòu)， 到2003年Aguiar等人[2]提出了組合Hopf代數(shù)的概念，越來越多的組合Hopf代數(shù)被發(fā)現(xiàn)和研究，并且很多Hopf代數(shù)與代數(shù)表示理論、代數(shù)幾何、圖論等研究領(lǐng)域有緊密的聯(lián)系[3，4].

由文獻(xiàn)[5]可知，Hopf代數(shù)結(jié)構(gòu)是由代數(shù)結(jié)構(gòu)和余代數(shù)結(jié)構(gòu)、雙代數(shù)結(jié)構(gòu)逐步推導(dǎo)得來的.Hopf代數(shù)擁有雙代數(shù)結(jié)構(gòu)，且代數(shù)結(jié)構(gòu)與余代數(shù)結(jié)構(gòu)兼容，并滿足對極映射條件.在代數(shù)B中，若存在一個(gè)直和分解B=⊕i≥0Bi，其中Bi中的元素為i階的，且任意p階與q階元素的積是p+q階元素，則B是分級代數(shù).類似地，可以給出分級余代數(shù)的定義.如果一個(gè)環(huán)R上的分級雙代數(shù)H=⊕i≥0Hi滿足H0?R，則稱H為分級連通的.由于任何分級連通的雙代數(shù)都擁有唯一的對極映射，所以分級連通的雙代數(shù)都是Hopf代數(shù).

在組合數(shù)學(xué)中，置換一詞傳統(tǒng)上是指一組有序的排列.1983年，基于 “字母”之上，Lothaire[6]將“字母”按照一定的順序排列并將這些有序列構(gòu)成了一個(gè)集合，之后Lothaire在這個(gè)集合上加上二元運(yùn)算，進(jìn)一步引入了代數(shù)結(jié)構(gòu).設(shè)A是一個(gè)字母表，A中的每個(gè)元素都是一個(gè)字母，由這些字母組成的“單詞”是一個(gè)有限序列，所有的單詞所構(gòu)成的集合記為A*.Lothaire、Eilenberg和Garsia等人[6-8]在集合A*上引入洗牌積運(yùn)算，并證明了這種運(yùn)算滿足交換律和結(jié)合律.2012年，Enjalbert等人[9]在這個(gè)置換集合上提出了擬積運(yùn)算，其中定義的洗牌擬積與切牌余積是兼容的.

設(shè)一個(gè)n階置換是由n個(gè)元素所構(gòu)成的一個(gè)排列.將所有[n]:={1,2,…,n}上的置換所組成的集合稱為n階對稱群，記為Sn.定義集合S∶=∪n≥0Sn，并賦予了S0={ε}，其中ε是空置換.2002年，通過研究非交換元素上對稱函數(shù)的Hopf代數(shù)結(jié)構(gòu)，Aguiar等人[10,11]分析了置換上的Malvenuto-Reutenauer Hopf代數(shù)結(jié)構(gòu)，并給出了在這個(gè)Hopf代數(shù)結(jié)構(gòu)上所存在的對極映射，但其中定義出的洗牌積運(yùn)算計(jì)數(shù)方式不滿足交換律.2018年，Bergeron等人[12]提出了“全局下降點(diǎn)”的概念.并以此為基礎(chǔ)，在置換集合S上重新定義了洗牌積運(yùn)算的計(jì)數(shù)方式，使其滿足了交換性且(kS，ш)是一個(gè)代數(shù)結(jié)構(gòu).進(jìn)一步，Bergeron等人又提出在這個(gè)代數(shù)結(jié)構(gòu)中洗牌積ш和切牌余積Δ是兼容的，即(kS，ш，Δ)是一個(gè)雙代數(shù).本文證明了置換集合(kS，ш，Δ)具有雙代數(shù)結(jié)構(gòu).通過對極映射的定義，找出了(kS，ш，Δ)上的對極映射公式并給出了證明.

2 Hopf代數(shù)

首先回顧一下關(guān)于Hopf代數(shù)的相關(guān)知識，詳細(xì)的結(jié)果可參看文獻(xiàn)[5].

設(shè)交換環(huán)R上的模B存在R線性映射η和μ:

η:B?RB→B(乘)，

μ:R→B，

且映射滿足圖1所示的交換圖表，則η是乘積映射，μ是單位映射，模B是一個(gè)R代數(shù)，記為(B，η，μ).為了記號簡潔，將η(g，f)記為gf.

圖1 η和μ交換圖表

設(shè)交換環(huán)R上的模B存在R線性映射Δ和ν:

Δ:B→B?RB(余乘)，

ν:B→R，

且映射滿足圖2所示的交換圖表，則Δ是余乘映射，ν是余單位映射，模B是一個(gè)R余代數(shù)，記為(B，Δ，ν).

圖2 Δ和ν交換圖表

若(B，η，μ，Δ，ν)既是R代數(shù)又是R余代數(shù)，且B滿足下列互相等價(jià)的兼容條件之一：

1)η和μ滿足余代數(shù)同態(tài)，

2)Δ和v滿足代數(shù)同態(tài)，

則B是一個(gè)雙代數(shù).

設(shè)B是一個(gè)雙代數(shù)，若B存在一個(gè)R線性映射S:B→B，使得對任意的b∈B滿足

(1)

圖3 對極映射

擁有對極映射的雙代數(shù)是Hopf代數(shù).

3 置換上的Hopf代數(shù)

設(shè)kS∶=⊕n≥0kSn是一個(gè)分級的向量空間，其中kSn是數(shù)域k上由Sn張成的向量空間.

設(shè)ω是在Sn中的一個(gè)置換，其階數(shù)為n.在這個(gè)置換上，第一個(gè)數(shù)字前面的位置記為位置0、第i個(gè)數(shù)字和第i+1個(gè)數(shù)字之間的位置記為位置i、最后一個(gè)數(shù)字后面的位置記為位置n，這些位置被稱為置換ω上的“間隙”[12].

對于n階置換ω上的間隙γ，若滿足運(yùn)算ω([γ])=[n][n-γ]，則稱此處的間隙為“全局下降點(diǎn)”，其中0和n一直都是全局下降點(diǎn).沒有其他全局下降點(diǎn)的置換稱為原子置換.因此，每一個(gè)置換ω都擁有一個(gè)唯一的分解式ω=ω1·ω2·…·ωl，其中ω1，…，ωl都是原子置換.S中每一個(gè)置換的長度都是以其含有的原子置換的個(gè)數(shù)來定義的，即置換ω的長度為|ω|=l.

例1設(shè)置換ω=7564231∈S7,求它的全局下降點(diǎn)及分解式.

解全局下降點(diǎn)有: 0，1，3，4，6，7，分解式為ω=7·56·4·23·1.

每一個(gè)置換ω都存在唯一的標(biāo)準(zhǔn)式，記為st(ω).例如st(756)=312.所以，之后記例1中ω分解式的標(biāo)準(zhǔn)式為1·12·1·12·1，重新計(jì)數(shù)時(shí)，從右到左計(jì)數(shù).

設(shè)置換α∈Sm和β∈Sn，定義置換α·β∈Sm+n為

例2已知α=132∈S3，β=2413∈S4，計(jì)算α·β.

解α·β=132·2413=5762413.

顯然α·β在間隙m處是一個(gè)全局下降點(diǎn).相反地，給定一個(gè)置換ω∈Sm+n，且在間隙m處是一個(gè)全局下降點(diǎn)，則存在唯一的一組置換α∈Sm和β∈Sn使得ω=α·β.

定義1設(shè)置換ω∈S，且其唯一的標(biāo)準(zhǔn)分解式為ω=ω1·ω2·…·ωl，其中ω1，...，ωl都是原子置換，則切牌余積為

(2)

例3求置換7564231在進(jìn)行切牌余積運(yùn)算后的結(jié)果.

解Δ(7564231)=?1·12·1·12·1+1?(12·1·12·1)+(1·12)?(1·12·1)

+(1·12·1)?(12·1)+(1·12·1·12)?1+1·12·1·12·1?

定義2在S上定義洗牌積ш，對于任意的π、ω∈S，定義πшε:=π，εшω:=ω,

(μ·ν)ш(σ·τ):=μ·(νшω)+σ·(πшτ)，

(3)

其中π=μ·β，ω=σ·τ，μ和σ是非平凡的原子置換.

置換中的洗牌積ш作用在置換的標(biāo)準(zhǔn)分解式上，它是一個(gè)標(biāo)準(zhǔn)的交換積.

例4已知π=312=1·12∈S3，ω=4213=1·213∈S4，長度都是2，求πшω的結(jié)果.

解πшω=312·4213

=1·12·1·213+1·1·12·213+1·1·213·12

+1·1·12·213+1·1·213·12+1·213·1·12

=7564213+7645213+7643512+7645213+7643512+7546312.

對于任意的p階置換集合Sp和q階置換集合Sq，通過定義1和定義2可得ш(kSp?kSq)=kSp+q，μ(k)=kS0.所以，代數(shù)(kS，ш，μ)是分級的.同時(shí)，(kS，Δ，ν)是分級余代數(shù).

4 主要結(jié)果

定理1(kS，ш，Δ)是一個(gè)Hopf代數(shù).

因?yàn)榉旨夁B通的雙代數(shù)都是Hopf代數(shù).已有kS0?k，所以只需要證明(kS，ш，Δ)是雙代數(shù)，即洗牌積ш與切牌余積Δ是兼容的.

引理1洗牌積ш與切牌余積Δ是兼容的，即

Δ(πшω)=Δ(π)шΔ(ω)，

(4)

其中π=π1·…·πi·…·πs，ω=ω1·…·ωj·…·ωt.

在證明這個(gè)引理之前，可以計(jì)算并觀察下面的例題.

例5已知π=312=1·12，ω=231=12·1∈S3，長度都是2，求Δ(312ш231)的結(jié)果.

解

Δ(312ш231)

=Δ(1·12·12·1+1·12·12·1+1·12·1·12+12·1·12·1+12·1·1·12+12·1·1·12)

從上面對Δ(312ш231)的計(jì)算過程可以發(fā)現(xiàn)，其中的每個(gè)結(jié)果項(xiàng)都將被符號″?″分為左邊和右邊.所以，從每個(gè)項(xiàng)的特點(diǎn)出發(fā)，可以根據(jù)在″?″之前的312和231中原子置換的數(shù)目來計(jì)算.

因此，在計(jì)算Δ(πшω)時(shí)，可以得到其每一個(gè)結(jié)果項(xiàng)也都是被符號″?″分為左右兩邊的.所以，置換π=π1·…·πi·…·πs和ω=ω1·…·ωj·…·ωt在經(jīng)過洗牌積運(yùn)算后，可以根據(jù)其每一個(gè)結(jié)果項(xiàng)中在符號″?″前面的原子置換數(shù)目來填寫Δ(πшω)的結(jié)果.也就是說，在符號″?″前面的那些原子置換是由″i″和″j″的值決定的.

接下來證明引理1.這里不妨假設(shè)m≤n.

證當(dāng)Δ(πшω)的所有結(jié)果項(xiàng)中″?″的左邊有″π″中原子置換的個(gè)數(shù)為i=0，1，2，...，s，且有″ω″中原子置換的個(gè)數(shù)為j=l時(shí)，記符合要求的結(jié)果項(xiàng)之和為Δ(πшω)|j=l，其中0≤l≤t.

當(dāng)i=0，1，2，…，s，j=0時(shí),這個(gè)條件要求結(jié)果項(xiàng)中″?″的左邊不存在任何ω中的原子置換″ωj″.那么符合要求的結(jié)果項(xiàng)之和為

+(π1·π2ш·)?(π3·…·πsшω)+…+(π1·…·πsш)?(шω)

:=Δ(πшω)|j=0.

當(dāng)i=0，1，2，…，s，j=k(0≤k≤t)時(shí)，符合要求的結(jié)果項(xiàng)之和為

(шω1·…·ωk)?(πшωk+1·…·ωt)

+(π1шω1·…·ωk)?(π2·…·πsшωk+1·…·ωt)

+···+(π1·…·πsшω1·…·ωk)?(·шωk+1·…·ωt)

:=Δ(πшω)|j=k

所以，Δ(πшω)的所有結(jié)果項(xiàng)中″?″的左邊有″π″中原子置換的個(gè)數(shù)為i=0，1，2，...，s，有″ω″中原子置換的個(gè)數(shù)為j=k(0≤k≤t)，結(jié)果項(xiàng)之和的通項(xiàng)公式為

Δ(πшω)的所有結(jié)果項(xiàng)中″?″的左邊有″π″中原子置換的個(gè)數(shù)為i=0，1，2，...，s，且有″ω″中原子置換的個(gè)數(shù)為j=0，1，2，...，t，這也就是說將j=0，1，2，...，t時(shí)的t+1個(gè)結(jié)果項(xiàng)之和的通項(xiàng)公式相加可得

Δ(πшω)

=Δ(πшω)|j=0+Δ(πшω)|j=1+Δ(πшω)|j=2+…+Δ(πшω)|j=k+…+Δ(πшω)|j=t

通過觀察可以發(fā)現(xiàn)上面ш左邊括號里的式子都是一樣的，提取公因式可得

Δ(πшω)

+(ω1·ω2?ω3·…·ωt)+…+(ω1·…·ωk?ωk+1·…·ωt)+…+(ω1·…·ωt?)]

=Δ(π1·…·πs)шΔ(ω1·…·ωt)

=Δ(π)шΔ(ω).

因此，可以得出在置換中洗牌積ш與切牌余積Δ是兼容的.所以，(kS，ш，Δ)是一個(gè)雙代數(shù).

引理1證明了(kS，ш，Δ)是一個(gè)雙代數(shù); 又因?yàn)樗欠旨夁B通的，所以(kS，ш，Δ)是一個(gè)Hopf代數(shù)，即定理1得證.

例6已知π=312=1·12，ω=231=12·1∈S3，長度都是2，證明Δ(πшω)=Δ(π)шΔ(ω).

證Δ(π)шΔ(ω)=Δ(1·12)шΔ(12·1)

=(?1·12+1?12+1·12?)ш(?12·1+12?1+12·1?)

=(?1·12)ш(?12·1)+(?1·12)ш(12?1)+(?1·12)ш(12·1?)

+(1?12)ш(?12·1)+(1?12)ш(12?1)+(1?12)ш(12·1?)

+(1·12?)ш(?12·1)+(1·12?)ш(12?1)+(1·12?)ш(12·1?).

再根據(jù)例5可以得出證明.

(kS，ш，Δ)是一個(gè)Hopf代數(shù)，那么它就存在一個(gè)對極映射，下面的引理2給出了它的對極映射公式及相關(guān)證明.

引理2(kS，ш，Δ)擁有唯一的對極映射S，對于任意長度為l的置換π=π1·π2·…·πl(wèi)有

S(π)=(-1)lπl(wèi)·πl(wèi)-1·…·π2·π1.

(5)

證易知對于Hopf代數(shù)(kS，ш，Δ)中的任意元素都滿足公式(1).

由于公式(1)中左右等號兩邊是對稱的，所以這里只需證明公式的右邊.

首先，根據(jù)公式(1)對置換π進(jìn)行切牌余積運(yùn)算

其次，根據(jù)公式(1) 對置換π進(jìn)行(S?1)°Δ(π)運(yùn)算,可得

最后，對(S?1)°Δ(π)進(jìn)行洗牌積ш運(yùn)算，可得

ш°(S?1)°Δ(π)

=шπ1·π2·…·πl(wèi)+(-1)1(π1)ш(π2·…·πl(wèi))

+(-1)2(π2·π1)ш(π3·…·πl(wèi))+…+(-1)n(πl(wèi)·πn-1·…·π2·π1)ш

=π1·π2·…·πl(wèi)-π1·π2·…·πl(wèi)-π2·(π1шπ3·…·πl(wèi))

+π2·(π1шπ3·…·πl(wèi))+π3·(π2·π1шπ4·…·πl(wèi))

-π3·(π2·π1шπ4·…·πl(wèi))-π4·(π3·π2·π1шπ5·…·πl(wèi))

+…+(-1)l-1πl(wèi)-1·(πl(wèi)-2·…·π1шπl(wèi))+(-1)l-1πl(wèi)·(πl(wèi)-1·…·π2·π1ш)

+(-1)lπl(wèi)·πl(wèi)-1·…·π2·π1ш

=0.

這就證明了ш°(S?1)°Δ(π)=0，從而對極映射S對于公式(1)等號右邊是成立的.同理，可以證明等號左邊也是成立的，即ш°(1?S)°Δ(π)=0，引理2得證.