限制歐拉多項(xiàng)式的一些組合性質(zhì)

張旭彤，張 彪

（天津師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，天津 300387）

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

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

在給出主要結(jié)論之前，首先給出相關(guān)概念.

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

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

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

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

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

的元素個(gè)數(shù)；用An（x）表示歐拉多項(xiàng)式，其定義為

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

的元素個(gè)數(shù)；利用j-歐拉數(shù)可以定義j-歐拉多項(xiàng)式為

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

性質(zhì) 1[4]設(shè) n、j 是正整數(shù)，且 1≤j≤n，則 j-歐拉多項(xiàng)式滿足

此外，j-歐拉多項(xiàng)式也可以看作是經(jīng)典歐拉多項(xiàng)式的細(xì)化，它們有如下關(guān)系：

性質(zhì) 2[4]設(shè) n、j 是正整數(shù)，且 1≤j≤n，則 j-歐拉多項(xiàng)式滿足

1 （i，j）-歐拉多項(xiàng)式

受到j(luò)-歐拉多項(xiàng)式的啟發(fā)，本文進(jìn)一步定義了同時(shí)限制排列的第一位和最后一位的情況.

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

的元素個(gè)數(shù)；利用（i，j）-歐拉數(shù)可以定義（i，j）-歐拉多項(xiàng)式為

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

引理設(shè) n、i、j、r 是正整數(shù)，并且 i+r≤n，j+r≤n，則有

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

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

以下 2 個(gè)定理給出了 j-歐拉多項(xiàng)式與（i，j）-歐拉多項(xiàng)式之間的關(guān)系.

定理1設(shè)n、j 是正整數(shù)，且1≤j≤n，則有

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

定理 2設(shè) n、i、j 是正整數(shù)，且 1≤j≤n，1≤i≤n-j，則有

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

由引理可得

因此定理得證.

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

本節(jié)證明在集合An，j中超越數(shù)和下降數(shù)的同分布性.

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

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

定理3設(shè)n、j 是正整數(shù)，且n≥1，則對(duì)于固定的 j∈[n]，有

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

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

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

下面給出一個(gè)與定理3 的證明有關(guān)的例子.

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

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

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

推論設(shè)矩陣M 為

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