唐善剛

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

Z表示整數(shù)集，a是正整數(shù)，令[1,a]={1,2,…,a}。設(shè)m為正整數(shù)，整數(shù)

(1)

研究限位排列數(shù)的基本方法是棋盤與棋子多項式[5-6]，本文利用容斥原理的計數(shù)方法[3-5, 7-13]、有限集合上封閉集族的計數(shù)方法與其它組合分析技巧的結(jié)合研究在陣列(1)下的[1,n]上的如下限位排列的計數(shù)[14]。

設(shè)A表示[1,n]上的所有全排列組成的集合，對任意B?A，令f(B)表示集合B的元素個數(shù)。對于φ∈A，us∈[1,ns]，界定與φ有關(guān)的命題Psus(φ)為：

其中1≤s≤m。

令

設(shè)Is?[1,ns]，令

設(shè)

非負整數(shù)l

本文要用到文獻[8]的一個組合恒等式，即下面的引理1。

引理1對于非負整數(shù)d,s,t，且s≤t，令

則有

1 ft1,…,tm的顯式計算公式

定理1 對于任意的非負整數(shù)ts≤ns(1≤s≤m)，則有

(2)

證明具體分為3個步驟來完成式(2)的證明。

步驟1 設(shè)σs是[1,ns]上的置換，且σs(us)=λus+ds，us∈[1,ns]。根據(jù)置換的輪換分解[15]，σs恰好分解為(ns,ds)個兩兩互不相交的ηs-輪換的乘積，由初等數(shù)論知識，不難證明σs的ηs-輪換分解為：

(3)

于是，陣列(1)基于式(3)的表示為：

(4)

其中1≤αs≤(ns,ds)，1≤s≤m。

根據(jù)陣列(4)與式(3)，界定如下的環(huán)形排列：

⊙bαs1bαs1bαs2bαs2…bαs (ηs -1)bαs (ηs -1)bαs ηsbαs ηs

(5)

對于環(huán)形排列(5)中任意取定的元素bαsj，對于φ∈A，根據(jù)陣列(4)與環(huán)形排列(5)，界定與φ有關(guān)的命題Pbαsj,bαs(j+1)(φ)與Pbαsj,bαsj(φ)為：

令

其中j∈Z，1≤αs≤(ns,ds)，1≤s≤m。

步驟2 在這個步驟中，我們需要證明幾個輔助的引理。

根據(jù)命題Pbαsj,bαs(j+1)、Pbαsj,bαsj、Psλαs+(j-1)ds與Psλαs+(j-2)ds的界定，顯然有如下的引理2成立。

引理2 對于φ∈A，對于環(huán)形排列(5)中任意取定的元素bαsj，若命題Pbαsj,bαs(j+1)(φ)成立，則命題Psλαs+(j-1)ds(φ)成立；若命題Pbαsj,bαsj(φ)成立，則命題Psλαs+(j-2)ds(φ)成立。 且

Asλαs+(j-1)ds=Abαsj,bαs(j+1)∪Abαs(j+1),bαs(j+1)，

Abαsj,bαs(j+1)∩Abαs(j+1),bαs(j+1)=?;

Asλαs+(j-2)ds=Abαsj,bαsj∪Abαs(j-1),bαsj，

Abαsj,bαsj∩Abαs(j-1),bαsj=?

引理3 從環(huán)形排列(5)中選取兩個不相鄰的元素bαsj1與bαsj2，設(shè)環(huán)形排列(5)中與bαsj1右相鄰的元素為bαs(h1+2)，環(huán)形排列(5)中與bαsj2右相鄰的元素為bαs(h2+2)，對于φ∈A，若命題Pbαsj1,bαs(h1+2)(φ)與Pbαsj2,bαs(h2+2)(φ)成立，則命題Psλαs+h1ds(φ)與Psλαs+h2ds(φ)成立，且

證明由引理2，命題Psλαs+h1ds(φ)與Psλαs+h2ds(φ)成立，且有

由環(huán)形排列(5)，bαs (h1 + 2)=bαs (j1 + 1)或bαsj1；bαs (h2 + 2)=bαs (j2 + 1)或bαsj2，從而

由于bαsj1與bαsj2在環(huán)形排列(5)中是不相鄰的，則bαsj1≠bαsj2，也即ηs不整除j1-j2。

(i) 當

根據(jù)ηs不整除j1-j2，即得

(ii) 當

根據(jù)ηs不整除j1-j2，即得

(iii) 當

(iv) 當

綜上情況(i)-(iv)所述，即得

由引理3，即得下面的引理4。

引理4 設(shè)從環(huán)形排列(5)中選取kαs個兩兩不相鄰的元素為bαsjv(1≤v≤kαs)，不妨設(shè)環(huán)形排列(5)中與bαsjv右相鄰的元素為bαs(hv+2)(1≤v≤kαs)，對于φ∈A，若命題Pbαsjv,bαs(hv+2)(φ)成立(1≤v≤kαs)，則命題Psλαs+hvds(φ)成立(1≤v≤kαs)，且

y≤kαs，x≠y;

(6)

步驟3 以下均約定{bαsjv|1≤v≤kαs}代表的是從環(huán)形排列(5)中任意選取kαs個兩兩不相鄰的元素的組合，且約定環(huán)形排列(5)中與bαsjv右相鄰的元素為bαs(hv+2)，其中1≤v≤kαs，1≤αs≤(ns,ds)，1≤s≤m。由文獻[5,16]，這樣的組合{bαsjv|1≤v≤kαs}的個數(shù)為：

(7)

注2 約定從環(huán)形排列(5)中選取0個兩兩不相鄰的元素的組合的個數(shù)為1，則式(7)對kαs=0也成立。

于是，根據(jù)式(6)、式(7)以及引理2與引理4，當0≤kαs≤ηs(1≤αs≤(ns,ds),1≤s≤m)時，即得

(8)

至此，式(2)成立。證畢。

2 主要結(jié)果

(9)

證明根據(jù)容斥原理[8]，可得

(10)

將式(2)代入式(10)即得式(9)。證畢。

推論1 對任意非負整數(shù)rs≤ns(1≤s≤m)，則[1,n]上使得陣列(1)中的第i個陣列中至多有ri個列，它們中的任意列都有相同的數(shù)(1≤i≤k)，而第j個陣列中恰好有rj個列，它們中的任意列都有相同的數(shù)(1+k≤j≤m)的全排列φ的個數(shù)為：

(11)

推論2 對任意非負整數(shù)rs≤ns(1≤s≤m)，則[1,n]上使得陣列(1)中的第i個陣列中至少有ri個列，它們中的任意列都有相同的數(shù)(1≤i≤k)，而第j個陣列中恰好有rj個列，它們中的任意列都有相同的數(shù)(1+k≤j≤m)的全排列φ的個數(shù)為：

(12)

推論3 對任意非負整數(shù)rs≤ns(1≤s≤m)，則[1,n]上使得陣列(1)中的第i個陣列中至多有ri個列，它們中的任意列都有相同的數(shù)(1≤i≤k)，而第j個陣列中至少有rj個列，它們中的任意列都有相同的數(shù)(1+k≤j≤m)的全排列φ的個數(shù)為：

(13)

推論4 [1,n]上使得陣列(1)中的任意列都沒有相同的數(shù)的全排列φ的個數(shù)為：

(14)

(15)

推論6 當(ns,ds)=1(1≤s≤m)時，對任意非負整數(shù)rs≤ns(1≤s≤m)，則[1,n]上使得陣列(1)中的第i個陣列中至多有ri個列，它們中的任意列都有相同的數(shù)(1≤i≤k)，而第j個陣列中恰好有rj個列，它們中的任意列都有相同的數(shù)(1+k≤j≤m)的全排列φ的個數(shù)為：

(16)

推論7 當(ns,ds)=1(1≤s≤m)時，對任意非負整數(shù)rs≤ns(1≤s≤m)，則[1,n]上使得陣列(1)中的第i個陣列中至少有ri個列，它們中的任意列都有相同的數(shù)(1≤i≤k)，而第j個陣列中恰好有rj個列，它們中的任意列都有相同的數(shù)(1+k≤j≤m)的全排列φ的個數(shù)為：

(17)

推論8 當(ns,ds)=1(1≤s≤m)時，對任意非負整數(shù)rs≤ns(1≤s≤m)，則[1,n]上使得陣列(1)中的第i個陣列中至多有ri個列，它們中的任意列都有相同的數(shù)(1≤i≤k)，而第j個陣列中至少有rj個列，它們中的任意列都有相同的數(shù)(1+k≤j≤m)的全排列φ的個數(shù)為：

(18)

推論9 當(ns,ds)=1(1≤s≤m)時，[1,n]上使得陣列(1)中的任意列都沒有相同的數(shù)的全排列φ的個數(shù)為：

(19)

注3 式(17)推廣了文獻[3]的結(jié)果，文獻[4]試圖推廣文獻[3]的結(jié)果，但文獻[4]的結(jié)果被證明是錯誤的[7]，式(17)是對文獻[4]的錯誤結(jié)果的改正與推廣，式(9)則是對陣列(1)中的ns>(ns,ds)≥1(1≤s≤m)情形下的結(jié)果的統(tǒng)一回答。

3 討 論

(20)

由于ft1,…,tm在陣列(1)中的計算方法并不適用于陣列(20)，從而導致ft1,…,tm在陣列(20)中的顯式計算公式很難獲得，關(guān)于這一點可以參閱文獻[5]，本文未能得到問題Ⅱ的顯式計數(shù)公式，僅僅得到δs=1(1≤s≤m)對應的問題Ⅰ的顯式計數(shù)公式，即式(9)，我們將在后續(xù)的研究中嘗試尋求ft1,…,tm在陣列(20)中的顯式計算公式的方法。

參考文獻：

[1] 魏萬迪. 限位排列和k一積和式 [J]. 應用數(shù)學學報，1983, 6(2): 177-182.

WEI W D. Permutations with restricted positions andk-permanent [J]. Acta Mathematicae Applicatae Sinica, 1983, 6(2): 177-182.

[2] 張?；?，張遴賢，林治勛. 限位排列的一個圖論方法 [J]. 應用數(shù)學學報，1983，6(2): 240-246.

ZHANG F J，ZHANG L X，LIN Z X. A method of graph theory for restricted permutations [J]. Acta Mathematicae Applicatae Sinica，1983, 6(2): 240-246.

[3] 魏萬迪. 廣容斥原理及其應用 [J]. 科學通報，1980, 25(7): 296-299.

WEI W D. A generalized principle of inclusion-exclusion and its applications [J]. Chinese Science Bulletin, 1980, 25(7): 296-299.

[4] 萬宏輝. 容斥原理的拓廣及其應用 [J]. 科學通報，1984, 29(16): 972-975.

WAN H H. A generalized principle of inclusion-exclusion and its applications [J]. Chinese Science Bulletin, 1984, 29(16): 972-975.

[5] STANLEY R P. Enumerative combinatorics: Volume 1 [M]. Cambridge: Cambridge University Press，1997.

[6] 唐保祥，任韓. 3類特殊圖完美匹配數(shù)的計算公式 [J]. 中山大學學報(自然科學版)，2017, 56(3): 36-40.

TANG B X，REN H. The counting formula of the perfect matchings of three types of special graphs [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2017, 56(3): 36-40.

[7] 唐善剛. 關(guān)于“容斥原理的拓廣及其應用”的注記 [J]. 山東大學學報(理學版)，2012, 47(10): 64-69.

TANG S G. A note on “generalized principle of inclusion-exclusion and its application” [J]. J Shandong University (Natural Science), 2012, 47 (10): 64-69.

[8] 唐善剛. 廣義容斥原理及其應用 [J]. 山東大學學報(理學版)，2009, 44(1): 83-90.

TANG S G. Generalized principle of inclusion-exclusion and its application [J]. J Shandong University (Natural Science), 2009, 44(1): 83-90.

[9] 唐善剛. 容斥原理的拓展及其應用 [J]. 山東大學學報(理學版)，2010, 45(12): 12-15.

TANG S G. A generalization of principle of inclusion-exclusion and its application [J]. J Shandong University (Natural Science), 2010, 45(12): 12-15.

[10] 唐善剛. 容斥原理的拓展及其應用(Ⅱ) [J]. 山東大學學報(理學版), 2011, 46(12): 70-75.

TANG S G. A generalization of principle of inclusion-exclusion and its application (Ⅱ) [J]. J Shandong University (Natural Science), 2011, 46(12): 70-75.

[11] 曹汝成. 廣義容斥原理及其應用 [J]. 數(shù)學研究與評論，1988, 8(4): 526-530.

CAO R C. A generalized principle of inclusion-exclusion and its applications [J]. J Mathematical Research and Exposition, 1988, 8(4): 526-530.

[12] 唐善剛. 賦權(quán)有限集上的容斥原理及應用 [J]. 浙江大學學報(理學版)，2014, 41(2): 123-126.

TANG S G. A principle of inclusion-exclusion on a weighted finite set and its applications [J]. J Zhejiang University (Science Edition), 2014, 41(2): 123-126.

[13] BENDER.E A, GOLDMAN J R. On the applications of mobius inversion in combinatorial analysis [J]. Amer Math Monthly, 1975, 82(8): 789-803.

[14] 唐保祥，任韓. 有限集合上封閉集族的計數(shù) [J]. 中山大學學報(自然科學版)，2010, 49(6): 11-14.

TANG B X，REN H. Enumeration of closed family of finite sets [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2010，49(6) : 11-14.

[15] 韓士安，林磊. 近世代數(shù) [M]. 北京： 科學出版社, 2004.

[16] 李磊. 關(guān)于幾個組合計數(shù)公式的推廣 [J]. 工程數(shù)學學報，1996，13(4) : 95-98.

LI L. Generalization of some combinatorial formulas [J]. J Engineering Mathematics，1996，13(4): 95-98.