The Face Vector of a Half-Open Hypersimplex

Takayuki Hibi

Department of Pure and Applied Mathematics Graduate School of Information Science and Technology

Osaka University Toyonaka, Osaka 560-0043

Japan

hibi@math.sci.osaka-u.ac.jp

Nan Li

Department of Mathematics Massachusetts Institute of Technology

Cambridge, MA 02139

USA

nan@math.mit.edu

Hidefumi Ohsugi

Department of Mathematical Sciences

School of Science and Technology Kwansei Gakuin University Sanda, Hyogo, 669-1337

Japan

ohsugi@kwansei.ac.jp

Abstract The half-open hypersimplex Δ′_{n,k} consists of those (x_{1}, …, x_{n}) ∈ [0, 1]^{n} with k−1 < x_{1} + ⋯ + x_{n} ≤ k, where 0 < k ≤ n. In this paper, we study the f-vector of a half-open hypersimplex and its generating functions.

1 Introduction

A hypersimplex is one of the most basic polytopes and has been well studied. Stanley [8, p. 49] gave a geometric proof that the normalized volume of the hypersimplex is the Eulerian number. De Loera, Sturmfels and Thomas [2] studied a natural connection of the hypersimplex with Gröbner bases. Lam and Postnikov [4] studied four triangulations of the hypersimplex and showed that these triangulations are identical. Other people have also looked at the Ehrhart h^{∗}-vectors of the hypersimplex. See, e.g., [3, 5]. On the other hand, Li [5] introduced the half-open hypersimplex and proved a conjecture of Stanley on a nice combinatorial description of the Ehrhart h^{∗}-vectors. In this paper, we study the f-vectors of the half-open hypersimplex.

Let k and n be integers with 0 < k ≤ n. We define the hypersimplex Δ_{n,k} and the half-open hypersimplex Δ′_{n,k} as follows:

Δ_{n,k} = { (x_{1}, …, x_{n}) ∈ [0, 1]^{n} : k − 1 ≤ x_{1} + ⋯ + x_{n} ≤ k },
Δ′_{n,k} = { (x_{1}, …, x_{n}) ∈ [0, 1]^{n} : k − 1 < x_{1} + ⋯ + x_{n} ≤ k }.

We call F a face of Δ′_{n,k} if and only if F is a face of Δ_{n,k} and F is not a subset of the hyperplane {(x_{1}, …, x_{n}) : x_{1} + ⋯ + x_{n} = k − 1}. Let f_{j}(Δ_{n,k}) denote the number of j-faces of Δ_{n,k} and let f_{j}(Δ′_{n,k}) denote those of Δ′_{n,k}, where j = 0, 1, …, n. The f-vector of Δ_{n,k} is

f(Δ_{n,k}) = (f_{0}(Δ_{n,k}), f_{1}(Δ_{n,k}), …, f_{n}(Δ_{n,k}))

and that of Δ′_{n,k} is

f(Δ′_{n,k}) = (f_{0}(Δ′_{n,k}), f_{1}(Δ′_{n,k}), …, f_{n}(Δ′_{n,k})).

Ziegler [9, Exercise 38] discussed the computation of the f-vector of Δ_{n,k}. In the present paper we are interested in the f-vector of Δ′_{n,k}.

First, in Section 2, we obtain a formula to compute f(Δ′_{n,k}) (Theorem 2). The formula yields easily a formula to compute f(Δ_{n,k}) (Corollary 4). Section 3 is devoted to the study of generating functions related to f(Δ′_{n,k}) and f(Δ_{n,k}). More precisely, we show that

∑_{n≥1} ∑_{k=1}^{n} ∑_{j=1}^{n} f_{j}(Δ′_{n,k}) x^{k}y^{n−k}t^{j} = \frac{(1 − x)xt}{(1 − x − y)(1 − x − y − xt)(1 − x − y − yt)},

∑_{n≥1} ∑_{k=1}^{n} ∑_{j=1}^{n} f_{j}(Δ_{n,k}) x^{k}y^{n−k}t^{j} = \frac{xt}{(1 − x − y)(1 − x − y − xt)(1 − x − y − yt)},

∑_{k=1}^{n} f_{j}(Δ′_{n,k}) = j · 2^{n−j−1} \frac{n + j + 2}{n + 1} · \binom{n + 1}{j + 1}.

Finally, in Section 4, we propose two open questions.

2 Face numbers of Δ′_{n,k}

In this section, we study the f-vector of Δ′_{n,k}.

Example 1. Since the hyperplanes of Δ′_{n,k} are

H = {(x_{1}, …, x_{n}) ∈ [0, 1]^{n} : x_{1} + ⋯ + x_{n} = k},
H_{i}^{(0)} = {(x_{1}, …, x_{n}) ∈ [0, 1]^{n} : x_{i} = 0} (i = 1, …, n),
H_{i}^{(1)} = {(x_{1}, …, x_{n}) ∈ [0, 1]^{n} : x_{i} = 1} (i = 1, …, n),

it follows that f_{n−1}(Δ′_{n,k}) = 2n + 1 for 2 ≤ k < n (and f_{n−1}(Δ′_{n,1}) = n + 1, f_{n−1}(Δ′_{n,n}) = n). Let us then see an example of f_{n−2}(Δ′_{n,k}) for 2 = k < n. This is equivalent to computing pairs of hyperplanes h_{1}, h_{2} which has (n − 2)-dimensional intersection with Δ′_{n,k}. Here is the enumeration:

• For all n > 2, H_{i}^{(1)} ∩ H_{j}^{(1)} ∩ Δ′_{n,2} = {e_{i} + e_{j}} is 0-dimensional.

• For all n > 2, the dimension of

H_{i}^{(1)} ∩ H_{j}^{(0)} ∩ Δ′_{n,2} = { (x_{1}, …, x_{n}) ∈ [0, 1]^{n} : x_{i} = 1, x_{j} = 0, 0 < ∑_{m∈[n]\{i,j}} x_{m} ≤ 1 }

is n − 2. There are 2\binom{n}{2} such pairs for n > 2.

• The intersection

H_{i}^{(0)} ∩ H_{j}^{(0)} ∩ Δ′_{n,2} = { (x_{1}, …, x_{n}) ∈ [0, 1]^{n} : x_{i} = x_{j} = 0, 1 < ∑_{m∈[n]\{i,j}} x_{m} ≤ 2 }

is (n − 2)-dimensional if n > 3, and empty if n = 3. There are \binom{n}{2} such pairs for n > 3.

• For all n > 2, the dimension of

H ∩ H_{i}^{(1)} ∩ Δ′_{n,2} = { (x_{1}, …, x_{n}) ∈ [0, 1]^{n} : x_{i} = 1, ∑_{m∈[n]\{i}} x_{m} = 1 }

is n − 2.

• The dimension of

H ∩ H_{i}^{(0)} ∩ Δ′_{n,2} = { (x_{1}, …, x_{n}) ∈ [0, 1]^{n} : x_{i} = 0, ∑_{m∈[n]\{i}} x_{m} = 2 }

is n − 2 for n > 3, and 0 for n = 3.

In conclusion, for k = 2 and n ≥ 3, one has

f_{n−2}(Δ′_{n,2}) = \begin{cases}2\binom{n}{2} + n, & if n = 3, \\ 3\binom{n}{2} + 2n, & if n > 3. \end{cases}

(It is easy to see that f_{0}(Δ′_{2,2}) = 1.)

Following the enumeration method in Example 1, one has the following general formula.

Theorem 2. Let 0 < k ≤ n and let f(Δ′_{n,k}) = (f_{0}(Δ′_{n,k}), …, f_{n}(Δ′_{n,k})) denote the f-vector of the half-open hypersimplex Δ′_{n,k}. Then one has f_{0}(Δ′_{n,k}) = \binom{n}{k} and

f_{j}(Δ′_{n,k}) = \binom{n + 1}{j + 1} ∑_{s=max\{0,k−j\}}^{k−1} \binom{n − j}{s}\frac{n − s + 1}{n + 1}

for j = 1, 2, …, n.

Proof. Similar as in Example 1 for f_{n−2}(Δ′_{n,k}) when k = 2, here for general k, f_{n−i}(Δ′_{n,k}) is the number of the i-set {h_{1}, …, h_{i}} which has (n − i)-dimensional intersection with Δ′_{n,k}. There are again two cases: in the formula (1) below, the part of \binom{n}{i} deals with the case H is not included in these i hyperplanes, and the part of \binom{n}{i−1} deals with the case when H is one of the i hyperplanes.

Let us look at the first case carefully, and the second case is enumerated similarly. In the first case, the i-tuple (h_{1}, …, h_{i}) satisfies

h_{1} ∩ ⋯ ∩ h_{i} = (⋂_{α∈I} H_{α}^{(0)}) ∩ (⋂_{β∈J} H_{β}^{(1)})

for some I, J ⊂ [n] such that I ∩ J = ∅ and #(I ∪ J) = i. Let s = #J. Then there are in total \binom{i}{s} such i-tuples. Now the key point is whether the intersection of all these i hyperplanes with Δ′_{n,k} is (n − i)-dimensional or not. Here is their intersection:

\{(x_{1}, …, x_{n}) ∈ [0, 1]^{n} : \begin{matrix}x_{α} = 0 (α ∈ I), x_{β} = 1 (β ∈ J) \\ k − s − 1 < ∑_{m∈[n]\(I∪J)} x_{m} ≤ k − s \end{matrix} \} .

Notice that the intersection is (n − i)-dimensional if and only if

1 ≤ k − s < #([n]\(I ∪ J)) = n − i.

This is exactly why we have max{0, k + i − n} ≤ s ≤ min{k − 1, i} in the summand when counting the above i-tuples. Thus, we have

f_{n−i}(Δ′_{n,k}) = \binom{n}{i} ∑_{s=max\{0,k+i−n\}}^{min\{k−1,i\}} \binom{i}{s} + \binom{n}{i − 1} ∑_{s=max\{0,k+i−n\}}^{min\{k−1,i−1\}} \binom{i − 1}{s}.  (1)

Hence,

f_{j}(Δ′_{n,k}) = \binom{n}{j} ∑_{s=max\{0,k−j\}}^{k−1} \binom{n − j}{s} + \binom{n}{j + 1} ∑_{s=max\{0,k−j\}}^{k−1} \binom{n − j − 1}{s}

= ∑_{s=max\{0,k−j\}}^{k−1} (\binom{n}{j}\binom{n − j}{s} + \binom{n}{j + 1}\binom{n − j − 1}{s})

= ∑_{s=max\{0,k−j\}}^{k−1} \binom{n + 1}{j + 1, s, n − j − s}\frac{n − s + 1}{n + 1}

= \binom{n + 1}{j + 1} ∑_{s=max\{0,k−j\}}^{k−1} \binom{n − j}{s}\frac{n − s + 1}{n + 1}.

Example 3. Let us take k = i = 2 for the equation (1) in Proof of Theorem 2.

• For n = 3, we have max{0, k + i − n} = 1 and min{k − 1, i} = min{k − 1, i − 1} = 1. So f_{n−2}(Δ′_{n,k}) = \binom{n}{2}\binom{2}{1} + \binom{n}{1}\binom{1}{1}.

• For n > 3, we have max{0, k + i − n} = 0 and min{k − 1, i} = min{k − 1, i − 1} = 1. So f_{n−2}(Δ′_{n,k}) = \binom{n}{2} (\binom{2}{0} + \binom{2}{1}) + \binom{n}{1} (\binom{1}{0} + \binom{1}{1}).

This matches Example 1 we computed.

Using the above method, it is not hard to get the f-vector of the hypersimplex Δ_{n,k} from the f-vector of the hypersimplex Δ′_{n,k}.

Corollary 4. Let f(Δ_{n,k}) = (f_{0}(Δ_{n,k}), …, f_{n}(Δ_{n,k})) be the f-vector of the hypersimplex Δ_{n,k} and let f(Δ′_{n,k}) = (f_{0}(Δ′_{n,k}), …, f_{n}(Δ′_{n,k})) be that of the half-open hypersimplex Δ′_{n,k}. Then one has f_{0}(Δ_{n,k}) = \binom{n}{k} + \binom{n}{k−1} and

f_{j}(Δ_{n,k}) = f_{j}(Δ′_{n,k}) + \binom{n}{j + 1} ∑_{s=max\{0,k−1−j\}}^{k−2} \binom{n − j − 1}{s} = \binom{n + 1}{j + 1} ∑_{s=max\{0,k−j\}}^{k−1} \binom{n − j}{s}

for j = 1, 2, …, n.

Proof. The only difference with the half-open hypersimplex is that there is now one more case for the i-tuple {h_{1}, …, h_{i}}, which is when one of them is the hyperplane defined by x_{1} + ⋯ + x_{n} = k − 1. And the set of such i-tuples {h_{1}, …, h_{i}} with (n − i)-dimensional intersection with Δ_{n,k} is exactly the same as the i-tuples {h_{1}, …, h_{i}} in the second case of Proof of Theorem 2 for the half-open hypersimplex Δ′_{n,k−1}, i.e., when the hyperplane defined by x_{1} +⋯+x_{n−1} = k−1 belongs to {h_{1}, …, h_{i}}. The number of such i-tuples is enumerated by the second summand of the equation (1), replacing k by k − 1. Therefore, we obtain the formula

f_{n−i}(Δ_{n,k}) = f_{n−i}(Δ′_{n,k}) + \binom{n}{i − 1} ∑_{s=max\{0,k−1+i−n\}}^{min\{k−2,i−1\}} \binom{i − 1}{s}.

Hence

f_{j}(Δ_{n,k})
= f_{j}(Δ′_{n,k}) + \binom{n}{j + 1} ∑_{s=max\{0,k−1−j\}}^{k−2} \binom{n − j − 1}{s}

= ∑_{s=max\{0,k−j\}}^{k−1} \binom{n + 1}{j + 1, s, n − j − s}\frac{n − s + 1}{n + 1} + ∑_{s=max\{0,k−1−j\}}^{k−2} \binom{n}{j + 1, s, n − 1 − j − s}

= ∑_{s=max\{0,k−j\}}^{k−1} \binom{n + 1}{j + 1, s, n − j − s}\frac{n − s + 1}{n + 1} + ∑_{s=max\{0,k−j\}}^{k−1} \binom{n}{j + 1, s − 1, n − j − s}

= ∑_{s=max\{0,k−j\}}^{k−1} (\binom{n + 1}{j + 1, s, n − j − s} + \binom{n}{j + 1, s − 1, n − j − s} − \binom{n + 1}{j + 1, s, n − j − s}\frac{s}{n + 1})

= ∑_{s=max\{0,k−j\}}^{k−1} \binom{n + 1}{j + 1, s, n − j − s}

= \binom{n + 1}{j + 1} ∑_{s=max\{0,k−j\}}^{k−1} \binom{n − j}{s},

as desired.

3 Generating functions

Next we discuss generating functions which are related to the f-vectors of half-open hypersimplices. Theorem 5. Let f_{j}(Δ′_{n,k}) denote the number of j-faces of Δ′_{n,k}. Then, we have

∑_{n≥1} ∑_{k=1}^{n} ∑_{j=1}^{n} f_{j}(Δ′_{n,k}) x^{k}y^{n−k}t^{j} = \frac{(1 − x)xt}{(1 − x − y)(1 − x − y − xt)(1 − x − y − yt)}.

Proof. The coefficient of x^{k}y^{n−k}t^{j} in

\frac{tx(1 − x)}{(1 − x − y)(1 − x − y − tx)(1 − x − y − ty)}

= \frac{tx(1 − x)}{(1 − x − y)^{3}} · \frac{1}{1 − \frac{tx}{1−x−y}} · \frac{1}{1 − \frac{tx}{1−x−y}}
= \frac{tx(1 − x)}{(1 − x − y)^{3}} (∑_{p≥0} (\frac{tx}{1 − x − y} )^{p}) (∑_{q≥0} (\frac{tx}{1 − x − y} )^{q})
= \frac{tx(1 − x)}{(1 − x − y)^{3}} (∑_{p≥0} ∑_{q≥0} (\frac{t}{1 − x − y} )^{p+q} x^{p}y^{q})
= ∑_{p≥0} ∑_{q≥0} \frac{t^{p+q+1}}{(1 − x − y)^{p+q+3}} (1 − x)x^{p+1}y^{q}

is equal to the coefficient of x^{k}y^{n−k} in

∑_{p=0}^{j−1} \frac{(1 − x)x^{p+1}y^{j−p−1}}{(1 − x − y)^{j+2}}

(since p + q + 1 = j if and only if q = j − p − 1 ≥ 0). It then follows that

∑_{p=0}^{j−1} \frac{(1 − x)x^{p+1}y^{j−p−1}}{(1 − x − y)^{j+2}} = ∑_{p=0}^{j−1}(1 − x)x^{p+1}y^{j−p−1} ∑_{r=0}^{∞} \binom{j + r + 1}{j + 1}(x + y)^{r}
= ∑_{p=0}^{j−1} ∑_{r≥0} ∑_{u=0}^{r}(1 − x)x^{p+1}y^{j−p−1}\binom{j + r + 1}{j + 1}\binom{r}{u}x^{u}y^{r−u}
= ∑_{p=0}^{j−1} ∑_{r≥0} ∑_{u=0}^{r} \binom{j + r + 1}{j + 1}\binom{r}{u}x^{p+u+1}y^{j−p+r−u−1}

− ∑_{p=0}^{j−1} ∑_{r≥0} ∑_{u=0}^{r} \binom{j + r + 1}{j + 1}\binom{r}{u}x^{p+u+2}y^{j−p+r−u−1}.

Note that • x^{p+u+1}y^{j−p+r−u−1} = x^{k}y^{n−k} if and only if p + u + 1 = k and j + r = n ;

• x^{p+u+2}y^{j−p+r−u−1} = x^{k}y^{n−k} if and only if p + u + 2 = k and j + r + 1 = n.

Thus, the coefficient of x^{k}y^{n−k} is

∑_{p=0}^{j−1} ∑_{r=n−j} ∑_{u=k−p−1} \binom{j + r + 1}{j + 1}\binom{r}{u} − ∑_{p=0}^{j−1} ∑_{r=n−j−1} ∑_{u=k−p−2} \binom{j + r + 1}{j + 1}\binom{r}{u}

= ∑_{p=max\{0,k−1−n+j\}}^{min\{j−1,k−1\}} \binom{n + 1}{j + 1}\binom{n − j}{k − p − 1} − ∑_{p=max\{0,k−1−n+j\}}^{min\{j−1,k−1\}} \binom{n}{j + 1}\binom{n − j − 1}{k − p − 2}
= ∑_{s=max\{0,k−j\}}^{min\{k−1,n−j\}} \binom{n + 1}{j + 1}\binom{n − j}{s} − ∑_{s=max\{0,k−j\}}^{min\{k−1,n−j\}} \binom{n}{j + 1}\binom{n − j − 1}{s − 1}
= \binom{n + 1}{j + 1} ∑_{s=max\{0,k−j\}}^{min\{k−1,n−j\}} (\binom{n − j}{s} − \frac{n − j}{n + 1}\binom{n − j − 1}{s − 1})
= \binom{n + 1}{j + 1} ∑_{s=max\{0,k−j\}}^{min\{k−1,n−j\}} \binom{n − j}{s}\frac{n − s + 1}{n + 1},

as desired.

By the proof of Theorem 5, we can show that Corollary 6. Let f_{j}(Δ_{n,k}) denote the number of j-faces of Δ_{n,k}. Then, we have

∑_{n≥1} ∑_{k=1}^{n} ∑_{j=1}^{n} f_{j}(Δ_{n,k}) x^{k}y^{n−k}t^{j} = \frac{xt}{(1 − x − y)(1 − x − y − xt)(1 − x − y − yt)}.

On the other hand, by Theorem 5, we have the f-vector of the hypersimplicial decomposition of the unit cube, and its generating function. Theorem 7. Let f_{j}(Δ′_{n,k}) denote the number of j-faces of the half-open hypersimplex Δ′_{n,k}. Then, we have

∑_{k=1}^{n} f_{j}(Δ′_{n,k}) = j · 2^{n−j−1} \frac{n + j + 2}{n + 1} · \binom{n + 1}{j + 1}

and

∑_{n≥1} ∑_{k=1}^{n} f_{j}(Δ′_{n,k}) x^{n} = \frac{jx^{j}(1 − x)}{(1 − 2x)^{j+2}} .

Proof. By substituting x for y in the equation of Theorem 5, we have

∑_{n≥1} ∑_{k=1}^{n} ∑_{j=1}^{n} f_{j}(Δ′_{n,k}) x^{n}t^{j} = \frac{(1 − x)xt}{(1 − 2x)(1 − 2x − xt)^{2}}

= \frac{(1 − x)xt}{(1 − 2x)^{3}(1 − \frac{x}{1−2x}t)^{2}}

= \frac{(1 − x)xt}{(1 − 2x)^{3}} ∑_{j≥0}(j + 1) (\frac{x}{1 − 2x})^{j} t^{j}.

Thus, we have

∑_{n≥1} ∑_{k=1}^{n} f_{j}(Δ′_{n,k})x^{n} = \frac{x(1 − x)}{(1 − 2x)^{3}} · j (\frac{x}{1 − 2x})^{j−1} = \frac{jx^{j}(1 − x)}{(1 − 2x)^{j+2}} .

Moreover, the coefficient of x^{n} in

\frac{jx^{j}(1 − x)}{(1 − 2x)^{j+2}} = jx^{j}(1 − x) ∑_{m≥0} \binom{m + j + 1}{j + 1}2^{m}x^{m}

= j ∑_{m≥0} \binom{m + j + 1}{j + 1}2^{m}x^{m+j} − j ∑_{m≥0} \binom{m + j + 1}{j + 1}2^{m}x^{m+j+1}

= j ∑_{m≥0} \binom{m + j + 1}{j + 1}2^{m}x^{m+j} − j ∑_{m≥0} \binom{m + j}{j + 1}2^{m−1}x^{m+j}

= j ∑_{m≥0} (2\binom{m + j + 1}{j + 1} − \binom{m + j}{j + 1}) 2^{m−1}x^{m+j}

= j ∑_{m≥0} \frac{m + 2j + 2}{m + j + 1}\binom{m + j + 1}{j + 1}2^{m−1}x^{m+j}

is

j \frac{(n − j) + 2j + 2}{(n − j) + j + 1}\binom{(n − j) + j + 1}{j + 1}2^{(n−j)−1} = j · 2^{n−j−1} \frac{n + j + 2}{n + 1} · \binom{n + 1}{j + 1}.

Geometric proof of Theorem 7. The first equation of Theorem 7 gives the f-vector of the hypersimplicial decomposition of the unit cube. Here we compute this f-vector directly. Similar as the proof of Theorem 2, for f_{j}(Δ′_{n,k}), we count the j-dimensional intersections obtained by (n − j) hyperplanes of the unit cube. There are again two types of such j-faces:

1. Intersections of n − j hyperplanes of the form H_{i}^{(0)} or H_{j}^{(1)}. There are 2^{n−j}\binom{n}{n−j}; 2. Intersections of n − j − 1 hyperplanes of the form H_{i}^{(0)} or H_{j}^{(1)} together with one

more hyperplane defined by ∑_{i=1}^{n} x_{i} = k. Similar to the argument in the proof of Theorem 2, we can see that each combination of the n − j − 1 hyperplanes intersects nontrivially (i.e., get j-dimensional intersection) with exactly j hyperplanes of the form ∑_{i=1}^{n} x_{i} = k. In fact, for a given choice of n − j − 1 hyperplanes of the form H_{i}^{(0)} or H_{j}^{(1)}, let s be the number of indices m with H_{m}^{(1)}, then above j hyperplanes correspond to k = s + 1, …, s + j. Therefore, there are j · 2^{n−j−1}\binom{n}{n−j−1} such j-faces.

Now comes a tricky part: the correct number of first type j-faces should be 2^{n−j}\binom{n}{n−j} times j. This is because there are exactly (j − 1) (j − 1)-faces in the interior of each such j-faces, resulting in j j-faces. Consider f_{2} for the three dimensional cube for a visual help. Therefore, there are in total

2^{n−j}\binom{n}{n − j} · j + j · 2^{n−j−1}\binom{n}{n − j − 1} = j · 2^{n−j−1} \frac{n + j + 2}{n + 1} · \binom{n + 1}{j + 1}

j-faces in the hypersimplicial decomposition of the unit cube.

4 Two open questions

In this section, we present two open questions related with Theorem 7.

First, notice that in the above geometric proof for Theorem 7, we get the result as a sum of two parts. Since the result of Theorem 7 is neat and simple, it would be very nice to have a direct combinatorial proof avoiding sums.

Question 8. Find a combinatorial proof for Theorem 7.

We also observe a relation between Theorem 7 and the coefficients of Chebyshev polynomials. It is known that, for ℓ > 0, the Chebyshev polynomials T_{ℓ}(x) of the first kind satisfies

T_{ℓ}(x) = \frac{ℓ}{2} ∑_{m=0}^{⌊ \frac{ℓ}{2} ⌋}(−1)^{m} \frac{(ℓ − m − 1)!}{m!(ℓ − 2m)!}(2x)^{ℓ−2m}

= ∑_{m=0}^{⌊ \frac{ℓ}{2} ⌋}(−1)^{m} \frac{ℓ}{ℓ − m}\binom{ℓ − m}{m}2^{ℓ−2m−1}x^{ℓ−2m}.

On the other hand, we proved that

\frac{1}{j} ∑_{k=1}^{n} f_{j}(Δ′_{n,k}) = 2^{n−j−1} \frac{n + j + 2}{n + 1}\binom{n + 1}{j + 1}.

Thus, for j = m − 1 and n = ℓ − m − 1, we have

\frac{1}{j} ∑_{k=1}^{n} f_{j}(Δ′_{n,k}) = 2^{ℓ−2m−1} \frac{ℓ}{ℓ − m}\binom{ℓ − m}{m}

which is the absolute value of the coefficient of x^{ℓ−2m} in T_{ℓ}(x). There are some known combinatorial models for Chebyshev polynomials such as [1, 6, 7], but their connection with f-vectors studied here is not clear to us.

Question 9. Find a combinatorial connection between Chebyshev polynomials and the sum of f-vectors for the half-open hypersimplex, or equivalently, the f-vectors of the hypersimplicial decomposition of the unit cube.

5 Acknowledgment

We want to thank Professor Richard Stanley for very helpful comments on our work.

References

[1] A. Benjamin and D. Walton, Counting on Chebyshev polynomials, Math. Mag. 82 (2009) 117–126.

[2] J. De Loera, B. Sturmfels and R. Thomas, Gröbner bases and triangulations of the second hypersimplex, Combinatorica 15 (1995) 409–424.

[3] M. Katzmann, The Hilbert series of algebras of Veronese type, Comm. Algebra 33 (2005) 1141–1146.

[4] T. Lam and A. Postnikov, Alcoved polytopes I, Discrete Comput. Geom. 38 (2007) 453– 478.

[5] N. Li, Ehrhart h^{∗}-vectors of hypersimplices, Discrete Comput. Geom. 48 (2012) 847–878.

[6] E. Munarini, A combinatorial interpretation of the Chebyshev polynomials, SIAM J. Discrete Math. 20 (2006), 649–655.

[7] L. Shapiro, A combinatorial proof of a Chebyshev polynomial identity, Discrete Math. 34 (1981) 203–206.

[8] R. Stanley, Eulerian partitions of a unit hypercube, in M. Aigner, ed., Higher Combinatorics, Reidel, 1977.

[9] G. M. Ziegler, Discrete Geometry, available at

   http://www3.math.tu-berlin.de/Vorlesungen/SS08/DiskreGeom/exercises/ex08.pdf.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 52B05. Keywords: half-open hypersimplex, f-vector, generating function.

Received October 13 2014; revised version received May 29 2015. Published in Journal of Integer Sequences, June 3 2015.

Return to Journal of Integer Sequences home page.