tags: Maths
预备定义
原始文献A Theorem on Reciprocal Polynomials with Applications to Permutations and Compositions;
对称多项式
对称(reciprocal)多项式:
f
(
x
)
=
a
n
x
n
+
.
.
.
+
a
0
f(x) = a_n x^n + ... + a_0
f(x)=anxn+...+a0是对称的, 如果
f
(
x
)
=
x
n
f
(
1
x
)
,
f(x) = x^n f\left(\frac 1x\right),
f(x)=xnf(x1),
即:
a
r
=
a
n
−
r
a_r = a_{n-r}
ar=an−r.
单峰对称多项式
多项式
f
(
x
)
=
a
n
x
n
+
.
.
.
+
a
0
f(x) = a_n x^n + ... + a_0
f(x)=anxn+...+a0称为单峰(unimodal)对称多项式, 如果它是对称的且对
1
≤
i
≤
n
/
2
1\leq i\leq n/2
1≤i≤n/2, 有
a
i
−
a
i
−
1
≥
0
a_i-a_{i-1}\geq0
ai−ai−1≥0.
Andrews定理
单峰对称多项式的乘积还是单峰对称的.
即多项式
f
(
x
)
=
∑
j
=
0
n
a
j
x
j
,
g
(
x
)
=
∑
j
=
0
m
b
j
x
j
,
f(x)=\sum_{j=0}^na_jx^j,\ \ g(x)=\sum_{j=0}^mb_jx^j,
f(x)=j=0∑najxj, g(x)=j=0∑mbjxj,
系数都是非负的, 则乘积仍保持对称单峰.
证明
令
f
(
x
)
g
(
x
)
=
h
(
x
)
=
∑
j
=
0
m
+
n
c
j
x
j
,
f(x)g(x)=h(x)=\sum_{j=0}^{m+n}c_jx^j,
f(x)g(x)=h(x)=j=0∑m+ncjxj,
则
h
(
x
)
=
f
(
x
)
g
(
x
)
=
x
n
f
(
1
/
x
)
x
m
g
(
1
/
x
)
=
x
n
+
m
h
(
1
/
x
)
,
h(x) = f(x)g(x)=x^nf(1/x)x^mg(1/x)=x^{n+m}h(1/x),
h(x)=f(x)g(x)=xnf(1/x)xmg(1/x)=xn+mh(1/x),
对称性得证.
由于对每一个
a
i
≥
0
,
b
i
≥
0
a_i\geq0, b_i\geq0
ai≥0,bi≥0, 有
c
j
=
∑
r
≥
0
,
s
≥
0
r
+
s
=
j
a
r
b
s
≥
0
,
c_j=\sum_{\stackrel{\small r+s=j}{r\geq0,s\geq0}}a_rb_s\geq0,
cj=r≥0,s≥0r+s=j∑arbs≥0,
定义
∀
r
∈
(
−
∞
,
0
)
∩
(
n
,
+
∞
)
,
有
a
r
=
0
\forall r\in(-\infty, 0)\cap(n, +\infty),\ \ 有 a_r=0
∀r∈(−∞,0)∩(n,+∞), 有ar=0
以及
∀
s
∈
(
−
∞
,
0
)
∩
(
m
,
+
∞
)
,
有
b
s
=
0
\forall s\in(-\infty, 0)\cap(m, +\infty),\ \ 有b_s=0
∀s∈(−∞,0)∩(m,+∞), 有bs=0
于是
∀
r
∈
(
−
∞
,
n
/
2
]
,
有
a
r
−
a
r
−
1
≥
0
\forall r\in (-\infty, n/2],\ \ 有a_r-a_{r-1}\geq0
∀r∈(−∞,n/2], 有ar−ar−1≥0
并且
∀
s
∈
(
−
∞
,
m
/
2
]
,
有
b
s
−
b
s
−
1
≥
0
\forall s\in (-\infty, m/2],\ \ 有b_s-b_{s-1}\geq0
∀s∈(−∞,m/2], 有bs−bs−1≥0
所以:
2
(
c
j
−
c
j
−
1
)
=
(
∑
r
a
r
b
j
−
r
+
∑
r
a
n
−
r
+
1
b
j
−
n
+
r
−
1
)
−
(
∑
r
a
r
−
1
b
j
−
r
+
∑
r
a
n
−
r
b
j
−
n
+
r
−
1
)
=
∑
r
(
a
r
−
a
r
−
1
)
b
j
−
r
+
∑
r
(
a
n
−
r
+
1
−
a
n
−
r
)
b
j
−
n
+
r
−
1
=
∑
r
(
a
r
−
a
r
−
1
)
(
b
j
−
r
−
b
j
−
n
+
r
−
1
)
(
since
a
r
=
a
n
−
r
)
=
∑
r
=
0
n
+
1
(
a
r
−
a
r
−
1
)
(
b
j
−
r
−
b
j
−
n
+
r
−
1
)
=
∑
r
=
0
(
n
+
1
)
/
2
(
a
r
−
a
r
−
1
)
(
b
j
−
r
−
b
j
−
n
+
r
−
1
)
+
∑
r
=
0
(
n
+
1
)
/
2
(
a
n
+
1
−
r
−
a
n
−
r
)
(
b
j
−
n
−
1
+
r
−
b
j
−
r
)
=
2
∑
r
=
0
(
n
+
1
)
/
2
(
a
r
−
a
r
−
1
)
(
b
j
−
r
−
b
j
−
n
+
r
−
1
)
=
2
∑
r
=
0
n
/
2
(
a
r
−
a
r
−
1
)
(
b
j
−
r
−
b
j
−
n
+
r
−
1
)
\begin{aligned} &2(c_{j} - c_{j-1}) \\[5pt] =& \left(\sum_{r}a_rb_{j-r}+\sum_{r}a_{n - r + 1}b_{j - n + r - 1}\right) \\ &- \left(\sum_{r}a_{r-1}b_{j-r} + \sum_{r}a_{n - r}b_{j - n + r - 1}\right)\\ =& \sum_{r}(a_r-a_{r-1})b_{j-r}+\sum_{r}(a_{n - r + 1}-a_{n-r})b_{j - n + r - 1} \\ =& \sum_{r}(a_r-a_{r-1})(b_{j-r} - b_{j - n + r - 1})\qquad(\text{since} \ a_r=a_{n-r}) \\ =& \sum_{r=0}^{n+1}(a_r-a_{r-1})(b_{j-r} - b_{j - n + r - 1}) \\ =& \sum_{r=0}^{(n+1)/2}(a_r-a_{r-1})(b_{j-r} - b_{j - n + r - 1})\\ &+ \sum_{r=0}^{(n+1)/2}(a_{n+1-r}-a_{n-r})(b_{j-n-1+r} - b_{j - r}) \\ =& 2\sum_{r=0}^{(n+1)/2}(a_r-a_{r-1})(b_{j-r} - b_{j - n + r - 1})\\ =& 2\sum_{r=0}^{n/2}(a_r-a_{r-1})(b_{j-r} - b_{j - n + r - 1})\\ \end{aligned}
=======2(cj−cj−1)(r∑arbj−r+r∑an−r+1bj−n+r−1)−(r∑ar−1bj−r+r∑an−rbj−n+r−1)r∑(ar−ar−1)bj−r+r∑(an−r+1−an−r)bj−n+r−1r∑(ar−ar−1)(bj−r−bj−n+r−1)(since ar=an−r)r=0∑n+1(ar−ar−1)(bj−r−bj−n+r−1)r=0∑(n+1)/2(ar−ar−1)(bj−r−bj−n+r−1)+r=0∑(n+1)/2(an+1−r−an−r)(bj−n−1+r−bj−r)2r=0∑(n+1)/2(ar−ar−1)(bj−r−bj−n+r−1)2r=0∑n/2(ar−ar−1)(bj−r−bj−n+r−1)
于是,
c
j
−
c
j
−
1
=
∑
0
≤
r
≤
n
/
2
(
a
r
−
a
r
−
1
)
(
b
j
−
r
−
b
j
−
n
−
1
+
r
)
.
(*)
c_j - c_{j - 1} = \sum_{0\leq r\leq n/2}(a_r-a_{r-1})(b_{j-r}-b_{j-n-1+r}). \tag{*}
cj−cj−1=0≤r≤n/2∑(ar−ar−1)(bj−r−bj−n−1+r).(*)
只需证明
c
j
−
c
j
−
1
≥
0
c_j-c_{j-1}\geq0
cj−cj−1≥0.
由前面的规定,
∀
0
≤
r
≤
n
/
2
\forall 0\leq r\leq n/2
∀0≤r≤n/2, 有
a
r
−
a
r
−
1
≥
0
a_{r}-a_{r-1}\geq0
ar−ar−1≥0;
-
如果
j
−
r
≤
m
/
2
j-r\leq m/2
j−r≤m/2, 由
n
+
1
≥
2
r
n+1\geq 2r
n+1≥2r, 得到
m
/
2
≥
j
−
r
≥
j
−
n
−
1
+
r
,
m/2\geq j-r\geq j-n-1+r,
m/2≥j−r≥j−n−1+r,
即
b
j
−
r
−
b
j
−
n
−
1
+
r
≥
0
b_{j-r}-b_{j-n-1+r}\geq0
bj−r−bj−n−1+r≥0.
-
如果
j
−
r
>
m
/
2
j-r> m/2
j−r>m/2, 由
0
≤
j
≤
(
m
+
n
)
/
2
0\leq j\leq (m+n)/2
0≤j≤(m+n)/2, 得到
m
+
n
+
1
≥
2
j
m+n+1\geq2j
m+n+1≥2j, 所以
m
/
2
>
m
−
j
+
r
≥
j
−
n
−
1
+
r
,
m/2> m-j+r\geq j-n-1+r,
m/2>m−j+r≥j−n−1+r,
因此
b
j
−
r
−
b
j
−
n
−
1
+
r
=
b
m
−
j
+
r
−
b
j
−
n
−
1
+
r
≥
0
b_{j-r}-b_{j-n-1+r}=b_{m-j+r}-b_{j-n-1+r}\geq0
bj−r−bj−n−1+r=bm−j+r−bj−n−1+r≥0
于是,
∀
j
∈
[
1
,
(
m
+
n
)
/
2
]
,
c
j
−
c
j
−
1
≥
0.
\forall j\in[1, (m+n)/2], c_j-c_{j-1}\geq0.
∀j∈[1,(m+n)/2],cj−cj−1≥0.
总结
主要用到了单峰的定义: 达到峰点之前都是递增序列, 并且由于对称性, 可以进一步展开系数, 代入找到乘积多项式的系数表示即可.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
