一類限位排列的計數*

唐善剛

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

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

(1)

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

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

其中1≤s≤m。

令

設Is?[1,ns]，令

設

非負整數l

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

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

則有

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

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

(2)

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

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

(3)

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

(4)

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

根據陣列(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，根據陣列(4)與環(huán)形排列(5)，界定與φ有關的命題Pbαsj,bαs(j+1)(φ)與Pbαsj,bαsj(φ)為：

令

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

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

根據命題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，設環(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) 當

根據ηs不整除j1-j2，即得

(ii) 當

根據ηs不整除j1-j2，即得

(iii) 當

(iv) 當

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

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

引理4 設從環(huán)形排列(5)中選取kαs個兩兩不相鄰的元素為bαsjv(1≤v≤kαs)，不妨設環(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}的個數為：

(7)

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

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

(8)

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

2 主要結果

(9)

證明根據容斥原理[8]，可得

(10)

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

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

(11)

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

(12)

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

(13)

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

(14)

(15)

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

(16)

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

(17)

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

(18)

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

(19)

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

3 討 論

(20)

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

參考文獻：

[1] 魏萬迪. 限位排列和k一積和式 [J]. 應用數學學報，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]. 應用數學學報，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類特殊圖完美匹配數的計算公式 [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] 唐善剛. 關于“容斥原理的拓廣及其應用”的注記 [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]. 數學研究與評論，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] 唐善剛. 賦權有限集上的容斥原理及應用 [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] 唐保祥，任韓. 有限集合上封閉集族的計數 [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] 韓士安，林磊. 近世代數 [M]. 北京： 科學出版社, 2004.

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

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