A generalization of Chebyshev polynomials and non rooted
posets
Masaya Tomie
tomie@math.tsukuba.ac.jp
In this paper we give a generalization of Chebyshev polynomials and using this we describe
the Mobius function of the generalized subword order derived from a poset {a1, · · · as, c | ai <
c for i = 1, · · · s}, which contains an affirmative answer for the conjecture by Björner, Sagan and
Vatter.(cf,[5] [10])
1 INTRODUCTION
Björner was the first to determine the Möbius functions of factor orders and subword orders. To
determine the Möbius functions, he used involutions, shellability, and generating functions. [2][3][4]
Björner and Stanley found an interesting relation among the subword order derived from a two
point set {a, b} , symmetric groups and composition orders. [6]
Factor orders, subword orders, and generalized subword orders were studied in the context of
Möbius functions derived from word orders.
In [10] Sagan and Vatter gave a description of the Möbius function of the generalized subword
order derived from positive integers in two ways, namely the sign reversing involution and the dis-
crete Morse theory. More generally they gave a combinatorial description of the Möbius functions
derived from rooted forests. And in [5][10] they gave a very interesting conjecture which connects
with the relation between a non-rooted forest P2 as in Notation.1 and Chebyshev polynomials.
Conjecture 1 ([5][10])
We put P := {a, b, c, | a < c, b < c }, and consider the poset P ∗ consisting of finite words of P
with its generalized subword order. Let µ be a Möbius function of P ∗. Suppose 0 ≤ i ≤ j.
Then µ(ai, cj) is the coefficient of Xj−i in Ti+j(X).
Now we call {Tn(X) | n ∈ N} Chebyshev polynomials of first kind.
A series of Chebyshev polynomials {T (X) | n ∈ N} is a system of orthogonal polynomials and
induces a special case of hypergeometric functions as a generalization of a binomial series. And
this polynomial series is an example of the best approximation polynomials.
Not only in analysis, but in combinatorics, Chebyshev polynomials appear in permutation
pattern avoidances [7] and Chebyshev posets, Chebyshev transformations defined by Hetyei which
are related to cd-indeices, f -vectors and h-vectors respectively.
In this paper we give a natural generalization of Chebyshev polynomials in the following way.
Definition 1 (generalized Chebyshev polynomials)
We define the polynomial T sk (X) for s, k ∈ N as follows:
(1) T s0 (X) = 1, T
1 (X) = (s− 1)X ,
(2) T sk+2(X) + T
k (X) = sX · T
k+1(X).
Now the T 2n(X) are Chebyshev polynomials of first kind. And notice deg(T
k (X)) = k.
Then, using generalized Chebyshev polynomials, we generalize the conjecture as follows.
http://arxiv.org/abs/0704.0685v2
Theorem 1
Let Ps be a poset as Notation.1 and µ be the Möbius function of P
s . Then for 0 ≤ m ≤ n ,
µ(am1 , c
n) is the coefficient of Xn−m in T sm+n(x).
2 PRELIMINERIES
In this section, we give some basic definitions and notations used in this paper. For the basic
definitions of posets and Möbius functions, see [12] and for the definitions of subword orders and
generalized subword orders, see [2] [3] [4] [5] [10]. First we recall a path in a poset P .[12]
Definition 2 ([12])
Let P be a poset. An arranged sequence (θ1, · · · , θr) with θi ∈ P and θ1 < · · · < θr, is called a
path of length r − 1 . We denote it by (θ1 → · · · → θr)p
Proposition 1 ([12])
Let P be a locally finite poset, µ be a Möbius function of P and Ck be the number of paths of P
of length k respectively. Then we have
µ(u, v) = Σk(−1)
kCk, for all u ≤ v ∈ P .
Definition 3 ([10])
Let P ∗ be the poset with the subword order derived from a poset P . We take p1, · · · pk and q1 · · · ql
from P ∗. If p1 · · · pk ≤ q1 · · · ql as a subword order, we call S(j1, · · · , jk) (j1 < · · · < jk), an
embedding of p1 · · · pk into q1 · · · ql if pi ≤ qji for 1 ≤ i ≤ k
And an embedding S(j1, · · · , jk) is called the right most embedding of p1 · · · pk into q1 · · · ql, if
for any embedding S′(j′1, · · · , j
k) , we have j
i ≤ ji for all 1 ≤ i ≤ k.
Notation 1
In this paper we fix a poset Ps for s ∈ N as follows.
Ps := {a1, · · ·as, c | ai < c, for i = 1, · · · s}}
Definition 4
We define as follows.
Let P ∗s be a poset with the generalized subword order derived from a poset Ps as in Notation
1 and let X be a set of the paths of P .
Put Mob(X) := Σk≥1Ck, where Ck is the number of paths in X whose length is k. Also we
define
{akcl} := {p1 · · · pk+l | ♯{p1, · · · , pk+l} ∩ {a1, · · · as} = k, ♯{p1, · · · , pk+l} ∩ {c} = l} for k, l ∈
N ∪ {0},
< p1 · · · pk, {a
lcm} >:= {q1 · · · ql+m ∈ {a
lcm} | p1 · · · pk ≤ q1 · · · ql+m} for k, l ∈ N ∪ {0}, and
Pat{p1 · · · pk, q1 · · · ql} := {(p1 · · · pk → θ1 →, · · · → θr → q1 · · · ql)p | p1 · · · pk < θ1 < · · · <
θr < q1 · · · ql, |θi| = l} respectively. Here |θ| is the number of letters of θ.
Definition 5 (generalized Chebyshev polynomial)
We define the polynomial T sk (X) s, k ∈ N as follows:
(1) T s0 (X) = 1, T
1 (X) = (s− 1)X ,
(2) T sk+2(X) + T
k (X) = sX · T
k+1(X).
Now the {T 2n(X) | n ∈ N} are Chebyshev polynomials of first kind. And notice deg(T
k (X)) = k.
Here we give a simple expression of the generalized Chebyshev polynomials.
Proposition 2
For s, n ∈ N, we have
T sn(X) = Σm≤n, n−m:even(−1)
(n−m)/2
(n+m)/2
(n−m)/2
) · sm − (
(n+m)/2− 1
(n−m)/2
) · sm−1
PROOF
We show the above formula by induction. It is easy to see T s0 (X) = 1, T
1 (X) = (s−1)X . Now
we have
T sn + T
= Σm≤n, n−m:even(−1)
(n−m)/2
(n+m)/2
(n−m)/2
) · sm − (
(n+m)/2− 1
(n−m)/2
) · sm−1
+Σm≤n+2, n+2−m:even(−1)
(n+2−m)/2
(n+ 2 +m)/2
(n+ 2−m)/2
) · sm − (
(n+ 2 +m)/2− 1
(n+ 2−m)/2
) · sm−1
) · sn+2 − (
) · sn+1
·Xn+2
+Σm≤n, n−m:even(−1)
(n−m)/2+1
(n+m)/2
(n−m)/2 + 1
) · sm − (
(n+m)/2− 1
(n−m)/2 + 1
) · sm−1
= sn+1(s− 1)Xn+2
+Σm≤n−1, n−1−m:even(−1)
(n−m−1)/2+1
(n+m+ 1)/2
(n−m− 1)/2 + 1
) · sm+1 − (
(n+m+ 1)/2− 1
(n−m− 1)/2 + 1
) · sm
·Xm+1
sn(s− 1)Xn+1
+Σm≤n−1, n−1−m:even(−1)
(n+1−m)/2
(n+ 1 +m)/2
(n+ 1−m)/2
) · sm − (
(n+ 1 +m)/2− 1
(n+ 1−m)/2
) · sm−1
= sX · T sn+1.
Hence we obtain the derived result. ✷
3 MAIN RESULTS
In this section, we give a proof of Theorem 1
Lemma 1
Let P be a finite poset and we take an element x ∈ P . We put as follows:
P≤x := {y | y ≤ x} , P̂≤x := {(θ1 → · · · → θr−1 → x)p | θi ∈ P} , P≥x := {y | y ≥ x} , P̂≥x :=
{x → θ1 → · · · → θr−1)p | θi ∈ P} and Px := {(· · · → τr → x → σ1 → · · ·) | τi ≤ x, σi ≥ x }.
Now a path (x) ∈ P̂≤x, P̂≥x, Px. Then we have MobPx = MobP̂≤x MobP̂≥x.
PROOF
Notice that a path which passes through x splits into the two paths, one starts from x and the
other one ends x. From that we obtain the derived result. ✷
Lemma 2
For m,n, p, q ∈ N∪ {0} such that 0 ≤ m ≤ n, 0 ≤ p ≤ m, 0 ≤ q ≤ n, we take p1 · · · pm, p̃1 · · · p̃m ∈
{am−pcp}. Then we have
♯ < p1 · · · pm, {a
n−qcq} >= ♯ < p̃1 · · · p̃m, {a
n−qcq} >.
PROOF
Claim 1 We have ♯ < p1 · · ·
i−th︷︸︸︷
ax · · · pm, {a
n−qcq} >= ♯ < p1 · · ·
i−th︷︸︸︷
ay · · · pm, {a
n−qcq} >.
(Proof of claim1)
We take ∀q1 · · · qn ∈< p1 · · ·
i−th︷︸︸︷
ax · · · pm, {a
n−qcq} >. And we consider the right most embedding
into q1 · · · qn. Notice that the right most embedding is unique. Here we put S(j1, j2, · · · , jm) as
the right most embedding p1 · · ·
i−th︷︸︸︷
ax · · · pm into q1 · · · qn .
Now we define the map Φ as follows.
Φ < p1 · · ·
i−th︷︸︸︷
ax · · · pm, {a
n−qcq} >−→< p1 · · ·
i−th︷︸︸︷
ay · · · pm, {a
n−qcq} >
Φ(q1q2, · · ·
ji−th︷︸︸︷
ax ax1 · · · axt
ji+1−th︷︸︸︷
pi+1 · · · qn) = q1q2 · · ·
ji−th︷︸︸︷
ay ay1 · · · ayt
ji+1−th︷︸︸︷
pi+1 · · · qn,
Here we put ayk = axk+y−x, and ak+s = ak.
It is easy to see the right most embedding of p1 · · ·
i−th︷︸︸︷
ay · · · pm into Φ(q1 · · · qn) is S(j1, j2, · · · , jm).
And by the construction of Φ, we can easily define the inverse map of Φ. Hence we prove this
claim.
Claim 2 We have ♯ < p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm, {a
n−qcq} >= ♯ < p1 · · ·
i−th︷︸︸︷
(i+1)−th
ax · · · pm, {a
n−qcq} >.
(Proof of claim2)
We take ∀q1 · · · qn ∈< p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm, {a
n−qcq} > and put S(j1, j2, · · · , jm) as the
right most embedding p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm into q1 · · · qn.
Now we define the map Φ as follows.
Φ < p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm, {a
n−qcq} >−→< p1 · · ·
i−th︷︸︸︷
(i+1)−th
ax · · · pm, {a
n−qcq} >,
Φ(q1 · · ·
=ax︷︸︸︷
qji · · ·︸ ︷︷ ︸
=c︷︸︸︷
qji+1 · · ·︸ ︷︷ ︸
qji+2 · · · qn) = q1 · · ·
=c︷︸︸︷
qji+1 · · ·︸ ︷︷ ︸
=ax︷︸︸︷
qji · · ·︸ ︷︷ ︸
qji+2 · · · qn.
Here the right most embedding of p1 · · ·
i−th︷︸︸︷
(i+1)−th
ax · · · pm into q1 · · ·
=c︷︸︸︷
qji+1 · · ·︸ ︷︷ ︸
=a︷︸︸︷
qji · · ·︸ ︷︷ ︸
qji+2 · · · qn
is S(j1 · · · ji, ji+2 + ji − ji+1, ji+2 · · · jm). By the construction, all of the elements of
< p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm, {a
n−qcq} > whose right most embedding are S(j1, j2, · · · , jm), have
one to one correspondence to the elements of < p1 · · ·
i−th︷︸︸︷
(i+1)−th
ax · · · pm, {a
n−qcq} > whose right
most embedding are S(j1 · · · ji, ji+2 + ji − ji+1, ji+2 · · · jm). Hence the Φ is bijeciton. Therefore
we have this claim2. By these claims we obtain the derived result. ✷
From Lemma 2 , if p1 · · · pm ∈ {a
m−pcp}, then
♯ < p1 · · · pm, {a
n−qcq} >= ♯ < a1 · · · a1︸ ︷︷ ︸
(m−p)times
c · · · c︸ ︷︷ ︸
p−times
, {an−qcq} >. So we denote the number as
M((m, p), (n, q)) for all 0 ≤ m ≤ n, 0 ≤ p ≤ m, 0 ≤ q ≤ n.
Lemma 3
Let k, l ∈ N∪ {0}, 0 ≤ k ≤ l and p1 · · · pl ∈ {al−kck}, then we have [p1 · · · pl, cl] ≃ Bl−k. Now Bl−k
is a Boolean algebra of rank l − k.
Lemma 4
For m,n, p, k ∈ N ∪ {0} such that 0 ≤ m ≤ n, 0 ≤ p ≤ m, we take p1 · · · pm ∈ {am−pcp}, then
the number of paths in Pat{p1 · · · pm, c
n} whose length are k equals to the number of paths in
Pat{ a1 · · · a1︸ ︷︷ ︸
(m−p)times
c · · · c︸ ︷︷ ︸
p−times
, cn}.
PROOF
Notice that if we take q1 · · · qn ∈ {a
n−qcq}, then the number of length l paths from q1 · · · qn to
cn equals to the number of length l paths from a1 · · ·a1︸ ︷︷ ︸
(n−q)times
c · · · c︸ ︷︷ ︸
q−times
to cn.
Hence we have
♯{p1 · · · pm → θ1 → · · · → θk = c
n | |θi| = n for i = 1, · · · k}
= Σp≤r≤nM((m, p), (n, r))♯{ a1 · · · a1︸ ︷︷ ︸
(n−r)times
c · · · c︸ ︷︷ ︸
r−times
→ τ1 → · · · → τk−1 = c
n}. (By Lemma 3)
Hence we obtain the derived result.
Lemma 5
For m,n, p ∈ N ∪ {0}, such that 0 ≤ m ≤ n, 0 ≤ p ≤ m, we take p1, · · · pm ∈ {am−pcp}. Then we
MobPat{p1 · · · pm, c
i=0 (−1)
n−p−iM((m, p, ), (n, p+ i)) ifm < n
(−1)n−m ifm = n
PROOF
From Lemma 4 we have MobPat{p1 · · · pm, c
n} = MobPat{ a1 · · · a1︸ ︷︷ ︸
(m−p)times
c · · · c︸ ︷︷ ︸
p−times
, cn}.
Then we have
MobPat{ a1 · · · a1︸ ︷︷ ︸
(m−p)times
c · · · c︸ ︷︷ ︸
p−times
, cn}
= (−1)Σ
i=0 M((m, p), (n, p+ i))µ( a1 · · ·a1︸ ︷︷ ︸
(n−p−i)times
c · · · c︸ ︷︷ ︸
(p+i)times
, cn) (By Proposition 1)
= (−1)Σ
i=0 M((m, p), (n, p+ i))(−1)
n−p−i.
Hence we obtain the derived result. ✷
Lemma 6
For m,n, p, q ∈ N ∪ {0} such that 1 ≤ m ≤ n, 1 ≤ p ≤ m, 1 ≤ q ≤ n, 1 ≤ p ≤ q, we have
M((m, p), (n, q)) = Σn−mi=0 M((m− 1, p− 1), (n− 1− i, q − 1)) · s
PROOF
We have
the left hand side
= ♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn} (By Lemma 2)
= ♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn, xn = c}
+♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn, xn−1 = c, xn 6= c}
· · ·
+♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn, xn−i = c, xn−i+k 6= c(1 ≤ k ≤ i)}
+♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn, xm = c, xm+k 6= c(1 ≤ k ≤ n−m)}
= ♯{ · · ·︸︷︷︸
p−1 ≤ A A ∈ {an−qcq−1}}
+♯{ · · ·︸︷︷︸
c︸︷︷︸
p−1 ≤ A A ∈ {an−q−1cq−1}} · s1
+♯{ · · ·︸︷︷︸
c︸︷︷︸
p−1 ≤ A A ∈ {an−q−icq−1}} · si
+♯{ · · ·︸︷︷︸
c︸︷︷︸
p−1 ≤ A A ∈ {am−qcq−1}} · sn−m
(In case of n− q − i < 0 , we recognize ♯{ · · ·︸︷︷︸
c︸︷︷︸
| am−pcp−1 ≤ A A ∈ an−q−icq−1} as 0.)
= M((m− 1, p− 1), (n− 1, q − 1)) · s0 +M((m− 1, p− 1), (n− 2, q − 1)) · s1 + · · ·
+M((m− 1, p− 1), (n− 1− i, q − 1)) · si · · ·M((m− 1, p− 1), (m− 1, q − 1)) · sn−m
Hence we obtain the derived result. ✷
Lemma 7
For m,n, i ∈ N ∪ {0} such that i ≤ m ≤ n, i ≤ p ≤ q, i ≤ p ≤ m, i ≤ q ≤ n, we have
M((m, p), (n, q)) = Σn−mk=0 M((m− i, p− i), (n− i− k, q − i)) · s
k · (
i+ k − 1
PROOF
In case of i = 1, it is shown by Lemma 6.
We show the above formula by induction. We suppose this lemma holds for i− 1. Now we see
M((m, p), (n, q)) = Σn−mk=0 M((m− i+ 1, p− i+ 1), (n− i− k + 1, q − i+ 1)) · s
i+ k − 2
= Σn−mk=0 (Σ
l=0 M((m− i, p− i), (n− i− k − l, q − i)) · 2
l) · sk(
i+ k − 2
= Σn−mk,l=0M((m− i, p− i), (n− i− (k + l), q − i)) · s
i+ k − 2
= Σn−ik+l=0M((m− i, p− i), (n− i− (k + l), q − i)) · s
i+ k − 2
= Σn−iα=0M((m− i, p− i), (n− i− α, q − i))(Σ
i+ j − 2
)) · sα.
Now we remark the following formula.
Σαx=0(
) = (
i+ α+ 1
hence we have
= Σn−iα=0M((m− i, p− i), (n− i− α, q − i))(Σ
i+ j − 2
)) · sα
= Σn−iα=0M((m− i, p− i), (n− i− α, q − i)) · s
n+ α− 1
Lemma 8
For m,n, p, q ∈ N, 1 ≤ m ≤ n, 1 ≤ p ≤ q, 1 ≤ p ≤ m, 1 ≤ q ≤ n, we have
M((m, p), (n, q)) = Σn−mk=0 M((m− p, 0), (n− p− k, q − p)) · s
k · (
p+ k − 1
Lemma 9
For 1 ≤ α ≤ β, we have
i=0M((α, 0), (β, i)) · (−1)
i = 0.
PROOF
We give a combinatorial proof. We put M̂i :=< a1 · · · a1︸ ︷︷ ︸
α−times
, {aβ−ici} >, M̂ :=
0≤i≤β M̂i,
M̂ev :=
0≤i≤β i; even M̂i and M̂odd :=
0≤i≤β i; odd M̂i.
Then we have Σ
i=0M((α, 0), (β, i)) · (−1)
i = ♯M̂ev − ♯M̂odd.
We consider the map Ψ as follows.
Ψ M̂ −→ M̂
Ψ( · · ·︸︷︷︸
a1ax1 · · ·axt) = · · ·︸︷︷︸
cax1 · · ·axt)
Ψ( · · ·︸︷︷︸
cax1 · · · axt) = · · ·︸︷︷︸
a1ax1 · · ·axt
Ψ( · · ·︸︷︷︸
a1) = · · ·︸︷︷︸
Ψ( · · ·︸︷︷︸
c) = · · ·︸︷︷︸
Here Ψ changes a1 into c and c into a1 which appears right most position of each elements.
Since α not being 0, each element of M̂ contains a1 or c. From that the map Ψ is well-defined.
Therefore obviously Ψ−1 = Ψ and Ψ(M̂ev) = (M̂odd) Ψ(M̂odd) = M̂ev. Hence Ψ is a bijection and
♯M̂ev = ♯M̂odd. Hence we obtain the derived result. ✷
Lemma 10
For m,n, p ∈ N ∪ {0}, 0 ≤ m < n, 0 ≤ p < m, we have
p1 · · · pm ∈ {a
m−pcp} =⇒ MobPat{p1 · · · pm, c
n} = 0.
PROOF
We have
MobPat{p1 · · · pm, c
n} = −Σ
i=0 M((m, p), (n, p+ i)) · (−1)
n−p−i
i=0 (−1)
n−p−iΣn−mk=0 M((m− p, 0), (n− p− k, i)) · s
p+ k − 1
= (−1)n−p−1Σ
i=0 Σ
k=0 M((m− p, 0), (n− p− k, i))(−1)
i · sk(
p+ k − 1
= (−1)n−p−1Σn−mk=0 {Σ
n−p−k
i=0 M((m− p, 0), (n− p− k, i))(−1)
︸ ︷︷ ︸
} · sk(
p+ k − 1
= 0. Hence we obtain the derived result. ✷
Lemma 11
For m,n ∈ N, 1 ≤ m ≤ n, we put
P := {am1 → τ1 → · · · → c
m → θk11 · · · → c
k1 → θk21 · · · → c
k2 → · · · → ckr | m < k1 < · · · <
kr = n, |τi| = m, |θ
j | = ki }, and p1 · · · pm ∈ {a
Then we have µ(p1 · · · pm, c
n) = µ(am1 , c
n) = Mob(P ) = (−1)mµ(cm, cn).
PROOF
We have
µ(p1 · · · pm, c
n) = Mob({(p1 · · · pm → θ1 → · · · θr → c
n) | p1 · · · pm < θ1 < · · · θr < c
Now we put
X l1l2
:= {(p1 · · · pm → · · · θr → τ1 → · · · τs → c
l2 → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 · · · →
cn) | |θr| = l1, θr 6= c
l1 , |τ1|, · · · |τs| = l2, |σ
j | = ki}.
Then we have
{(p1 · · · pm → θ1 → · · · θr → c
n) | p1 · · · pm < θ1 < · · · θr < c
m≤l1<l2≤n
X l1l2⊎
{(p1 · · · pm → · · · → c
m → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 · · · → cn) | |σkij | = ki}.
Now for m ≤ l1 < l2 ≤ n,
Mob(X l1l2 ) =
Σq1···ql1 6=c
l1Mob({(p1 · · · pm → θ1 → · · · → θr → q1 · · · ql1) | p1 · · · pm < θ1 < · · · < q1 · · · ql1})·
Mob({(q1 · · · ql1 → τ1 → · · · → τs → c
l2) | |τi| = l2})·
Mob({(cl2 → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 → · · · → cn) | |σkij | = ki}).
By Lemma 10 , we have
Mob({(q1 · · · ql1 → τ1 → · · · → τs → c
l2) | |τi| = l2}) = 0.
Hence we have Mob(X l1l2 ) = 0
Therefore we have µ(p1, · · · pm, c
Mob({(p1, · · · pm → · · · → c
m → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 · · · → cn) | |σkij | = ki})
= Mob({(p1 · · · pm → θ1 · · · θr → c
m) | |θi| = m})·
Mob({(cm → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 · · · → cn) | |σkij | = ki})
= (−1)m · µ(cm, cn).
Hence we obtain the derived result. ✷
Lemma 12
We have
µ(φ, c) = s− 1, µ(ai, c) = −1, µ(c, c
2) = 2s− 1, µ(ai, c
2) = −2s+ 1.
Now we put T (k, n) := MobPat{ck → θ1 → · · · → θr = c
n | |θi| = n}, T (n, k) = 0 for
0 ≤ k < n, and T (n, n) := −1 for 0 ≤ n .
Lemma 13
For 0 ≤ k ≤ n, we have
T (k, n) = −Σni=k(
) · sn−i · (−1)n−i.
PROOF
In case when k = n, it is trivial.
In case when 0 ≤ k < n, we have
T (k, n) = −Σni=kM((k, k), (n, i)) · (−1)
Now we have
M((k, k), (n, i)) = (
) · sn−i.
Hence we obtain the derived result.
Lemma 14
For 0 ≤ k ≤ l, we have T (k, l)− T (k − 1, l − 1) = −sT (k, l− 1).
PROOF
In case when k = l, it is trivial.
It is enough to show the case of k < l. Then we have
T (k, l)− T (k − 1, l − 1)
= −Σli=k(
) · sl−i · (−1)l−i +Σl−1i=k−1(
l − 1
) · sl−i−1 · (−1)l−i−1
= −Σl−1i=k(
) · sl−i · (−1)l−i − 1 + Σl−2i=k−1(
l − 1
) · sl−i−1 · (−1)l−i−1 + 1
= −Σl−1i=k{(
l − 1
)} · sl−i · (−1)l−i
= −s · Σl−1i=k(
) · sl−i−1 · (−1)l−i−1 = −sT (k, l− 1).
Hence we obtain the derived result. ✷
Lemma 15
Suppose 1 ≤ m < n, then we have
µ(cm, cn) = Σn−1k=mµ(c
m, ck)T (k, n).
PROOF
We heve µ(cm, cn)
= Mob({(cm → σm11 → · · · → c
m1 → σm21 → · · · → c
m2 → · · · cmr−1 → σ
1 · · · → c
cn) | |σmij | = mi}).
In case of 2 ≤ r, we put k = mr−1 and in case of r = 1, we put k = m. By Lemma 1, we obtain
the derived result.
Lemma 16
For 1 ≤ m < n, we have
µ(cm, cn)− µ(cm−1, cn−1) = sµ(cm, cn−1).
PROOF
In case of n = 2, we see µ(c, c2) − µ(φ, c) = (2s − 1) − (s − 1) = s, µ(c, c) = 1 . Hence this
lemma holds for n = 2. holds.
We prove by induction on n. Suppose that the relation holds for n− 1. Then we have
µ(cm, cn)− µ(cm−1, cn−1)
= Σn−1k=mµ(c
m, ck)T (k, n)− Σn−2k=m−1µ(c
m−1, ck)T (k, n− 1)
= Σn−1k=mµ(c
m, ck)T (k, n)− µ(cm, ck)T (k − 1, n− 1) + µ(cm, ck)T (k − 1, n− 1)
−µ(cm−1, ck−1)T (k − 1, n− 1)
= Σn−1k=mµ(c
m, ck)(−s)T (k, n− 1) + sµ(cm, ck−1)T (k − 1, n− 1)
= Σn−1k=mµ(c
m, ck)(−s)T (k, n− 1) + sΣn−1k=m+1µ(c
m, ck−1)T (k − 1, n− 1)
= (−s)µ(cm, cn−1)T (n− 1, n− 1)
= sµ(cm, cn−1).
Lemma 17
For 1 ≤ m ≤ n, we have
µ(am1 , c
n) + µ(am−11 , c
n−1) = sµ(am1 , c
n−1).
PROOF
In case of m < n, we have by Lemma 16. In case of m = n, from am1 � c
n−1, µ(am1 , c
n) = (−1)m
and µ(am−11 , c
n−1) = (−1)m−1, therefore the right hand side = 0. Hence we obtan the derived
result.
Lemma 18
For 1 ≤ m ≤ n, µ(am1 , c
n) is coefficient of Xn−m in T sm+n(X).
PROOF
If m + n = 2, i.e m = n = 1, we have T s2 (X) = s(s − 1)X
2 − 1, µ(a1, c) = −1. Hence this
lemma holds.
If 3 ≤ m+ n, by the relation T sk+2(X) + T
k (X) = sX · T
k+1(X) and Lemma 17 we obtain the
derived result.
Lemma 19
For n ∈ N we heve µ(φ, cn) = sn−1(s− 1).
PROOF
If n = 1, our claim follows from Lemma 12. We show by induction. We suppose that µ(φ, ck) =
sk−1(s− 1) when k ≤ n− 1
Now we have
µ(φ, cn)
= Σnk=1MobPat(φ, c
k)µ(ck, cn) (by Lemma10)
= Σnk=1
−Σki=0s
iM((0, 0), (k, k − i))(−1)i
µ(ck, cn)
= Σnk=1
−Σki=0s
)(−1)i
µ(ck, cn)
= Σnk=1 − (1 − s)
kµ(ck, cn).
And we have
µ(φ, cn)− sµ(φ, cn−1)
= Σnk=1 − (1 − s)
kµ(ck, cn)− Σn−1k=1 − (1− s)
kµ(ck, cn−1)
= Σn−1k=1 − (1− s)
µ(ck, cn)− sµ(ck, cn−1)
− (1− s)n
= Σn−1k=1 − (1− s)
kµ(ck−1, cn−1)− (1− s)n (by Lemma15)
= −(1− s)
Σn−1k=1 (1 − s)
k−1µ(ck−1, cn−1)
− (1 − s)n
= −(1− s)
Σn−2k=0 (1 − s)
kµ(ck, cn−1)
− (1− s)n
= −(1− s)
−µ(φ, cn−1)− µ(φ, cn−1)− (1− s)n−1)
− (1− s)n
So we have µ(φ, cn) = sµ(φ, cn−1). Hence we obtain the derived result. ✷
Lemma 20
For n ∈ N, µ(φ, cn) is the coefficient of Xn in T sn(X).
Therefore we have the following theorem.
Theorem 2
For 0 ≤ m ≤ n , µ(am1 , c
n) is the coefficient of Xn−m in T sm+n(x).
Corollary 1
Conjecture 1 is true.
ACKNOWLEDGEMENT
The author wishes to thank Professor Jun Morita for his valuable advice. And he is also grateful
to Professor Daisuke Sagaki, Sho Matsumoto for their helpful comments.
REFERENCE
[1] Björner,A. Shellable andCohen-Macaulaypartially ordered sets. Trans. Amer. Math. Soc. 260,
1 (1980), 159-183.
[2] Björner,A. TheMobius function of subwordorder. In Invariant theory and tableaux (Min-
neapolis, MN, 1988), vol. 19 of IMA Vol. Math. Appl. Springer, New York, 1990
[3] Björner,A. TheMobius function of factor order. Theoret. Comput. Sci. 117, 1-2 (1993) 91-98
[4] Björner,A.Reutenauer, C.Rationality of theMobius function of subwordorder. Theoret. Com-
put. Sci. 98, 1 (1992), 53-63.
[5] Björner,A. Sagan,B, E.Rationality of theMobius function of the compositionposet. Theoret.
Comput. Sci. 359 (2006), no.1-3, 282-298.
[6] Björner,A. Stanley, R, P.An analogue for compositions. arXiv:math.CO/0508043.
[7] Chow,T.West, J. Forbidden subsequences andChebyshev polynomials. Discrete Math. 204, 1-
3,(1990),119-128.
[8] Ehrenbourg,R.Readdy,M.TheChebyshev transformsof the first and secondkinds.
arXiv:math.CO/0412124.
[9] Hetyei,G.Chebyshev posets.DiscreteComput.Geom.32,4 (2004), 493-520.
[10] Sagan,B, E.Vatter, V.TheMobius function of the composition poset. J. Algebraic, Combin. 24
(2006), no.2,117-136.
[11] Stanley,R, P. Flag f -vectorsand the cd-index. Math. Z. 216,(1994),483-499
[12] Stanley,R, P. Enumerative combinatorics. Vol. 1, vol. 49 of Cambridge Studies in Advanced
Mathematics. Cambridge University Press Cambridge, 1997.
http://arxiv.org/abs/math/0508043
http://arxiv.org/abs/math/0412124
	INTRODUCTION
	PRELIMINERIES
	MAIN RESULTS

  In this paper we give a generalization of Chebyshev polynomials and using
this we describe the M\"obius function of the generalized subword order from a
poset {a1,...as,c |ai<c}, which contains an affirmative answer for the
conjecture by Bj\"orner, Sagan, Vatter.[5,10]

A generalization of Chebyshev polynomials and non rooted
posets
Masaya Tomie
tomie@math.tsukuba.ac.jp
In this paper we give a generalization of Chebyshev polynomials and using this we describe
the Mobius function of the generalized subword order derived from a poset {a1, · · · as, c | ai <
c for i = 1, · · · s}, which contains an affirmative answer for the conjecture by Björner, Sagan and
Vatter.(cf,[5] [10])
1 INTRODUCTION
Björner was the first to determine the Möbius functions of factor orders and subword orders. To
determine the Möbius functions, he used involutions, shellability, and generating functions. [2][3][4]
Björner and Stanley found an interesting relation among the subword order derived from a two
point set {a, b} , symmetric groups and composition orders. [6]
Factor orders, subword orders, and generalized subword orders were studied in the context of
Möbius functions derived from word orders.
In [10] Sagan and Vatter gave a description of the Möbius function of the generalized subword
order derived from positive integers in two ways, namely the sign reversing involution and the dis-
crete Morse theory. More generally they gave a combinatorial description of the Möbius functions
derived from rooted forests. And in [5][10] they gave a very interesting conjecture which connects
with the relation between a non-rooted forest P2 as in Notation.1 and Chebyshev polynomials.
Conjecture 1 ([5][10])
We put P := {a, b, c, | a < c, b < c }, and consider the poset P ∗ consisting of finite words of P
with its generalized subword order. Let µ be a Möbius function of P ∗. Suppose 0 ≤ i ≤ j.
Then µ(ai, cj) is the coefficient of Xj−i in Ti+j(X).
Now we call {Tn(X) | n ∈ N} Chebyshev polynomials of first kind.
A series of Chebyshev polynomials {T (X) | n ∈ N} is a system of orthogonal polynomials and
induces a special case of hypergeometric functions as a generalization of a binomial series. And
this polynomial series is an example of the best approximation polynomials.
Not only in analysis, but in combinatorics, Chebyshev polynomials appear in permutation
pattern avoidances [7] and Chebyshev posets, Chebyshev transformations defined by Hetyei which
are related to cd-indeices, f -vectors and h-vectors respectively.
In this paper we give a natural generalization of Chebyshev polynomials in the following way.
Definition 1 (generalized Chebyshev polynomials)
We define the polynomial T sk (X) for s, k ∈ N as follows:
(1) T s0 (X) = 1, T
1 (X) = (s− 1)X ,
(2) T sk+2(X) + T
k (X) = sX · T
k+1(X).
Now the T 2n(X) are Chebyshev polynomials of first kind. And notice deg(T
k (X)) = k.
Then, using generalized Chebyshev polynomials, we generalize the conjecture as follows.
http://arxiv.org/abs/0704.0685v2
Theorem 1
Let Ps be a poset as Notation.1 and µ be the Möbius function of P
s . Then for 0 ≤ m ≤ n ,
µ(am1 , c
n) is the coefficient of Xn−m in T sm+n(x).
2 PRELIMINERIES
In this section, we give some basic definitions and notations used in this paper. For the basic
definitions of posets and Möbius functions, see [12] and for the definitions of subword orders and
generalized subword orders, see [2] [3] [4] [5] [10]. First we recall a path in a poset P .[12]
Definition 2 ([12])
Let P be a poset. An arranged sequence (θ1, · · · , θr) with θi ∈ P and θ1 < · · · < θr, is called a
path of length r − 1 . We denote it by (θ1 → · · · → θr)p
Proposition 1 ([12])
Let P be a locally finite poset, µ be a Möbius function of P and Ck be the number of paths of P
of length k respectively. Then we have
µ(u, v) = Σk(−1)
kCk, for all u ≤ v ∈ P .
Definition 3 ([10])
Let P ∗ be the poset with the subword order derived from a poset P . We take p1, · · · pk and q1 · · · ql
from P ∗. If p1 · · · pk ≤ q1 · · · ql as a subword order, we call S(j1, · · · , jk) (j1 < · · · < jk), an
embedding of p1 · · · pk into q1 · · · ql if pi ≤ qji for 1 ≤ i ≤ k
And an embedding S(j1, · · · , jk) is called the right most embedding of p1 · · · pk into q1 · · · ql, if
for any embedding S′(j′1, · · · , j
k) , we have j
i ≤ ji for all 1 ≤ i ≤ k.
Notation 1
In this paper we fix a poset Ps for s ∈ N as follows.
Ps := {a1, · · ·as, c | ai < c, for i = 1, · · · s}}
Definition 4
We define as follows.
Let P ∗s be a poset with the generalized subword order derived from a poset Ps as in Notation
1 and let X be a set of the paths of P .
Put Mob(X) := Σk≥1Ck, where Ck is the number of paths in X whose length is k. Also we
define
{akcl} := {p1 · · · pk+l | ♯{p1, · · · , pk+l} ∩ {a1, · · · as} = k, ♯{p1, · · · , pk+l} ∩ {c} = l} for k, l ∈
N ∪ {0},
< p1 · · · pk, {a
lcm} >:= {q1 · · · ql+m ∈ {a
lcm} | p1 · · · pk ≤ q1 · · · ql+m} for k, l ∈ N ∪ {0}, and
Pat{p1 · · · pk, q1 · · · ql} := {(p1 · · · pk → θ1 →, · · · → θr → q1 · · · ql)p | p1 · · · pk < θ1 < · · · <
θr < q1 · · · ql, |θi| = l} respectively. Here |θ| is the number of letters of θ.
Definition 5 (generalized Chebyshev polynomial)
We define the polynomial T sk (X) s, k ∈ N as follows:
(1) T s0 (X) = 1, T
1 (X) = (s− 1)X ,
(2) T sk+2(X) + T
k (X) = sX · T
k+1(X).
Now the {T 2n(X) | n ∈ N} are Chebyshev polynomials of first kind. And notice deg(T
k (X)) = k.
Here we give a simple expression of the generalized Chebyshev polynomials.
Proposition 2
For s, n ∈ N, we have
T sn(X) = Σm≤n, n−m:even(−1)
(n−m)/2
(n+m)/2
(n−m)/2
) · sm − (
(n+m)/2− 1
(n−m)/2
) · sm−1
PROOF
We show the above formula by induction. It is easy to see T s0 (X) = 1, T
1 (X) = (s−1)X . Now
we have
T sn + T
= Σm≤n, n−m:even(−1)
(n−m)/2
(n+m)/2
(n−m)/2
) · sm − (
(n+m)/2− 1
(n−m)/2
) · sm−1
+Σm≤n+2, n+2−m:even(−1)
(n+2−m)/2
(n+ 2 +m)/2
(n+ 2−m)/2
) · sm − (
(n+ 2 +m)/2− 1
(n+ 2−m)/2
) · sm−1
) · sn+2 − (
) · sn+1
·Xn+2
+Σm≤n, n−m:even(−1)
(n−m)/2+1
(n+m)/2
(n−m)/2 + 1
) · sm − (
(n+m)/2− 1
(n−m)/2 + 1
) · sm−1
= sn+1(s− 1)Xn+2
+Σm≤n−1, n−1−m:even(−1)
(n−m−1)/2+1
(n+m+ 1)/2
(n−m− 1)/2 + 1
) · sm+1 − (
(n+m+ 1)/2− 1
(n−m− 1)/2 + 1
) · sm
·Xm+1
sn(s− 1)Xn+1
+Σm≤n−1, n−1−m:even(−1)
(n+1−m)/2
(n+ 1 +m)/2
(n+ 1−m)/2
) · sm − (
(n+ 1 +m)/2− 1
(n+ 1−m)/2
) · sm−1
= sX · T sn+1.
Hence we obtain the derived result. ✷
3 MAIN RESULTS
In this section, we give a proof of Theorem 1
Lemma 1
Let P be a finite poset and we take an element x ∈ P . We put as follows:
P≤x := {y | y ≤ x} , P̂≤x := {(θ1 → · · · → θr−1 → x)p | θi ∈ P} , P≥x := {y | y ≥ x} , P̂≥x :=
{x → θ1 → · · · → θr−1)p | θi ∈ P} and Px := {(· · · → τr → x → σ1 → · · ·) | τi ≤ x, σi ≥ x }.
Now a path (x) ∈ P̂≤x, P̂≥x, Px. Then we have MobPx = MobP̂≤x MobP̂≥x.
PROOF
Notice that a path which passes through x splits into the two paths, one starts from x and the
other one ends x. From that we obtain the derived result. ✷
Lemma 2
For m,n, p, q ∈ N∪ {0} such that 0 ≤ m ≤ n, 0 ≤ p ≤ m, 0 ≤ q ≤ n, we take p1 · · · pm, p̃1 · · · p̃m ∈
{am−pcp}. Then we have
♯ < p1 · · · pm, {a
n−qcq} >= ♯ < p̃1 · · · p̃m, {a
n−qcq} >.
PROOF
Claim 1 We have ♯ < p1 · · ·
i−th︷︸︸︷
ax · · · pm, {a
n−qcq} >= ♯ < p1 · · ·
i−th︷︸︸︷
ay · · · pm, {a
n−qcq} >.
(Proof of claim1)
We take ∀q1 · · · qn ∈< p1 · · ·
i−th︷︸︸︷
ax · · · pm, {a
n−qcq} >. And we consider the right most embedding
into q1 · · · qn. Notice that the right most embedding is unique. Here we put S(j1, j2, · · · , jm) as
the right most embedding p1 · · ·
i−th︷︸︸︷
ax · · · pm into q1 · · · qn .
Now we define the map Φ as follows.
Φ < p1 · · ·
i−th︷︸︸︷
ax · · · pm, {a
n−qcq} >−→< p1 · · ·
i−th︷︸︸︷
ay · · · pm, {a
n−qcq} >
Φ(q1q2, · · ·
ji−th︷︸︸︷
ax ax1 · · · axt
ji+1−th︷︸︸︷
pi+1 · · · qn) = q1q2 · · ·
ji−th︷︸︸︷
ay ay1 · · · ayt
ji+1−th︷︸︸︷
pi+1 · · · qn,
Here we put ayk = axk+y−x, and ak+s = ak.
It is easy to see the right most embedding of p1 · · ·
i−th︷︸︸︷
ay · · · pm into Φ(q1 · · · qn) is S(j1, j2, · · · , jm).
And by the construction of Φ, we can easily define the inverse map of Φ. Hence we prove this
claim.
Claim 2 We have ♯ < p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm, {a
n−qcq} >= ♯ < p1 · · ·
i−th︷︸︸︷
(i+1)−th
ax · · · pm, {a
n−qcq} >.
(Proof of claim2)
We take ∀q1 · · · qn ∈< p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm, {a
n−qcq} > and put S(j1, j2, · · · , jm) as the
right most embedding p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm into q1 · · · qn.
Now we define the map Φ as follows.
Φ < p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm, {a
n−qcq} >−→< p1 · · ·
i−th︷︸︸︷
(i+1)−th
ax · · · pm, {a
n−qcq} >,
Φ(q1 · · ·
=ax︷︸︸︷
qji · · ·︸ ︷︷ ︸
=c︷︸︸︷
qji+1 · · ·︸ ︷︷ ︸
qji+2 · · · qn) = q1 · · ·
=c︷︸︸︷
qji+1 · · ·︸ ︷︷ ︸
=ax︷︸︸︷
qji · · ·︸ ︷︷ ︸
qji+2 · · · qn.
Here the right most embedding of p1 · · ·
i−th︷︸︸︷
(i+1)−th
ax · · · pm into q1 · · ·
=c︷︸︸︷
qji+1 · · ·︸ ︷︷ ︸
=a︷︸︸︷
qji · · ·︸ ︷︷ ︸
qji+2 · · · qn
is S(j1 · · · ji, ji+2 + ji − ji+1, ji+2 · · · jm). By the construction, all of the elements of
< p1 · · ·
i−th︷︸︸︷
(i+1)−th
c · · · pm, {a
n−qcq} > whose right most embedding are S(j1, j2, · · · , jm), have
one to one correspondence to the elements of < p1 · · ·
i−th︷︸︸︷
(i+1)−th
ax · · · pm, {a
n−qcq} > whose right
most embedding are S(j1 · · · ji, ji+2 + ji − ji+1, ji+2 · · · jm). Hence the Φ is bijeciton. Therefore
we have this claim2. By these claims we obtain the derived result. ✷
From Lemma 2 , if p1 · · · pm ∈ {a
m−pcp}, then
♯ < p1 · · · pm, {a
n−qcq} >= ♯ < a1 · · · a1︸ ︷︷ ︸
(m−p)times
c · · · c︸ ︷︷ ︸
p−times
, {an−qcq} >. So we denote the number as
M((m, p), (n, q)) for all 0 ≤ m ≤ n, 0 ≤ p ≤ m, 0 ≤ q ≤ n.
Lemma 3
Let k, l ∈ N∪ {0}, 0 ≤ k ≤ l and p1 · · · pl ∈ {al−kck}, then we have [p1 · · · pl, cl] ≃ Bl−k. Now Bl−k
is a Boolean algebra of rank l − k.
Lemma 4
For m,n, p, k ∈ N ∪ {0} such that 0 ≤ m ≤ n, 0 ≤ p ≤ m, we take p1 · · · pm ∈ {am−pcp}, then
the number of paths in Pat{p1 · · · pm, c
n} whose length are k equals to the number of paths in
Pat{ a1 · · · a1︸ ︷︷ ︸
(m−p)times
c · · · c︸ ︷︷ ︸
p−times
, cn}.
PROOF
Notice that if we take q1 · · · qn ∈ {a
n−qcq}, then the number of length l paths from q1 · · · qn to
cn equals to the number of length l paths from a1 · · ·a1︸ ︷︷ ︸
(n−q)times
c · · · c︸ ︷︷ ︸
q−times
to cn.
Hence we have
♯{p1 · · · pm → θ1 → · · · → θk = c
n | |θi| = n for i = 1, · · · k}
= Σp≤r≤nM((m, p), (n, r))♯{ a1 · · · a1︸ ︷︷ ︸
(n−r)times
c · · · c︸ ︷︷ ︸
r−times
→ τ1 → · · · → τk−1 = c
n}. (By Lemma 3)
Hence we obtain the derived result.
Lemma 5
For m,n, p ∈ N ∪ {0}, such that 0 ≤ m ≤ n, 0 ≤ p ≤ m, we take p1, · · · pm ∈ {am−pcp}. Then we
MobPat{p1 · · · pm, c
i=0 (−1)
n−p−iM((m, p, ), (n, p+ i)) ifm < n
(−1)n−m ifm = n
PROOF
From Lemma 4 we have MobPat{p1 · · · pm, c
n} = MobPat{ a1 · · · a1︸ ︷︷ ︸
(m−p)times
c · · · c︸ ︷︷ ︸
p−times
, cn}.
Then we have
MobPat{ a1 · · · a1︸ ︷︷ ︸
(m−p)times
c · · · c︸ ︷︷ ︸
p−times
, cn}
= (−1)Σ
i=0 M((m, p), (n, p+ i))µ( a1 · · ·a1︸ ︷︷ ︸
(n−p−i)times
c · · · c︸ ︷︷ ︸
(p+i)times
, cn) (By Proposition 1)
= (−1)Σ
i=0 M((m, p), (n, p+ i))(−1)
n−p−i.
Hence we obtain the derived result. ✷
Lemma 6
For m,n, p, q ∈ N ∪ {0} such that 1 ≤ m ≤ n, 1 ≤ p ≤ m, 1 ≤ q ≤ n, 1 ≤ p ≤ q, we have
M((m, p), (n, q)) = Σn−mi=0 M((m− 1, p− 1), (n− 1− i, q − 1)) · s
PROOF
We have
the left hand side
= ♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn} (By Lemma 2)
= ♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn, xn = c}
+♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn, xn−1 = c, xn 6= c}
· · ·
+♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn, xn−i = c, xn−i+k 6= c(1 ≤ k ≤ i)}
+♯{x1 · · ·xn ∈ {a
n−qcq} | a
p ≤ x1 · · ·xn, xm = c, xm+k 6= c(1 ≤ k ≤ n−m)}
= ♯{ · · ·︸︷︷︸
p−1 ≤ A A ∈ {an−qcq−1}}
+♯{ · · ·︸︷︷︸
c︸︷︷︸
p−1 ≤ A A ∈ {an−q−1cq−1}} · s1
+♯{ · · ·︸︷︷︸
c︸︷︷︸
p−1 ≤ A A ∈ {an−q−icq−1}} · si
+♯{ · · ·︸︷︷︸
c︸︷︷︸
p−1 ≤ A A ∈ {am−qcq−1}} · sn−m
(In case of n− q − i < 0 , we recognize ♯{ · · ·︸︷︷︸
c︸︷︷︸
| am−pcp−1 ≤ A A ∈ an−q−icq−1} as 0.)
= M((m− 1, p− 1), (n− 1, q − 1)) · s0 +M((m− 1, p− 1), (n− 2, q − 1)) · s1 + · · ·
+M((m− 1, p− 1), (n− 1− i, q − 1)) · si · · ·M((m− 1, p− 1), (m− 1, q − 1)) · sn−m
Hence we obtain the derived result. ✷
Lemma 7
For m,n, i ∈ N ∪ {0} such that i ≤ m ≤ n, i ≤ p ≤ q, i ≤ p ≤ m, i ≤ q ≤ n, we have
M((m, p), (n, q)) = Σn−mk=0 M((m− i, p− i), (n− i− k, q − i)) · s
k · (
i+ k − 1
PROOF
In case of i = 1, it is shown by Lemma 6.
We show the above formula by induction. We suppose this lemma holds for i− 1. Now we see
M((m, p), (n, q)) = Σn−mk=0 M((m− i+ 1, p− i+ 1), (n− i− k + 1, q − i+ 1)) · s
i+ k − 2
= Σn−mk=0 (Σ
l=0 M((m− i, p− i), (n− i− k − l, q − i)) · 2
l) · sk(
i+ k − 2
= Σn−mk,l=0M((m− i, p− i), (n− i− (k + l), q − i)) · s
i+ k − 2
= Σn−ik+l=0M((m− i, p− i), (n− i− (k + l), q − i)) · s
i+ k − 2
= Σn−iα=0M((m− i, p− i), (n− i− α, q − i))(Σ
i+ j − 2
)) · sα.
Now we remark the following formula.
Σαx=0(
) = (
i+ α+ 1
hence we have
= Σn−iα=0M((m− i, p− i), (n− i− α, q − i))(Σ
i+ j − 2
)) · sα
= Σn−iα=0M((m− i, p− i), (n− i− α, q − i)) · s
n+ α− 1
Lemma 8
For m,n, p, q ∈ N, 1 ≤ m ≤ n, 1 ≤ p ≤ q, 1 ≤ p ≤ m, 1 ≤ q ≤ n, we have
M((m, p), (n, q)) = Σn−mk=0 M((m− p, 0), (n− p− k, q − p)) · s
k · (
p+ k − 1
Lemma 9
For 1 ≤ α ≤ β, we have
i=0M((α, 0), (β, i)) · (−1)
i = 0.
PROOF
We give a combinatorial proof. We put M̂i :=< a1 · · · a1︸ ︷︷ ︸
α−times
, {aβ−ici} >, M̂ :=
0≤i≤β M̂i,
M̂ev :=
0≤i≤β i; even M̂i and M̂odd :=
0≤i≤β i; odd M̂i.
Then we have Σ
i=0M((α, 0), (β, i)) · (−1)
i = ♯M̂ev − ♯M̂odd.
We consider the map Ψ as follows.
Ψ M̂ −→ M̂
Ψ( · · ·︸︷︷︸
a1ax1 · · ·axt) = · · ·︸︷︷︸
cax1 · · ·axt)
Ψ( · · ·︸︷︷︸
cax1 · · · axt) = · · ·︸︷︷︸
a1ax1 · · ·axt
Ψ( · · ·︸︷︷︸
a1) = · · ·︸︷︷︸
Ψ( · · ·︸︷︷︸
c) = · · ·︸︷︷︸
Here Ψ changes a1 into c and c into a1 which appears right most position of each elements.
Since α not being 0, each element of M̂ contains a1 or c. From that the map Ψ is well-defined.
Therefore obviously Ψ−1 = Ψ and Ψ(M̂ev) = (M̂odd) Ψ(M̂odd) = M̂ev. Hence Ψ is a bijection and
♯M̂ev = ♯M̂odd. Hence we obtain the derived result. ✷
Lemma 10
For m,n, p ∈ N ∪ {0}, 0 ≤ m < n, 0 ≤ p < m, we have
p1 · · · pm ∈ {a
m−pcp} =⇒ MobPat{p1 · · · pm, c
n} = 0.
PROOF
We have
MobPat{p1 · · · pm, c
n} = −Σ
i=0 M((m, p), (n, p+ i)) · (−1)
n−p−i
i=0 (−1)
n−p−iΣn−mk=0 M((m− p, 0), (n− p− k, i)) · s
p+ k − 1
= (−1)n−p−1Σ
i=0 Σ
k=0 M((m− p, 0), (n− p− k, i))(−1)
i · sk(
p+ k − 1
= (−1)n−p−1Σn−mk=0 {Σ
n−p−k
i=0 M((m− p, 0), (n− p− k, i))(−1)
︸ ︷︷ ︸
} · sk(
p+ k − 1
= 0. Hence we obtain the derived result. ✷
Lemma 11
For m,n ∈ N, 1 ≤ m ≤ n, we put
P := {am1 → τ1 → · · · → c
m → θk11 · · · → c
k1 → θk21 · · · → c
k2 → · · · → ckr | m < k1 < · · · <
kr = n, |τi| = m, |θ
j | = ki }, and p1 · · · pm ∈ {a
Then we have µ(p1 · · · pm, c
n) = µ(am1 , c
n) = Mob(P ) = (−1)mµ(cm, cn).
PROOF
We have
µ(p1 · · · pm, c
n) = Mob({(p1 · · · pm → θ1 → · · · θr → c
n) | p1 · · · pm < θ1 < · · · θr < c
Now we put
X l1l2
:= {(p1 · · · pm → · · · θr → τ1 → · · · τs → c
l2 → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 · · · →
cn) | |θr| = l1, θr 6= c
l1 , |τ1|, · · · |τs| = l2, |σ
j | = ki}.
Then we have
{(p1 · · · pm → θ1 → · · · θr → c
n) | p1 · · · pm < θ1 < · · · θr < c
m≤l1<l2≤n
X l1l2⊎
{(p1 · · · pm → · · · → c
m → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 · · · → cn) | |σkij | = ki}.
Now for m ≤ l1 < l2 ≤ n,
Mob(X l1l2 ) =
Σq1···ql1 6=c
l1Mob({(p1 · · · pm → θ1 → · · · → θr → q1 · · · ql1) | p1 · · · pm < θ1 < · · · < q1 · · · ql1})·
Mob({(q1 · · · ql1 → τ1 → · · · → τs → c
l2) | |τi| = l2})·
Mob({(cl2 → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 → · · · → cn) | |σkij | = ki}).
By Lemma 10 , we have
Mob({(q1 · · · ql1 → τ1 → · · · → τs → c
l2) | |τi| = l2}) = 0.
Hence we have Mob(X l1l2 ) = 0
Therefore we have µ(p1, · · · pm, c
Mob({(p1, · · · pm → · · · → c
m → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 · · · → cn) | |σkij | = ki})
= Mob({(p1 · · · pm → θ1 · · · θr → c
m) | |θi| = m})·
Mob({(cm → σk11 → · · · → c
k1 → σk21 → · · · → c
k2 · · · → cn) | |σkij | = ki})
= (−1)m · µ(cm, cn).
Hence we obtain the derived result. ✷
Lemma 12
We have
µ(φ, c) = s− 1, µ(ai, c) = −1, µ(c, c
2) = 2s− 1, µ(ai, c
2) = −2s+ 1.
Now we put T (k, n) := MobPat{ck → θ1 → · · · → θr = c
n | |θi| = n}, T (n, k) = 0 for
0 ≤ k < n, and T (n, n) := −1 for 0 ≤ n .
Lemma 13
For 0 ≤ k ≤ n, we have
T (k, n) = −Σni=k(
) · sn−i · (−1)n−i.
PROOF
In case when k = n, it is trivial.
In case when 0 ≤ k < n, we have
T (k, n) = −Σni=kM((k, k), (n, i)) · (−1)
Now we have
M((k, k), (n, i)) = (
) · sn−i.
Hence we obtain the derived result.
Lemma 14
For 0 ≤ k ≤ l, we have T (k, l)− T (k − 1, l − 1) = −sT (k, l− 1).
PROOF
In case when k = l, it is trivial.
It is enough to show the case of k < l. Then we have
T (k, l)− T (k − 1, l − 1)
= −Σli=k(
) · sl−i · (−1)l−i +Σl−1i=k−1(
l − 1
) · sl−i−1 · (−1)l−i−1
= −Σl−1i=k(
) · sl−i · (−1)l−i − 1 + Σl−2i=k−1(
l − 1
) · sl−i−1 · (−1)l−i−1 + 1
= −Σl−1i=k{(
l − 1
)} · sl−i · (−1)l−i
= −s · Σl−1i=k(
) · sl−i−1 · (−1)l−i−1 = −sT (k, l− 1).
Hence we obtain the derived result. ✷
Lemma 15
Suppose 1 ≤ m < n, then we have
µ(cm, cn) = Σn−1k=mµ(c
m, ck)T (k, n).
PROOF
We heve µ(cm, cn)
= Mob({(cm → σm11 → · · · → c
m1 → σm21 → · · · → c
m2 → · · · cmr−1 → σ
1 · · · → c
cn) | |σmij | = mi}).
In case of 2 ≤ r, we put k = mr−1 and in case of r = 1, we put k = m. By Lemma 1, we obtain
the derived result.
Lemma 16
For 1 ≤ m < n, we have
µ(cm, cn)− µ(cm−1, cn−1) = sµ(cm, cn−1).
PROOF
In case of n = 2, we see µ(c, c2) − µ(φ, c) = (2s − 1) − (s − 1) = s, µ(c, c) = 1 . Hence this
lemma holds for n = 2. holds.
We prove by induction on n. Suppose that the relation holds for n− 1. Then we have
µ(cm, cn)− µ(cm−1, cn−1)
= Σn−1k=mµ(c
m, ck)T (k, n)− Σn−2k=m−1µ(c
m−1, ck)T (k, n− 1)
= Σn−1k=mµ(c
m, ck)T (k, n)− µ(cm, ck)T (k − 1, n− 1) + µ(cm, ck)T (k − 1, n− 1)
−µ(cm−1, ck−1)T (k − 1, n− 1)
= Σn−1k=mµ(c
m, ck)(−s)T (k, n− 1) + sµ(cm, ck−1)T (k − 1, n− 1)
= Σn−1k=mµ(c
m, ck)(−s)T (k, n− 1) + sΣn−1k=m+1µ(c
m, ck−1)T (k − 1, n− 1)
= (−s)µ(cm, cn−1)T (n− 1, n− 1)
= sµ(cm, cn−1).
Lemma 17
For 1 ≤ m ≤ n, we have
µ(am1 , c
n) + µ(am−11 , c
n−1) = sµ(am1 , c
n−1).
PROOF
In case of m < n, we have by Lemma 16. In case of m = n, from am1 � c
n−1, µ(am1 , c
n) = (−1)m
and µ(am−11 , c
n−1) = (−1)m−1, therefore the right hand side = 0. Hence we obtan the derived
result.
Lemma 18
For 1 ≤ m ≤ n, µ(am1 , c
n) is coefficient of Xn−m in T sm+n(X).
PROOF
If m + n = 2, i.e m = n = 1, we have T s2 (X) = s(s − 1)X
2 − 1, µ(a1, c) = −1. Hence this
lemma holds.
If 3 ≤ m+ n, by the relation T sk+2(X) + T
k (X) = sX · T
k+1(X) and Lemma 17 we obtain the
derived result.
Lemma 19
For n ∈ N we heve µ(φ, cn) = sn−1(s− 1).
PROOF
If n = 1, our claim follows from Lemma 12. We show by induction. We suppose that µ(φ, ck) =
sk−1(s− 1) when k ≤ n− 1
Now we have
µ(φ, cn)
= Σnk=1MobPat(φ, c
k)µ(ck, cn) (by Lemma10)
= Σnk=1
−Σki=0s
iM((0, 0), (k, k − i))(−1)i
µ(ck, cn)
= Σnk=1
−Σki=0s
)(−1)i
µ(ck, cn)
= Σnk=1 − (1 − s)
kµ(ck, cn).
And we have
µ(φ, cn)− sµ(φ, cn−1)
= Σnk=1 − (1 − s)
kµ(ck, cn)− Σn−1k=1 − (1− s)
kµ(ck, cn−1)
= Σn−1k=1 − (1− s)
µ(ck, cn)− sµ(ck, cn−1)
− (1− s)n
= Σn−1k=1 − (1− s)
kµ(ck−1, cn−1)− (1− s)n (by Lemma15)
= −(1− s)
Σn−1k=1 (1 − s)
k−1µ(ck−1, cn−1)
− (1 − s)n
= −(1− s)
Σn−2k=0 (1 − s)
kµ(ck, cn−1)
− (1− s)n
= −(1− s)
−µ(φ, cn−1)− µ(φ, cn−1)− (1− s)n−1)
− (1− s)n
So we have µ(φ, cn) = sµ(φ, cn−1). Hence we obtain the derived result. ✷
Lemma 20
For n ∈ N, µ(φ, cn) is the coefficient of Xn in T sn(X).
Therefore we have the following theorem.
Theorem 2
For 0 ≤ m ≤ n , µ(am1 , c
n) is the coefficient of Xn−m in T sm+n(x).
Corollary 1
Conjecture 1 is true.
ACKNOWLEDGEMENT
The author wishes to thank Professor Jun Morita for his valuable advice. And he is also grateful
to Professor Daisuke Sagaki, Sho Matsumoto for their helpful comments.
REFERENCE
[1] Björner,A. Shellable andCohen-Macaulaypartially ordered sets. Trans. Amer. Math. Soc. 260,
1 (1980), 159-183.
[2] Björner,A. TheMobius function of subwordorder. In Invariant theory and tableaux (Min-
neapolis, MN, 1988), vol. 19 of IMA Vol. Math. Appl. Springer, New York, 1990
[3] Björner,A. TheMobius function of factor order. Theoret. Comput. Sci. 117, 1-2 (1993) 91-98
[4] Björner,A.Reutenauer, C.Rationality of theMobius function of subwordorder. Theoret. Com-
put. Sci. 98, 1 (1992), 53-63.
[5] Björner,A. Sagan,B, E.Rationality of theMobius function of the compositionposet. Theoret.
Comput. Sci. 359 (2006), no.1-3, 282-298.
[6] Björner,A. Stanley, R, P.An analogue for compositions. arXiv:math.CO/0508043.
[7] Chow,T.West, J. Forbidden subsequences andChebyshev polynomials. Discrete Math. 204, 1-
3,(1990),119-128.
[8] Ehrenbourg,R.Readdy,M.TheChebyshev transformsof the first and secondkinds.
arXiv:math.CO/0412124.
[9] Hetyei,G.Chebyshev posets.DiscreteComput.Geom.32,4 (2004), 493-520.
[10] Sagan,B, E.Vatter, V.TheMobius function of the composition poset. J. Algebraic, Combin. 24
(2006), no.2,117-136.
[11] Stanley,R, P. Flag f -vectorsand the cd-index. Math. Z. 216,(1994),483-499
[12] Stanley,R, P. Enumerative combinatorics. Vol. 1, vol. 49 of Cambridge Studies in Advanced
Mathematics. Cambridge University Press Cambridge, 1997.
http://arxiv.org/abs/math/0508043
http://arxiv.org/abs/math/0412124
	INTRODUCTION
	PRELIMINERIES
	MAIN RESULTS
