限制歐拉多項式的一些組合性質

張旭彤，張 彪

（天津師范大學數學科學學院，天津 300387）

歐拉多項式是組合數學中一類極其重要的多項式，歐拉數也是一類非常重要的組合數，它們在組合數學中有著非常重要的應用和意義，因而被廣泛研究并取得了豐碩的成果[1-2].1998 年，Ehrenborg 等[3]通過對歐拉數加以限制給出了一個關于單位立方體中相鄰2 個切片混合體積的組合解釋.在此基礎上，2008年，Brenti 等[4]在經典歐拉多項式和歐拉數的基礎上，通過限制排列的第一位提出了限制歐拉多項式和限制歐拉數的概念，并研究了它們的相關性質.限制歐拉多項式又被稱為j-歐拉多項式[2]，它在幾何方面有很多應用.文獻[4]應用限制歐拉多項式研究了布爾復形在重心重分下的f 向量和h 向量的相關理論.文獻[5]通過構造回文的限制歐拉多項式證明了布爾復形在重心重分下的γ向量是一個均衡單純復形的f 向量.文獻[6]通過對s-歐拉多項式加以限制研究了推廣歐拉多項式的實零點問題.文獻[7]通過證明半開的格平行立方體是j-歐拉多項式的線性組合而證明了格分割多面體的h*多項式是實零點的.

本研究提出了一種新的限制歐拉多項式的概念，它是通過同時限制排列第一位和最后一位而得到的，并給出了這種新的限制歐拉多項式的一個簡單性質的組合證明.利用該性質，給出了2 個關于原限制歐拉多項式與新的限制歐拉多項式關系的性質，并給出了對應的組合證明.此外，本研究還利用文獻[8-9]提出的一個組合雙射證明了在限制排列最后一位的n元排列集合中超越數和下降數的同分布性.

在給出主要結論之前，首先給出相關概念.

定義 1設 n、i 是正整數，且 1≤i≤n，定義 n 元排列的表示為

其中 πi∈[n]={1，2，…，n}.

由于第一行是固定的，因此可以去掉第一行得到排列的一行表示為π=π1π2…πn.用π-1（i）表示數字i在排列π中所對應的位置，并用Sn表示n 元排列組成的集合.

定義 2設n、i 是正整數，且1≤i πi+1，則稱第 i 個位置為排列 π的一個下降位，用 Des（π）={i∈[n-1]：πi> πi+1}表示排列π的下降集，用des（π）表示下降集的元素個數，稱為排列π的下降數.

定義 3設 n、k 是正整數，且 0≤k≤n - 1.用A（n，k）表示歐拉數，定義歐拉數為集合

的元素個數；用An（x）表示歐拉多項式，其定義為

定義 4[4]設n、j 是正整數，且1≤j≤n，用An，j（x）表示j-歐拉多項式，用an，j（k）表示j-歐拉數.定義j-歐拉數為集合

的元素個數；利用j-歐拉數可以定義j-歐拉多項式為

對于給定的排列 σ= σ1σ2…σn∈An，j，令 πi=n+1-σn+1-i，構造排列 π = π1π2…πn∈Sn，排列 σ 的第一位 j使得排列π的第n 位為n+1-j，即可得到如下性質.

性質 1[4]設 n、j 是正整數，且 1≤j≤n，則 j-歐拉多項式滿足

此外，j-歐拉多項式也可以看作是經典歐拉多項式的細化，它們有如下關系：

性質 2[4]設 n、j 是正整數，且 1≤j≤n，則 j-歐拉多項式滿足

1 （i，j）-歐拉多項式

受到j-歐拉多項式的啟發，本文進一步定義了同時限制排列的第一位和最后一位的情況.

定義 5設 n、i、j 是正整數，且 1≤i≠j≤n，0≤k≤n-1，用An，i，j（x）表示（i，j）-歐拉多項式，用an，i，j（k）表示（i，j）-歐拉數.定義（i，j）-歐拉數為集合

的元素個數；利用（i，j）-歐拉數可以定義（i，j）-歐拉多項式為

由（i，j）-歐拉多項式的定義，可以得到以下引理.

引理設 n、i、j、r 是正整數，并且 i+r≤n，j+r≤n，則有

證明首先證明An，i，j（x）= An，i+1，j+1（x），其中i、j≤n+1.構造 An，i，j到 An，i+1，j+1的映射，對于給定的排列 p∈An，i，j，將排列 p 中所有小于 n 的數字加 1，再將 n 變為 1，則得到排列 p′∈An，i+1，j+1，p 映射為 p′.如給定排列 p =34251∈A5，3，1，經該映射后得到排列 p′=45312∈A5，4，2，并且有 des（p）=des（p′）=2.由于逆映射可通過該映射唯一確定，故容易驗證該映射是一個雙射.雖然這個雙射破壞了原先排列p 中n 與其后面元素所形成的下降位，但是同時也在排列p′中1 的位置前面形成了新的下降位，而且其他連續數對之間的關系沒有改變.因此，這個雙射沒有影響下降數的大小，也就自然得到了

按照以上方法，同理可以證明

以下 2 個定理給出了 j-歐拉多項式與（i，j）-歐拉多項式之間的關系.

定理1設n、j 是正整數，且1≤j≤n，則有

證明 由j-歐拉多項式An，j（x）的定義可得An，j（x）=An+1，j，n+1（x），再由引理可得

定理 2設 n、i、j 是正整數，且 1≤j≤n，1≤i≤n-j，則有

證明對于給定的排列 σ= σ1σ2…σn∈An，j，構造映射 φ：An，j→An+1，j+1，1，使得排列 π = π1π2…πn+1=φ（σ）∈An+1，j+1，1.具體構造為：將排列 σ 中的每個數字加1，再將數字1 放到排列的最后一位，則得到排列π∈An+1，j+1，1，其中：π1=j +1，πn+1=1.如對于排列 σ=23154∈A5，2，其中：n=5，j=2，des（σ）=2，則通過映射可得 π = φ（σ）=342651∈A6，3，1，其中：π1=3，π6=1，des（π）=3.由于φ的逆映射可通過φ唯一確定，故容易驗證該映射是一個雙射.該雙射增加了一個πn與πn+1=1 形成的下降位，但是并沒有影響其他數對之間的大小關系，故有 des（π）=des（σ）+1.因此可得

由引理可得

因此定理得證.

2 超越數和下降數在集合An，j中的同分布性

本節證明在集合An，j中超越數和下降數的同分布性.

定義 6[10]設排列π∈Sn，用exc（π）表示超越數，其定義為

其中滿足條件的i 稱為排列π的一個超越位.

定理3設n、j 是正整數，且n≥1，則對于固定的 j∈[n]，有

證明首先構造組合雙射如下：對于給定的排列σ=σ1σ2…σn∈Sn，構造 φ：Sn→Sn，使得 π = π1π2…πn=φ（σ）.定義 σ0=0，并且令 k∈[n].若對于 m> k，有σk > σm，則令 πσk+1=σk；否則，在排列σ中找到第1個在σk左邊并小于σk的元素，若該元素為σi，則令πσi+1=σk.由于該雙射表明了在集合Sn中下降數和超越數的同分布性，因此利用該雙射可得

這是由于在排列σ∈An，j中沒有比1 更小的元素，并且σ0=0 是第一個小于1 的元素，因此第一個元素j在經過雙射φ變換后使得排列的第j 個位置變成了1，令 σ=σ1σ2…σn∈φ（τ），則有 σj=1.

對于給定的排列 σ=σ1σ2…σn∈Sn，令 πi=n+1-σ-1（n+1-i），構造排列φ（σ）=π=π1π2…πn∈Sn，則i 是排列π中的一個超越位當且僅當σ-1（n+1-i）是排列σ中的一個超越位.這是因為，若i 是排列π中的一個超越位，則πi>i，則有n+1-σ-1（n+1-i）>i，變形得σ-1（n+1-i）i，即πi>i，所以i 是排列π中的一個超越位.因此，映射φ是一個雙射.此外，經過雙射φ變換后，排列σ中的第j 位σj=1 確定了排列π中最后一位為πn=n+1-j.因此可得

下面給出一個與定理3 的證明有關的例子.

例對于排列 τ =23541∈A5，2，其中：n=5，j=2，des（τ）= 2，通過定理 3 的雙射 φ 可得 σ =φ（τ）=41253∈S5，其中：σ2=1，exc（σ）=2.再經過定理 3 的雙射 φ 變換后，得 π= 25134∈S5，其中：π5= 4，exc（π）=2.

定義7設n ×n 階矩陣M=（mi，j），用per（M）表示矩陣M 的積和式，定義為

由定理3 得到的在限制排列最后一位的前提下下降數和超越數的同分布性，以及矩陣積和式的定義，可得如下推論.

推論設矩陣M 為

將矩陣M 劃掉第n 行和第j 列得到的子矩陣記為Mj，則有