Proving some conjectures on Kekulé numbers for certain benzenoids by using Chebyshev polynomials

Guoce Xin^1,∗ and Yueming Zhong² ^1,2School of Mathematical Sciences, Capital Normal University, Beijing 100048, PR China ¹guoce_xin@163.com & ²zhongyueming107@gmail.com

Abstract.

In chemistry, Cyvin-Gutman enumerates Kekulé numbers for certain benzenoids and record it as $A050446$ on OEIS. This number is exactly the two variable array $T(n,m)$ defined by the recursion $T(n,m)=T(n,m-1)+\sum^{\lfloor\frac{n-1}{2}\rfloor}_{k=0}T(2k,m-1)T(n-1-2k,m)$ , where $T(n,0)=T(0,m)=1$ for all nonnegative integers $m,n$ . Interestingly, this number also appeared in the context of weighted graphs, graph polytopes, magic labellings, and unit primitive matrices, studied by different authors. Several interesting conjectures were made on the OEIS. These conjectures are related to both the row and column generating function of $T(n,m)$ . In this paper, give explicit formula of the column generating function, which is also the generating function $F(n,x)$ studied by Bóna, Ju, and Yoshida. We also get trig function representations by using Chebyshev polynomials of the second kind. This allows us to prove all these conjectures.

*

This work was partially supported by NSFC(12071311).

Mathematic subject classification: Primary 05A15; Secondary 15A18, 05C78, 52B11.

Keywords: Chebyshev polynomials; Kekulé numbers; unit-primitive matrix; linear graphs.

1. Introduction

Throughout this paper, we use standard set notations $\mathbb{N},\mathbb{P}$ for nonnegative integers, and positive integers, respectively. We also use $\chi(true)=1$ and $\chi(false)=0$ .

Definition 1.1.

The two parameter sequence $A050446$ on [9] is defined by

(1.1)

T(n,m)=T(n,m-1)+\sum^{\lfloor\frac{n-1}{2}\rfloor}_{k=0}T(2k,m-1)T(n-1-2k,m),\qquad m\in\mathbb{P}

with initial condition $T(n,0)=1$ for all $n\in\mathbb{N}$ .

Table 1 gives the first several values of $T(n,m)$ as the $(n,m)$ entries.

	0	1	2	3	4	5	6	7	8	9	…
0	1	1	1	1	1	1	1	1	1	1	…
1	1	2	3	4	5	6	7	8	9	10	…
2	1	3	6	10	15	21	28	36	45	55	…
3	1	5	14	30	55	91	140	204	285	385	…
4	1	8	31	85	190	371	658	1086	1695	2530	…
5	1	13	70	246	671	1547	3164	5916	10317	17017	…
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮

Table 1. The first values of

T(n,m)=K\{z(n,m)\}.

One can find many interesting properties about $T(n,m)$ on [9]. It counts certain chemistry structure, and several combinatorial structures as we shall introduce. Let

T(x,m)=\sum_{n\geq 0}T(n,m)x^{n},\qquad T(n,y)=\sum_{m\geq 0}T(n,m)y^{m}

be the row and column generating function of $T(n,m)$ , respectively. There are six conjectures related to $T(x,m)$ and $T(n,y)$ . We will state them in Section 2 after introducing some notations.

1.1. Kekulé structures

The number $T(n,m)$ appeared in chemistry [3] as the number $K\{z(n,m)\}$ of Kekulé structures of the benzenoid hydrocarbon $z(n,m)$ , where $z(n,m)$ is a zigzag chain interpreted as $n$ tier condensed linear chains (rows) of $m$ hexagons each in a zigzag arrangement as in Figure 1.

Refer to caption — Figure 1. Zigzag chain and $z(m,n)$

The special case $z(1,1)$ is the single structure of benzene ( $C_{6}H_{6}$ ). In Figure 2, picture (1) illustrates $C_{6}H_{6}$ , and picture (2) gives the two Kekulé structures regarded differently in chemistry.

The explicit definition of $K\{z(n,m)\}$ is too involved so we only give several of them in Figure 3. We cannot find a reference proving that $K\{z(n,m)\}=T(n,m)$ .

1.2. Combinatorial Models

Let $G=(V,E)$ be a simple graph with vertex set $V=\{v_{1},v_{2},...,v_{n}\}$ and edge set $E$ . We will introduce three combinatorial models: i) Graph polytope studied in [8, 11, 15]; ii) Weighted graph studied in [1]; iii) Magic labellings of a graph studied in [13]. Though the concepts are for general graphs, we will focus on the linear graph (or path) $L_{n}$ with $n$ vertices.

The graph polytope $P(G)$ associated to a simple graph $G$ is defined as

P(G)=\{(x_{1},\dots,x_{n})\in[0,1]^{n}\mid v_{i}v_{j}\in E\Rightarrow x_{i}+x_{j}\leq 1\}.

The dilation of $P(G)$ by $m$ is denoted $mP(G)$ . The Ehrhart series of $P(G)$ is defined by

Ehr(G)=Ehr(G,x)=1+\sum_{m\geq 1}|(mP(G)\cap\mathbb{N}^{n})|x^{m}.

See [8, 11] for further references.

A a weighted graph of $G$ with distribution $\alpha=(m_{1},m_{2},...,m_{n})\in\mathbb{N}^{n}$ is a triplet $WG_{\alpha}=(V,E,\alpha)$ , where the weight of $v_{i}$ is $m_{i}$ . It is natural to define the weight of an edge $v_{i}v_{j}\in E$ to be $m_{i}+m_{j}$ . Let $WG(m)$ be the number of all weighted graphs of $G$ with a fixed upper bound $m$ for weight of each vertex and edge of $G$ . That is, $m_{i}\in[m]:=\{0,1,2,...,m\}$ for all $i$ and

(1.2)

m_{i}+m_{j}\leq m\text{\ if\ }v_{i}v_{j}\in E.

An interesting question is to compute the generating function of $WG(m)$ :

\rho(G)=\rho(G,x)=\sum\limits_{m=0}^{\infty}WG(m)x^{m}.

Let $G=(V,E)$ be a finite (undirected) graph with vertex set $V=\{v_{1},\dots,v_{n}\}$ and edge set $E$ . We allow loops in $E$ so $G$ is also called a pseudo graph in the terminology of [6]. A magic labelling of $G$ with magic sum $s$ is a labelling of the edges in $E$ by nonnegative integers such that for each vertex $v\in V$ , the weight $wt(v)$ of $v$ , defined to be the sum of labels of all edges incident to $v$ , is equal to $s$ . Denote by $M_{G}(s)$ the number of magic labelling of $G$ with magic sum $s$ . More precisely, $M_{G}(s)$ counts the number of maps $\mu:E\mapsto\mathbb{N}$ satisfying

(1.3)

\displaystyle wt(v_{i}):=\sum_{v_{i}v_{j}\in E}\mu(v_{i},v_{j})=s,\qquad i=1,2,\dots,n.

An interesting question is compute the generating function

\mathcal{M}(G)=\mathcal{M}(G,x)=\sum_{s\geq 0}M_{G}(s)x^{s}.

Finally, let $A_{m}=(a_{i,j})$ be the order $m$ matrix defined by $a_{i,j}=\chi(i+j\leq m+1)$ . It is called a unit-primitive matrix by Jeffery [7] in a different context.

The following result is claimed on [9], but we cannot find a real proof in the literature.

Theorem 1.2.

For $(n,m)\in\mathbb{N}^{2}$ , the number $T(n,m)$ has the following interpretations.

(1)

The $(1,1)$ entry of the matrix $A_{m+1}^{n+1}$ , also equal to $u_{m+1}^{T}A_{m+1}^{n-1}u_{m+1}$ , where $u_{m}=(1,1,\dots,1)^{T}\in\mathbb{N}^{m}$ .
(2)

The number $WL_{n}(m)$ of weighted graphs of $L_{n}$ with a fixed upper bound $m$ .
(3)

The number of integer lattice points in the dilated graph polytope $mP(L_{n})$ .
(4)

The number of magic labellings of the pseudo graph $\tilde{L}_{n}$ with magic sum $m$ , where $\tilde{L}_{n}$ is obtained from the linear graph $L_{n+1}$ by attaching one loop at each vertex.

Consequently in terms of generating functions, we have

\displaystyle T(n,x)=\sum_{m\geq 0}T(n,m)x^{m}=Ehr({L_{n}})=\rho(L_{n})=\mathcal{M}(\tilde{L}_{n}).

The equivalence of (2), (3), (4) can be easily seen by an example of $m=3$ . By definition, $WL_{3}(m)$ is the number of $\mathbb{N}$ -solutions $\alpha=(m_{1},m_{2},m_{3})$ of the system $m_{1}+m_{2}\leq m,\ m_{2}+m_{3}\leq m$ . The $\alpha$ ’s are exactly the lattice points of the $m$ dilated graph polytope $P(L_{3})=\{(x_{1},x_{2},x_{3})\in\mathbb{R}:x_{1}+x_{2}\leq 1,\ x_{2}+x_{3}\leq 1\}$ . Let $\ell_{1}=m-m_{1},\ell_{2}=m-m_{1}-m_{2},\ell_{3}=m-m_{2}-m_{3},\ell_{4}=m-m_{3}$ . Then the system is translated to

m_{1}+\ell_{1}=m,\ \ell_{2}+m_{1}+m_{2}=m,\ \ell_{3}+m_{2}+m_{3}=m,\ \ell_{4}+m_{3}=m,

which says the labelling as in Figure 4 is a magic labeling of $\tilde{L}_{3}$ .

To see that (2) is equivalent to (1), we describe $\alpha$ as a walk on the finite state $[m]$ of the $\alpha_{i}$ ’s: first choose $\alpha_{1}\in[m]$ , then choose $\alpha_{2}$ to be any number in $[m-\alpha_{1}]$ , since we have the restriction $\alpha_{1}+\alpha_{2}\leq m$ , and then choose $\alpha_{3}$ to be any number in $[m-\alpha_{2}]$ by the restriction $\alpha_{2}+\alpha_{3}\leq m$ . The transfer matrix from the state of $\alpha_{i}$ to the state of $\alpha_{i+1}$ is just $A_{m+1}$ , the unit primitive matrix of order $m+1$ . It then follows that $WL_{3}(m)=u_{m+1}^{T}A_{m+1}^{2}u_{m+1}$ .

The transfer matrix idea was used in [1], where weighted graphs were systematically enumerated and the following beautiful formula about $L_{n}$ was cited.

Theorem 1.3.

(Bóna et al. [2]). For $m=0,1,2,...$ , let

F(m,x)=\sum\limits_{k=0}^{\infty}WL_{k}(m)x^{k}=1+\sum\limits_{k=0}^{\infty}(u_{m+1}^{T}A_{m+1}^{k}u_{m+1})x^{k+1}.

Then

	$\displaystyle F(m,x)$	$\displaystyle=\frac{1}{-x+F(m-1,-x)}=\frac{1}{-x+\frac{1}{x+F(m-2,x)}}$
		$\displaystyle:=[-x,x,F(m-2,x)],$

where $F(0,x)=1/(-x+1)=[-x,1]$ and $F(1,x)=(1+x)/(1-x-x^{2})=[-x,x,1]$ . That is, $F(m,x)=[-x,x,-x,x,...,(-1)^{m-1}x,1]$ .

However, the cited paper was never finished (private communication), so it is necessary to give a proof.

1.3. Main Results

Our objectives in this paper is 4-folded.

Firstly, we give a proof of Theorem 1.2. For convenience, we use $v_{m,i}$ to denote the $i$ -th unit column vector in $\mathbb{R}^{m}$ . Let $\overline{T}(n,m)=u_{m}^{T}A_{m}^{n}v_{m,1}=u_{m}^{T}A_{m}^{n-1}u_{m}$ . Then it is sufficient to prove the following.

Theorem 1.4.

For $m,n\in\mathbb{N}$ , we have

(1.4)

T(n,m)=\overline{T}(n,m+1).

Secondly, we give two proofs of Theorem 1.3. Further more, we obtain trig function representation.

Theorem 1.5.

For $n\in\mathbb{P}$ , we have

F(n,x)=(-1)^{n+1}\frac{\sin(n+1)\theta-\sin n\theta}{\sin(n+2)\theta-\sin(n+1)\theta}=(-1)^{n+1}\frac{\cos(\frac{2n+1}{2}\theta)}{\cos(\frac{2n+3}{2}\theta)},

where $\cos\theta=\frac{(-1)^{n}x}{2}$ .

Thirdly, we obtain a factorization of the characteristic polynomial $f_{A_{n}}$ of $A_{n}$ as follows, where throughout the paper, we use $f_{A}(x)=|xI_{n}-A|$ to denote the characteristic polynomial of an order $n$ matrix $A$ .

Theorem 1.6.

For a given positive integer $n$ , we have

f_{A_{n}}(x)=|xI_{n}-A_{n}|=\prod\limits_{j=1}^{n}\left[x-(-1)^{n+1}\left(2\cos\frac{(2j-1)\pi}{2n+1}\right)^{-1}\right].

Finally, we prove the six conjectures related to $T(n,m)$ in Section 2.

1.4. Summary

This paper is organized as follows: In Section 2 we state the six conjectures after introducing some notations. Chebyshev polynomial of the second kind plays an important role in our development. Section 3 proves Theorem 1.4, an equivalent form of Theorem 1.2. The idea is to use matrix computation to derive certain recursion of $\overline{T}_{n,m}$ . The idea is used to give a proof of Theorems 1.3, but seems irrelevant to the other sections. Section 4 studies many properties of the unit primitive matrix $A_{n}$ , especially its eigenvalues. As consequences, we give the proof of Theorems 1.5-1.6 and Conjecture 1. We also give explicit formula of the column generating function $T(x,m)=F(m,x)$ . In Section 5, we first use the magic labelling model to sketch a proof of Conjectures 2-3, which are related to the row generating function $T(n,x)$ . Conjectures 4-6 are about the numerator of $T(n,x)$ . We prove them in later subsections by using the explicit formulas of the column generating function $T(x,m)$ .

2. Six Conjectures Related to $T(n,m)$

We will introduce 6 interesting conjectures related to the unit-primitive matrix $A_{n}$ and the sequence $T(m,n)$ . Their proofs will be given in later sections.

Our development highly relies on Chebyshev polynomial of the second kind (CPS for short), which is defined recursively by

\displaystyle U_{0}(x)=1,\quad U_{1}(x)=2x,\quad U_{n}(x)=2xU_{n-1}(x)-U_{n-2}(x).

We also need the well-known formula (see, e.g., [10]):

(2.1)

U_{n}(x)=\frac{\sin[(n+1)\cos^{-1}x]}{\sin(\cos^{-1}x)}=\sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}(-1)^{k}\binom{n-k}{k}(2x)^{n-2k}.

Many results are related to the polynomials $P_{n}(x),n\in\mathbb{P}$ defined by

(2.2)

\displaystyle P_{n}(x)=\sum_{k=0}^{n}P(n,k)x^{k}=\sum_{k=0}^{n}(-1)^{\lfloor\frac{3k}{2}\rfloor}\binom{\lfloor\frac{n+k}{2}\rfloor}{k}x^{k}.

The first conjecture is related to the unit-primitive matrix $A_{n}$ .

Conjecture 1.

(A187660 [9]). (i) For positive integer $n\in\mathbb{P}$ . The characteristic polynomial $f_{A_{n}}(x)$ of the $n\times n$ unit-primitive matrix $A_{n}$ is:

(2.3)

\displaystyle f_{A_{n}}(x)=\det(xI_{n}-A_{n})=x^{n}P_{n}(1/x).

(ii) The $n$ eigenvalues of $A_{n}$ are given by $w_{n,j}=U_{n-1}(\delta_{n,j})$ , where $\delta_{n,j}=2\cos(\frac{2j-1}{2n+1}\pi)$ for $j=1,...,n$ .

The other 5 conjectures are all related to the sequence $T(n,m)$ defined by (1.1).

Let $E_{n}$ be the Euler number [12, Section 3.16] with exponential generating function

\sec(x)=\sum_{n\geq 0}\frac{E_{2n}}{(2n)!}x^{2n},\qquad\tan(x)=\sum_{n\geq 0}\frac{E_{2n+1}}{(2n+1)!}x^{2n+1}.

The following result was observed in [9].

Lemma 2.1.

For fixed nonnegative integer $n$ , $T(n,m)$ is a polynomial in $m$ of degree $n$ with leading coefficient $\ell_{n}=E_{n}/n!$ . Therefore the $n$ -th row generating function of $T(n,m)$ is of the following form

T(n,x)=\sum_{m\geq 0}T(n,m)x^{m}=H_{n}(x)/(1-x)^{n+1},

where $H_{n}(x)$ is a polynomial of degree no more than $n$ . Here we start with row $0$ .

Proof.

The reason is so simple that we include it here. For the first part, let $p_{n}(m)=T(n,m)$ . We need to show that $p_{n}(x)\in\mathbb{Q}[x]$ with $\deg p_{n}(x)=n$ and the leading coefficient is $E_{n}/n!$ . The assertion clearly holds for $n=0$ , since $p_{0}(m)=1$ . Assume the lemma holds for all $k<n$ . To show the assertion holds for $p_{n}(m)$ , we rewrite (1.1) as

\displaystyle\Delta(p_{n}(m))=p_{n}(m)-p_{n}(m-1)=\sum^{\lfloor\frac{n-1}{2}\rfloor}_{k=0}p_{2k}(m-1)p_{n-1-2k}(m).

That is, the divided difference of $p_{n}(m)$ is a sum of polynomials of degree $n-1$ with leading coefficient

L=\sum^{\lfloor\frac{n-1}{2}\rfloor}_{k=0}\ell_{2k}\ell_{n-1-2k}=\sum^{\lfloor\frac{n-1}{2}\rfloor}_{k=0}\frac{E_{2k}}{(2k)!}\frac{E_{n-1-2k}}{(n-1-2k)!}

by the induction hypothesis. Therefore $p_{n}(m)$ is a polynomial in $m$ of degree $n$ with leading coefficient $\ell_{n}=L/n$ . It is in fact $E_{n}$ follows by equating coefficient of $x^{n-1}$ in the identity $\frac{\mathrm{d}}{\mathrm{d}x}(\sec(x)+\tan(x))=\sec(x)(\sec(x)+\tan(x)).$

The second part follows by classical theory on rational functions. See [12].

Simple calculation shows that $H_{0}(x)=H_{1}(x)=1$ . The second conjecture gives more details on $H_{n}(x)$ .

Conjecture 2.

(A205497 [9]). For $n\geq 2$ , the numerator of the $n$ -th row generating function of $T(n,m)$ is a polynomial of degree $n-2$ . That is

H_{n}(x)=M_{n-2,0}+M_{n-3,1}x+M_{n-4,2}x^{2}+\cdots+M_{0,n-2}x^{n-2},

where $M_{n-2-j,j}$ is as in Table 2 below for $j=0,1,\dots,n-2$ .

The array $M_{i,j}$ is given by the sequence A205497 in [9]. Christopher H. Gribble kindly calculated the first 100 antidiagonals of the array $M$ which starts as in Table 2.

	0	1	2	3	4	5	…
0	1	1	1	1	1	1	…
1	1	3	7	14	26	46	…
2	1	7	31	109	334	937	…
3	1	14	109	623	2951	12331	…
4	1	26	334	2951	20641	123216	…
5	1	46	937	12331	123216	1019051	…
⋮	⋮	⋮	⋮	⋮	⋮	⋮

Table 2. The

M_{n,k}

There are several conjectures about $M_{i,j}$ .

Conjecture 3.

(A205497 [9]). $M_{n,k}=M_{k,n}$ , for all $n$ and $k$ ; that is, $M$ is symmetric about the central terms $\{1,3,31,623,...\}$ .

Conjecture 4.

(A205497 [9]). Assuming Conjecture 2, we have these following results.

(1)

The generating function for row (or column) $n$ of $M$ is of the form

(2.4) $\frac{G_{n}(x)}{\left(P_{1}(x))^{n+1}(P_{2}(x))^{n}...(P_{n}(x)\right)^{2}P_{n+1}(x)}.$
(2)

The numerator $G_{n}(x)$ is a polynomial of degree $\frac{n(n+4)(n+5)}{6}$ ( $A005586(n)$ , see [9]).
(3)

The denominator $(P_{1}(x))^{n+1}(P_{2}(x))^{n}...(P_{n}(x))^{2}P_{n+1}(x)$ is a polynomial of degree $\frac{n(n+1)(n+2)}{6}$ ( $A000292(n+1)$ , see [9]).

Conjecture 5.

(A205497 [9]). The generation functions from column 0 to 4 of $M$ are the following 5 in order.

(0)

$1/(1-x)$ ;
(1)

$\frac{1}{(1-x)^{2}(1-x-x^{2})}$ ;
(2)

$\frac{1-x^{2}-x^{3}-x^{4}+x^{5}}{(1-x)^{3}(1-x-x^{2})^{2}(1-2x-x^{2}+x^{3})}$ ;
(3)

$\frac{1+x-6x^{2}-15x^{3}+21x^{4}+35x^{5}-13x^{6}-51x^{7}+3x^{8}+21x^{9}+5x^{10}+x^{11}-5x^{12}-x^{13}-x^{14}}{(1-x)^{4}(1-x-x^{2})^{3}(1-2x-x^{2}+x^{3})^{2}(1-2x-3x^{2}+x^{3}+x^{4})}$ ;
(4)

$\frac{N_{4}(x)}{(1-x)^{5}(1-x-x^{2})^{4}(1-2x-x^{2}+x^{3})^{3}(1-2x-3x^{2}+x^{3}+x^{4})^{2}(1-3x-3x^{2}+4x^{3}+x^{4}-x^{5})}$ .

Here

	$\displaystyle N_{4}(x)$	$\displaystyle=1+4x-31x^{2}-67x^{3}+348x^{4}+418x^{5}-1893x^{6}-1084x^{7}+4326x^{8}+4295x^{9}-7680x^{10}-9172x^{11}+9104x^{12}$
		$\displaystyle+11627x^{13}-5483x^{14}-10773x^{15}+1108x^{16}+7255x^{17}+315x^{18}-3085x^{19}-228x^{20}+669x^{21}+102x^{22}$
		$\displaystyle-23x^{23}-45x^{24}-16x^{25}+11x^{26}+2x^{27}-x^{28}.$

Conjecture 6.

(A205497 [9]). Assuming Conjecture 2, we have

\mathrm{lim}_{n\rightarrow\infty}\frac{M_{n+1,m}}{M_{n,m}}=U_{m}\left(\cos\left(\frac{\pi}{2m+3}\right)\right).

This limit is also equal to spectral radius of the $m\times m$ unit-primitive matrix $A_{m}$ , where identical limits for the columns of the transpose $M^{T}$ of $M$ .

3. Proofs of Theorems 1.3 and 1.4

In this section, we first prove Theorem 1.4 by using matrix computations. Then we use similar idea to give our first proof of Theorem 1.3. The ideas in this section are irrelevant to the other sections.

We use the following notations: $X_{m}=(v_{m,1},v_{m,2},...,v_{m,m})$ , $\bar{A}_{m}=A_{m}-X_{m}$ and $J_{m}=u_{m}u_{m}^{T}$ (the all $1$ matrix). The basic properties of these order $m$ matrices are given in the following lemma. They will be used in the next subsection.

Lemma 3.1.

For a given positive integer $m$ , the following equations all hold true.

(1)

$\bar{A}_{m}X_{m}+X_{m}A_{m}=J_{m}$ and $X_{m}\bar{A}_{m}+A_{m}X_{m}=J_{m}$ ;
(2)

$A_{m}v_{m,1}=u_{m}$ ;
(3)

$u_{m}^{T}X_{m}=u_{m}^{T}$ ;
(4)

$A_{m}v_{m,1}u_{m}^{T}=J_{m}$ ;
(5)

$\bar{A}_{m}X_{m}v_{m,1}=0$ ;
(6)

$A_{m}X_{m}v_{m,1}=v_{m,1}$ ;
(7)

$u_{m}^{T}\bar{A}_{m}v_{m,1}=\bar{u}_{m}^{T}\bar{A}_{m}v_{m,1}=u_{m-1}^{T}A_{m-1}v_{m-1,1}$ , where $\bar{u}_{m}=u_{m}-v_{m,m}$ .

Proof.

The first six equalities are straightforward, so we only prove the seventh equality. By using block matrix operation, we have

	$\displaystyle u_{m}^{T}\bar{A}_{m}v_{m,1}$	$\displaystyle=(u_{m-1}^{T},1)\begin{pmatrix}A_{m-1}&0\\ 0&0\end{pmatrix}\binom{v_{m-1,1}}{0}$
		$\displaystyle=(u_{m-1}^{T}A_{m-1},0)\binom{v_{m-1,1}}{0}$
		$\displaystyle=(u_{m}^{T}-v_{m,m}^{T})\bar{A}_{m}v_{m,m}=\bar{u}_{m}^{T}\bar{A}_{m}v_{m,1}$
		$\displaystyle=u_{m-1}^{T}A_{m-1}v_{m-1,1}.$

3.1. Proof of Theorem 1.4

To prove Theorem 1.4, it is sufficient to show that $\overline{T}(n,m+1)$ satisfy the same recursion (1.1) as for $T(n,m)$ . This is Corollary 3.6 below.

We need some lemmas.

Lemma 3.2.

Given three positive integers $m$ , $n$ and $k$ with $1\leq k\leq n-2$ , we have

(3.1)

\bar{A}_{m}^{k}A^{n-k}_{m}-\bar{A}^{k+2}_{m}A_{m}^{n-k-2}=\bar{A}_{m}^{k+1}v_{m,1}u_{m}^{T}A_{m}^{n-k-2}.

Proof.

		$\displaystyle\bar{A}_{m}^{k}A^{n-k}_{m}-\bar{A}^{k+2}_{m}A_{m}^{n-k-2}$
		$\displaystyle=\bar{A}_{m}^{k}(\bar{A}_{m}+X_{m})A_{m}^{n-k-1}-\bar{A}^{k+2}_{m}A_{m}^{n-k-2}$
		$\displaystyle=\bar{A}_{m}^{k+1}(\bar{A}_{m}+X_{m})A_{m}^{n-k-2}+\bar{A}_{m}^{k}X_{m}A_{m}^{n-k-1}-\bar{A}^{k+2}_{m}A_{m}^{n-k-2}$
		$\displaystyle=\bar{A}_{m}^{k+2}A_{m}^{n-k-2}+\bar{A}_{m}^{k}(\bar{A}_{m}X_{m}+X_{m}A_{m})A_{m}^{n-k-2}-\bar{A}^{k+2}_{m}A_{m}^{n-k-2}$
	(by Lemma 3.1(1))	$\displaystyle=\bar{A}_{m}^{k}J_{m}A_{m}^{n-k-2}$
	(by Lemma 3.1(4))	$\displaystyle=\bar{A}_{m}^{k}A_{m}v_{m,1}u_{m}^{T}A_{m}^{n-k-2}$
		$\displaystyle=\bar{A}_{m}^{k}(\bar{A}_{m}+X_{m})v_{m,1}u_{m}^{T}A_{m}^{n-k-2}$
		$\displaystyle=\bar{A}_{m}^{k+1}v_{m,1}u_{m}^{T}A_{m}^{n-k-2}+\bar{A}_{m}^{k}X_{m}v_{m,1}u_{m}^{T}A_{m}^{n-k-2}$
	(by Lemma 3.1(5))	$\displaystyle=\bar{A}_{m}^{k+1}v_{m,1}u_{m}^{T}A_{m}^{n-k-2}.$

Lemma 3.3.

For given two positive integers $m$ and $n$ , we have

u_{m}^{T}\bar{A}_{m}^{2\lfloor\frac{n-1}{2}\rfloor+1}A_{m}^{n-2\lfloor\frac{n-1}{2}\rfloor-1}v_{m,1}=u_{m}^{T}\bar{A}_{m}^{n}v_{m,1}.

Proof.

We discuss by the parity of $n$ as follows.

If $n$ is odd, then $2\lfloor\frac{n-1}{2}\rfloor+1=n$ . We have

u_{m}^{T}\bar{A}_{m}^{2\lfloor\frac{n-1}{2}\rfloor+1}A_{m}^{n-2\lfloor\frac{n-1}{2}\rfloor-1}v_{m,1}=u_{m}^{T}\bar{A}_{m}^{n}v_{m,1}.

If $n$ is even, then $2\lfloor\frac{n-1}{2}\rfloor+1=n-1$ . We have

	$\displaystyle u_{m}^{T}\bar{A}_{m}^{2\lfloor\frac{n-1}{2}\rfloor+1}A_{m}^{n-2\lfloor\frac{n-1}{2}\rfloor-1}v_{m,1}$	$\displaystyle=u_{m}^{T}\bar{A}_{m}^{n-1}A_{m}v_{m,1}$
		$\displaystyle=u_{m}^{T}\bar{A}_{m}^{n-1}(\bar{A}_{m}+X_{m})v_{m,1}$
	(by Lemma 3.1(5))	$\displaystyle=u_{m}^{T}\bar{A}_{m}^{n}v_{m,1}.$

This completes the proof.

Lemma 3.4.

For given two positive integers $m$ and $n$ , we have

\bar{A}_{m}A_{m}^{n-1}-\bar{A}_{m}^{2\lfloor\frac{n-1}{2}\rfloor+1}A_{m}^{n-2\lfloor\frac{n-1}{2}\rfloor-1}+v_{m,1}u_{m}^{T}A_{m}^{n-1}=\sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}\bar{A}_{m}^{2i}v_{m,1}u_{m}^{T}A_{m}^{n-1-2i}.

Proof.

By adding Equation (3.1) with respect to $k=1,3,...,2\lfloor\frac{n-1}{2}\rfloor-1$ , we get

(3.2)

\bar{A}_{m}A_{m}^{n-1}-\bar{A}_{m}^{2\lfloor\frac{n-1}{2}\rfloor+1}A_{m}^{n-2\lfloor\frac{n-1}{2}\rfloor-1}=\sum\limits_{i=1}^{\lfloor\frac{n-1}{2}\rfloor}\bar{A}_{m}^{2i}v_{m,1}u_{m}^{T}A_{m}^{n-1-2i}.

This is just a equivalent form of the lemma.

A direct consequence of Lemma 3.4 is the following.

Theorem 3.5.

Let $m$ and $n$ be two positive integers. Then for any vectors ${\boldsymbol{\alpha}}=(\alpha_{1},....\alpha_{m})$ and ${\boldsymbol{\beta}}=(\beta_{1},...,\beta_{m})$ , we have

{\boldsymbol{\alpha}}^{T}\bar{A}_{m}A_{m}^{n-1}{\boldsymbol{\beta}}-{\boldsymbol{\alpha}}^{T}\bar{A}_{m}^{2\lfloor\frac{n-1}{2}\rfloor+1}A_{m}^{n-2\lfloor\frac{n-1}{2}\rfloor-1}{\boldsymbol{\beta}}+{\boldsymbol{\alpha}}^{T}v_{m,1}u_{m}^{T}A_{m}^{n-1}{\boldsymbol{\beta}}=\sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}{\boldsymbol{\alpha}}^{T}\bar{A}_{m}^{2i}v_{m,1}u_{m}^{T}A_{m}^{n-1-2i}{\boldsymbol{\beta}}.

In particular, setting ${\boldsymbol{\alpha}}=u_{m}$ and ${\boldsymbol{\beta}}=v_{m,1}$ gives the following corollary.

Corollary 3.6.

For positive integers $m$ and $n$ , we have

(3.3)

\overline{T}(n,m)=\overline{T}(n,m-1)+\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\overline{T}(2k,m-1)\overline{T}(n-2k-1,m).

Proof.

It is easy to check that Equation (3.3) holds for $n=1$ . Now for $n\geq 2$ , we have

	$\displaystyle\overline{T}(n,m)$	$\displaystyle=u_{m}^{T}A_{m}^{n}v_{m,1}$
		$\displaystyle=u_{m}^{T}(\bar{A}_{m}+X_{m})A_{m}^{n-1}v_{m,1}$
		$\displaystyle=u_{m}^{T}\bar{A}_{m}A_{m}^{n-1}v_{m,1}+u_{m}^{T}X_{m}A_{m}^{n-1}v_{m,1}$
		$\displaystyle=u_{m}^{T}\bar{A}_{m}A_{m}^{n-1}v_{m,1}+u_{m}^{T}A_{m}^{n-1}v_{m,1}$
	(by Theorem 3.5)	$\displaystyle=u_{m}^{T}\bar{A}_{m}^{2\lfloor\frac{n-1}{2}\rfloor+1}A_{m}^{n-2\lfloor\frac{n-1}{2}\rfloor-1}v_{m,1}+\sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}u_{m}^{T}\bar{A}_{m}^{2i}v_{m,1}u_{m}^{T}A_{m}^{n-1-2i}v_{m,1}$
	(by Lemma 3.3)	$\displaystyle=\overline{T}(n,m-1)+\sum^{\lfloor\frac{n-1}{2}\rfloor}_{k=0}\overline{T}(2k,m-1)\overline{T}(n-1-2k,m).$

3.2. Proof of Theorem 1.3

We will prove a more general result by using similar technique as in the previous subsection.

Lemma 3.7.

For given three positive integers $m$ , $n$ and $k$ , we have

A_{m}^{n-k}X_{m}\bar{A}_{m}^{k}+A_{m}^{n-k-1}X_{m}\bar{A}_{m}^{k+1}=A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}.

Proof.

We have

	$\displaystyle A_{m}^{n-k}X_{m}\bar{A}_{m}^{k}+A_{m}^{n-k-1}X_{m}\bar{A}_{m}^{k+1}$	$\displaystyle=A_{m}^{n-k-1}(A_{m}X_{m}+X_{m}\bar{A}_{m})\bar{A}_{m}^{k}$
	(by Lemma 3.1(1))	$\displaystyle=A_{m}^{n-k-1}J_{m}\bar{A}_{m}^{k}$
		$\displaystyle=A_{m}^{n-k-1}u_{m}u_{m}^{T}\bar{A}_{m}^{k}$
	(by Lemma 3.1(2))	$\displaystyle=A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}.$

Lemma 3.8.

For given two positive integers $m$ and $n$ , we have

A_{m}^{n}X_{m}+(-1)^{n-1}X_{m}\bar{A}_{m}^{n}=\sum\limits_{k=0}^{n-1}(-1)^{k}A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}.

Proof.

By Lemma 3.7, we have

(3.4)

(-1)^{k}(A_{m}^{n-k}X_{m}\bar{A}_{m}^{k}+A_{m}^{n-k-1}X_{m}\bar{A}_{m}^{k+1})=(-1)^{k}A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}.

Adding Equation (3.6) with respect to $k=0,...,n-1$ gives

A_{m}^{n}X_{m}+(-1)^{n-1}X_{m}\bar{A}_{m}^{n}=\sum\limits_{k=0}^{n-1}(-1)^{k}A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}.

This completes the proof.

Lemma 3.9.

For given two positive integers $m$ and $n$ , we have

(3.5)

A_{m}^{n}X_{m}-(-1)^{n}X_{m}\bar{A}_{m}^{n}+(-1)^{n}v_{m,1}u_{m}^{T}\bar{A}_{m}^{n}-A_{m}^{n}v_{m,1}v_{m,m}^{T}=\sum\limits_{k=0}^{n}(-1)^{k}A_{m}^{n-k}v_{m,1}\bar{u}_{m}^{T}\bar{A}_{m}^{k}.

Proof.

By Lemma 3.7, we have

(3.6)

(-1)^{k}(A_{m}^{n-k}X_{m}\bar{A}_{m}^{k}+A_{m}^{n-k-1}X_{m}\bar{A}_{m}^{k+1})=(-1)^{k}A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}.

Adding Equation (3.6) with respect to $k=0,...,n-1$ gives

	$\displaystyle A_{m}^{n}X_{m}+(-1)^{n-1}X_{m}\bar{A}_{m}^{n}$	$\displaystyle=\sum\limits_{k=0}^{n-1}(-1)^{k}A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}$
	$\displaystyle(\text{by }u_{m}^{T}\bar{A}_{m}=\bar{u}_{m}^{T}\bar{A}_{m})\quad$	$\displaystyle=A_{m}^{n}v_{m,1}u_{m}^{T}+\sum\limits_{k=1}^{n-1}(-1)^{k}A_{m}^{n-k}v_{m,1}\bar{u}_{m}^{T}\bar{A}_{m}^{k}$
		$\displaystyle=A_{m}^{n}v_{m,1}\bar{u}_{m}^{T}+A_{m}^{n}v_{m,1}v_{m,m}^{T}+\sum\limits_{k=1}^{n-1}(-1)^{k}A_{m}^{n-k}v_{m,1}\bar{u}_{m}^{T}\bar{A}_{m}^{k}.$

The lemma then follows.

Theorem 3.10.

Let $m$ and $n$ be positive integers. Then for any vectors ${\boldsymbol{\alpha}}=(\alpha_{1},...,\alpha_{m})^{T}$ and ${\boldsymbol{\beta}}=(\beta_{1},...,\beta_{m})^{T}$ , we have

(3.7)

{\boldsymbol{\alpha}}^{T}A_{m}^{n}X_{m}{\boldsymbol{\beta}}-(-1)^{n}{\boldsymbol{\alpha}}^{T}X_{m}\bar{A}_{m}^{n}{\boldsymbol{\beta}}+(-1)^{n}\alpha_{1}u_{m}^{T}\bar{A}_{m}^{n}{\boldsymbol{\beta}}-{\boldsymbol{\alpha}}^{T}A_{m}^{n}v_{m,1}\beta_{m}=\sum\limits_{k=0}^{n}{\boldsymbol{\alpha}}^{T}A_{m}^{n-k}v_{m,1}\bar{u}_{m}^{T}\bar{A}_{m}^{k}{\boldsymbol{\beta}}(-1)^{k}.

Proof.

Multiply Equation (3.5) from the left by ${\boldsymbol{\alpha}}$ and from the right by ${\boldsymbol{\beta}}$ .

Corollary 3.11.

For $n,m\in\mathbb{P}$ and $n\geq 2$ , we have

\overline{T}(n-1,m)=\sum\limits^{n}_{k=0}(-1)^{n-k}\overline{T}(k,m)\overline{T}(n-k,m-1).

Proof.

Setting ${\boldsymbol{\alpha}}=u_{m}$ and ${\boldsymbol{\beta}}=v_{m,1}$ (so ${\boldsymbol{\beta}}_{m}=0$ ) in Theorem 3.10 gives

u_{m}^{T}A_{m}^{n}X_{m}v_{m,1}-(-1)^{n}u_{m}^{T}X_{m}\bar{A}_{m}^{n}v_{m,1}+(-1)^{n}u_{m}^{T}\bar{A}_{m}^{n}v_{m,1}=\sum\limits_{k=0}^{n}u_{m}^{T}A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}v_{m,1}(-1)^{k}.

Since $A_{m}X_{m}v_{m,1}=v_{m,1}$ and $u_{m}^{T}X_{m}=u_{m}^{T}$ , we have

u_{m}^{T}A_{m}^{n-1}v_{m,1}=\sum\limits_{k=0}^{n}u_{m}^{T}A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}v_{m,1}(-1)^{k}.

This is just

\overline{T}(n-1,m)=\sum^{n}_{k=0}(-1)^{k}\overline{T}(n-k,m)\overline{T}(k,m-1)=\sum^{n}_{k=0}(-1)^{n-k}\overline{T}(k,m)\overline{T}(n-k,m-1).

First Proof of Theorem 1.3.

It suffices to show that

(3.8)

F(m,x)=\frac{1}{-x+F(m-1,-x)},

which is equivalent to

xF(m,x)=F(m,x)F(m-1,-x)-1.

Put in the formula

F(m,x)=\sum_{k=0}^{\infty}T(k,m)x^{k}=\sum_{k=0}^{\infty}\bar{T}(k,m+1)x^{k},

and equate coefficient of $x^{n}$ , we need to prove

\bar{T}(n-1,m+1)=\sum_{k=0}^{n}\bar{T}(k,m+1)(-1)^{(}n-k)\bar{T}(n-k,m),

which is just Corollary 3.11 (replacing $m$ by $m+1$ ). This completes the proof.

Define $\overline{T}^{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}(x,m)=\sum\limits_{n=0}^{\infty}{\boldsymbol{\alpha}}^{T}A_{m}^{n}x^{n}{\boldsymbol{\beta}}$ . Then

\overline{T}^{u_{m},v_{m,1}}(x,m)=\sum\limits_{n=0}^{\infty}u_{m}^{T}A_{m}^{n}v_{m,1}x^{n}=F(m-1,x).

Equation (3.7) in Theorem 3.10 can be written in the form of generating function of $x$ as follows.

Theorem 3.12.

For a given positive integer $m$ , we have

(3.9)			$\displaystyle T^{{\boldsymbol{\alpha}},X_{m}{\boldsymbol{\beta}}}(x,m)-T^{\overline{X_{m}{\boldsymbol{\alpha}}},\overline{{\boldsymbol{\beta}}}}(-x,m-1)+\alpha_{1}T^{\bar{u}_{m},\bar{{\boldsymbol{\beta}}}}(-x,m-1)-\beta_{m}T^{{\boldsymbol{\alpha}},v_{m,1}}(x,m)$
		$\displaystyle=T^{{\boldsymbol{\alpha}},v_{m,1}}(x,m)T^{\bar{u}_{m},\bar{{\boldsymbol{\beta}}}}(-x,m-1).$

Proof.

We multiply $x^{n}$ on both sides of Equation (3.7) of Theorem 3.10 and take sum with respect to $n$ from 0 to infinity. We get

\sum\limits_{n=0}^{\infty}({\boldsymbol{\alpha}}^{T}A_{m}^{n}X_{m}{\boldsymbol{\beta}}-(-1)^{n}{\boldsymbol{\alpha}}^{T}X_{m}\bar{A}_{m}^{n}{\boldsymbol{\beta}}+(-1)^{n}\alpha_{1}u_{m}^{T}\bar{A}_{m}^{n}{\boldsymbol{\beta}}-{\boldsymbol{\alpha}}^{T}A_{m}^{n}v_{m,1}\beta_{m})x^{n}=\sum\limits_{n=0}^{\infty}(\sum\limits_{k=0}^{n}{\boldsymbol{\alpha}}^{T}A_{m}^{n-k}v_{m,1}u_{m}^{T}\bar{A}_{m}^{k}{\boldsymbol{\beta}}(-1)^{k})x^{n}.

In terms of generating functions, this is just (3.9).

Let ${\boldsymbol{\alpha}}=u_{m}$ and $\beta_{m}=0$ in Equation (3.9) of Theorem 3.12. We have the following corollary.

Corollary 3.13.

For a given positive integer $m$ , we have

T^{u_{m},(0,\beta_{m-1},...,\beta_{1})^{T}}(x,m)=T^{u_{m},v_{m,1}}(x,m)T^{\bar{u},(\beta_{1},\beta_{2},...,\beta_{m-1})^{T}}(-x,m-1).

Let ${\boldsymbol{\beta}}=v_{m,i}$ with $i=1,...,m-1$ in Corollary 3.13. We get the following corollary.

Corollary 3.14.

For a given positive integer $m$ , we have

T^{u_{m},v_{m,m-i+1}}(x,m)=T^{u_{m},v_{m,1}}(x,m)T^{\bar{u},\bar{v}_{m-1,i}}(-x,m-1),

where $i=1,...,m-1$ and $\bar{v}_{m-1,i}$ is the $m-1$ dimensional vector obtained by removing the last component of $v_{m,i}$ .

4. Some results about $A_{n}$

From now on, we will consider $A_{n}$ instead of $A_{m}$ in last section.

4.1. The Characteristic polynomial of $A_{n}$

In this subsection, our main goal is to prove Theorem 1.6 and Conjecture 1.

Recall that $A_{n}$ is the unit primitive matrix of order $n$ . We need to introduce two closely related matrix $T_{n}$ and $T^{\prime}_{n}$ and their relation to the CPS $U_{n}(x)$ . Let $T_{n}^{\prime}$ be an $n\times n$ matrix with ${(T_{n}^{\prime})}_{ij}=\chi(|i-j|=1)$ . Damianou give the following result.

Theorem 4.1.

(Damianou [4]). For a given positive integer $n$ , we have $f_{T_{n}^{\prime}}(2x)=U_{n}(x)$ .

Let $T_{n}$ be the $n\times n$ matrix with entries $(T_{n})_{ij}=(T_{n}^{\prime})_{i,j}+\chi((i,j)=(1,1)).$ We will use the following fact.

Fact 4.2.

(Jeffery [7]). For $n\geq 2$ , we have $A_{n}=U_{n-1}(\frac{T_{n}}{2})$ .

We have the following conclusion.

Lemma 4.3.

For a given positive integer $n$ , we have

(1)

$f_{T_{n}}(2x)=f_{T_{n}^{\prime}}(2x)-f_{T_{n-1}^{\prime}}(2x)=\frac{\sin[(n+1)\theta]-\sin n\theta}{\sin\theta}$ , where $\cos\theta=x$ ;
(2)

$f_{T_{n}}(x)=xf_{T_{n-1}}(x)-f_{T_{n-2}}(x)$ ;
(3)

$f_{A_{n}}(x)=x^{2}f_{A_{n-2}}(x)-(-1)^{n+1}f_{A_{n-1}}(-x)$ .

Proof.

(1)

By splitting the first column of the determinant, we obtain

	$\displaystyle f_{T_{n}}(2x)$	$\displaystyle=\|2xI_{n}-T_{n}\|$
		$\displaystyle=\begin{vmatrix}2x&-1&0&\cdots&0&0\\ -1&2x&-1&\cdots&0&0\\ 0&-1&2x&\cdots&0&0\\ \vdots&\vdots&\vdots&&\vdots&\vdots\\ 0&0&0&\cdots&2x&-1\\ 0&0&0&\cdots&-1&2x\end{vmatrix}+\begin{vmatrix}-1&-1&0&\cdots&0&0\\ 0&2x&-1&\cdots&0&0\\ 0&-1&2x&\cdots&0&0\\ \vdots&\vdots&\vdots&&\vdots&\vdots\\ 0&0&0&\cdots&2x&-1\\ 0&0&0&\cdots&-1&2x\end{vmatrix}$
		$\displaystyle=f_{T_{n}^{\prime}}(2x)-f_{T_{n-1}^{\prime}}(2x)$
		$\displaystyle=\frac{\sin[(n+1)\theta]-\sin n\theta}{\sin\theta},$

where in the last step, we use Theorem 4.1 and $\cos\theta=x$ .

(2)

By expanding along the rightmost column, we obtain

	$\displaystyle f_{T_{n}}(x)$	$\displaystyle=\|xI_{n}-T_{n}\|$
		$\displaystyle=x\begin{vmatrix}x-1&-1&0&\cdots&0&0\\ -1&x&-1&\cdots&0&0\\ 0&-1&x&\cdots&0&0\\ \vdots&\vdots&\vdots&&\vdots&\vdots\\ 0&0&0&\cdots&x&-1\\ 0&0&0&\cdots&-1&x\end{vmatrix}+\begin{vmatrix}x-1&-1&0&\cdots&0&0\\ -1&x&-1&\cdots&0&0\\ 0&-1&x&\cdots&0&0\\ \vdots&\vdots&\vdots&&\vdots&\vdots\\ 0&0&0&\cdots&x&-1\\ 0&0&0&\cdots&-1&x\end{vmatrix}$
		$\displaystyle=xf_{T_{n-1}}(x)-f_{T_{n-2}}(x).$

(3)

The proof is almost identical to that of Lemma 4.16, so we omit it here.

Comparing the recursions in Lemma 4.3 gives the following result.

Lemma 4.4.

For a given positive integer $n$ , we have

(4.1)

f_{A_{n}}(x)=(-1)^{\lfloor\frac{n+1}{2}\rfloor}f_{T_{n}}\left((-1)^{n+1}\frac{1}{x}\right)x^{n}.

Proof.

We prove by induction on $n$ .

It is straightforward to check the lemma for $n=1,2$ . Assume the lemma holds for all positive integers less than $n$ . Then for general $n$ , we have

		$\displaystyle f_{A_{n}}(x)$
	(by Lemma 4.3(3))	$\displaystyle=x^{2}f_{A_{n-2}}(x)-(-1)^{n}f_{A_{n-1}}(-x)$
		$\displaystyle=x^{2}(-1)^{\lfloor\frac{n-1}{2}\rfloor}f_{T_{n-2}}\left(\frac{(-1)^{n-1}}{x}\right)x^{n-2}-(-1)^{\lfloor\frac{n+1}{2}\rfloor+n}f_{T_{n-1}}\left(\frac{(-1)^{n}}{-x}\right)x^{n-1}$
	(by Lemma 4.3(2))	$\displaystyle=x^{n-1}(-1)^{\lfloor\frac{n+1}{2}\rfloor+n}\left(x(-1)^{n}f_{T_{n-2}}\left(\frac{(-1)^{n}}{x}\right)-f_{T_{n-1}}\left(\frac{(-1)^{n+1}}{x}\right)\right)$
		$\displaystyle=x^{n}(-1)^{\lfloor\frac{n+1}{2}\rfloor}f_{T_{n}}\left((-1)^{n+1}\frac{1}{x}\right).$

This completes the induction.

Combining Lemma 4.3 and Equation (2.1) gives the following explicit formula.

Lemma 4.5.

For a given positive integer $n$ , we have

f_{T_{n}}(x)=\sum\limits_{k=0}^{n}(-1)^{\lfloor\frac{n+1}{2}\rfloor+\lfloor\frac{3k}{2}\rfloor-nk-k}\binom{\lfloor\frac{n+k}{2}\rfloor}{k}x^{k}.

Proof.

	$\displaystyle f_{T_{n}}(x)$	$\displaystyle=f_{T_{n}^{\prime}}(x)-f_{T_{n-1}^{\prime}}(x)$
		$\displaystyle=\sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}(-1)^{k}\frac{(n-k)!}{k!(n-2k)!}x^{n-2k}-\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}(-1)^{k}\frac{(n-1-k)!}{k!(n-1-2k)!}x^{n-1-2k}$
		$\displaystyle=\left\{\begin{aligned} \sum\limits_{i\in n_{e}}(-1)^{\frac{n-i}{2}}\binom{\frac{n+i}{2}}{i}x^{i}+\sum\limits_{i\in n_{o}}(-1)^{\frac{n-i-1}{2}}\binom{\frac{n+i-1}{2}}{i}x^{i}&,\ \ \text{$n$ \ is even,}\\ \sum\limits_{i\in n_{o}}(-1)^{\frac{n-i}{2}}\binom{\frac{n+i}{2}}{i}x^{i}+\sum\limits_{i\in n_{e}}(-1)^{\frac{n-i-1}{2}}\binom{\frac{n+i-1}{2}}{i}x^{i}&,\ \ \text{$n$ \ is odd.}\\ \end{aligned}\right.$
		$\displaystyle=\sum\limits_{k=0}^{n}(-1)^{\lfloor\frac{n+1}{2}\rfloor+\lfloor\frac{3k}{2}\rfloor-nk-k}\binom{\lfloor\frac{n+k}{2}\rfloor}{k}x^{k},$

where $n_{o}:=\{i:0\leq i\leq n,i\ \text{is\ odd}\}$ and $n_{e}:=\{i:0\leq i\leq n,i\ \text{is \ even}\}$ .

By Lemmas 4.4 and 4.5, we get the explicit formula of $f_{A_{n}}(x)$ as follows.

Lemma 4.6.

For a given positive integer $n$ , we have

f_{A_{n}}(x)=\sum\limits_{k=0}^{n}(-1)^{\lfloor\frac{3k}{2}\rfloor}\binom{\lfloor\frac{n+k}{2}\rfloor}{k}x^{n-k}.

Compare with the definition of $P_{n}(x)$ in (2.2), we obtain the following result.

Corollary 4.7.

For a given positive integer $n$ , we have

P_{n}(x)=|I_{n}-xA_{n}|.

Now, we give all solution of the equation $f_{T_{n}}(x)=0$ as follows.

Lemma 4.8.

For a given positive integer $n$ , $T_{n}$ has $n$ distinct eigenvalues $\delta_{n,j}=2\cos\frac{(2j-1)\pi}{2n+1}$ where $j=1,2,\dots,n$ .

Proof.

By Equation (2.1) and Lemma 4.3, we get

f_{T_{n}}(x)=\frac{\sin[(n+1)\theta]-\sin n\theta}{\sin\theta}.

Here $\cos\theta=\frac{x}{2}$ . Then for $1\leq j\leq n$ , $\delta_{n,j}=2\cos\theta_{n,j}$ is a root of $f_{T_{n}}(x)$ if and only if

(4.2)

\sin[(n+1)\theta_{n,j}]-\sin n\theta_{n,j}=0.

The equality clearly holds when $\theta_{n,j}=\frac{(2j-1)\pi}{2n+1}$ , since $(n+1)\theta_{n,j}+n\theta_{n,j}=(2j-1)\pi$ . This completes the proof.

Consequently, we can obtain all the roots of $f_{A_{n}}(x)$ by Lemmas 4.4 and 4.8.

Lemma 4.9.

For a given positive integer $n$ , the unit-primitive matrix $A_{n}$ has $n$ distinct eigenvalues

\lambda_{n,j}=\frac{(-1)^{n+1}}{\delta_{n,j}}=\frac{(-1)^{n+1}}{2\cos\frac{(2j-1)\pi}{2n+1}},

where $j=1,2,\dots,n$ .

Recall Fact 4.2 says that $A_{n}=U_{n-1}(\frac{T_{n}}{2})$ . Then by Lemmas 4.8 and 4.9, we get the following result, which can also be obtained by direct calculation.

Corollary 4.10.

For $n\in\mathbb{P}$ , we have

\{U_{n-1}(\delta_{n,j}/2),j=1,\dots,n\}=\{\lambda_{n,j},j=1,\dots,n\},

where $\delta_{n,j}=2\cos\frac{(2j-1)\pi}{2n+1}$ and $\lambda_{n,j}=\frac{(-1)^{n+1}}{\delta_{n,j}}$ with $j=1,2,\dots,n$ .

Proof of Theorem 1.6.

The theorem is a direct consequence of Lemma 4.9.

Proof of Conjecture 1.

For part (i), we have

	$\displaystyle f_{A_{n}}$	$\displaystyle=\|xI_{n}-A_{n}\|$
		$\displaystyle=x^{n}\|I_{n}-\frac{1}{x}A_{n}\|$
	(by Corollary 4.7)	$\displaystyle=x^{n}P_{n}(1/x).$

Part (ii) follows by Lemma 4.9 and Corollary 4.10.

We have the following result which is useful for asymptotic analysis.

Lemma 4.11.

For $n\in\mathbb{P}$ , the eigenvalues $\lambda_{n,j}=\frac{(-1)^{n+1}}{2\cos\frac{(2j-1)\pi}{2n+1}}$ of $A_{n}$ are ordered as follows.

(1)

If $n$ is odd, then

\lambda_{n,{\lfloor\frac{n}{2}}\rfloor+2}<\cdots<\lambda_{n,{n}}<0<\lambda_{n,{1}}<\cdots<\lambda_{n,{\lfloor\frac{n}{2}\rfloor+1}},

\lambda_{n,j}>1\Leftrightarrow\frac{n+2}{3}<j<\frac{2n+3}{4},\text{ and }\lambda_{n,j}<1\Leftrightarrow\frac{2n+3}{4}<j<\frac{4n+5}{6};

(2)

If $n$ is even, then

\lambda_{n,{\lfloor\frac{n}{2}\rfloor}}<\lambda_{n,{\lfloor\frac{n}{2}\rfloor-1}}<\cdots<\lambda_{n,{1}}<0<\lambda_{n,{n}}<\lambda_{n,{n-1}}<\cdots<\lambda_{n,{\lfloor\frac{n}{2}\rfloor+1}},

\lambda_{n,j}>1\Leftrightarrow\frac{2n+3}{4}<j<\frac{4n+5}{6},\text{ and }\lambda_{n,j}<1\Leftrightarrow\frac{n+2}{3}<j<\frac{2n+3}{4}.

Moreover, the spectral radius of $A_{n}$ is given by the formula

\max_{j=1}^{n}|\lambda_{n,j}|=\lambda_{n,{\lfloor\frac{n}{2}\rfloor+1}}=U_{n}(\cos(\frac{\pi}{2n+1}))=\frac{1}{2\sin(\frac{\pi}{2(2n+1)})}.

Proof.

Observe that the function $\cos(\theta)$ is monotonically decreasing in the interval $[0,\pi]$ . The first statement is straightforward.

By comparing $|\lambda_{n,{\lfloor\frac{n}{2}}\rfloor+2}|$ with $|\lambda_{n,{\lfloor\frac{n}{2}\rfloor+1}}|$ when $n$ is odd, and similarly when $n$ is even, we see that $\max_{j=1}^{n}|\lambda_{n,j}|=\lambda_{n,{\lfloor\frac{n}{2}\rfloor+1}}$ for all $n$ .

Finally, direction computation gives

\displaystyle U_{n}(\cos(\frac{\pi}{2n+1}))

\displaystyle=\frac{\sin[(n+1)\frac{\pi}{2n+1}]}{\sin(\frac{\pi}{2n+1})}=\frac{\cos[\frac{\pi}{2(2n+1)}]}{\sin(\frac{\pi}{2n+1})}=\frac{1}{2\sin(\frac{\pi}{2(2n+1)})};

	$\displaystyle\lambda_{n,{\lfloor\frac{n}{2}\rfloor+1}}$	$\displaystyle=\frac{(-1)^{n+1}}{2\cos\frac{(2\lfloor\frac{n}{2}\rfloor+1)\pi}{2n+1}}$
		$\displaystyle=\left\{\begin{array}[]{ll}\displaystyle\frac{-1}{2\cos\frac{(n+1)\pi}{2n+1}}=\frac{1}{2\sin(\frac{\pi}{2(2n+1)})},&\text{when $n$ is even;}\\ \displaystyle\frac{1}{2\cos\frac{n\pi}{2n+1}}=\frac{1}{2\sin(\frac{\pi}{2(2n+1)})},&\text{when $n$ is odd.}\end{array}\right.$

This completes the proof.

We finish this subsection by the following byproduct by direct computation.

Proposition 4.12.

For a given positive integer $n$ , and $j=1,2,\dots,n$ , we have

f_{T_{n}}(2\cos\frac{(2j-1)\pi}{n})=\left\{\begin{aligned} -1,&\ j\neq\frac{n+1}{2},\\ (-1)^{n-1}(2n+1),&\ j=\frac{n+1}{2}.\end{aligned}\right.

4.2. Some results about $P_{n}(x)$ and the proof of Theorem 1.5

In this subsection, our goal is to give some results about $P_{n}(x)$ and prove Theorem 1.5. Our starting point is the determinant formula $P_{n}(x)=\det(I_{n}-xA_{n})$ proved in Corollary 4.7.

We use the following notations: $u_{n}=(1,1,\dots,1)^{T}\in\mathbb{R}^{n}$ and $v_{n,j}$ is the $j$ -th unit column vector in $\mathbb{R}^{n}$ ; for an order $n$ matrix $A$ , we denote by $A^{*}$ the adjoint matrix of $A$ . It is clear that $v_{n,i}^{T}A^{*}v_{n,j}$ is just the $(i,j)$ entry of $A^{*}$ , or the $(j,i)$ -minor of $A$ .

Lemma 4.13.

For $n\in\mathbb{P}$ , we have

u_{n}^{T}(I_{n}-xA_{n})^{*}v_{n,1}=P_{n-1}(-x).

Proof.

Observe that $u_{n}^{T}(I_{n}-xA_{n})^{*}v_{n,1}$ is just the sum of the first column entries of $(I_{n}-xA_{n})^{*}$ . Then it is standard to rewrite and compute as follows.

	$\displaystyle u_{n}^{T}(I_{n}-xA_{n})^{*}v_{n,1}$	$\displaystyle=\begin{vmatrix}1&-x&-x&\cdots&-x&-x\\ 1&1-x&-x&\cdots&-x&0\\ 1&-x&1-x&\cdots&0&0\\ \vdots&\vdots&\vdots&&\vdots&\vdots\\ 1&-x&0&\cdots&1&0\\ 1&0&0&\cdots&0&1\end{vmatrix}$
		(Add the multiple of column 1 by $x$ to all the other columns)
		$\displaystyle=\begin{vmatrix}1&0&0&\cdots&0&0\\ 1&1&0&\cdots&0&x\\ 1&0&1&\cdots&x&x\\ \vdots&\vdots&\vdots&&\vdots&\vdots\\ 1&0&x&\cdots&1+x&x\\ 1&x&x&\cdots&x&1+x\end{vmatrix}=\begin{vmatrix}1&0&\cdots&0&x\\ 0&1&\cdots&x&x\\ \vdots&\vdots&&\vdots&\vdots\\ 0&x&\cdots&1+x&x\\ x&x&\cdots&x&1+x\end{vmatrix}$
		$\displaystyle=P_{n-1}(-x).$

Similar determinant computation gives the following result as a byproduct.

Proposition 4.14.

For $n\geq 2$ , we have

(I_{n}-xA_{n})^{*}_{1,j}=\left\{\begin{aligned} P_{n-2}(x),\quad&j=1;\\ xP_{n-2j+1}(-x),\quad&1<j<\lfloor\frac{n+1}{2}\rfloor+1;\\ xP_{2j-n-2}(x),\quad&\lfloor\frac{n+1}{2}\rfloor<j\leq n.\end{aligned}\right.

Combining the above with $(\lambda_{n,j}E-A_{n})(\lambda_{n,j}E-A_{n})^{*}=0$ for $1\leq j\leq n$ , we obtain explicit diagonalization of $A_{n}$ as follows.

Corollary 4.15.

For a given positive integer $n$ and $1\leq j\leq n$ , the unit eigenvector of $A_{n}$ with respect to the eigenvalue $\lambda_{n,j}$ is

{\boldmath\eta_{n,j}}=\frac{2}{\sqrt{2n+1}}(\eta_{1}(\theta_{j}),\eta_{2}(\theta_{j}),\dots,\eta_{n}(\theta_{j}))^{T}

where $\theta_{j}=\frac{(2j-1)\pi}{2n+1}$ , and

\eta_{k}(\theta)=\left\{\begin{aligned} \frac{\cos\left(\frac{2n-3}{2}\theta\right)}{2\cos\theta},\quad&k=1;\\ (-1)^{k+1}\cos\left(\frac{2n-4k+3}{2}\theta\right),\quad&1<k\leq n.\end{aligned}\right.

Consequently, $U=(\eta_{n,1},\dots,\eta_{n_{n}})$ is an orthogonal matrix and $U^{T}A_{n}U=\mathop{\mathrm{diag}}(\lambda_{n,1},\dots,\lambda_{n,n})$ .

The following result follows by the explicit formula of $P_{n}(x)$ in (2.2), but we will give a determinant proof.

Lemma 4.16.

For $n\in\mathbb{P}$ , we have $P_{n+1}(x)=-xP_{n}(-x)+P_{n-1}(x).$

Proof.

We have

	$\displaystyle P_{n+1}(x)$	$\displaystyle=\|I_{n+1}-xA_{n+1}\|\qquad\text{(by splitting column 1)}$
		$\displaystyle=\underbrace{\begin{vmatrix}-x&-x&-x&\cdots&-x&-x\\ -x&1-x&-x&\cdots&-x&0\\ -x&-x&1-x&\cdots&0&0\\ \vdots&\vdots&\vdots&&\vdots&\vdots\\ -x&-x&0&\cdots&1&0\\ -x&0&0&\cdots&0&1\end{vmatrix}}_{①}+\underbrace{\begin{vmatrix}\boxed{1}&-x&-x&\cdots&-x&-x\\ 0&1-x&-x&\cdots&-x&0\\ 0&-x&1-x&\cdots&0&0\\ \vdots&\vdots&\vdots&&\vdots&\vdots\\ 0&-x&0&\cdots&1&0\\ 0&0&0&\cdots&0&\boxed{1}\end{vmatrix}}_{②}$
		$\displaystyle=\underbrace{-xP_{n}(-x)}_{①^{\prime}}+\underbrace{P_{n-1}(x)}_{②^{\prime}},$

where $①^{\prime}$ is obtained from $①$ by factoring out $-x$ from column 1 and then applying Lemma 4.13, and $②^{\prime}$ is obtained from $②$ by expanding along the two boxed entries in the determinant.

A direct consequence of Lemma 4.16 is the following.

Corollary 4.17.

For $n\in\mathbb{P}$ , we have

\frac{P_{n}(-x)}{P_{n+1}(x)}=\frac{1}{-x+\frac{P_{n-1}(x)}{P_{n}(-x)}}.

Now we give explicit formula of $F(n,x)$ and reprove Theorem 1.3.

Theorem 4.18.

For $n\in\mathbb{N}$ , we have $F(n,x)=\frac{P_{n}(-x)}{P_{n+1}(x)}$ . Consequently by Corollary 4.17, the continued fraction formulas in Theorem 1.3 hold true.

Proof.

	$\displaystyle F(n,x)$	$\displaystyle=\sum\limits_{k=0}^{\infty}WL_{k}(n)x^{k}=\sum\limits_{k=0}^{\infty}(u_{n+1}^{T}A_{n+1}^{k}u_{n+1})x^{k+1}+1$
		$\displaystyle=\sum\limits_{k=0}^{\infty}(u_{n+1}^{T}A_{n+1}^{k}v_{n+1,1})x^{k}=u_{n+1}^{T}(I_{n+1}-xA_{n+1})^{-1}v_{n+1,1}$
		$\displaystyle=\frac{u_{n+1}^{T}(I_{n+1}-xA_{n+1})^{*}v_{n+1,1}}{\|I_{n+1}-xA_{n+1}\|}$
	(by Corollary 4.7)	$\displaystyle=\frac{u_{n+1}^{T}(I_{n+1}-xA_{n+1})^{*}v_{n+1,1}}{P_{n+1}(x)}$
	(by Lemma 4.13)	$\displaystyle=\frac{P_{n}(-x)}{P_{n+1}(x)}.$

Next we derive a trig representation of $P_{n}(x)$ with the help of $T_{n}$ .

Lemma 4.19.

Let $n\in\mathbb{P}$ . Then we have

P_{n}(x)=(-1)^{\binom{n+1}{2}}f_{T_{n}}\left((-1)^{n+1}x\right).

Thus $P_{n}(x)$ has $n$ distinct roots $\frac{(-1)^{n+1}}{\delta_{n,j}},\ 1\leq j\leq n$ , where $\delta_{n,j}=2\cos\frac{(2j-1)\pi}{2n+1}$ .

Proof.

By Lemma 4.5, we have

	$\displaystyle(-1)^{\binom{n+1}{2}}f_{T_{n}}((-1)^{n+1}x)$	$\displaystyle=\sum\limits_{k=0}^{n}(-1)^{\lfloor\frac{n+1}{2}\rfloor+\lfloor\frac{3k}{2}\rfloor-nk-k+\binom{n+1}{2}}\binom{\lfloor\frac{n+k}{2}\rfloor}{k}(-x)^{(n+1)k}$
		$\displaystyle=\sum\limits_{k=0}^{n}(-1)^{\lfloor\frac{3k}{2}\rfloor}\binom{\lfloor\frac{n+k}{2}\rfloor}{k}x^{k}=P_{n}(x).$

By Theorem 4.8, $P_{n}(x)$ has $n$ distinct roots $\frac{(-1)^{n+1}}{\delta_{n,j}}$ as stated in the lemma.

Note that we can also prove this lemma by using the recursions in Lemmas 4.3 and 4.16.

Lemma 4.20.

For $n\in\mathbb{P}$ , we have

P_{n}(x)=\frac{\sin(n+1)\theta-\sin n\theta}{\sin\theta}(-1)^{\binom{n+1}{2}}=\frac{\cos\left(\frac{2n+1}{2}\theta\right)}{\cos\frac{\theta}{2}}(-1)^{\binom{n+1}{2}},

where $\cos\theta=\frac{(-1)^{n+1}x}{2}$ .

Proof.

By Lemma 4.19 and 4.3, we have

	$\displaystyle P_{n}(x)$	$\displaystyle=(-1)^{\binom{n+1}{2}}f_{T_{n}}\left((-1)^{n+1}x\right)$
		$\displaystyle=(-1)^{\binom{n+1}{2}}\left[U_{n}\left((-1)^{n+1}x/2\right)-U_{n-1}\left((-1)^{n+1}x/2\right)\right]$
		$\displaystyle=\frac{\sin(n+1)\theta-\sin n\theta}{\sin\theta}(-1)^{\binom{n+1}{2}}$
		$\displaystyle=\frac{2\cos\left(\frac{2n+1}{2}\theta\right)\sin\frac{\theta}{2}}{\sin\theta}(-1)^{\binom{n+1}{2}}$
		$\displaystyle=\frac{\cos\left(\frac{2n+1}{2}\theta\right)}{\cos\frac{\theta}{2}}(-1)^{\binom{n+1}{2}}.$

Proof of Theorem 1.5.

We have

	$\displaystyle F(n,x)$	$\displaystyle=\frac{P_{n}(-x)}{P_{n+1}(x)}\quad(\text{by Corollary \ref{cor:P-recursive}})$
		$\displaystyle=(-1)^{n+1}\frac{\frac{\sin(n+1)\theta^{\prime}-\sin n\theta^{\prime}}{\sin\theta^{\prime}}}{\frac{\sin(n+2)\theta-\sin(n+1)\theta}{\sin\theta}}\quad(\text{by\ Lemma\ \ref{lem:Pn-theta}})$
		$\displaystyle=(-1)^{n+1}\frac{\sin(n+1)\theta-\sin n\theta}{\sin(n+2)\theta-\sin(n+1)\theta}$
		$\displaystyle=(-1)^{n+1}\frac{\cos(\frac{2n+1}{2}\theta)}{\cos(\frac{2n+3}{2}\theta)},$

where $\cos\theta=\frac{(-1)^{n+2}x}{2}$ and $\cos\theta^{\prime}=\frac{(-1)^{n+1}(-x)}{2}=\cos\theta$ so that we choose $\theta=\theta^{\prime}$ .

Corollary 4.21.

For $n\in\mathbb{P}$ , the partial fraction decomposition of $F(n-1,x)$ is:

(4.3)

F(n-1,x)=\sum_{j=1}^{n}\frac{\gamma_{n,j}}{1-x_{n,j}x},

where $x_{n,j}=\frac{(-1)^{n+1}}{2\cos\theta_{j}}$ with $\theta_{j}=\frac{\pi(2j-1)}{2n+1}$ for $j=1,\dots,n$ . Moreover, $\gamma_{n,j}=(-1)^{n+1}\frac{2\cos\theta_{j}\tan^{2}\theta_{j}}{2n+1}$ , and asymptotically we have

WL_{N}(n-1)\sim\frac{\left(\csc\frac{\pi}{2(2n+1)}\right)^{N-1}\cot^{2}\frac{\pi}{2(2n+1)}}{2^{N-1}(2n+1)},\quad N\to\infty.

Proof.

The partial fraction (4.3) follows by Lemmas 4.18 and 4.19, where $x_{n,j}=(-1)^{n+1}\delta_{n,j}=\frac{(-1)^{n+1}}{2\cos\theta_{j}}$ , and $\gamma_{n,j}$ are constants for all $j=1,\dots,n$ .

For a particular $j$ , the constant $\gamma_{n,j}$ can be computed by using L’Hospital’s rule, where we need the relation $2\cos\theta=(-1)^{n+1}x$ and $\mathrm{d}x=2(-1)^{n+2}\sin\theta\mathrm{d}\theta$ .

	$\displaystyle\gamma_{n,j}$	$\displaystyle=\frac{P_{n-1}(-x)}{P_{n}(x)}(1-x_{n,j}x)\Big{\|}_{x=\frac{1}{x_{n,j}}}$
		$\displaystyle=(-1)^{n}\frac{\cos(\frac{2n-1}{2}\theta)}{\cos(\frac{2n+1}{2}\theta)}(1-x_{n,j}x)\Big{\|}_{\theta=\theta_{j}}$
		$\displaystyle=(-1)^{n}\frac{\cos(\frac{2n-1}{2}\theta)}{-\frac{2n+1}{2}\sin(\frac{2n+1}{2}\theta)\mathrm{d}\theta}(-x_{n,j}\mathrm{d}x)\Big{\|}_{\theta=\theta_{j}}$
		$\displaystyle=(-1)^{n+1}\frac{\cos(\frac{2n-1}{2}\theta_{j})\tan\theta_{j}}{\frac{2n+1}{2}\sin(\frac{2n+1}{2}\theta_{j})}$
		$\displaystyle=(-1)^{n+1}\frac{2\sin\theta_{j}\tan\theta_{j}}{2n+1}=(-1)^{n+1}\frac{2\cos\theta_{j}\tan^{2}\theta_{j}}{2n+1}.$

By Theorem 4.11, $\max\{x_{n,j},j=1,2,\dots,n\}=x_{n,\lfloor\frac{n}{2}\rfloor+1}$ , denote by $2\cos(\tau)$ . By the fact $\cos(\tau)=\cos\frac{\pi(2\lfloor\frac{n}{2}\rfloor+1)}{2n+1}=(-1)^{n+1}\sin\frac{\pi}{2(2n+1)}$ and $\sin(\tau)=\cos\frac{\pi}{2(2n+1)}$ , we have

WL_{N}(n-1)\sim\gamma_{n,\lfloor\frac{n}{2}\rfloor+1}x_{n,\lfloor\frac{n}{2}\rfloor+1}^{N}=\frac{\left(\csc\frac{\pi}{2(2n+1)}\right)^{N-1}\cot^{2}\frac{\pi}{2(2n+1)}}{2^{N-1}(2n+1)},\quad N\to\infty.

In particular, it is an easy exercise in calculus to show that

T({n-1,n-1})=WL_{n-1}(n-1)\sim\frac{2^{n+1}n^{n-1}\sqrt{e}}{\pi^{n}},n\to\infty.

Remark 4.22.

Let $C_{k}$ be the graph of a $k$ -cycle with $k\geq 3$ . It was shown in [1] that $WC_{k}(n)=\textrm{trace}(A_{n+1}^{k})$ , and

CF(n,x)=\sum_{k\geq 1}WC_{k}(n)x^{k}=\left\lfloor\frac{n+1}{2}\right\rfloor x-\frac{x\frac{d}{dx}P_{n+1}(x)}{P_{n+1}(x)}.

Then we can obtain more explicit formula of $CF(n,x)$ . Moreover, we have

WC_{N}(n-1)\sim\left(\frac{(-1)^{(n+1)}}{2\cos\tau}\right)^{N}=\left(\frac{\csc\frac{\pi}{2(2n+1)}}{2}\right)^{N},\qquad N\to\infty.

5. Some results on the generating function of $T(n,m)$

In this section, our main goal is to prove Conjectures 2-6.

5.1. Proof of Conjectures 2-3

If we assume Theorem 1.2 holds true, then $T(n,x)=\rho(L_{n},x)=Ehr(L_{n},x)$ has been studied. For instance, [1, Corollary 3.8] asserts that

\rho(L_{n},x)=\frac{H(x)}{(1-x)^{n+1}}

for some symmetric polynomial $H(x)$ of degree at most $n$ . Here by saying that $H(x)$ is symmetric, we mean that $x^{d}H(1/x)=H(x)$ if $\deg H(x)=d$ . Such $H(x)$ is also called palindromic in some literature. Indeed Bona et. al. gave a description of $\rho(G,x)$ when $G$ is a simple bipartite graph in [1, Theorem 3.6]. But they seemed to be unaware of Conjectures 2-3 and didn’t study $\deg H(x)$ .

Lee et. al. [8] studied the Ehrhart series of graph polytopes and claimed that Conjectures 2-3 are consequences of their Theorem 4 by showing that $P(L_{n})$ is an $n$ -dimensional regular positive reflexive polytope with parameter $k=2$ (see the paper for the concepts). Their claim is true, but need to modular Theorem 1.2.

The two conjectures can also be attacked by the magic labelling model. Firstly, Stanley [13] studied magic labellings of general pseudo graphs and give a characterization of $\mathcal{M}(G,x)$ . In particular, $\mathcal{M}(G,x)$ has denominator $(1-x)^{n+1}$ if the graph obtained by removing all loops from $G$ is bipartite. Since removing all loops from $\tilde{L}_{n}$ is just $L_{n+1}$ , $\mathcal{M}(\tilde{L}_{n})$ is of the desired form $\frac{H(x)}{(1-x)^{n+1}}$ .

For details of the numerator $H(x)$ , we would like to introduce Stanley’s Reciprocity Theorem, which is a more general result and seems easier to use. We basically follow [EC1, Chapter 4.6].

Let $A$ be an $r$ by $n$ matrix with integer entries. The null space of $A$ is denoted $\mathbf{nul}(A)=\{\alpha\in\mathbb{R}^{n}:A\alpha=0\}$ , which is also the solution space $\mathbf{nul}(\Phi)$ of the homogeneous linear Diophantine system $\Phi:\ A\mathbf{x}=\mathbf{0}$ . The $\mathbb{N}$ -solution set $\mathbf{nul}(A)\cap\mathbb{N}^{n}$ forms an additive monoid (semigroup with a unit). Stanly’s Reciprocity Theorem [13][Theorem 4.1] gives a nice connection between the following two generating functions:

E(\mathbf{x})=\sum\limits_{(\alpha_{1},...,\alpha_{n})\in\mathbf{nul}(A)\cap\mathbb{N}^{n}}x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{n}^{\alpha_{n}},\ \ \bar{E}(\mathbf{x})=\sum\limits_{(\alpha_{1},...,\alpha_{n})\in\mathbf{nul}(A)\cap\mathbb{P}^{n}}x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{n}^{\alpha_{n}}.

For further references and generalizations, see [14].

Theorem 5.1.

(Stanley’s Reciprocity Theorem). Let $A$ be an $r$ by $n$ integral matrix of full rank $r$ . If there is at least one $\alpha\in\mathbb{P}^{n}\cap\mathbf{nul}(A)$ , then we have as rational functions

\bar{E}(x_{1},...,x_{n})=(-1)^{n-r}E(x_{1}^{-1},...,x_{n}^{-1}).

Sketched Proof of Conjectures 2-3.

By Theorem 1.2 and the discussion above, we have shown

T(n,x)=M(\tilde{L}_{n},x)=\frac{H(x)}{(1-x)^{n+1}}.

To prove Conjectures 2-3, it is sufficient to show that

x^{3}\mathcal{M}(\tilde{L}_{n},x)=(-1)^{n+1}\mathcal{M}(\tilde{L}_{n},x^{-1}).

This will be explained by Stanley’s Reciprocity Theorem.

Firstly, the system $\Phi$ of homogeneous linear Diophantine equations is given by

\Phi:\ m_{i-1}+m_{i}+\ell_{i}-s=0,\quad 1\leq i\leq n+1,\text{ set }m_{0}=m_{n+1}=0.

See Figure 4 for the $n=3$ case. Secondly, the generating function $E(\mathbf{x})$ refers to

E(\mathbf{y},\mathbf{z},x)=\sum_{(m_{1},\dots,m_{n},\ell_{1},\dots,\ell_{n+1},s)\in\mathbf{nul}(\Phi)\cap\mathbb{N}^{2n+2}}y_{1}^{m_{1}}\cdots y_{n}^{m_{n}}z_{1}^{\ell_{1}}\cdots z_{n+1}^{\ell_{n+1}}x^{s},

and similarly for $\bar{E}(\mathbf{y},\mathbf{z},x)$ . It is clear that $\mathcal{M}(\tilde{L}_{n},x)=E(1,1,\dots,1,x)$ . Thirdly, the vector $\eta=(1,\dots,1,3)$ belongs to $\mathbb{P}^{2n+2}\cap\mathbf{nul}(\Phi)$ so that Stanley’s Reciprocity Theorem applies. Finally, observe that $\alpha\in\mathbb{P}^{2n+2}\cap\mathbf{nul}(\Phi)\Leftrightarrow\alpha-\eta\in\mathbb{N}^{2n+2}\cap\mathbf{nul}(\Phi)$ . It follows that $\bar{E}(\mathbf{y},\mathbf{z},x)=y_{1}\cdots y_{n}z_{1}\cdots z_{n+1}x^{3}E(\mathbf{y},\mathbf{z},x)$ , and consequently

x^{3}\mathcal{M}(\tilde{L}_{n},x)=(-1)^{n+1}\mathcal{M}(\tilde{L}_{n},x^{-1}),

as desired.

It is worth mentioning that Chen et al [5] proved that $H(x)$ is unimodal.

5.2. Proof of Conjecture 4

Though $M_{n-2-i,i}$ is defined using the row generating function $T(n,x)$ , the proof of Conjecture 4 relies on the column generating function $T(x,m)=F(m,x)$ .

Firstly, we need to represent $M_{n-2-i,i}$ in terms of $T(n,m)$ .

Lemma 5.2.

For $m,n\in\mathbb{N}$ , we have

(5.1)

M_{n-2-m,m}=\sum\limits_{k=0}^{m}\binom{n+1}{k}T(n,m-k)(-1)^{k}.

Note that $M_{-i,m}=0$ for $i\geq 0$ .

Proof.

The lemma follows by comparing the coefficients of $x^{m}$ on both sides of

(1-x)^{n+1}\sum_{k\geq 0}T(n,k)x^{k}=\sum\limits_{i=0}^{n-2}M_{n-2-i,i}x^{i}.

Define $M_{m}(x)=\sum\limits_{n=0}^{\infty}M_{n,m}x^{n}$ . Then, we get the following lemma.

Lemma 5.3.

For $m,n\in\mathbb{N}$ and $n\geq 2$ , we have

M_{m}(x)=x^{-m-2}\sum\limits_{n=0}^{\infty}\left(\sum\limits_{k=0}^{m}\binom{n+1}{k}T(n,m-k)(-1)^{k}\right)x^{n}.

Proof.

By Lemma 5.2, we get

\sum\limits_{n=0}^{\infty}M_{n-2-m,m}x^{n}=\sum\limits_{n=0}^{\infty}\left(\sum\limits_{k=0}^{m}\binom{n+1}{k}T(n,m-k)(-1)^{k}\right)x^{n},

which is equivalent to the equation

x^{2+m}M_{m}(x)=\sum\limits_{n=0}^{\infty}\left(\sum\limits_{k=0}^{m}\binom{n+1}{k}T(n,m-k)(-1)^{k}\right)x^{n}.

Then, we have $M_{m}(x)=x^{-m-2}\sum\limits_{n=0}^{\infty}\left(\sum\limits_{k=0}^{m}\binom{n+1}{k}T(n,m-k)(-1)^{k}\right)x^{n}.$

In terms of $F(m,x)=T(x,m)=\sum\limits_{k=0}^{\infty}T(k,m)x^{k},$ we obtain:

Theorem 5.4.

For $m,n\in\mathbb{N}$ and $n\geq 2$ , we have

M_{m}(x)=x^{-m-2}\sum\limits_{k=0}^{m}(-1)^{k}\frac{\mathrm{d}^{k}(xF(m-k,x))}{\mathrm{d}x}\frac{x^{k-1}}{k!}.

Or equivalently by Theorem 4.18, we have

M_{n}(x)=x^{-n-2}\sum\limits_{k=0}^{n}(-1)^{k}\frac{\mathrm{d}^{k}(x\frac{P_{n-k}(-x)}{P_{n+1-k}(x)})}{\mathrm{d}x}\frac{x^{k-1}}{k!}.

Proof.

For $m,n\in\mathbb{N}$ and $n\geq 2$ , and by Lemma 5.3, we get

	$\displaystyle M_{m}(x)$	$\displaystyle=x^{-m-2}\sum\limits_{n=0}^{\infty}\left(\sum\limits_{k=0}^{m}\binom{n+1}{k}T(n,m-k)(-1)^{k}\right)x^{n}$
		$\displaystyle=x^{-m-2}\sum\limits_{k=0}^{m}\left(\sum\limits_{n=0}^{\infty}\binom{n+1}{k}T(n,m-k)(-1)^{k}\right)x^{n}$
		$\displaystyle=x^{-m-2}\sum\limits_{k=0}^{m}(-1)^{k}\frac{\mathrm{d}^{k}(F(m-k,x)x)}{\mathrm{d}x}\frac{x^{k-1}}{k!}.$

To prove Conjecture 4, we need two more lemmas. Firstly let us define the degree of a rational function $f(x)/g(x)$ to be $\deg f(x)/g(x)=\deg f(x)-\deg g(x)$ .

Lemma 5.5.

Let $R_{1}(x)$ and $R_{2}(x)$ be any two nonzero rational functions. Then we have

(1)

$\deg R_{1}(x)\pm R_{2}(x)\leq\max(\deg R_{1}(x),\deg R_{2}(x))$ , and we always have the equality if $\deg R_{1}(x)\neq\deg R_{2}(x)$ ;
(2)

$\deg R_{1}(x)R_{2}(x)=\deg R_{1}(x)+\deg R_{2}(x)$ ;
(3)

$\deg R_{1}^{\prime}(x)\leq\deg R_{1}(x)-1$ . Consequently, $\deg R_{1}^{(k)}(x)\leq\deg R_{1}(x)-k$ .

Proof.

The first two items are obvious. The third one follows by the quotient rule of derivatives. More precisely, write $R_{1}(x)=f(x)/g(x)$ . Then

R_{1}^{\prime}(x)=\frac{f^{\prime}(x)g(x)-f(x)g^{\prime}(x)}{g(x)^{2}}.

Item 3 follows since $\deg f^{\prime}(x)g(x)=\deg f(x)g^{\prime}(x)=\deg f(x)+\deg g(x)-1$ .

Lemma 5.6.

For given $n\in\mathbb{P}$ , we have $\deg xF(n,x)+1\leq-2$ .

Proof.

By Theorem 4.18, it suffice to show that $\deg\left(xP_{n}(-x)+P_{n+1}(x)\right)\leq n-1$ .

By the explicit formula of $P_{n}(x)$ in , we have

	$\displaystyle xP_{n}(-x)$	$\displaystyle+P_{n+1}(x)=x\sum\limits_{i=0}^{n}(-1)^{\lfloor\frac{3i}{2}\rfloor}\binom{\lfloor\frac{n+i}{2}\rfloor}{i}(-x)^{i}+\sum\limits_{i=0}^{n+1}(-1)^{\lfloor\frac{3i}{2}\rfloor}\binom{\lfloor\frac{n+1+i}{2}\rfloor}{i}x^{i}$
		$\displaystyle=\left((-1)^{\lfloor\frac{3n}{2}\rfloor+n}+(-1)^{\lfloor\frac{3n+3}{2}\rfloor}\right)x^{n+1}+\left((-1)^{\lfloor\frac{3n-3}{2}\rfloor+n-1}+(-1)^{\lfloor\frac{3n}{2}\rfloor}\right)x^{n}+Q_{n-1}(x)$
		$\displaystyle=Q_{n-1}(x),$

where $Q_{n-1}(x)$ is a polynomial of degree at most $n-1$ . This completes the proof.

Proof of Conjecture 4.

By Theorem 5.4, we need to analyze the property of each summand.

For the term for $k=0$ , $xF(n,x)\cdot x^{-1}$ has degree $-1$ and denominator $P_{n+1}(x)$ .

For each term for $k$ with $1\leq k\leq n$ , $(xF(n-k,x))^{(k)}$ clearly has denominator $P_{n-k+1}(x)^{k+1}$ . By Lemma 5.6, it has degree

\deg\frac{x^{k}}{k!}(xF(n-k,x))^{(k)}=\deg x^{k}(xF(n-k,x)+1)^{(k)}\leq-2.

Thus

\deg\sum\limits_{k=1}^{m}(-1)^{k}\frac{\mathrm{d}^{k}(xF(n-k,x))}{\mathrm{d}x}\frac{x^{k-1}}{k!}\leq-2.

It follows that $\deg M_{n}(x)=-3-n$ .

By taking common denominators, we see that

M_{n}(x)=\frac{G_{n}(x)}{(P_{1}(x))^{n+1}(P_{2}(x))^{n}...(P_{n}(x))^{2}P_{n+1}(x)}

for some polynomial $G_{n}(x)$ . This proved part (1).

Next, the degree of the displayed denominator of $M_{n}(x)$ is equal to

\displaystyle\sum\limits_{i=1}^{n+1}i(n+2-i)

\displaystyle=\frac{(n+1)(n+2)(n+3)}{6}.

This proves part (3).

Finally,

\deg G(x)=\frac{(n+1)(n+2)(n+3)}{6}+\deg M_{n}(x)=\frac{(n-1)(n+3)(n+4)}{6}.

This proves part (2).

Remark 5.7.

From the proof, we see that in general $G_{n}(x)$ need not be coprime to the displayed denominator. Indeed, the degree of the denominator of $M_{7}(x)$ in Equation 2.4 is 120, but our computation by Maple shows that the degree of the denominator of $M_{7}(x)$ is 118. The reason is that $P_{1}(x)$ and $P_{7}(x)$ have a common factor $x-1$ , where $P_{1}(x)=-x+1$ and $P_{7}(x)=\left(x-1\right)\left({x}^{2}-x-1\right)\left({x}^{4}+{x}^{3}-4\,{x}^{2}-4\,x+1\right)$ .

5.3. Proof of Conjecture 5

By using Theorem 5.4, Maple can easily produce $M_{n}(x)$ for $n\leq 11$ ?. However the result becomes too complex to print here, so we only do the cases for $n=1,2,3,4$ . Conjecture 5 then follows by our computation.

Example 5.8.

$M_{0}(x)=1/(1-x)$ . This follows easily by $M_{n,0}=1$ for $n\in\mathbb{N}$ .

Example 5.9.

$M_{1}(x)=\frac{1}{(1-x)^{2}(1-x-x^{2})}$ .

Proof.

By Theorem 5.4, we get

	$\displaystyle M_{1}(x)$	$\displaystyle=x^{-3}\sum\limits_{k=0}^{1}(-1)^{k}\frac{\mathrm{d}^{k}(F(1-k,x)x)}{\mathrm{d}x}\frac{x^{k-1}}{k!}$
		$\displaystyle=x^{-3}\left(F(1,x)-\frac{\mathrm{d}^{1}(F(0,x)x)}{\mathrm{d}x}\right)$
		$\displaystyle=x^{-3}\left(\frac{1+x}{1-x-{x}^{2}}-\frac{1}{\left({1-x}\right)^{2}}\right)$
		$\displaystyle=\frac{1}{\left({1-x}\right)^{2}\left({1-x-{x}^{2}}\right)}.$

Example 5.10.

$M_{2}(x)=\frac{1-x^{2}-x^{3}-x^{4}+x^{5}}{(1-x)^{3}(1-x-x^{2})^{2}(1-2x-x^{2}+x^{3})}$ .

Proof.

By Theorem 5.4, we get

	$\displaystyle M_{2}(x)$	$\displaystyle=x^{-4}\sum\limits_{k=0}^{2}(-1)^{k}\frac{\mathrm{d}^{k}(F(2-k,x)x)}{\mathrm{d}x}\frac{x^{k-1}}{k!}$
		$\displaystyle=x^{-4}\left(\frac{1+x-{x}^{2}}{1-2\,x-{x}^{2}+{x}^{3}}-\left(\frac{\left({1+x}\right)x}{1-x-{x}^{2}}\right)^{\prime}+\frac{x}{\left({1-x}\right)^{3}}\right)$
		$\displaystyle=\frac{{1-{x}^{2}-{x}^{3}-{x}^{4}+{x}^{5}}}{\left({1-x}\right)^{3}\left({1-x-{x}^{2}}\right)^{2}\left({1-2\,x-{x}^{2}+{x}^{3}}\right)}.$

Here $(f(x))^{\prime}$ means the derivative of $f(x)$ with respect to $x$ .

Example 5.11.

M_{3}(x)=\frac{N_{3}(x)}{(1-x)^{4}(1-x-x^{2})^{3}(1-2x-x^{2}+x^{3})^{2}(1-2x-3x^{2}+x^{3}+x^{4})},

where

N_{3}(x)=1+x-6\,{x}^{2}-15\,{x}^{3}+21\,{x}^{4}+35\,{x}^{5}-13\,{x}^{6}-51\,{x}^{7}+3\,{x}^{8}\\ +21\,{x}^{9}+5\,{x}^{10}+{x}^{11}-5\,{x}^{12}-{x}^{13}+{x}^{14}.

Proof.

By Theorem 5.4, we get

	$\displaystyle M_{3}(x)=\frac{1}{x^{5}}\sum\limits_{k=0}^{3}(-1)^{k}\frac{\mathrm{d}^{k}(F(3-k,x)x)}{\mathrm{d}x}\frac{x^{k-1}}{k!}$
	$\displaystyle=\frac{1}{x^{5}}\left(\frac{1+2\,x-{x}^{2}-{x}^{3}}{1-2\,x-3\,{x}^{2}+{x}^{3}+{x}^{4}}-\frac{1+2\,x-4\,{x}^{2}+2\,{x}^{3}}{\left({1-2\,x-{x}^{2}+{x}^{3}}\right)^{2}}+\frac{x\left({2+3\,x+3\,{x}^{2}}\right)}{\left({1-x-{x}^{2}}\right)^{3}}-\frac{x^{2}}{\left({1-x}\right)^{4}}\right).$

Simplifying gives the desired formula.

Example 5.12.

M_{4}(x)=\frac{N_{4}(x)}{(1-x)^{5}(1-x-x^{2})^{4}(1-2x-x^{2}+x^{3})^{3}(P_{4}(x))^{2}P_{5}(x)},

where

	$\displaystyle N_{4}(x)=1+$	$\displaystyle 4x-31x^{2}-67x^{3}+348x^{4}+418x^{5}-1893x^{6}-1084x^{7}+4326x^{8}$
		$\displaystyle+4295x^{9}-7680x^{10}-9172x^{11}+9104x^{12}+11627x^{13}-5483x^{14}-10773x^{15}$
		$\displaystyle+1108x^{16}+7255x^{17}+315x^{18}-3085x^{19}-228x^{20}+669x^{21}$
		$\displaystyle+102x^{22}-23x^{23}-45x^{24}-16x^{25}+11x^{26}+2x^{27}-x^{28}.$

Proof.

By Theorem 5.4, we get

	$\displaystyle M_{4}(x)$	$\displaystyle=x^{-6}\sum\limits_{k=0}^{4}(-1)^{k}\frac{\mathrm{d}^{k}(F(4-k,x)x)}{\mathrm{d}x}\frac{x^{k-1}}{k!}$
		$\displaystyle=x^{-6}\left(\frac{1+2\,x-3\,{x}^{2}-{x}^{3}+{x}^{4}}{1-3\,x-3\,{x}^{2}+4\,{x}^{3}+{x}^{4}-{x}^{5}}-\frac{1+4\,x-4\,{x}^{2}-2\,{x}^{3}+4\,{x}^{4}+2\,{x}^{5}}{\left({1-2\,x-3\,{x}^{2}+{x}^{3}+{x}^{4}}\right)^{2}}\right)$
		$\displaystyle+x^{-6}\left(\frac{x\left({3+3\,{x}^{2}-11\,{x}^{3}+9\,{x}^{4}-3\,{x}^{5}}\right)}{\left({1-2\,x-{x}^{2}+{x}^{3}}\right)^{3}}-\frac{x^{2}\left({3+8\,x+6\,{x}^{2}+4\,{x}^{3}}\right)}{\left({1-x-{x}^{2}}\right)^{4}}+\frac{x^{3}}{\left({1-x}\right)^{5}}\right).$

Simplifying gives the desired result.

5.4. Proof of Conjecture 6

Our proof relies on Corollary 4.21, we first give a lemma.

By Equation (5.1), we have

M_{n-2-m,m}=\sum\limits_{k=0}^{m}\binom{n+1}{k}T(n,m-k)(-1)^{k}.

Furthermore, by Corollary 4.21, we can obtain the following result.

Lemma 5.13.

For $n-2\geq m$ , we have

M_{n-2-m,m}\sim\frac{\left(\csc\frac{\pi}{2(2m+1)}\right)^{n-1}\cot^{2}\frac{\pi}{2(2m+1)}}{2^{n-1}(2m+1)},\quad n\to\infty.

Proof of Conjecture 6.

We have

		$\displaystyle\mathrm{lim}_{n\rightarrow\infty}\frac{M_{n+1,m}}{M_{n,m}}$
		$\displaystyle=\mathrm{lim}_{n\rightarrow\infty}\frac{\frac{\left(\csc\frac{\pi}{2(2m+1)}\right)^{n+m+2}\cot^{2}\frac{\pi}{2(2m+1)}}{2^{n}(2m+1)}}{\frac{\left(\csc\frac{\pi}{2(2m+1)}\right)^{n+m+1}\cot^{2}\frac{\pi}{2(2m+1)}}{2^{n-1}(2m+1)}}$
		$\displaystyle=\frac{1}{2\sin\frac{\pi}{2(2m+1)}}$
		$\displaystyle=\frac{(-1)^{m+1}}{2\cos(\frac{(2\lfloor\frac{m}{2}\rfloor+1)\pi}{2m+1})}$
	(by Corollary 4.11)	$\displaystyle=U_{m}(\cos(\frac{\pi}{2m+1})).$

Acknowledgments: The authors would like to thank Bóna for helpful conversations.

References

[1] M. Bóna, H.-K. Ju and R. Yoshida, On the enumeration of a certain weighted graphs, Discrete Applied Math., 155, 1481–1496, 1988.
[2] M. Bóna, H.-K. Ju and R. Yoshida, Zigzag posets and wall posets, in preparation.
[3] S. J. Cyvin and I. Gutman, Kekul¨¦ structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, pp. 142–144, 1988.
[4] P.A. Damianou, On the characteristic polynomial of Cartan matrices and Chebyshev polynomials, arXiv:1110.6620, 2011.
[5] Herman Z.Q. Chen and Philip B. Zhang, The unimodality of the Ehrhart $\delta$ -polynomial of the chain polytope of the zig-zag poset, arXiv:1603.08283, 2016.
[6] Frank Harary, Graph Theory, Reading, Massachusetts, Addison-Wesley, 1969.
[7] L. E. Jeffery, Danzer matrix, https://oeis.org/wiki/User:L._Edson_Jeffery/Unit-Primitive_Matrices.
[8] Daeseok Lee and Hyeong-Kwan Ju, An extension of Hibi’s palindromic theorem, arXiv:1503.05658, 2015.
[9] The On-Line Encyclopedia of Integer Sequences.
[10] J. Spanier and K. B. Oldham, “The Chebyshev Polynomials $T_{n}(x)$ and $U_{n}(x)$ ,” Ch. 22 in An Atlas of Functions. Washington, DC: Hemisphere, pp. 193–207, 1987.
[11] R. Stanley, Volumes and Ehrhart polynomials of convex polytopes, available at (http://www-math.mit.edu/ rstan/trans.html), 1999.
[12] R. Stanley, Enumerative Combinatorics, vol. I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997.
[13] R. Stanley, Linear homogeneous diophantine equations and magic labelings of graphs, Duke Math. J. 40, 607–632, 1973.
[14] Guoce Xin, A generalization of Stanley’s monster reciprocity theorem, Journal of Combinatorial Theorem series A, 114(8):1526–1544, 2007.
[15] G.M. Ziegler, Graphs of Polytopes, In: Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152. Springer, New York, NY, 1995.

Proving some conjectures on Kekulé numbers for certain benzenoids by using Chebyshev polynomials

Abstract.

1. Introduction

Definition 1.1.

1.1. Kekulé structures

1.2. Combinatorial Models

Theorem 1.2.

Theorem 1.3.

1.3. Main Results

Theorem 1.4.

Theorem 1.5.

Theorem 1.6.

1.4. Summary

2. Six Conjectures Related to T​(n,m)T(n,m)

Conjecture 1.

Lemma 2.1.

Proof.

Conjecture 2.

Conjecture 3.

Conjecture 4.

Conjecture 5.

Conjecture 6.

3. Proofs of Theorems 1.3 and 1.4

Lemma 3.1.

Proof.

3.1. Proof of Theorem 1.4

Lemma 3.2.

Proof.

Lemma 3.3.

Proof.

Lemma 3.4.

Proof.

Theorem 3.5.

Corollary 3.6.

Proof.

3.2. Proof of Theorem 1.3

Lemma 3.7.

Proof.

Lemma 3.8.

Proof.

Lemma 3.9.

Proof.

Theorem 3.10.

Proof.

Corollary 3.11.

Proof.

First Proof of Theorem 1.3.

Theorem 3.12.

Proof.

Corollary 3.13.

Corollary 3.14.

4. Some results about AnA_{n}

4.1. The Characteristic polynomial of AnA_{n}

Theorem 4.1.

Fact 4.2.

Lemma 4.3.

Proof.

Lemma 4.4.

Proof.

Lemma 4.5.

Proof.

Lemma 4.6.

Corollary 4.7.

Lemma 4.8.

Proof.

Lemma 4.9.

Corollary 4.10.

Proof of Theorem 1.6.

Proof of Conjecture 1.

Lemma 4.11.

Proof.

Proposition 4.12.

4.2. Some results about Pn​(x)P_{n}(x) and the proof of Theorem 1.5

Lemma 4.13.

Proof.

Proposition 4.14.

Corollary 4.15.

Lemma 4.16.

Proof.

Corollary 4.17.

2. Six Conjectures Related to $T(n,m)$

4. Some results about $A_{n}$

4.1. The Characteristic polynomial of $A_{n}$

4.2. Some results about $P_{n}(x)$ and the proof of Theorem 1.5

5. Some results on the generating function of $T(n,m)$