\documentclass[12pt,reqno]{article}
%\sloppy
\usepackage
[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.2in}
\setlength{\textheight}{8.0in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\makeatletter
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\def\endofproofmark{$\Box$}
\def\RR{{\mathbb R}}
\def\NN{{\mathbb N}}
\def\endofproofmark{$\Box$}
\begin{center}
\vskip 1cm
{\LARGE\bf
On an Integer Sequence Related to
a Product of Trigonometric Functions, and its
Combinatorial Relevance}
\vskip 1cm
\large Dorin Andrica \\
\vskip .5cm
``Babe\c s--Bolyai'' University\\
Faculty of Mathematics and Computer Science\\
Str. M. Kog\v alniceanu nr. 1\\
3400 Cluj--Napoca, Romania \\
\href{mailto:dandrica@math.ubbcluj.ro}{\tt dandrica@math.ubbcluj.ro} \\
\vskip 1cm
\large Ioan Tomescu\\
\vskip .5cm
University of Bucharest\\
Faculty of Mathematics and Computer Science\\
Str. Academiei, 14\\
R-70109 Bucharest, Romania\\
\href{mailto:ioan@math.math.unibuc.ro}{\tt ioan@math.math.unibuc.ro}\\
\end{center}
\date{}
%\maketitle
\pagestyle{myheadings}
%%%%%%%%%%%%%%%%%%%%%%%%%MACROS%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theo}{Theorem}[section]
\newtheorem{prop}[theo]{Proposition}
\newtheorem{lemma}[theo]{Lemma}
\newtheorem{cor}[theo]{Corollary}
\newtheorem{problem}{Problem}
\def\frameqed{\framebox(5.2,6.2){}}
\def\deshqed{\dashbox{2.71}(3.5,9.00){}}
\def\ruleqed{\rule{5.25\unitlength}{9.75\unitlength}}
\def\myqed{\rule{8.00\unitlength}{12.00\unitlength}}
\def\qed{\hbox{\hskip 6pt\vrule width 7pt height11pt depth1pt\hskip 3pt}
\bigskip}
\newenvironment{proof}{\trivlist\item[\hskip\labelsep{\bf Proof}:]}{\hfill
$\frameqed$ \endtrivlist}
\newcommand{\COM}[2]{{#1\choose#2}}
%%%%%%%%%%%%%%%%%%%END%OF%MACROS%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\thispagestyle{empty}
\null
\addtolength{\textheight}{2cm}
\begin{abstract}
In this paper it is shown that for $n\equiv 0$ or 3 (mod 4), the middle term
$S(n)$ in the expansion of the polynomial $(1+x)(1+x^{2})\cdots
(1+x^{n})$ occurs naturally when one analyzes when a discontinuous
product of trigonometric functions is a derivative of a function.
This number also represents the number of partitions of $T_{n}/2=n(n+1)/4$,
(where $T_{n}$ is the $n$th triangular number) into distinct parts less than or equal
to $n$. It is proved in a constructive way that $S(n)\geq 6S(n-4)$ for every $n\geq 8$,
and an asymptotic evaluation of $S(n)^{1/n}$ is obtained as a consequence of the unimodality
of the coefficients of this polynomial. Also an integral expression of $S(n)$
is deduced.
\end{abstract}
\section{Notation and preliminary results}
In a paper of Andrica \cite{andr} the following
necessary and sufficient condition that some product of derivatives
is also a derivative is deduced:
\begin{theo}
Let $n_{1},\ldots ,n_{k}\geq 0$ be integers with $n_{1}+\ldots +n_{k}\geq 1$
and let $\alpha _{1},\ldots ,\alpha _{k}$ be real numbers different from zero.
The function $f_{n_{1},\ldots ,n_{k}}^{\alpha _{1},\ldots ,\alpha _{k}}:\RR \rightarrow \RR $,
defined by
$$f_{n_{1},\ldots ,n_{k}}^{\alpha _{1},\ldots ,\alpha _{k}}(x)=\left\{ \begin{array}{ll}
\cos^{n_{1}}(\alpha _{1}/x)\cdots \cos^{n_{k}}(\alpha _{k}/x), & \mbox{if $ x\neq 0 $;} \\
\alpha, & \mbox{if $ x=0 $;}
\end{array}
\right. $$
is a derivative if and only if
$$\alpha =\frac{1}{2^{n_{1}+\ldots +n_{k}}}S(n_{1},\ldots ,n_{k};\alpha _{1},
\ldots ,\alpha _{k}),$$
where $S(n_{1},\ldots ,n_{k};\alpha _{1},\ldots ,\alpha _{k})$ is the number of all
choices of signs $+$ and $-$ such that
\begin{equation}
\underbrace{\pm \alpha _{1} \pm \ldots \pm
\alpha _{1}}_{n_{1}\, times}\, \, \underbrace{\pm
\alpha _{2}\pm \ldots \pm \alpha _{2}}_{n_{2} \,
times}\, \pm \ldots \, \underbrace{\pm
\alpha _{k}\pm \ldots \pm \alpha _{k}}_{n_{k}\, times} =0.
\end{equation}
\end{theo}
Note that this theorem extends one previously published in \cite{andr-buz}.\\
We shall present another combinatorial interpretations of the numbers
$$S(n_{1},\ldots ,n_{k};\alpha _{1},\ldots ,\alpha _{k})$$
and an integral
representation, while the last section is devoted to the sequence $S(n)=
S(\underbrace{1,\ldots ,1}_{n\, {\rm times}};1,2,3,\ldots ,n)$ for $n\geq 1$.
\medskip
Let $M$ be a multiset of type $\alpha _{1}^{n_{1}}\alpha _{2}^{n_{2}}\ldots
\alpha _{k}^{n_{k}}$, i.e., a multiset containing $\alpha _{i}$ with multiplicity
$n_{i}$ for every $1\leq i\leq k$. It is clear that $S(n_{1},\ldots ,n_{k};
\alpha _{1},\ldots \alpha _{k})$ is the number of ordered partitions having equal
sums of $M$, i.e., of ordered pairs $(C_{1},C_{2})$ such that $C_{1}\cup
C_{2}=M$, $C_{1}\cap C_{2}=\emptyset $ and $\sum_{x\in C_{1}}x =\sum_{y\in C_{2}}
y =\frac{1}{2}\sum_{i=1}^{k}n_{i}\alpha _{i}$. Indeed, there exists a bijection between the set
of all choices of $+$ or $-$ signs in (1) and the set of all ordered partitions with
equal sums of $M$ defined as follows: We put $\alpha _{i}$ from (1) in $C_{1}$
if its sign is $+$ and in $C_{2}$ otherwise.
\par
It is also clear that $S(n_{1},\ldots ,n_{k};\alpha _{1}\ldots ,\alpha _{k})$ is the term not depending
on $z$ in the expansion
\begin{equation}
F(z)=\left(z^{\alpha _{1}}+\frac{1}{z^{\alpha _{1}}}\right)^{n_{1}}\left(z^{\alpha _{2}}+
\frac{1}{z^{\alpha _{2}}}\right)^{n_{2}}\ldots \left(z^{\alpha _{k}}+\frac{1}{z^{\alpha _{k}}}\right)^{n_{k}}.
\end{equation}
Wilf \cite{wilf} outlines a proof that for $n_{1}=n_{2}=\ldots =n_{k}=1$, the coefficient of
$z^{n}$ in $F(z)$ represents the number of ways of choosing $+$ or $-$ signs
such that $\pm \alpha _{1}\pm \alpha _{2}\pm \ldots
\pm \alpha _{k}=n$.
If $\alpha _{1},\ldots ,\alpha _{k}$ are positive integers, from (2) one gets
\begin{equation}
F(z)=S(n_{1},\ldots ,n_{k};\alpha _{1},\ldots ,\alpha _{k})+ \sum_{\alpha \neq 0}
a_{\alpha}z^{\alpha},
\end{equation}
where the sum has only a finite number of terms and $\alpha $ and $a_{\alpha}$
are integers. By substituting $z=\cos t+ i\sin t$, $t\in \RR $ in (3) one deduces
$$2^{n_{1}+\ldots +n_{k}}\prod _{j=1}^{k}(\cos\alpha _{j}t)^{n_{j}}=
S(n_{1},\ldots ,n_{k};\alpha _{1},\ldots ,\alpha _{k})+\sum_{\alpha \neq 0}
a_{\alpha}(\cos\alpha t+i\sin\alpha t)$$
By integration on $[0,2\pi ]$ we find the following integral expression of
$S(n_{1},\ldots ,n_{k};\alpha _{1},\ldots ,\alpha _{k})$:
$$S(n_{1},\ldots ,n_{k};\alpha _{1},\ldots ,\alpha _{k})=\frac {2^{n_{1}+
\ldots +n_{k}}}{2\pi }\int _{0}^{2\pi }(\cos\alpha _{1}t)^{n_{1}}\cdots
(\cos \alpha _{k}t)^{n_{k}} dt. $$
\section{A particular case and its connection with polynomial unimodality}
An interesting particular case is obtained for $n_{1}=n_{2}=\ldots =n_{k}=1$
and $\alpha _{i}=i$ for every $1\leq i\leq k$. In this case $S(n)$ is the number of ways of choosing $+$
and $-$ signs such that $\pm 1\pm 2\pm \ldots \pm n=0$.
Since now $M=\{1,2,\ldots ,n\}$ has sum $T_{n}=n(n+1)/2$ and every class of an
ordered bipartition of $M$ must have sum $T_{n}/2$, it follows that $S(n)=0$
for $n\equiv 1$ or 2 (mod 4) and $S(n)\neq 0$ for $n\equiv 0$ or 3 (mod 4).
The following theorem proposes several equivalent definitions of the sequence
$S(n)$ for $n\geq 1$.
\begin{theo}
For every $n\geq 1$ the following properties are equivalent:\\
\hspace*{0.5cm}(i) $S(n)$ is the number of choices of $+$ and $-$ signs such that
$\pm 1\pm 2\pm \ldots \pm n=0;$\\
\hspace*{0.4cm}(ii) $S(n)$ is the number of ordered bipartitions into classes having equal sums of
$\{1,2,\ldots ,n\}$;\\
\hspace*{0.3cm}(iii) $S(n)$ is the term not depending on $x$ in the expansion of
$$\left(x+\frac{1}{x}\right)\left(x^{2}+\frac{1}{x^{2}}\right)\ldots \left(x^{n}+\frac{1}{x^{n}}\right);$$
\hspace*{0.4cm}(iv) $S(n)$ is the number of partitions of $T_{n}/2$ into distinct parts, less
than or equal to $n$, if $n\equiv 0$ or $3\ ({\rm mod}\, 4)$, and $S(n)=0$ otherwise;\\
\hspace*{0.5cm}(v) $S(n)$ is the number of distinct subsets of $\{1,\ldots ,n\}$ whose elements sum
to $T_{n}/2 $ if $n\equiv 0\, or \, 3\ ({\rm mod}\, 4)$, and $S(n)=0$ if $n\equiv 1\, or\, 2
\ ({\rm mod}\, 4)$;\\
\hspace*{0.4cm}(vi) $S(n)$ is the coefficient of $x^{T_{n}/2}$ in the polynomial $G_{n}(x)=
(1+x)(1+x^{2})\ldots (1+x^{n})$ when $n\equiv 0\, or\, 3\ ({\rm mod}\, 4)$, and $S(n)=0$ otherwise;\\
\hspace*{0.3cm}(vii) $$S(n)=\frac{2^{n-1}}{\pi }\int_{0}^{2\pi}\cos t \cos 2t \cdots \cos nt\, dt;$$
\hspace*{0.2cm}(viii) $S(n)/2^{n}$ is the unique real number $\alpha $ having the property
that the function $f:\RR \rightarrow \RR $, defined by
$$ f(x)=\left\{
\begin{array}{ll}
\cos (1/x)\cos (2/x)\cdots \cos (n/x), & \mbox{if $ x\neq 0$;}\\
\alpha, & \mbox{if $ x=0$;}
\end{array}
\right.
$$ is a derivative.
\end{theo}
\begin{proof}
Some equivalences are obvious or were shown in the general case. For
example, the equivalence between (ii) and (v) is given by the bijection
$\varphi$ defined for every bipartition $M=C_{1}\cup C_{2}$ such that
$\sum_{x\in C_{1}}x=\sum _{y\in C_{2}}y $ by $\varphi (C_{1}\cup C_{2})=
C_{1}\subset M$.
\end{proof}
Let us denote
\begin{equation}
G_{n}(x)=(1+x)(1+x^{2})\ldots (1+x^{n})=\sum_{i=0}^{T_{n}}G(n,i)x^{i}.
\end{equation}
Note that the property that the coefficient of $x^{i}$ in $G_{n}(x)$ is the
number of distinct subsets of $\{1,\ldots ,n\}$ whose elements sum to $i$ was used by
Friedman and Keith \cite{friedm-keith}
to deduce a necessary and sufficient condition for the existence of a basic
($n$,$k$) magic carpet.
Stanley \cite{stan}, using the ``hard Lefschetz theorem'' from algebraic geometry,
proved that the posets $M(n)$ of all partitions of integers into distinct
parts less than or equal to $n$ are rank unimodal, by showing the existence
of a chain decomposition for $M(n)$. This fact is equivalent to the unimodality
of the polynomial $G_{n}(x)$, which implies that $S(n)$ is the maximum coefficient
in the expansion of $G_{n}(x)$ for $n\equiv 0$ or 3 ({\rm mod} 4).
Stanley's proof was subsequently simplified by Proctor \cite{pro}.
The property of symmetry of the coefficients in (4), namely $G(n,i)=
G(n,T_{n}-i)$ for every $0\leq i\leq T_{n}$ was pointed out by
Friedman and Keith\cite{friedm-keith}; they also found the
recurrence $G(n,i)=G(n-1,i)+G(n-1,i-n)$. This latter recurrence, which is a consequence
of the identity $G_{n}(x)=G_{n-1}(x)(1+x^{n})$, allows us to compute any finite submatrix
of the numbers $G(n,i)$ and thus the numbers $S(n)=G(n,T_{n}/2)$.
Some values of $S(n)$, starting with $n=3$, are given in the following table:
\bigskip
\begin{center}
\begin{tabular}{|r|r||r|r||r|r||r|r|}
\hline
$n$ & $S(n)$ & $n$ & $S(n)$ & $n$ & $S(n)$ & $n$ & $S(n)$ \\
\hline
3 & 2 & 13 & 0 & 23 & 99,820 & 33 & 0 \\
\hline
4 & 2 & 14 & 0 & 24 & 187,692 & 34 & 0 \\
\hline
5 & 0 & 15 & 722 & 25 & 0 & 35 & 221,653,776 \\
\hline
6 & 0 & 16 & 1,314 & 26 & 0 & 36 & 425,363,952 \\
\hline
7 & 8 & 17 & 0 & 27 & 1,265,204 & 37 & 0 \\
\hline
8 & 14 & 18 & 0 & 28 & 2,399,784 & 38 & 0 \\
\hline
9 & 0 & 19 & 8,220 & 29 & 0 & 39 & 3,025,553,180 \\
\hline
10 & 0 & 20 & 15,272 & 30 & 0 & 40 & 5,830,034,720\\
\hline
11 & 70 & 21 & 0 & 31 & 16,547,220 & 41 & 0 \\
\hline
12 & 124 & 22 & 0 & 32 & 31,592,878 & 42 & 0 \\
\hline
\end{tabular} \\
\end{center}
\bigskip
\noindent and thus the terms different from zero form a subsequence of the sequence A025591
in Sloane \cite{sloane}.
Another recurrence satisfied by the numbers $G(n,i)$ is the following:
\begin{lemma}
We have $G(n,i)=\sum_{j\geq 0}G(n-1-j,i-n+j).$
\end{lemma}
\begin{proof}
Let ${\cal P}(k,i)$ denote the set of partitions of $i$ into distinct
parts such that the maximum part is equal to $k$. It is clear that
$$G(n,i)=\left|\bigcup_{j\geq 0}{\cal P}(n-j,i)\right|=\sum_{j\geq 0}|{\cal P}(n-j,i)|=
\sum_{j\geq 0}G(n-1-j,i-n+j). $$
Indeed, there is a bijection between the set of partitions of $i$ into distinct parts such that the
maximum part equals $n-j$ and the set of partitions of $i-n+j$ into distinct parts
less than or equal to $n-1-j$, defined by deleting the maximum part, equal to $n-j$, in any partition
in ${\cal P}(n-j,i)$. Hence $|{\cal P}(n-j,i)|=G(n-1-j,i-n+j)$.
\end{proof}
\begin{theo}
For any $n\geq 8$ we have $S(n)\geq 6S(n-4)$.
\end{theo}
\begin{proof}
For $n\leq 11$ this inequality is verified by inspection.
For $n\geq 12$ we shall propose a constructive
proof yielding for any ordered partition of $\{1,\ldots ,n-4\}$ in two classes $C_{1}$ and $C_{2}$ with
equal sums six ordered partitions of $\{1,\ldots ,n\}$
in two classes ${\tt C_{1}'}$ and ${\tt C_{2}'}$ having
equal sums and all partitions generated will be distinct.
Indeed, for any ordered bipartition with equal sums $\{1,\ldots ,n-4\}=C_{1}
\cup C_{2}$ we can generate six ordered bipartitions with equal sums $\{1,\ldots ,n\}={\tt C_{1}'}
\cup {\tt C_{2}'}$ as follows:
\medskip
(a) ${\tt C_{1}'}=C_{1}\cup \{n-3,n\}$ and ${\tt C_{2}'}=C_{2}\cup \{n-2,n-1\}$;
\medskip
(b) ${\tt C_{1}'}=C_{1}\cup \{n-2,n-1\}$ and ${\tt C_{2}'}=C_{2}\cup \{n-3,n\}$;
\medskip
(c) Without loss of generality suppose $1\in C_{1}$. We define ${\tt C_{1}''}=
C_{1}\backslash \{1\}$, ${\tt C_{2}''}=C_{2}\cup \{1\}$, ${\tt C_{1}'}={\tt C_{1}''}\cup
\{n-2,n\}$ and ${\tt C_{2}'}={\tt C_{2}''}\cup \{n-3,n-1\}$;
\medskip
(d) Without loss of generality suppose $2\in C_{1}$. Now ${\tt C_{1}''}=C_{1}
\backslash \{2\}$, ${\tt C_{2}''}=C_{2}\cup \{2\}$, ${\tt C_{1}'}={\tt C_{1}''}\cup
\{n-1,n\}$, ${\tt C_{2}'}= {\tt C_{2}''}\cup \{n-3,n-2\}$.
\medskip
Case (e) is a little more complicated, but we will be able to do it by combining
two simple transformations.
\medskip
(e) Suppose $1\in C_{1}$. If $n-4$ belongs to the same class, we define
${\tt C_{1}''}=C_{1}\backslash \{1,n-4\}$, ${\tt C_{2}''}=C_{2}\cup \{1,n-4\}$,
${\tt C_{1}'}={\tt C_{1}''}\cup \{n-3,n-2,n-1\}$ and ${\tt C_{2}'}={\tt C_{2}''}\cup \{n\}$.
This transformation resolves the imbalance of $2n-6$ between ${\tt C_{1}''}$ and ${\tt C_{2}''}$
and will be called of type A.
Otherwise $1\in C_{1}$ and $n-4\in C_{2}$.
If $2\in C_{2}$ one defines ${\tt C_{2}''}=C_{2}\backslash \{2,n-4\}$,
${\tt C_{1}''}=C_{1}\cup \{2,n-4\}$, ${\tt C_{1}'}={\tt C_{1}''}\cup \{n-1\}$ and
${\tt C_{2}'}={\tt C_{2}''}\cup \{n,n-2,n-3\}$. This transformation balances classes
${\tt C_{1}''}$ and ${\tt C_{2}''}$ by $2n-4$ and will be called of type B.
Otherwise $2\in C_{1}$, hence $C_{1}=\{1,2,\ldots \}$ and $C_{2}=\{n-4,\ldots \}$.
If $n-5\in C_{1}$ then ${\tt C_{1}''}=C_{1}\backslash \{2,n-5\}$, ${\tt C_{2}''}=
C_{2}\cup \{2,n-5\}$, ${\tt C_{1}'}={\tt C_{1}''}\cup \{n-3,n-2,n-1\}$ and
${\tt C_{2}'}={\tt C_{2}''}\cup \{n\}$.
Otherwise $n-5\in C_{2}$, hence $C_{1}=\{1,2,\ldots
\}$, $C_{2}=\{n-4,n-5,\ldots \}$. Now if $3\in C_{2}$ we move 3 and $n-5$ into
$C_{1}$ and apply a type B transformation.
Otherwise $3\in C_{1}$ and if
$n-6\in C_{1}$, we add $n-6$ and 3 to $C_{2}$ and apply a type A transformation;
otherwise $C_{1}=\{1,2,3,\ldots \}$ and $C_{2}=\{n-4,n-5,n-6,\ldots \}$ and so on.
Note that a transformation of type A or B can be applied to every partition $\pi =C_{1}\cup C_{2}$
of $\{1,\ldots ,n-4\}$ since otherwise $\pi$ must have classes $C_{1}=\{1,2,3,\ldots \}$ and
$C_{2}=\{n-4,n-5,n-6,\ldots \}$ such that for every $k\in C_{1}$ verifying $1\leq k\leq
(n-4)/2$, the number $n-k-3$ belongs to $C_{2}$. But this contradicts the property that $C_{1}$ and
$C_{2}$ have the same sum for every $n\geq 8$.
If $1\in C_{2}$ this algorithm runs
similarly and all partitions generated in this way are pairwise distinct.
\medskip
(f) Suppose $3\in C_{1}$. If $n-4\in C_{1}$, we move 3 and $n-4$ into $C_{2}$ and
annihilate the imbalance equal to $2n-2$ by defining ${\tt C_{1}'}={\tt C_{1}''}\cup
\{n,n-1,n-3\}$ and ${\tt C_{2}'}={\tt C_{2}''}\cup \{n-2\}$ (a type C transformation).
Otherwise $C_{1}=\{3,\ldots \}$, $C_{2}=\{n-4,\ldots \}$. If $4\in C_{2}$ we
move 4 and $n-4$ into $C_{1}$ which produces an imbalance equal to $2n$; then define
${\tt C_{1}'}={\tt C_{1}''}\cup \{n-3\}$ and ${\tt C_{2}'}={\tt C_{2}''}\cup \{n,n-1,n-2\}$
(a type D transformation).
Otherwise $C_{1}=\{3,4,\ldots \}$ and $C_{2}=
\{n-4,\ldots \}$. If $n-5\in C_{1}$ we move 4 and $n-5$ into $C_{2}$ and
apply a type C transformation; otherwise $C_{1}=\{3,4,\ldots \}$ and $C_{2}=\{
n-4,n-5,\ldots \}$. In this way we can apply a transformation of type C or D
to every partition $\pi $ of $\{1,\ldots ,n-4\}$ since otherwise $C_{1}=\{3,4,5,\ldots
\}$, $C_{2}=\{n-4,n-5,n-6,\ldots\}$ such that for every $k\in C_{1}$, $3\leq k\leq (n-2)/2$, we have
$n-k-1\in C_{2}$. This is a contradiction, since in this case $C_{1}$ and $C_{2}$
cannot have the same sum for every $n\geq 12$. As in the previous cases all partitions
produced in this way are distinct.
\end{proof}
This theorem has the following consequence:
\begin{cor}
We have
\begin{equation}
S(n)>6^{n/4}\approx 1.56508^{n}
\end{equation}
for every $n\equiv 0$ $ or$ $3$ $ (mod\, 4)$ and $n\geq 16$.
\end{cor}
\begin{proof}
If $n=4k$ one gets $S(4k)\geq 6^{n/4-4}S(16)>6^{n/4}$ since $S(16)=1,314$.
Similarly, $S(4k+3)\geq 6^{k-3}S(15)=6^{(n-15)/4}S(15)>6^{n/4}$ because $S(15)=722$.
\end{proof}
Note that in \cite{friedm-keith} the maximum coefficient in the polynomial $G_{n}(x)$,
which coincides with $S(n)$ for $n\equiv $ 0 or 3 (mod 4),
is bounded below by $2(n+1)$ for every $n\geq 10$.
Although the lower bound (5) is exponential, its order of magnitude is far from being exact, as can
be seen below.
\begin{lemma}
\begin{equation}
\lim_{n\rightarrow \infty}S(4n)^{1/(4n)}=\lim_{n\rightarrow \infty}
S(4n+3)^{1/(4n+3)}=2.
\end{equation}
\end{lemma}
\begin{proof}
Since the sequence of coefficients $(G(n,i))_{i=0,\ldots ,T_{n}}$ in $G_{n}(x)$
is unimodal (\cite{pro,sloane}) and symmetric, and the first and last coefficient
are equal to 1, it follows that for every $n\geq 5$, $n\equiv 0$ or
3 (mod 4), $$S(n)>\frac{2^{n}-2}{T_{n}-1}>\frac{2^{n}}{T_{n}}=
\frac{2^{n+1}}{n^{2}+n}.$$
Indeed, $\sum_{i=0}^{T_{n}}G(n,i)=G_{n}(1)=2^{n}$ and $T_{n}<2^{n-1}$ for every $n\geq 5$.
On the other hand, $S(n)<2^{n}-2$, the number of ordered partitions having two classes of $\{1,\ldots ,n\}$,
and these two inequalities imply (6).
\end{proof}
A better upper bound for $S(n)$ is $\COM{n}{\lfloor n/2\rfloor }\leq C_{1}\frac{2^{n}}{\sqrt{n}}$
for some constant $C_{1}>0$.
This follows from the following particular case of a result of Erd\H os (see
\cite{aigner} or \cite{erdos}): Fix an interval of length $2$ and consider the set of combinations
$\sum_{i=1}^{n}\varepsilon _{i}i$, that lie within the interval,
where $\varepsilon _{i}\in \{1,-1\}$ for every $1\leq i\leq n$. The sets $\{i: \varepsilon _{i}=1\}$
that correspond to these combinations form an
antichain in the poset of subsets of $\{1,\ldots ,n\}$ ordered by
inclusion. By Sperner's theorem \cite{sper} the maximum number of elements in such an antichain is
$\COM{n}{\lfloor n/2\rfloor}$, which is an upper bound for the number of combinations
$\sum _{i=1}^{n}\varepsilon _{i}i$ that sum to 0.
\bigskip
\noindent {\bf Conjecture 2.6} {\em For} $n\equiv 0$ or 3 (mod 4) {\em we have}
$$S(n)\sim \sqrt{6/\pi}\cdot \frac{2^{n}}{n\sqrt{n}}\, , $$
where $f(n)\sim g(n)$ means that $\lim_{n\rightarrow \infty}f(n)/g(n)=1$.\\
\bigskip
This behavior was verified by computer experiments up to $n=100$.
\section{Acknowledgements}
The authors are grateful to J. Radcliffe from University of Nebraska (Lincoln)
for useful discussions related to the upper bound for $S(n)$.
Also, the authors are indebted to the referee of the paper for his/her very useful remarks, including
the present form of Conjecture 2.6.
\begin{thebibliography}{99}
\bibitem{aigner}
%1
M. Aigner and G.-M. Ziegler, {\em Proofs from THE BOOK}, Springer Verlag, Berlin,
Heidelberg, 1998.
\bibitem{andr-buz}
%2
D. Andrica and \c S. Buze\c teanu, On the product of two or more derivatives, {\em
Revue Roumaine Math.\ Pures Appl.}, {\bf 30} (1985), 703--710.
\bibitem{andr}
%3
D. Andrica, A combinatorial result concerning the product of more derivatives, {\em
Bull.\ Calcutta Math.\ Soc.}, {\bf 92} (4) (2000), 299--304.
\bibitem{erdos}
%4
P. Erd\H os, On a lemma of Littlewood and Offord, {\em Bull.\ Amer.\ Math.\ Soc.},
{\bf 5} (1945), 898--902.
\bibitem{friedm-keith}
%5
E. Friedman and M. Keith,
\htmladdnormallink{Magic carpets}{http://www.math.uwaterloo.ca/JIS/VOL3/KEITH/carpet.html},
\htmladdnormallink{\em Journal of Integer Sequences}{http://www.math.uwaterloo.ca/JIS},
{\bf 3} (2000), Article 00.2.5.
\bibitem{pro}
%6
R. Proctor, Solution of two difficult combinatorial problems with linear
algebra, {\em Amer.\ Math.\ Monthly}, {\bf 89} (1982), 721--734.
\bibitem{sloane}
%7
N. J. A. Sloane
\newblock{\em\htmladdnormallink{The On-Line Encyclopedia of Integer Sequences}{http://www.research.att.com/~njas/sequences/}}, {\tt {http://www.research.att.com/\char'176njas/sequences/}}.
\bibitem{sper}
%8
E. Sperner, Ein Satz \"uber Untermengen einer endlichen Menge,
{\em Math.\ Zeitschrift}, {\bf 27} (1928), 544--548.
\bibitem{stan}
%9
R. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property,
{\em SIAM J. Alg.\ Discr.\ Math.}, {\bf 1} (1980), 164--184.
\bibitem{wilf}
%10
H. Wilf, \htmladdnormallink{\em Generatingfunctionology}{http://www.math.upenn.edu/~wilf/DownldGF.html},
Academic Press, New York, 1994.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
05A15, 05A16, 05A17, 05A18, 06A07, 11B75 .\ \
\noindent \emph{Keywords:
unimodal polynomial, triangular number, derivative, partition,
Sperner's theorem, generating function}
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence \seqnum{A025591}.)
\vspace*{+.1in}
\noindent
Received September 25, 2002;
revised version received November 3, 2002.
Published in {\it Journal of Integer Sequences} November 14, 2002.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\end{document}