剩余类环上的轮换多项式的计数∗

唐善刚

(西华师范大学数学与信息学院,四川南充637009)

容斥原理是组合数学的一个重要的计数方法[1−11],文献[1-2,4-10]将经典的容斥原理拓广至赋权有限集上的广义容斥原理,并用于解决更加复杂的组合计数问题,获得了一系列组合计数问题的显式计数公式,如限位排列的计数[1−3,12],Mnage问题的计数[4,9,10,13],本文主要应用广义容斥原理与群作用于集合的等价类的计数方法研究模n剩余类环上的轮换多项式的组合计数问题,得到了模n剩余类环上的轮换多项式个数的若干显式计数公式与相应的组合恒等式.对任意的有限集B,约定|B|表示B中的元素的个数,约定Z表示整数集,Z0表示非负整数集.

0 有关概念及引理

定义1已知n,s为正整数,Zn表示模n剩余类环,设f(x1,···,xs)是Zn上关于不定元xq(1≤q≤s)的多项式,且

定义2设R表示M上的单项式之间的一种二元关系,且R被界定为如下的

其中α1···αs表示由数字α1,···,αs组成的环形排列.

注1R是M上的单项式间的等价关系,称为关于R唯一确定的M的一个等价类.

根据Zn上的轮换多项式的定义,不难得到下面的引理1.

引理1f(x1,···,xs)是Zn上的轮换多项式,f(x1,···,xs)含有单项式则f(x1,···,xs)含有单项式其中β1···βs=α1···αs.

注2当轮换多项式f(x1,···,xs)含有单项式时,由引理1,关于R所唯一确定的M的等价类中的每个单项式必为f(x1,···,xs)的项,据此,称为轮换多项式f(x1,···,xs)的同型项,c称之为轮换多项式f(x1,···,xs)的同型项的系数.

引理2[5]对于非负整数d,s,t,且s≤t,令

则有

1 计数问题

λ是非负整数,整数s>1,令这里为Zn的加法零元.非负整数k≤m,将作一个m部划分(m>0),不妨设其中|Ai|=ni≥0(1≤i≤m),是非负整数,且ri≤ri ≤ni(1≤i≤m),提出如下Zn上的轮换多项式的计数问题.

问题Ⅰ求Zn上的次数不超过λ的s元轮换多项式，使得Ai中至少有ri个元素,但又至多有ri个元素为其系数(1≤i≤m)的那样的s元轮换多项式的个数.

问题Ⅱ求Zn上的次数等于λ的s元轮换多项式，使得Ai中至少有ri个元素,但又至多有ri个元素为其系数(1≤i≤m)的那样的s元轮换多项式的个数.

设Gλ表示Zn上的次数不大于λ的一切s元轮换多项式构成的集合,对任意C⊆Gλ,用Q(C)表示C中的元素的个数.对于y∈Gλ,v∈Ai,界定命题Piv(y)为下面的

对任意v∈Ai,设

对任意Ii⊆Ai,设

其中Ai−Ii表示集合Ai与Ii的差集,且约定:

设

当l

对任意的非负整数ti≤ni(1≤i≤m),用式(1)的右边来定义Qt1,···,tm为

2 Qt1,··,tm的显式计算公式

根据容斥原理的计数原理[1−2,4−10]，求的计数公式,关键在于Qt1,···,tm的显式计算公式.

定理1对任意的非负整数ti≤ni(1≤i≤m),则有

证明设集合X={1,2,···,s},对∀p∈Z,定义X上的置换σp为

其中µp+q表示p+q除以s的最小正剩余数.

设Sλ=则G为s阶循环群.根据群作用于集合的定义[14],G作用于Sλ被定义为:对任意σp∈G,对任意有如下的

从而对于定义2中的等价关系R,有

于是根据群作用于集合的Burnside引理[14],即有

其中Ψ(σp)表示在Sλ中使得的个数.

用gcd(p,s)表示整数p与s的最大公约数,不妨设gcd(p,s)=d,根据置换的轮换分解[14],σp可唯一分解为d个两两不相交的轮换的乘积.于是Ψ(σp)相当于求关于非负整数变量yj(1≤j≤d)的不等式λ的解(y1,···,yd)的个数,从而Ψ(σp)=又在模s的完全剩余系中与s的最大公约数为d的整数个数为且G又为s阶循环群,进而得到

(ⅰ)从Eλ中选取τ个元素的组合的个数为

(ⅱ)取定Ii⊆Ai且|Ii|=ti(1≤i≤m),将Eλ中选定的τ个元素并赋予其在中的系数作为中的轮换多项式的同型项,则这样的轮换多项式的个数相当于求指数型生成函数的泰勒展开式中的系数,经计算展开式中的系数为

(ⅲ)对取定的Ii⊆Ai且|Ii|=ti(1≤i≤m),根据(ⅰ)与(ⅱ)的相应结果,以及乘法与加法计数原理,即有

注3当Ii=∅(1≤i≤m),即ti=0(1≤i≤m)时,式(3)仍然成立,也即

将式(3)代入式(1),化简即得

至此,式(2)成立.

3 主要结果

定理2整数λ≥0,Zn上的次数不超过λ的s元轮换多项式使得Ai中至少有ri个元素,但又至多有ri个元素为其系数(1≤i≤m)的那样的s元轮换多项式的个数为

证明根据广义容斥原理[6],则有

将式(2)代入式(6)即得式(5).

定理3当整数λ>0时,Zn上的次数等于λ的s元轮换多项式使得Ai中至少有ri个元素,但又至多有个元素为其系数(1≤i≤m)的那样的s元轮换多项式的个数为

证明当整数λ>0时,Zn上的次数等于λ的s元轮换多项式使得Ai中至少有ri个元素,但又至多有个元素为其系数(1≤i≤m)的那样的s元轮换多项式的个数为

将式(5)代入上式，化简即得式(7).

推论1整数λ≥0,Zn上的次数不超过λ的s元轮换多项式使得Ai中至少有ri个元素(1≤i≤m)为其系数的那样的s元轮换多项式的个数为

推论2当整数λ>0时,Zn上的次数等于λ的s元轮换多项式使得Ai中至少有ri个元素(1≤i≤m)为其系数的那样的s元轮换多项式的个数为

推论3整数λ≥0,Zn上的次数不超过λ的s元轮换多项式使得Ai中恰好有ri个元素(1≤i≤m)为其系数的那样的s元轮换多项式的个数为

推论4当整数λ>0时,Zn上的次数等于λ的s元轮换多项式使得Ai中恰好有ri个元素(1≤i≤m)为其系数的那样的s元轮换多项式的个数为

在式(5)与(7)中ri=0(1≤i≤m),即得

推论5整数λ≥0,Zn上的次数不超过λ的s元轮换多项式使得Ai中至多有个元素(1≤i≤m)为其系数的那样的s元轮换多项式的个数为

推论6当整数λ>0时,Zn上的次数等于λ的s元轮换多项式使得Ai中至多有个元素(1≤i≤m)为其系数的那样的s元轮换多项式的个数为

推论7

其中ni为非负整数,且整数λ>0,整数s>1.

当式(14)中的m=1时,有如下的组合恒等式.

推论8

其中整数n≥1,整数λ>0,整数s>1.

特别地,式(14)与(15)中的λ=0时,有如下的组合恒等式.

推论9

其中ni为非负整数(1≤i≤m),且

推论10

其中整数n≥1.