與群作用于集合的等價(jià)類計(jì)數(shù)有關(guān)的組合恒等式

唐善剛

(西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川 南充 637009)

組合恒等式是組合數(shù)學(xué)研究領(lǐng)域的一個(gè)熱點(diǎn)問題[1-2]，它在概率論、統(tǒng)計(jì)學(xué)、數(shù)論、密碼學(xué)以及數(shù)學(xué)的其它領(lǐng)域也有著廣泛的應(yīng)用，研究新的組合恒等式在數(shù)學(xué)理論與應(yīng)用層面都是一項(xiàng)有意義的工作?，F(xiàn)有文獻(xiàn)對(duì)組合恒等式的研究已得到很多重要的成果，如文獻(xiàn)[3-6]得到了若干與格路計(jì)數(shù)有關(guān)的組合恒等式，文獻(xiàn)[7]應(yīng)用復(fù)變函數(shù)、組合與圖論方法論研究的是與nn-1有關(guān)的組合恒等式的新證法及其應(yīng)用，文獻(xiàn)[8]得到若干與正整數(shù)的有序分拆有關(guān)的組合恒等式，文獻(xiàn)[9]應(yīng)用母函數(shù)的組合分析技巧得到一些新的組合恒等式，文獻(xiàn)[10-11]研究的是與Vandermonde恒等式有關(guān)的一些新的組合恒等式。本文應(yīng)用有別于文獻(xiàn)[3-11]的Burnside-Polya計(jì)數(shù)法[1]、容斥原理[12-17]等組合分析方法與置換的輪換分解[18]的群論方法的巧妙結(jié)合，得到與恒等群、循環(huán)群和二面體群作用于一類映射集的等價(jià)類的計(jì)數(shù)有關(guān)的組合恒等式，這些組合恒等式較之于文獻(xiàn)[3-11]的結(jié)果是完全不同的類型、且是新穎的，也豐富、拓寬了組合恒等式的研究范圍、方法與結(jié)果，并對(duì)發(fā)現(xiàn)新的組合恒等式也有一定的應(yīng)用價(jià)值。

(1)

(2)

(3)

(4)

我們將給出式(1)～(4)的一種統(tǒng)一的組合證明，為此，需要用到下面的一些預(yù)備知識(shí)。

1 預(yù)備知識(shí)

定義1對(duì)任意u∈Z，定義[1,2k]上的置換θu為：

定義2對(duì)任意u∈Z，定義[1,2k]上的置換ηu為：

引理1令G0={θ0}，G1={θu|u∈Z}，G2={θu|u∈Z}∪{ηu|u∈Z}，則G0是恒等群、G1是2k階循環(huán)群、G2是4k階非循環(huán)群(一般稱其為二面體群)。

定義3定義Gv×M→M的映射gv為：

gv:Gv×M→M(σ,f)→f′，

容易證明gv(v=0,1,2)滿足“群在集合上的作用”的公理化定義[18]，即有下面的引理2。

引理2gv是群Gv在M上的作用，這里v=0,1,2。

定義4設(shè)λ,μ∈M，定義λ與μ之間的二元關(guān)系Rgv為：存在σ∈Gv，使得λ=gv((σ,μ))，一般將λ=gv((σ,μ))記之為λRgvμ，這里v=0,1,2。

根據(jù)等價(jià)關(guān)系的公理化定義[18]，有下面的引理3。

引理3Rgv是M上的元素之間的等價(jià)關(guān)系，這里v=0,1,2。

定義5設(shè)λ∈M，根據(jù)引理3，稱{μ∈M|μRgvλ}是群Gv作用于M的等價(jià)類(或稱軌道)。

引理7[14-15]對(duì)于非負(fù)整數(shù)d,s,t，且s≤t，令

則有

其中約定：

有了上述準(zhǔn)備工作，我們發(fā)現(xiàn)組合恒等式(1)～(4)可由如下的組合計(jì)數(shù)問題來得到。

2 定理的證明

下面給出定理1～定理4的一種統(tǒng)一的組合證明，需指出的是，以下證明過程中涉及到的所有符號(hào)、記法及其數(shù)學(xué)含義與第1節(jié)中交代的是完全一致的，如無必要，無需另作說明。

(5)

其中v=0,1,2。

根據(jù)文獻(xiàn)[14]的推論1中的容斥原理，即得

(6)

其中v=0,1,2。

下面給出求Qv(t1,,tm)的計(jì)算公式的具體方法(v=0,1,2)。

(7)

(8)

(i) 對(duì)任意u∈Z，不妨設(shè)gcd(u,2k)=d，則有

情形2當(dāng)σ=ηu，u∈Z。由置換的輪換分解[18]，不妨設(shè)ηu的兩兩不相交的輪換分解為：

(9)

(ii) 對(duì)任意u∈Z，且u為奇數(shù)時(shí)，則有

(iii) 對(duì)任意u∈Z，且2|u，k為奇數(shù)或4|u，2|k時(shí)，則有ψ2(ηu)=0

(iv) 對(duì)任意u∈Z，且2|u，2|k，4不整除u時(shí)，則有

將上述ψ1(θu)與ψ2(ηu)的計(jì)算公式代入式(7)，即得

(10)

(11)

(12)

其中k≡1(mod 2)。

(13)

其中k≡0(mod 2)。

注意到，對(duì)任意的非負(fù)整數(shù)ti≤ni(1≤i≤m)，有如下的式(14)。

(14)

其中Ii?Ai且|Ii|=ti(1≤i≤m)，v=0,1,2。

于是，將式(10)～(13)分別代入式(14)，即得Qv(t1,,tm)的如下的計(jì)算公式(v=0,1,2)。

(15)

(16)

(17)

其中k≡1(mod 2)。

(18)

其中k≡0(mod 2)。

最后將式(15)～(18)代入式(6)，即得

(19)

(20)

(21)

其中k≡1(mod 2)。

(22)

其中k≡0(mod 2)。

(23)

(24)

將式(24)代入式(23)，即得

(25)

(26)

將式(26)代入式(25)，即得

至此，定理1～定理4得以證畢。