%%\title{The integer sequence A002620 and upper antagonistic functions}
%%\author{Sam E. Speed
%%\thanks{Department of Mathematical Sciences, University of Memphis, \ Memphis, TN 38152-6429 \qquad email:
%%\protect\href{mailto:speeds@msci.memphis.edu}{speeds@msci.memphis.edu} \qquad
%%(P.O. Box 381993, Germantown, TN 38183-1993)}} % , \ (901) 754-5657)}}
%\date{2-25-2003}


\documentclass[12pt,reqno]{article}
\usepackage{amssymb}  %for mathbb, mathfrak fonts
\usepackage{amsmath}  %for substack, text cases
\usepackage{epsf}
\usepackage{color}
%\usepackage{verbatim} %for comment
%\usepackage[pagewise]{lineno} \linenumbers
%\usepackage{snapshot}

\usepackage{pseudocode} %uses fancybox.sty
\makeatletter
\setlength{\pcode@width}{5.5in}
\renewcommand{\pcode@AF}[1]{\mbox{\texttt{#1}}}
\makeatother
\renewcommand{\GETS}{:=}


%\usepackage{showkeys}
%comment out hyperref,  use following to get showkeys labels in margin
\usepackage[pagebackref,
colorlinks=true,
linkcolor=green,filecolor=webbrown,citecolor=blue]{hyperref}%see \doc\hyperref\manual.pdf
%linkcolor=webgreen,filecolor=webbrown,citecolor=webgreen]{hyperref}%see \doc\hyperref\manual.pdf
%\def\href{}
%\def\htmladdnormallink{}{}


\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\renewcommand{\baselinestretch}{1.2}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}


\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small


\newtheorem{fact}{Theorem}[section]
\newtheorem{Thm}[fact]{Theorem}
\newtheorem{Def}[fact]{Definition}
\newtheorem{Pro}[fact]{Proposition}
\newtheorem{Cor}[fact]{Corollary}
\newtheorem{Lem}[fact]{Lemma}
\newtheorem{Fact}[fact]{Fact}
%\newtheorem{Exm}[fact]{Example}



\def\Min{\mathop{\hbox{\rm Min}}\limits}
\def\Max{\mathop{\hbox{\rm Max}}\limits}



\newcommand{\qed}{{\ensuremath\Box}}

\makeatletter
%from Computer Modern Typefaces as Multiple Master Fonts, Version 1.21
%by A.S.Berfnikov and S.B.Turtia, documentation for mff.sty
% \TeXLiveCD\texmf\Doc\latex\Mff\Mffdoc.tex
%\def\hackersmile{\@ifnextchar[{\@hackersmile}{\@hackersmile[10]}}
\def\QED{\@ifnextchar[{\@hackersmile}{\@hackersmile[8]}}
\def\@hackersmile[#1]{\hbox{%
   \unitlength=1pt\relax
   \unitlength=#1\unitlength
   \divide\unitlength by 10\relax
   \thinlines % \thicklines
   \raise -3\unitlength \hbox{%
   \begin{picture}(12,12)(-6,-6)
   \put(0,0){\circle{10}}
   \put(-2,1.75){\circle*{1}}
   \put(2,1.75){\circle*{1}}
   \thinlines  % \thicklines
   \put(-2.75,3){\line(1,0){1.5}}
   \put(2.75,3){\line(-1,0){1.5}}
   \put(0,-1){\line(0,1){3}}
   \put(-2.5,-2.5){\line(1,0){5}}
   \put(-2.5,-2.5){\line(0,1){1}}
   \put(2.5,-2.5){\line(0,1){1}}
   \end{picture}%
}}}
\makeatother
%The `hacker smile' \LaTeX\ picture macro used for the end of a proof is
%from \emph{Computer Modern Typefaces as Multiple Master Fonts}, Version
%1.21, Mmfdoc.tex, by A.S.Berfnikov and S.B.Turtia, documentation
%for mff.sty, on the CTAN archive.
%%on \TeXLiveCD\texmf\Doc\latex\Mff\Mffdoc.tex






%from ROYLE.TEX JIS article
\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
 -.2ex}{2.3ex plus .2ex}{\large\bf}}
\makeatother



\begin{document}
%\maketitle
\begin{center}
\vspace*{1in}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\vskip1cm

{\LARGE\bf The Integer Sequence A002620 and Upper Antagonistic Functions}\\

\vskip 1.5cm

{\large Sam E. Speed} \bigskip \\
Department of Mathematical Sciences \\
University of Memphis \\
Memphis, TN 38152-3240 \medskip \\
Email address: \href{mailto:speeds@msci.memphis.edu}{speeds@msci.memphis.edu}
\vskip2cm
{\bf Abstract}
\end{center}

\emph{ This paper shows the equivalence of various integer functions to
the integer sequence  A002620, and to the  maximum of the product
of certain pairs of combinatorial or graphical invariants. This maximum is the same as
the upper bound of the Nordhaus-Gaddum inequality and related to Tur\'an's number.
The computer algebra program \texttt{MAPLE} is used  for solutions of linear
recurrence and differential equations in some of the proofs.
Chapter three of  \emph{The Encyclopedia of Integer Sequences} by Sloane and Plouffe
describes the usefulness of apparently different expressions of an integer sequence.}




\bigskip\medskip
\setcounter{section}{1}



Define $\lfloor r \rfloor$, the floor of $r$, to be the largest
integer less than or equal to a real number $r$, and
$\lceil r \rceil$, the ceiling of $r$,  the smallest
integer greater than or equal to  $r$.
 For manipulations of floor and ceiling operations, see chapter
three of~\cite{gkp89}, and for graph theory terms see~\cite{cl96,d97,h69}.

%The set $\{1,2,\ldots ,n\}$ is denoted by $1..n$.

\begin{Thm}\label{T:main} For $n$ a positive integer the expressions
in the following \ref{last} paragraphs are equal.
$($for  $n=0$ see the comment at the end of this list$)$

\begin{enumerate}
  \item\label{seq} The $n^{th}$ term of the infinite sequence
  $1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,\dots$ \\
  which is sequence
  \htmladdnormallink{A002620}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=002620}
   of the \htmladdnormallink{The On-Line Encyclopedia of Integer Sequences}
  {http://www.research.att.com/~njas/sequences}
  \textup{(OEIS)~\cite{OEIS}} without the leading zeros. See the comment at end of this list.

  \item\label{eo}
  $\begin{cases} k^2,&  \!\!n=2k{-}1\\ k(k+1),&  n=2k  \end{cases}  =
 \begin{cases} \sum\limits_{i=1}^k (2i-1),& \!\text{$n=2k{-}1$}\\ \sum\limits_{i=1}^k 2k ,&  n=2k  \end{cases}
    \!=  \begin{cases} \frac{(n+1)^2}{4},& \text{$n$ odd }\\
  \frac{(n+1)^2-1}{4},& \text{$n$ even}  \end{cases} = $
  {$\frac{n^2}{4}+\frac{n}{2}+ \frac{1-(-1)^n}{8}$}.

  \item\label{floor} $\left\lfloor (\frac{n+1}{2})^2\right\rfloor =
  \left\lceil \frac{(n+1)^2-1}{4}\right\rceil= \left\lfloor (\frac{n+1}{2})\right\rfloor
  + \left\lfloor (\frac{n}{2})^2\right\rfloor = \left\lceil
  (\frac{n-1}{2})\right\rceil  + \left\lceil (\frac{n}{2})^2\right\rceil$.


  \item\label{fs} $\left\lfloor \frac{n+1}{2}\right\rfloor{\cdot}\left\lceil
  \frac{n+1}{2}\right\rceil
  \: = \: \left\lfloor \frac{n+1}{2}\right\rfloor
  {\cdot}\Big(\left\lfloor \frac{n+1}{2}\right\rfloor +$
  {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $n$ odd }\\
         1,& \text{if $n$ even} \\
      \end{smallmatrix}
   \right.
  $}%
   $\Big)
  \:=\: \left\lfloor \frac{n+1}{2}\right\rfloor
  \cdot \left\lfloor \frac{n+2}{2}\right\rfloor
  \:=\: \left\lceil \frac{n}{2}\right\rceil
  \cdot \left\lceil \frac{n+1}{2}\right\rceil$%
  $\:=\: \left\lceil \frac{n}{2}\right\rceil
  {\cdot}\Big(\left\lceil \frac{n}{2}\right\rceil +$
  {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $n$ odd }\\
         1,& \text{if $n$ even} \\
      \end{smallmatrix}
   \right.
  $}%
   $\Big)$%
  $\:=\: \left\lceil \frac{n+1}{2}\right\rceil
  {\cdot}\Big(\left\lceil \frac{n+1}{2}\right\rceil -$
  {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $n$ odd }\\
         1,& \text{if $n$ even} \\
      \end{smallmatrix}
   \right.
  $}%
   $\Big)$.%

  \item\label{sum} $\sum\limits_{k=0}^{n-1} \left\lfloor\frac{k+2}{2} \right\rfloor
  = \sum\limits_{k=1}^{n} \left\lfloor\frac{k+1}{2} \right\rfloor
  = \sum\limits_{k=2}^{n+1} \left\lfloor\frac{k}{2} \right\rfloor
  =n+\sum\limits_{k=2}^{n-1} \left\lfloor\frac{k}{2} \right\rfloor
  =\sum\limits_{k=1}^{n} \left\lceil\frac{k}{2} \right\rceil$.

  \item\label{sumflr} $\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor} \!\! (n-2k) =
  n+(n-1)\left\lfloor\frac{n-1}{2}\right\rfloor-
  \left\lfloor\frac{n-1}{2}\right\rfloor^2=
  \Big(n+1-\left\lfloor\frac{n+1}{2}\right\rfloor \Big)
  \left\lfloor\frac{n+1}{2}\right\rfloor =
  \!\!\!\!\sum\limits_{k=\lfloor\frac{n+1}{2} \rfloor+1}^{n+1} \!\!\!\!(2k-n-2) =\\
  \sum\limits_{k=0}^{\lceil\frac{n-1}{2}\rceil}
  \!\!(n-2k)=n+(n-1)\left\lceil\frac{n-1}{2}\right\rceil-
  \left\lceil\frac{n-1}{2}\right\rceil^2=
  \Big(n+1-\left\lceil\frac{n+1}{2}\right\rceil \Big)
  \left\lceil\frac{n+1}{2}\right\rceil=
   \!\!\!\!\sum\limits_{k=\lceil\frac{n+1}{2}\rceil+1}^{n+1} \!\!\!\!(2k-n-2)=\\
   \!\!\!\!\sum\limits_{k=\lfloor\frac{n+2}{2} \rfloor}^{n} \!\!\!\!(2k-n) =
   \!\!\!\!\sum\limits_{k=\lceil\frac{n+1}{2}\rceil}^{n} \!\!\!\!\!(2k-n) =
   \sum\limits_{k=1}^{\lfloor\frac{n+1}{2}\rfloor} \!\!2k \; - $
   {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         \lfloor\frac{n+1}{2}\rfloor, & \text{if $n$ odd }\\
         0,& \text{if $n$ even} \\
      \end{smallmatrix}
   \right.$
   }% \small
 $ =  \sum\limits_{k=1}^{\lceil\frac{n+1}{2}\rceil} \!\!(2k-1) \; - $
   {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0, & \text{if $n$ odd }\\
         \lceil\frac{n+1}{2}\rceil,& \text{if $n$ even} \\
      \end{smallmatrix}
   \right.$}.% \small




 % \vspace{-.1in}
  \item\label{gf}
   The coefficient of $x^n$ in the power series expansion of
  $\frac{x}{1-2x+2x^3-x^4} = \frac{x}{(1+x)(1-x)^3} = \\
  \frac{1}{(1-x)^2}\sum\limits_{k=1}^\infty x^{2k-1}$.   This is
  the generating function of the sequence.



\item\label{rr} {\bfseries recurrence equations.} The $n^{th}$ term of the sequence $\langle a(k)\rangle_{k=1}^\infty$
  which is the solution of \textbf{any} of the following recurrence  equations
   for all positive integers $k:$

  \vspace{-.1in}
  \begin{enumerate}
   \item\label{rra} $a(k+1)+a(k)= \binom{k+2}{2} =   \frac{(k+2)(k+1)}{2}$
   \quad with $a(1)=1$.

   \item\label{recp}  $a(k+2)= a(k)+k+2$
   \quad with $a(1)=1$, $a(2)=2$.

   \item\label{rec}  $a(k+3)= a(k+2)+a(k+1)-a(k)+1$
     \quad with $a(1)=1$, $a(2)=2$, $a(3)=4$.

   \item\label{rrd} $a(k+4) = 2a(k+3)-2a(k+1)+a(k)$
    \quad with $a(1)=1$, $a(2)=2$, $a(3)=4$, $a(4)=6$.
   \item\label{rre} $(k+1)a(k+2) = 2a(k+1)+(k+3)a(k)$
   \quad with $a(1)=1$, $a(2)=2$.
   \item\label{rrf} $(k+2)a(k+3) = (k+3)a(k+2)+(k+2)a(k+1)-(k+3)a(k)$
     \quad with $a(1)=1$, $a(2)=2$, $a(3)=4$.
  \end{enumerate}



%\pagebreak[2]

\item\label{delq} {\bfseries difference equations.} The $n^{th}$ term of the sequence $\langle a(k)\rangle_{k=1}^\infty$
  which is the solution of \textbf{any} of the following difference
  equations for all positive integers $k$,
  where $\triangle a(k) = a(k+1)-a(k)$ and  $\triangle^2a(k) = \triangle a(k+1)- \triangle
  a(k)$.

  \vspace{-.1in}
  \begin{enumerate}
   \item\label{diff}   $\triangle a(k) = 1,2,2,3,3,4,4,5,5,\dots, \lceil \frac{k+1}{2}\rceil,\dots$
     and with $a(1)=1$. This difference sequence is like the
     sequence
     \htmladdnormallink{A004526}
     {http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=004526}
      of \textup{OEIS~\cite{OEIS}}.

  \item\label{d1}  $\triangle^2a(k)=$
   {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         1,& \text{if $k$ odd } \\
         % \quad added for centering
         0,& \text{if $k$ even}
      \end{smallmatrix}
   \right. $   % \; , \; \; i=1, \dots, n   %end of subscript
  } \quad  with $a(1)=\triangle a(1)=1$.

  \item\label{dp}
  $\triangle a(k+1)+\triangle a(k)=k+2$ \quad
  with $a(1)=\triangle a(1)=1$.

  \item\label{delq3}
  $\triangle a(k+2)=\triangle a(k)+1$ \quad
  with $a(1)=\triangle a(1)=1, \triangle a(2)=2$.

  \item\label{delq4}
  $\triangle^2 a(k+1) +\triangle^2 a(k)=1$ \quad
  with $a(1)=\triangle a(1)=\triangle^2 a(1)=1$.

  \item\label{d2}
    $\triangle^3a(k)+2\triangle^2a(k)=1$ \quad
     with $a(1)=\triangle a(1)=\triangle^2 a(1)=1$.
\end{enumerate}


\item\label{de} {\bfseries differential equations.}
  \vspace{-.1in}
  \begin{enumerate}
    \item\label{dea}  The coefficient of $x^{n-1}$ in the power series expansion of the
 solution $F(x)$ of the differential equation:
$(1-x^2)${\Large$\frac{dF}{dx}$}$(x)= 2(1+2x)F(x)$ with  $F(0)=1$.
\par
 \medskip
 \hspace*{-.3in} The coefficient of $x^n$ in the power series expansion of the
 solution $F(x)$ of \textbf{any} of the following differential equations:
    \item\label{deb}   $(1-x^2)${\Large$\frac{dF}{dx}$}$(x)= (4+3x-2x^2+x^3)F(x)+1$
    with  $F(0)=0$.
   \item\label{dec} $(1-x^2)${\Large$\frac{d^2F}{dx^2}$}$(x)=
   (4+5x-2x^2+x^3)${\Large$\frac{dF}{dx}$}$(x) + (3-4x+3x^2)F(x)$ with
    $F(0)=0$, {\Large$\frac{dF}{dx}$}$(0)=1$.

 \medskip
 \hspace*{-.3in} The coefficient of $x^{n+1}$ in the power series expansion of the
 solution $F(x)$ of \textbf{any} of the following differential equations:
    \item\label{ded}   $(1-x^2)${\Large$\frac{dF}{dx}$}$(x)=
    (6+2x-4x^2+2x^3)F(x)+2x$
    with  $F(0)=0$.
   \item\label{dee} $x(1-x^2)${\Large$\frac{d^2F}{dx^2}$}$(x)=
   (1+6x+3x^2-4x^3+2x^4)${\Large$\frac{dF}{dx}$}$(x) +
   (-6-4x^2+4x^3)F(x)$ \\
    with $F(0)=0$  %  {\Large$\frac{dF}{dx}$}$(0)=0$
    and {\Large$\frac{d^2F}{d^2x}$}$(0)=2$.
    $($or {\Large$\frac{dF}{dx}$}$(-2)=\frac{-4}{27}$, {\Large$\frac{dF}{dx}$}$(2)=\frac{28}{9})$
  \end{enumerate}

  \item\label{quad} $\Max_{k\in\{1,\dots,n\}} k\cdot(n-k+1)$.

  \item\label{spart} $\Max_{\mathfrak{A}\in\text{Part}(1..n)}
  |\mathfrak{A}|\cdot\Max_{A\in\mathfrak{A}} |A|$ \
  where $\text{Part}(1..n)$ is the collection of set partitions of the set
  $\{1,\ldots,n\}$,  $|\mathfrak{A}|$ is the number of blocks, and
  $\Max_{A\in\mathfrak{A}} |A|$ is the size of the largest block
  of partition $\mathfrak{A}$.

  \item\label{perm} $\Max_{\alpha\in\textup{perm}(n)} i(\alpha)\cdot  d(\alpha)$
  \quad where $\textup{perm}(n)$ is the set of permutations of $\{1,\dots,n\}$,
   $i(\alpha)$ is the length of the longest increasing subsequence and
   $d(\alpha)$ the longest decreasing subsequence of permutation
   $\alpha$. See~\textup{\cite{s61cjm}}.


  \item\label{part} $\Max_{p\in S(n)} \max(p)\cdot\textup{len}(p)$
  \quad where $S(n)$ is the set of compositions or partitions of $n$ $($the
  sequences, with or without regard to order, of positive integers which sum to $n)$,
  $\max(p)$ is the size of the largest part, and $\textup{len}(p)$ is the
  number of parts  of $p$.
  See chapter 6 of~\textup{\cite{r78}}.

  \item\label{pp} $\Max_{P\in\textup{ppart}(n)}
   \textup{\#rows}(P)\cdot\textup{\#cols}(P)$
  \quad where $\textup{ppart}(n)$ is the set of plane partitions or Young
  tableaux  of $n$.
  See~\textup{\cite[p.217]{c94}}, \textup{\cite[p.81]{sw86}}, \textup{\cite{f97}} and \textup{\cite{s61cjm}}.

  \item\label{gphc} $\Max_{G\in\textup{graph}(n)}  \chi(G)\cdot\chi(\overline{G})$
  \quad where $\textup{graph}(n)$ is the set of simple graphs on $n$
  vertices, $\chi(G)$ is the chromatic number and $\overline{G}$ the complement
   of graph $G$.

  \item\label{gpha} $\Max_{G\in\textup{graph}(n)}  \omega(G)\cdot\overline{\omega}(G)$
  \quad where $\textup{graph}(n)$ is the set of simple graphs on $n$
  vertices, $\overline{\omega}(G)=\omega(\overline{G})$ is the independence number and $\omega(G)$ is the
  clique number  of graph $G$.


  \item\label{gphd} $\Max_{G\in\textup{graph}(n)}  (1+\Delta(G))\cdot\gamma(G)$\quad
  where $\Delta(G)$ is the size of the largest degree of the vertices and
  $\gamma(G)$ is the domination number of the simple graph $G$.
  $( \gamma$ is the smallest size set of vertices of $G$, such that
  every vertex is in the set or adjacent to it.$)$

  \item\label{gen} $\Max_{u\in\Omega_n} f(u)\cdot g(u)$
  \quad where $\langle \Omega_k\rangle_{k=1}^\infty$ is a
  sequence of finite sets and for each  positive integer $k$, there are
  functions $f$ and $g$ from $\Omega_k$ to $\{1,\dots,k\}$ such that
  for all $u\in\Omega_k, \; f(u)+g(u)\leq k+1$, and   there exist
   $w\in\Omega_k$, such that $f(w)+g(w)=k+1$ and
  $|f(w)-g(w)|\leq 1$.

  Note that this is a generalization of the above items~\ref{quad}
  to~\ref{gphd}, which are special cases;
  see section~\textup{\ref{s-antf}} below.

  \item\label{mgph} The number of graphs with multiple edges and loops on
  two  vertices and $n-1$ edges.

 \item The number of connected  bipartite graphs with part sizes $n$ and $2$.
 See~\emph{\htmladdnormallink{Gordon Royle}
{http://www.cs.uwa.edu.au/~gordon/}}, \texttt{/www.cs.uwa.edu.au/\~{}gordon/}


  \item\label{tri} The number of $($noncongruent$)$ integer-sided triangles
  with largest side n. See~\textup{\cite{jm00amm,m74amm}}

  \item\label{put} The value of $f(n)$ where $f$ is the solution of the functional
  equation $f(m+k)-f(m-k)= k(m+1)$ for positive integers $k<m$, and $f(1)=1, f(2)=2$.


  \item\label{los} The $n^{th}$ term of the row $3\; {(}$and column $3)$
  of Losanitsch's array.


\hspace*{-.26in}\fbox{\parbox{6.2in}{
\qquad Losanitsch's array, values of $L(r,c)$
from~\textup{\cite{class}}

\setlength{\tabcolsep}{5pt}
\begin{tabular}{@{}c|cccccccccccll@{}}
$r \backslash \,c$ & 1&2&3&4&5&6&7&8&9&10&11 && seq. no. in
OEIS~\textup{\cite{OEIS}}\\ \hline 1&1&1&1&1&1&1&1&1&1&1&1 &\dots&A000012\\
2&1&1&2&2&3&3&4&4&5&5&6 &\dots&
\htmladdnormallink{A004526}
{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=004526}
\\
3&1&2&4&6&9&12&16&20&25&30&36 &\dots&
\htmladdnormallink{\textbf{A002620}}
{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=002620}
\\
4&1&2&6&10&19&28&44&60&85&110&146 &\dots&
\htmladdnormallink{A005993}
{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005993}
\\
5&1&3&9&19&38&66&110&170&255&365&511 &\dots&
\htmladdnormallink{A005994}
{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005994}
\\
6&1&3&12&28&66&126&236&396&651&1001&1512  &\dots&
\htmladdnormallink{A005995}
{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005995}
\\
\end{tabular}

\smallskip
$L(r,c)=L(r,c-1)+L(r-1,c)-$
  {\small
   $\!\!\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         \binom{(r+c)/2}{c/2},& \text{if both $r,c$ even} \\
         0,& \text{otherwise}
      \end{smallmatrix}
   \right.
  $}%
 and $L(1,c)=L(r,1)=1$ for all $r,c$ positive integers.
}}


\item\label{cp} $1+ |A_n|$
\quad where $A_n = \bigl\{\, \{i,j\}\subseteq \{1,\ldots,n\}
\mid \, i\neq j \text{ and } n\leq i+j\,\bigr\}$

this is one more than the sum for $n\leq m\leq 2n-1$
of the number of partitions of m with two distinct parts from
$\{1,\dots,n\}$.

%\newpage
\item\label{sa} The sum of the $n^{th}$ row  of the following array.

\begin{tabular}{c|cccccccccc}
$n \backslash \,k$ &  1 & 2& 3& 4& 5&6 & 7& 8& 9 & \\ \hline
1 & \textbf{1}& \\
2 & 1& 1 &\\
3 & 1& \textbf{2} & 1\\
4 & 1& 2 & 2 & 1 &   &  &  & \\
5 & 1& 2 & \textbf{3} & 2 & 1 &  &  & \\
6 & 1& 2 & 3 & 3 & 2 & 1&  & \\
7 & 1& 2 & 3 & \textbf{4} & 3 & 2& 1& \\
8 & 1& 2 & 3 & 4 & 4 & 3& 2& 1 \\
9 & 1& 2 & 3 & 4 & \textbf{5} & 4& 3& 2& 1\\
\end{tabular}


\item\label{i-pd}  One more than the sum for $n\leq m\leq 2n-1$
of the number of partitions of m
with two  parts  minus $n-1$ choose 2
$\quad = \quad 1+\displaystyle\sum_{m=n}^{2n-1} \left\lfloor\frac{m-1}{2}\right\rfloor
-\binom{n-1}{2}\quad =\quad
1+\displaystyle\sum_{m=n}^{2n-1} \left\lfloor\frac{m}{2}\right\rfloor
-\left\lfloor\frac{n}{2}\right\rfloor-\binom{n-1}{2},
 \\ \quad = \quad
1+\displaystyle\sum_{i=0}^{n-1} \left\lfloor\frac{n-1+i}{2}\right\rfloor
-\binom{n-1}{2} \quad = \quad
 1+\displaystyle\sum_{i=0}^{n-1} \left\lceil\frac{n-2+i}{2}\right\rceil -\binom{n-1}{2} ,
 \\ \quad = \quad
  \begin{cases} f_f(n)+n, &\text{if $n$ odd }\\
  f_f(n),& \text{if $n$ even}  \end{cases}$ \quad
  where $f_f(n) = (n+\lfloor n/2 \rfloor)\lfloor n/2 \rfloor -\binom{n}{2}$, \\
  $\quad = \quad
  \begin{cases} f_c(n)-n, &\text{if $n$ odd }\\
  f_c(n),& \text{if $n$ even}  \end{cases}$ \quad
  where $f_c(n) = (n+\lceil n/2 \rceil)\lceil n/2 \rceil -\binom{n}{2}$.


\item\label{i-t} Tur\'an's number for triangles in a graph on $n+1$ vertices
$=$ the maximum number of edges of a graph on $n+1$ vertices which has no
triangles
$ = %ex(n+1; K_{3}^{(2)})=
\binom{n+1}{2}-\binom{\lfloor\frac{n+1}{2}\rfloor}{2}-\binom{\lfloor\frac{n+2}{2}\rfloor}{2}
= \binom{n+1}{2}-\binom{\lceil\frac{n}{2}\rceil}{2}-\binom{\lceil\frac{n+1}{2}\rceil}{2}
= \binom{\lfloor\frac{n+2}{2}\rfloor}{2}+\binom{\lfloor\frac{n+3}{2}\rfloor}{2}
= \binom{\lceil\frac{n+1}{2}\rceil}{2}+\binom{\lceil\frac{n+2}{2}\rceil}{2}
= \binom{\lfloor\frac{n+2}{2}\rfloor}{2}+\binom{\lceil\frac{n+2}{2}\rceil}{2} $.



\item\label{i-opt}\label{last}
$\Max_{u\in[0,1]^{n+1}} \;\sum\limits_{1\leq i<j\leq n+1} \!\!|u_i-u_j|$ \quad where
$[0,1]^{n+1}$ is the collection of sequences of real numbers from
 the interval $[0,1]$ of length $n+1$. This is problem $97$ of~\textup{\cite{bkm95}}.
\end{enumerate}
\end{Thm}


\medskip
\noindent{\bfseries Other expressions.}
  In OEIS~\cite{OEIS} for this sequence, there is a reference to probability~\cite{f55},
  and in \cite{cse} the
\htmladdnormallink{Encyclopedia of Combinatorial Structures $105$}
{http://www.algo.inira.fr/bin/encyclopedia?Search=ECSnb&argsearch=105}
   there is a combinatorial structure for this sequence.
  In~\cite{c00} this sequence counts orbits of permutation groups.
  The inverse image of diagonals $(\pm i, \pm i)$ under the spiral
  function of~\cite[Exercise 40, p.99]{gkp89} is sequence
  \text{A002620}.


\smallskip
\noindent{\bfseries Comment.} For all of the expressions in theorem~\ref{T:main},
it could be argued (or defined) that they are zero for $n=0$. In
the OEIS~\cite{OEIS} this sequence is preceded by \emph{two}
zeros. One reason for this may be that the lower triangular matrix given
by the method of~\cite{gsww92} for A002620 has a simpler form when this input
sequence has at least two leading zeros. See~\cite{pw00} for more
recent work on this method.









%\pagebreak[4]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Antagonistic functions}\label{s-antf}

Two integer functions which satisfy the conditions of item~\ref{gen} of
the main theorem, are antagonistic in the sense that, in general,
they are not both too large at the same time.

\begin{Def} Let $n$ be a positive integer, $\Omega$ a finite set, then
$f$ and $g$ are $($upper$)$ \emph{antagonistic} on $\Omega$ of order $n$ if
\begin{enumerate}{}%
\item $f$ and $g$ are functions from $\Omega$ to $\{1,\dots,n\}$,
\item for any $u\in \Omega, \quad f(u)+g(u)\leq n+1$,
\item $\Max_{u\in\Omega} f(u)\cdot g(u) =
\left\lfloor \left(\frac{n+1}{2}\right)^2\right\rfloor$.
\end{enumerate}
\end{Def}

  This  is related to the upper bound of the
  Nordhaus-Gaddum inequality~\cite{ng56}; see~\cite{f68}.

\noindent Examples of antagonistic functions are in items~\ref{quad}
to~\ref{gphd} of the main theorem.
In this paper, only upper antagonistic functions are considered \cite{s00}.




\subsection{Examples which are not antagonistic}

\textbf{A.}
Let $\Omega_n=\textup{graph}(n)$, the simple graphs on $n$ vertices. Let
$f(G) =\overline{\omega}(G)$, the independence number of graph $G$, and
$g(G)= 1+\lfloor \frac{1}{n} \sum_{v=1}^n \textup{deg}(v)\rfloor$.
If $n=6$, $f$ and $g$ are \emph{not} antagonistic,  because the graph $G$ on $6$ vertices which is the
complement of $K_4$, has $\overline{\omega}(G)=4$ and
$1+\lfloor \frac{1}{6} \sum_{v=1}^6 \textup{deg}(v)\rfloor =
1+\lfloor \frac{18}{6} \rfloor = 4$. Thus $f(G)+g(G)>n+1$ and the
definition fails.

\medskip
\noindent\textbf{B.}
Let $\Omega_n=\{1,\dots,n\}, f(i)=i$ and $g(i)=\lceil
\frac{n}{i}\rceil$ for $1\leq i\leq n$.
If $5\leq n$, $f$ and $g$ are \emph{not} antagonistic, since
$\Max_{i\in\{1..n\}} f(i){\cdot}g(i) <
\left\lfloor \left(\frac{n+1}{2}\right)^2\right\rfloor$
and the definition fails.



\subsection{Properties of antagonistic functions}


\begin{Pro}\label{l-antg1}  Let $n$ be a positive integer, $\Omega$ a finite set,
 $f$ and $g$ functions from $\Omega$ to $\{1,\dots,n\}$, such that
for every $u\in\Omega, f(u)+g(u)\leq n+1$,  then\\
$f$ and $g$ are  antagonistic of order $n$ if and only if
there is a $w\in\Omega$ such that
$\left\lfloor \left(\frac{n+1}{2}\right)^2\right\rfloor \leq f(w)\cdot g(w)$.
\end{Pro}
\textbf{Proof}
There exists ${w\in\Omega}$ such that  $f(w)\cdot g(w) \geq
\left\lfloor \left(\frac{n+1}{2}\right)^2\right\rfloor$
is the same as
$\Max_{u\in\Omega} f(u){\cdot}g(u) \geq
\left\lfloor \left(\frac{n+1}{2}\right)^2\right\rfloor$ and the
opposite inequality follows from the AM-GM inequality $ab\leq
\left\lfloor \left(\frac{a+b}{2}\right)^2\right\rfloor$
and the assumption $f(u)+g(u)\leq n+1$. \qed

%\medskip
\begin{Lem}\label{l:antg2} Let $i$ and $j$ be positive integers, then
$|i-j|\leq 1 \iff \left\lfloor \frac{(i+j)^2}{4}\right\rfloor
 \leq i{\cdot}j$
\end{Lem}
\textbf{Proof.} Let $i$ and $j$ be positive integers,
$|i-j|\leq 1 \iff (i-j)^2\leq 1 \iff (i-j)^2 < 4 \iff
(i+j)^2  < 4 (i j +1) \iff
\frac{(i+j)^2}{4} -1 < i j \iff
\lfloor\frac{(i+j)^2}{4}\rfloor \leq i j$,
for the last implication see~\textup{\cite[p.69]{gkp89}}. \qed

\begin{Fact}\label{f-fun} The function $m \mapsto \lfloor \frac{m^2}{4}\rfloor$
 on the positive integers is

\vspace{-.1in}
\begin{enumerate}
  \item strictly increasing and thus is one-to-one, and
  \item $\lfloor \frac{m^2}{4}\rfloor \leq \lfloor \frac{n^2}{4}\rfloor
  \Longrightarrow m\leq n$ for all $m$ and $n$ positive integers.
\end{enumerate}
\end{Fact}

\begin{Lem}  Let $n$ be a positive integer, $\Omega$ a finite set,
 $f$ and $g$ functions from $\Omega$ to $\{1,\dots,n\}$, such that
for every $u\in\Omega, f(u)+g(u)\leq n+1$,  then for every
$w\in\Omega$,\par

\smallskip
$\left\lfloor \frac{(n+1)^2}{4}\right\rfloor
\leq f(w)\cdot g(w) \quad\text{if and only if}\quad  f(w)+g(w)=n+1
\;\text{ and }\; |f(w)-g(w)|\leq 1.$
\end{Lem}
\noindent\textbf{Proof.} $(\Rightarrow$ \emph{left part})
By AM-GM, $\left\lfloor \frac{(n+1)^2}{4}\right\rfloor
\leq f(w)\cdot g(w) \Rightarrow \left\lfloor \frac{(n+1)^2}{4}\right\rfloor
\leq \left\lfloor \frac{(f(w)+g(w))^2}{4}\right\rfloor
\Rightarrow n+1\leq f(w)+g(w)$ the last by fact~\ref{f-fun}, and
since $f(w)+g(w)\leq n+1$ by assumption, we get
$f(w)+g(w)=n+1$. \\
(\emph{right part}) $f(w)+g(w)\leq n+1$ and
$\left\lfloor \frac{(n+1)^2}{4}\right\rfloor
\leq f(w)\cdot g(w) \Rightarrow
\left\lfloor \frac{(f(w)+g(w))^2}{4}\right\rfloor
\leq f(w)\cdot g(w) \Rightarrow |f(w)-g(w)|\leq 1$ by
lemma~\ref{l:antg2}. \qed

\noindent\textbf{Proof.} $(\Leftarrow)$ (\emph{this is used  several
times in the following proof of the main theorem})
By lemma~\ref{l:antg2} $|f(w)-g(w)|\leq 1 \Rightarrow
\left\lfloor \frac{(f(w)+g(w))^2}{4}\right\rfloor
\leq f(w)\cdot g(w)$, but since $f(w)+g(w)=n+1$ we get
$\left\lfloor \frac{(n+1)^2}{4}\right\rfloor
\leq f(w)\cdot g(w)$. \qed


\medskip
\noindent In summary we have the following.
\begin{Pro}[Characterization of antagonistic functions]\label{antg}
 Let $n$ be a positive integer, $\Omega$ a finite set, and
 $f$ and $g$ functions from $\Omega$ to $\{1,\dots,n\}$ such that
 $f(u)+g(u)\leq n+1$ for all $u\in\Omega$, then
$f$ and $g$ are  antagonistic of order $n$ on $\Omega$ if and only if
there exists $w\in\Omega$ such that  $f(w)+g(w)=n+1$  and
 $|f(w)-g(w)|\leq 1$.
\end{Pro}

Note that, $|f(w)-g(w)|\leq 1$ can be replaced
by $|f(w)-g(w)|=$
 {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $n$ odd }\\
         1,& \text{if $n$ even} \\
      \end{smallmatrix}
  \right.$}
and those $w\in\Omega$ for which the maximum is achieved are
exactly those which satisfy the right hand conditions.




%\medskip
\begin{Fact}\label{f-fn} Let $A$ and $B$ be finite sets, $f$ a function from
$A$ \textbf{onto} $B$,
$G$ a mapping from $B$ to $\mathbb{R}$ and for all $a\in A$, let
$F(a)=G(f(a))$, then
$\Max_{a\in A} F(a) = \Max_{b\in B} G(b) \quad \text{and} \quad
\Min_{a\in A} F(a) = \Min_{b\in B} G(b)$.
\end{Fact}


   In items~\ref{perm} to~\ref{gpha}, of the theorem $\Omega$ is a
  complemented lattice. It would be interesting to study those functions $f$ from
  $\Omega$ to $\{1,\dots,n\}$ such that $f$ and $\overline{f}$ are
  antagonistic, where $\overline{f}(u)= f(\overline{u})$.

Please send to the author other examples of these functions.
(There are more in graph theory, consider  upper domination $\Gamma$,
irredundance $IR$~\cite{cm89dm}, and CO-irredundance $COIR$~\cite{cmm00dm} numbers)


\medskip
 We could count  those elements which achieve the
  maximum in items~\ref{quad} to~\ref{gphd} of the main theorem.
 Note, we must define  when two elements are different.

\begin{itemize}
\setlength{\topsep}{0pt}
\setlength{\itemsep}{0pt}

%\vspace{-.1in}
%  \item For item~\ref{perm}, count $=1,2,\dots$
  \item For items~\ref{part}, the count is $1,2,1,2,1,2,1,2,1\dots =$
{\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         1,& \text{if $n$ odd } \\
         2,& \text{if $n$ even}
      \end{smallmatrix}
 \right.
$}
  which is sequence A000034.
  \item For items~\ref{quad}, the count is $1,2,2,6,8,\dots$
  \item For item~\ref{gphc}, the count is $1,2,2,6,8,\dots$
  \item For item~\ref{gpha}, the count is $1,2,2,6,7,\dots$
  \item For item~\ref{gphd}, the count is $1,2,2,5,4,\dots$
\end{itemize}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Proof of the theorem}

\noindent\fbox{\parbox{6.4in}{Most of the expressions
involving floors and ceilings in the theorem
may be shown to be equal to item~\ref{eo} by setting $n=2k$ and $n=2k-1$ and
manipulating the resulting algebraic expression.
Such examples are items~\ref{floor},~\ref{fs},~\ref{sum},~\ref{sumflr},~\ref{i-pd},
 and~\ref{i-t}. This is how many of these expressions were found.}}

\bigskip
\noindent$\bullet\; (\ref{seq}=\ref{eo})$ %1=2
From the pattern of the sequence in item $1$, the $2k-1^{th}$
term is $k^2$ and the $2k^{th}$ term is $k^2+k$.

\noindent$\bullet\; (\ref{eo})$ %2
use {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $n$ odd } \\
         1,& \text{if $n$ even} \\
      \end{smallmatrix}
   \right.$}%
$=\frac{1-(-1)^n}{2}$ for the last equality.



\noindent$\bullet\; (\ref{eo}=\ref{floor})$ %2=3
If $n$ is odd, $\frac{(n+1)^2}{4} =
\left\lfloor \frac{(n+1)^2}{4}\right\rfloor$ since $4$ divides
$(n+1)^2$ and if $n$ is even $(=2k)$, then $\frac{(n+1)^2-1}{4}
= \frac{(2k+1)^2-1}{4} = k^2+k = \left\lfloor k^2+k+\frac{1}{4}\right\rfloor
= \left\lfloor \frac{(2k+1)^2}{4}\right\rfloor =
\left\lfloor \frac{(n+1)^2}{4}\right\rfloor$.

\noindent$\bullet\; (\ref{eo}=\ref{fs})$ %2=4
if $n$ even $(n=2k)$, then $\left\lfloor \frac{n+1}{2}\right\rfloor{\cdot}\left\lceil
  \frac{n+1}{2}\right\rceil
  \: = \: \left\lfloor k+\frac{1}{2}\right\rfloor{\cdot}\left\lceil
  k+\frac{1}{2}\right\rceil
  \: = \: k(k+1)$ and
  if $n$ is odd $(=2k-1)$, then $\left\lfloor \frac{n+1}{2}\right\rfloor{\cdot}\left\lceil
  \frac{n+1}{2}\right\rceil
  \: = \: k^2$.

%\bigskip
\noindent$\bullet\; (\ref{fs})$ %4
The expressions in this item are shown to
equal by using $\lceil \frac{m}{2}\rceil = \lfloor
\frac{m+1}{2}\rfloor$, \;  $\lceil \frac{m}{2}\rceil - \lfloor
\frac{m}{2}\rfloor = $
 {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         1,& \text{if $m$ odd } \\
         0,& \text{if $m$ even}
      \end{smallmatrix}
   \right.$}%
and $\lceil \frac{m+1}{2}\rceil = \lceil\frac{m}{2}\rceil+$
 {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $m$ odd }\\
         1,& \text{if $m$ even} \\
      \end{smallmatrix}
   \right.$}%
from chapter 3 of \cite{gkp89}.


%\bigskip
\noindent$\bullet\; (\ref{fs}=\ref{sum})$ %4=5
item
$\ref{sum}\;=\; \sum_{k=1}^n
\lceil \frac{k}{2} \rceil \;=\; 2\left(\sum_{k=1}^{\lceil n/2\rceil} k\right) -$
 {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         \lceil n/2\rceil,& \text{if $n$ odd } \\
         0,& \text{if $n$ even}
      \end{smallmatrix}
   \right.
 $}\\%
$\;=\; \lceil\frac{n}{2}\rceil
\left(\lceil\frac{n}{2}\rceil+1\right)-$
 {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         \lceil n/2\rceil,& \text{if $n$ odd } \\
         0,& \text{if $n$ even}
      \end{smallmatrix}
   \right.
 $}%
$\;=\;  \lceil\frac{n}{2}\rceil
\Big(\lceil\frac{n}{2}\rceil +$
 {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $n$ odd }\\
         1,& \text{if $n$ even} \\
      \end{smallmatrix}
   \right.
 $}%
$\Big) =$ item~$\ref{fs}$.


\noindent$\bullet\; (\ref{fs}=\ref{sumflr})$ Use
$m=\lfloor\frac{m}{2}\rfloor +\lceil\frac{m}{2}\rceil$.

\noindent$\bullet\; (\ref{sumflr})$ %6
In the last line:

For $n=2m$,\\ $\sum_{k=\lfloor\frac{n+2}{2}\rfloor}^n  2k-n =
\sum_{k=m+1}^{2m} 2k-2m =
\sum_{i=1}^m 2i = \sum_{k=m+1}^{2m} 2k-2m =
\sum_{k=\lceil\frac{n+1}{2}\rceil}^n  2k-n$.

For $n=2m-1$,\\ $\sum_{k=\lfloor\frac{n+2}{2}\rfloor}^n  2k-n =
\sum_{k=m}^{2m-1} 2k-2m+1 =
\sum_{i=1}^m 2i-1 = \sum_{k=m}^{2m-1} 2k-2m+1 =
\sum_{k=\lceil\frac{n+1}{2}\rceil}^n  2k-n$.


\medskip

\noindent$\bullet\; (\ref{gf}=(\ref{rra},\ldots,\ref{rrd}))$ %7=8(a..d)

Use \texttt{rsolve} of Maple V Release 5 (or Maple 7) with generating function option as follows. \\*
\noindent\fbox{\parbox{6.3in}{%
\small
$\boldsymbol{>}$ \ \textbf{8(a)} \
\texttt{rsolve(\{f(n+1)+f(n)=(n+2)*(n+1)/2, f(1)=1\},
f,'genfunc'(x)):factor(\%);}

\hspace{1.3in}$ - {\displaystyle \frac {x}{( - 1 + x)^{3}\,(1 +
x)}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{8(b)} \
\texttt{rsolve(\{f(n+2) = f(n)+n+2, f(1)=1,f(2)=2\},
f,'genfunc'(x)):factor(\%);}

\hspace{1.3in}$ - {\displaystyle \frac {x}{( - 1 + x)^{3}\,(1 +
x)}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{8(c)}
\texttt{rsolve(\{f(n+3) = \\ f(n+2)+f(n+1)-f(n)+1,
f(1)=1,f(2)=2,f(3)=4\}, f, 'genfunc'(x)):factor(\%);}

\hspace{1.3in}$ - {\displaystyle \frac {x}{( - 1 + x)^{3}\,(1 +
x)}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{8(d)}
\texttt{rsolve(\{f(n+4) = \\ 2*f(n+3)-2*f(n+1)+f(n),
f(1)=1,f(2)=2,f(3)=4,f(4)=6\}, f,'genfunc'(x)):factor(\%);}

\hspace{1.3in}$ - {\displaystyle \frac {x}{( - 1 + x)^{3}\,(1 +
x)}}$

\smallskip
The generating function option of \texttt{rsolve} is only valid for constant
coefficients equations.
}} %end fbox parbox




\medskip
\noindent$\bullet\; (\ref{eo}=\ref{rr})$
Use \texttt{rsolve} of Maple V Release 5 (or Maple 7) as follows.\\*
\noindent\fbox{\parbox{6.3in}{%
\small
$\boldsymbol{>}$ \ \textbf{8(a)} \
\texttt{rsolve(\{f(n+1)+f(n)=(n+2)*(n+1)/2, f(1)=1\}, f):simplify(\%);}

\hspace{1.3in}${\displaystyle \frac {1}{8}} \,(-1)^{(n + 1)} + {\displaystyle
\frac {1}{4}} \,n^{2} + {\displaystyle \frac {1}{2}} \,n +
{\displaystyle \frac {1}{8}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{8(b)} \
\texttt{rsolve(\{f(n+2) = f(n)+n+2, f(1)=1,f(2)=2\},
f):simplify(\%);}

\hspace{1.3in}${\displaystyle \frac {1}{8}} \,(-1)^{(n + 1)} + {\displaystyle
\frac {1}{4}} \,n^{2} + {\displaystyle \frac {1}{2}} \,n +
{\displaystyle \frac {1}{8}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{8(c)} \
\texttt{rsolve(\{f(n+3) = f(n+2)+f(n+1)-f(n)+1,
f(1)=1,f(2)=2,f(3)=4\}, f): simplify(\%);}


\hspace{1.3in}${\displaystyle \frac {1}{8}} \,(-1)^{(n + 1)} + {\displaystyle
\frac {1}{2}} \,n + {\displaystyle \frac {1}{8}}  +
{\displaystyle \frac {1}{4}} \,n^{2}$

\smallskip
$\boldsymbol{>}$ \ \textbf{8(d)} \\
\texttt{rsolve(\{f(n+4) = 2*f(n+3)-2*f(n+1)+f(n),
f(1)=1,f(2)=2,f(3)=4,f(4)=6\}, f):simplify(\%);}

\hspace{1.3in}${\displaystyle \frac {1}{8}} \,(-1)^{(n + 1)} + {\displaystyle
\frac {1}{4}} \,n^{2} + {\displaystyle \frac {1}{2}} \,n +
{\displaystyle \frac {1}{8}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{8(e)} \
\texttt{rsolve(\{(n+1)*f(n+2) = 2*f(n+1)+(n+3)*f(n),
f(1)=1,f(0)=0\}, f):simplify(\%);}

\hspace{1.3in}${\displaystyle \frac {1}{8}} \,(-1)^{(n + 1)} + {\displaystyle
\frac {1}{4}} \,n^{2} + {\displaystyle \frac {1}{2}} \,n +
{\displaystyle \frac {1}{8}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{8(f)}
\texttt{rsolve(\{(n+2)*f(n+3)=}\\
\hspace*{.5in} \texttt{(n+3)*f(n+2)+(n+2)*f(n+1)-(n+3)*f(n), f(2)=2,f(1) = 1,
f(0) = 0\},f);}


\hspace{1.3in}$ - {\displaystyle \frac {1}{8}} \,(-1)^{n} + {\displaystyle
\frac {1}{8}}  + {\displaystyle \frac {1}{2}} \,n +
{\displaystyle \frac {1}{4}} \,n^{2}$
}} % end fbox parbox

%\medskip

\noindent$\bullet\; (\ref{rr})$ Using \texttt{rectohomrec} from
the Maple V Release 5 share package \texttt{gfun},
\ref{rra} gives \ref{rre},
 \ref{recp} gives \ref{rrf} and  \ref{rec} gives \ref{rrd}.

\noindent$\bullet\; (\ref{sum}=\ref{diff})$ sum of difference, see~\cite{m90}.

\vspace{-.05in}
\noindent$\bullet\; (\ref{gf}=\ref{diff})$
the generating function
of the sequence in item~\ref{diff} is $\frac{x}{(1-x)(1-x^2)} = \\
 \frac{1}{(1-x)}\sum\limits_{k=1}^\infty x^{2k-1} =
 \sum\limits_{k=1}^\infty \lceil\frac{k+1}{2}\rceil  x^k$.

%\vspace{-.05in}
\noindent$\bullet\; (\ref{rr}=\ref{delq})$ Easy to show
\ref{recp}$=$\ref{dp} and \ref{rec}$=$\ref{delq3}.


%\bigskip
\noindent$\bullet\; (\ref{delq})$
These are shown
to be equal by simple manipulations of differences;
 see~\cite{m90}.

\noindent$\bullet\; (\ref{gf}=\ref{de})$ %10=7
Show (using Maple) that  the generating function satisfies  the
differential equation.



\medskip
%\pagebreak[4]  %because \\*  in the next line did not work
\noindent$\bullet\; (\ref{gf}=\ref{de})$ %10=7
Use \texttt{dsolve} of Maple V Release 5 (or Maple 7) as follows. \\*%
\fbox{\parbox{6in}{%
\small
$\boldsymbol{>}$ \ \textbf{10(a)} \
\texttt{ode1:=(1-x$^2$)*diff(F(x),x)=2*(1+2*x)*F(x);}

\hspace{1.3in}$\mathit{ode1} := (1 - x^{2})\,({\frac {\partial }{\partial x}}\,
\mathrm{F}(x))=2\,(1 + 2\,x)\,\mathrm{F}(x)$

%\smallskip
$\boldsymbol{>}$ \
\texttt{dsolve(\{ode1,F(0)=1\},F(x));}
%\hspace{1.3in}
\qquad$\mathrm{F}(x)= - {\displaystyle \frac {1}{(x + 1)\,(x -
1)^{3}}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{10(b)} \
\texttt{ode2:=(1-x$^2$)*diff(F(x),x)=1+(4+3*x-2*x$^2$+x$^3$)*F(x);}

\hspace{1.3in}$\mathit{ode2} := (1 - x^{2})\,({\frac {\partial }{\partial x}}\,
\mathrm{F}(x))=1 + (4 + 3\,x - 2\,x^{2} + x^{3})\,\mathrm{F}(x)$

\smallskip
$\boldsymbol{>}$ \
\texttt{simplify(dsolve(\{ode2,F(0)=0\},F(x)));}
%\hspace{1.3in}
\qquad$\mathrm{F}(x)= - {\displaystyle \frac {x}{(x + 1)\,(x -
1)^{3}}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{10(c)} \
\texttt{ode3:=(1-x$^2$)*diff(F(x),x,x)=(4+5*x-2*x$^2$+x$^3$)*diff(F(x),x)+(3-4*x+3*x$^2$)*F(x);}

\hspace{.8in}$\mathit{ode3} := (1 - x^{2})\,({\frac {\partial ^{2}}{\partial x
^{2}}}\,\mathrm{F}(x))=(4 + 5\,x - 2\,x^{2} + x^{3})\,({\frac {
\partial }{\partial x}}\,\mathrm{F}(x)) + (3 - 4\,x + 3\,x^{2})\,
\mathrm{F}(x)$


\smallskip
$\boldsymbol{>}$ \
\texttt{dsolve(\{ode3,F(0)=0,D(F)(0)=1\},F(x));}
%\hspace{1.3in}
\qquad$\mathrm{F}(x)= - {\displaystyle \frac {x}{(x + 1)\,(x -
1)^{3}}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{10(d)} \
\texttt{ode4:=(1-x$^2$)*diff(F(x),x)=2x+(6+2*x-4*x$^2$+2*x$^3$)*F(x);}

\hspace{.8in}$\mathit{ode4} := (1 - x^{2})\,({\frac {\partial ^{2}}{\partial x
^{2}}}\,\mathrm{F}(x))=2x +(6 + 2\,x - 4\,x^{2} + 2\,x^{3})\,\mathrm{F}(x)$


%\smallskip
$\boldsymbol{>}$ \
\texttt{dsolve(\{ode4,F(0)=0\},F(x));}
%\hspace{1.3in}
\qquad$\mathrm{F}(x)= - {\displaystyle \frac {x^2}{(x + 1)\,(x -1)^{3}}}$

\smallskip
$\boldsymbol{>}$ \ \textbf{10(e)} \
 \texttt{ode5:=x*(1-x$^2$)*diff(F(x),x,x)=(1+6*x+3*x$^2$-4*x$^3$+2x$^4$)*F(x)+(-6-4x$^2$+4x$^3$)*F(x);}

\hspace{.2in}$\mathit{ode5} := x(1 - x^{2})\,({\frac {\partial ^{2}}{\partial x
^{2}}}\,\mathrm{F}(x))=(1 + 6\,x + 3\,x^{2} - 4\,x^{3} +2\,x^4)({\frac {\partial }{\partial x
}}\,\mathrm{F}(x))+ (-6-4x^2+4x^3)\,\mathrm{F}(x)$


%\smallskip
$\boldsymbol{>}$ \
\texttt{dsolve(\{ode5,F(0)=0,D(D(F))(0)=2\},F(x));}
\qquad$\mathrm{F}(x)= - {\displaystyle \frac {x^2}{(x + 1)\,(x -1)^{3}}}$
}} %end fbox



\noindent$\bullet\; (\ref{seq}=\ref{de})$ \texttt{listtodiffeq} from
Maple V R5 share package \texttt{gfun} was used to get \ref{dea},
\ref{deb} and \ref{ded}.

\noindent$\bullet\; (\ref{de})$ Using \texttt{diffeqtohomdiffeq} from
Maple V Release 5 share package \texttt{gfun},
  \ref{deb} gives \ref{dec} and \ref{ded} gives \ref{dee}.


%\medskip
\noindent$\bullet\; (\ref{fs}=\ref{quad})$
A quadratic $f(x)=ax^2+bx+c$ with integer coefficients and $a$
negative has its maximum value at $x= \lfloor \frac{-b}{2a} \rfloor$
and $x= \lceil \frac{-b}{2a} \rceil$.
So item~\ref{quad} $= \Max_{k\in\{1..n\}} -k^2+(n+1)k =
(n+1-\lfloor\frac{n+1}{2}\rfloor)\lfloor\frac{n+1}{2}\rfloor=
\lceil\frac{n+1}{2}\rceil  \lfloor\frac{n+1}{2}\rfloor =$
item~\ref{fs}, since $m -\lfloor\frac{m}{2}\rfloor =
 \lfloor\frac{m}{2}\rfloor +$
 {\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         1,& \text{if $n$ odd }\\
         0,& \text{if $n$ even} \\
      \end{smallmatrix}
   \right.$}%
$=\lceil\frac{m}{2}\rceil$.
Similarly  for $x=\lceil \frac{n+1}{2} \rceil$.

\noindent$\bullet\; (\ref{quad}=\ref{spart})$
Since item~\ref{spart} $= \Max_{\mathfrak{A}\in\text{Part}(1..n)}
  |\mathfrak{A}|\cdot\Max_{A\in\mathfrak{A}} |A| =
  \Max_{m\in\{1..n\}}m \Max_{\mathfrak{A}\in\text{Part}_m(1..n)}
  \Max_{A\in\mathfrak{A}} |A| = \\ \Max_{m\in\{1..n\}}m(n-m+1)
   =$ item~\ref{quad},  where $\text{Part}_m(1..n)$ are the set
   partitions of $\{1..n\}$ with $m$ blocks.

\noindent$\bullet\; (\ref{perm}=\ref{pp})$
The Robinson-Schensted-Knuth
algorithm~\cite[p.218]{c94},~\cite[p.94]{sw86}
 gives a bijection between
permutations of $\{1,\dots,n\}$ and ordered pairs of Young tableaux of
$n$ of the same shape, where the number of rows of the tableaux is the
length of the longest increasing subsequence of the permutation
and the number of columns is length of the longest decreasing
subsequence.


\smallskip
\noindent The {\bfseries RSK} algorithm as used in C. C. Rousseau's
\emph{Partitions and q-series in combinatorics} course at the University of
Memphis in spring 2000.

\vspace*{-.1in}
{\footnotesize
\begin{pseudocode}[shadowbox]{RSK}{n,\langle a_i\rangle_{i=1}^n}
\text{INPUT: n, a positive integer}\\
\text{INPUT: $(a_i)_{i=1}^n$, a permutation of }\{1..n\} \\
\text{OUTPUT: $(P,Q)$, a pair of standard Young
tableaux of order $n$ }\\
\hspace*{.54in}\text{and both of the same shape }\\
%\text{(OUTPUT: the common shape of P and Q is a partition of n)}\\
\\
P[\,,]\GETS \emptyset, Q[\,,]\GETS \emptyset \quad \COMMENT{these are empty 2D arrays}\\
\FOR p \GETS 1\TO n
\DO
\BEGIN
b\GETS a_p \\
r\GETS 1 \\
\WHILE \text{row r is not empty \textbf{and} $b$ is not greater than the last cell in row $r$ of $P$}
\DO
\BEGIN
c \GETS \Min\{j \mid b\leq P(r,j) \} \\
\text{swap}(b,P(r,c)) \\
r\GETS r+1
\END \\
\COMMENT{add a new cell at end of row $r$ of $P$ and $Q$}
\vspace*{-.1in}\\
c\GETS 1+\text{the number of cells in row r} \\
P(r,c)\GETS b \\
Q(r,c)\GETS p
\END \\
\\
\RETURN{P,Q}
\end{pseudocode}
} %end small

\vspace*{-.15in}
For  a partition of $n$, $a$, the
$\text{\#rows(shapeRSK}(n,a) = $ the size of longest increasing subsequence of $a$
and  $\text{\#cols(shapeRSK}(n,a) = $ the size of longest decreasing subsequence of
$a$.


\medskip
\noindent The inverse of the {\bfseries RSK} algorithm.

\vspace*{-.1in}
{\footnotesize
\begin{pseudocode}[shadowbox]{iRSK}{n,\langle P,Q\rangle}
\text{INPUT: n, a positive integer}\\
\text{INPUT: $(P,Q)$, a pair of standard Young
tableaux of order $n$ }\\
\hspace*{.54in}\text{and both of the same shape }\\
\text{OUTPUT: $(a_i)_{i=1}^n$, a permutation of }\{1..n\} \\
\\
\FOR p \GETS n \DOWNTO 1
\DO
\BEGIN
(r,c) \GETS \text{find the row and column of the value of
$p$ in array $Q$} \\
b\GETS P(r,c) \\
\text{delete  cell } (r,c) \text{ of }P\\
\WHILE r\neq 1
\ADO
\BEGIN
r\GETS r-1 \\
\COMMENT{in row $r$ of $P$ put $b$ in the correct spot }
\vspace*{-.1in}\\
\hspace*{.7in}\text{and pass back the bumped value as $b$} \\
c \GETS \Max\{j \mid P(r,j)<b \} \\
\text{swap}(b,P(r,c))
\END \\
a_p \GETS b
\END\\
\\
\RETURN{(a_i)_{i=1}^n}
\end{pseudocode}
} %end small

\vspace*{-.15in}
For  $P,Q$ StdYoungTab of $n$ with the same shape,
then  $\text{iRSK}(n, (P,Q))^{-1} = \text{iRSK}(n, (Q,P))$

\medskip

\noindent$\bullet\; (\ref{spart}=\ref{part})$ Use
fact~\ref{f-fn}.

\noindent$\bullet\; (\ref{part})$ use fact~\ref{f-fn} to show
that compositions and partitions of $n$ give the same result.

\noindent$\bullet\; (\ref{fs}=\ref{part})$ The partitions
$(\lfloor\frac{n+1}{2}\rfloor,
\underbrace{1,\dots,1}_{\lceil\frac{n-1}{2}\rceil \text{ $1$'s} })$
and
$(\lceil\frac{n+1}{2}\rceil,
\underbrace{1,\dots,1}_{\lfloor\frac{n-1}{2}\rfloor  \text{ $1$'s} })$
are (the only) partitions of $n$
which achieve the maximum value since
$\lfloor\frac{n+1}{2}\rfloor+\lceil\frac{n-1}{2}\rceil=n$
and $\lceil\frac{n+1}{2}\rceil+\lfloor\frac{n-1}{2}\rfloor=n$
and they are equal if $n$ is odd.
But for the first partition, max$\cdot\text{len} =
 \lfloor\frac{n+1}{2}\rfloor\cdot \left(\lceil\frac{n-1}{2}\rceil +1\right)
 =$ item~\ref{fs}, and for the second max$\cdot\text{len} =
 \lceil\frac{n+1}{2}\rceil \cdot \left(\lfloor\frac{n-1}{2}\rfloor+1\right)=$
 item~\ref{fs}.


%\noindent$\bullet\; (\ref{quad}=\ref{part})$

%\bigskip
\noindent$\bullet\; (\ref{part}=\ref{pp})$ Use fact~\ref{f-fn}.

\noindent$\bullet\; (\ref{fs}=\ref{gphc})$
It is known that $\chi(G)+\chi(\overline{G})\leq n+1$ for any
graph $G$ with $n$ vertices~\cite{ng56},~\cite[p. 232]{cl96}.
Now if $G=K_{\lceil\frac{n+1}{2}\rceil}
\uplus (n- \lceil\frac{n+1}{2}\rceil)K_1$, then
 $\chi(G)=\chi(K_{\lceil\frac{n+1}{2}\rceil})= \lceil\frac{n+1}{2}\rceil$
 and $\chi(\overline{G})=\chi(K_n - K_{\lceil\frac{n+1}{2}\rceil})=
 n+1-\lceil\frac{n+1}{2}\rceil= \lfloor\frac{n+1}{2}\rfloor$.
Now proposition~\ref{antg}.

\noindent$\bullet\; (\ref{floor}=\ref{gpha})$
Let $G=(n-\lceil\frac{n}{2}\rceil){\cdot}\textup{K}_1\uplus
\textup{K}_{\lceil\frac{n}{2}\rceil}$,
then $\omega(G)= \lceil\frac{n}{2}\rceil$
and, since $n=\lceil\frac{n}{2}\rceil+\lfloor\frac{n}{2}\rfloor$,
$\overline{\omega}(G)=\lfloor\frac{n}{2}\rfloor+1$, so
$\overline{\omega}(G)-\omega(G)=1-(\lceil\frac{n}{2}\rceil
-\lfloor\frac{n}{2}\rfloor) =$
{\small
   $\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $n$ odd }\\
         1,& \text{if $n$ even} \\
      \end{smallmatrix}
 \right.
$}. We also have $\overline{\omega}(H)+\omega(H)\leq n+1$ for every
 $H\in \textup{graph}(n)$, so use proposition~\ref{antg}.

\noindent$\bullet\; (\ref{fs}=\ref{gphd})$
It is known that $1+\Delta(G)+\gamma(\overline{G})\leq n+1$ for any
graph $G$ with $n$ vertices~\cite[p. 304]{b73}.
Let $G=\lceil\frac{n-1}{2}\rceil {\cdot}\textup{K}_1\uplus
\textup{K}_{1,\lfloor\frac{n-1}{2}\rfloor}$, then
$1+\Delta(G) = 1+\lfloor\frac{n-1}{2}\rfloor= \lfloor\frac{n+1}{2}\rfloor$
and $\gamma(G)= 1+\lceil\frac{n-1}{2}\rceil
=\lceil\frac{n+1}{2}\rceil$.
note that $|V(G)| =\lceil\frac{n-1}{2}\rceil
+\lfloor\frac{n-1}{2}\rfloor+1 = n$.


\noindent$\bullet\; (\ref{floor}=\ref{gen})$ See proposition~\ref{antg}.

\noindent$\bullet\; (\ref{sum}=\ref{mgph})$
The number of graphs with only $m$ loops on two vertices is
equal to the number of partitions of $m$ with at most two parts
$(=\lfloor \frac{m+2}{2} \rfloor)$.
Of the $n-1$ edges if $k\in\{1,\dots,n-1\}$ are between vertices, there
are then $\lfloor \frac{n-1-k+2}{2} \rfloor$ graphs with the
remaining edges. Hence the total number of graphs is
$\sum_{k=0}^{n-1}\lfloor \frac{n-1-k+2}{2}\rfloor =
\sum_{k=0}^{n-1}\lfloor \frac{k+2}{2}\rfloor$ which is item~\ref{sum}.


\noindent$\bullet\; (\ref{sumflr}=\ref{tri})$
From the following table of the triangles with largest side $n$, we see that the
total number of triangles is $\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}
  (n-2k)$ which is item~\ref{sumflr}.
\quad
\begin{tabular}[t]{l|l}
 n& sides of  triangle \\ \hline
1& 111 \\
2& 222 221 \\
3& 333 332 331 , 322 \\
4&444 443 442 441 , 433 432 \\
5&555 554 553 552 551 , 544 543 542 , 533
\end{tabular}

Note the strict triangular inequality will be satisfied for
integer sided triangles.

\noindent$\bullet\; (\ref{seq}=\ref{tri})$ See~\cite{jm00amm}.

\noindent$\bullet\; (\ref{dp}=\ref{put})$ Let $k=1$ in~\ref{put}, see~\cite{a85}.

\noindent$\bullet\; (\ref{diff}=\ref{los})$
From the definition of the Losanitsch
number following the table of values of $L(r,c)$, we have
$L(3,c+1)-L(3,c)=L(2,c+1)=1,2,2,3,3,4,4,\dots$ and $L(2,1)=1$,
which is item~\ref{diff}.


\noindent$\bullet\; (\ref{cp}=\ref{sa})$\
$a_{n,k} =
\left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         1,& \text{if $k=1$} \\
         |\{U\in A_n \mid \min(U)=k-1 \}|,& \text{if $k \neq 1$}
      \end{smallmatrix}
 \right.$, where $a_{n,k}$ is the
values of the array in item~\ref{sa}, and $A_n$ is as in
item~\ref{cp}. (this is how the array in item~\ref{sa} was found)


\noindent$\bullet\; (\ref{eo}=\ref{sa})$
If $n$ is even item~\ref{sa} $= 2\sum_{k=1}^{\frac{n}{2}} k =
\frac{n}{2}(\frac{n}{2}+1) =$
item~\ref{eo}. If $n$ is odd item~\ref{sa} $=
2\sum_{k=1}^{\frac{n-1}{2}} k + \frac{n+1}{2}=
\frac{n-1}{2}(\frac{n-1}{2}+1)+ \frac{n+1}{2} =$ item~\ref{eo}.

\noindent$\bullet\; (\ref{eo}=\ref{i-pd})$ %2=26
Let $n=2k$ and $=2k-1$. See chapter 6 of~\cite{r78} for partitions.

\noindent$\bullet\; (\ref{i-t})$\
use: if $n=2k$ then $\lfloor\frac{n+1}{2}\rfloor=\lceil\frac{n}{2}\rceil=k$,
$\lfloor\frac{n+2}{2}\rfloor=\lceil\frac{n+1}{2}\rceil=k+1$, and
$\lfloor\frac{n+3}{2}\rfloor=\lceil\frac{n+2}{2}\rceil=k+1$.

if $n=2k+1$ then $\lfloor\frac{n+1}{2}\rfloor=\lceil\frac{n}{2}\rceil=k+1$,
$\lfloor\frac{n+2}{2}\rfloor=\lceil\frac{n+1}{2}\rceil=k+1$, and
$\lfloor\frac{n+3}{2}\rfloor=\lceil\frac{n+2}{2}\rceil=k+2$.


\noindent$\bullet\; (\ref{fs}=\ref{i-t})$ %4=27
Let $s=3$ and $m=n+1$ in Tur\'an's theorem.

Every graph on m vertices not containing a complete graph of $s$ vertices, $K_s$, has at most $ex(m;
K_{s}^{(2)})$ vertices.

\vspace{-.1in}
\begin{Pro}[Tur\'an\protect\cite{a95amm,ms65cjm}]  Let $2\leq m,s$ be positive integers, then the
following are equal.
\begin{enumerate}

  \item $\binom{m}{2}-\displaystyle\sum_{i=0}^{s-2}
  \binom{\lfloor\frac{m+i}{s-1}\rfloor}{2}$, \quad see~\textup{\cite[p.294]{b78},\cite[p.54]{b86}}

  \item $\displaystyle\sum_{0\leq i<j< s-1}
  \left\lfloor\frac{m+i}{s-1}\right\rfloor\cdot
  \left\lfloor\frac{m+j}{s-1}\right\rfloor$, \quad see~\textup{\cite[294]{b78},\cite[p.1234]{ggl95v2}}

  \item $\frac{(s-2)(m^2-k^2)}{2(s-1)}+\binom{k}{2}$
  where $k\;
  =\mod(m,s-1)=m-(s-1)\lfloor\frac{m}{s-1}\rfloor$, \quad see~\textup{\cite[p.18]{h69}}

  \item $ex(m; K_{s}^{(2)}):= $ the maximum number of $2$-sets $($edges$)$
  of $\{1,\dots,m\}$ which have  no $s$ cliques.
\end{enumerate}
\end{Pro}

%See~\cite{a95amm,ms65cjm}

\medskip
\begin{tabular}{c|cccccccc ccccccl} \hline
  % after \\ : \hline or \cline{col1-col2} \cline{col3-col4} ...
   & &\makebox[0pt][l]{$ex(m; K_{s}^{(2)})$} &&&&&&& &&&&&& sequence \\ \hline
   $s\backslash m$ &2 &3 &4 &5 &6 &7 &8 &9 &10&11&12&13&14&15\\ \hline
      2    &0  &0  &0 &0 &0 &0 &0 &0&0 &0 &0 &0 &0 &0 \\
      3    &1  &2  &4 &6 &9 &12 &16 &20 & 25&30&36&42&49&56&\textbf{A002620}\\
      4    &$\downarrow$ &3  &5 &8 &12 &16 &21 &27 &33&40&48&56&65&75& A000212 \\
      5    &  &$\downarrow$&6 &9 &13 &18 &24 &30 &37&45&54&63&73&84& A033436\\
      6    &  &  &$\downarrow$&10 &14 &19 &25 &32 &40&48&57&67&78&90& A033437\\
      7    &  &  & &$\downarrow$&15 &20 &26 &33&41&50&60&70&81&93& \\
      8    &  &  & & &$\downarrow$&21 &27&34 &42&51&61&72&84&96& \\
      9    & &  &  & & &$\downarrow$&28 & 35 &43&52&62&73&85&98& \\
\end{tabular}

The numbers in the diagonal sequence $1,3,6,10,15,21,28,36,\ldots$ are the triangle numbers,
 sequence A000217 $=\lim\limits_{s\to\infty} ex(m; K_{s}^{(2)})$.


\noindent$\bullet\; (\ref{sumflr}=\ref{i-opt})$ %4=28
See proof in~\cite[Problem 97]{bkm95}.

\noindent End of proof of the theorem. \QED

\medskip
Redundancy in the above illustrates different methods.
Some of these methods may suggest ways to analyze other sequences, see~\cite[Ch.2]{EIS}.


\bigskip\bigskip

\noindent Using $\sum_{k=n}^{2n-1} \left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $k$ odd } \\
        1 ,& \text{if $k$ even}
      \end{smallmatrix}
 \right.
    = \lfloor\frac{n}{2}\rfloor$, $p_2(k)=p_2^{*}(k) + \left\{% the large curly bracket, matches  \right.
      \begin{smallmatrix}
         0,& \text{if $k$ odd } \\
        1 ,& \text{if $k$ even}
      \end{smallmatrix}
 \right.$
and~\ref{cp} and~\ref{i-pd} of the theorem we have.

\vspace{-.1in}
%\begin{Cor} For $n$ a positive integer.
%$$\sum_{k=0}^{n-1} \;  p_{2}^{*}(n+k) -p_{2}^{*}({\leq}n, n+k)   = \binom{n-1}{2}$$
%where $p_{2}^{*}(m)=$ number of partitions of $m$ with two distinct parts,
%and $p_{2}^{*}({\leq}n,m)=$ number of partitions of $m$ with two distinct parts
%which are at most $n$. See chapter 6 of~\textup{\cite{r78}} for partitions.
%\end{Cor}
\begin{Cor} For $n$ a positive integer.
$$\sum_{k=0}^{n-1} \; \left(p_2^{*}(n+k)-p_2^{*}(\max\leq n,n+k)\right)    \quad =\quad
\sum_{k=0}^{n-1} \;  p_{2}^{*}(\max>n,n+k)   \quad =\quad \binom{n-1}{2}$$
where $p_2^{*}(m) =$ the number of partitions of $m$ with two \emph{distinct} parts, and
$p_{2}^{*}(\max>n,m)=$ the number of partitions of $m$ with two \emph{distinct}
parts, the largest part greater than $n$.
See~\textup{\cite[Ch.12,13,14]{a94}},\textup{\cite{p56},\cite[Ch.6]{r78}} for partitions.
\end{Cor}


%What about a combinatorial proof and generalization of this corollary?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Acknowledgements}
Thanks to the referee for suggestions, and apologies to the editor for my delay
in making the changes.

%
%Items \ref{seq},\ref{eo},\ref{fs},%
%\ref{gf},\ref{rec},\ref{diff},\ref{d1},\ref{mgph},\ref{tri},\ref{put} and
%\ref{los} of the main theorem are from OEIS~\cite{OEIS} for
%sequence
% \htmladdnormallink{A002620}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=002620}
%, which has references.



%\bigskip

%\vfill
%-----------------------------------------------------
%\addcontentsline{toc}{chapter}{Bibliography}
\renewcommand{\baselinestretch}{.5}
\small
\frenchspacing
\begin{thebibliography} {99}

\bibitem{a95amm} M.~Aigner,
Tur\'an's graph theorem,
\emph{Amer.\ Math.\ Monthly}, \textbf{102} (1995), 808--816.

%\bibitem{az98} M.~Aigner and G.~M.~Ziegler,
%\emph{Proofs from THE BOOK}, Springer, 1998.
%(A 2nd edition was published in 2000)

\bibitem{a85} G. L. Alexanderson et al., \emph{The William Powell
Putnam Mathematical Competition - Problems and Solutions:
1965-1984}, Mathematical Association of America,, 1985. (Problem A-1 of $27^{th}$ Competition)

\bibitem{a94} G.~E.~Andrews,
\emph{Number Theory}, Dover, 1994. Corrected reprint of 1971 edition.


\bibitem{bkm95} E.~J.~Barbeau, M.~S.~Klamkin, and W.~O.~J.~Moser,
\emph{Five Hundred Mathematical Challenges},
Mathematical Association of America, 1995.

\bibitem{b73} C. Berge, \emph{Graphs and Hypergraphs}, North
Holland, 1973.

\bibitem{b78} B. Bollob\'as, \emph{Extremal Graph Theory},
Academic Press, 1978.

\bibitem{b86} B. Bollob\'as, \emph{Combinatorics}, Cambridge
University Press, 1986.

%\bibitem{b99} B. Bollob\'as, \emph{Modern Graph Theory}, Springer-Verlag, 1998.

\bibitem{c94} P. J. Cameron, \emph{Combinatorics}, Cambridge
University Press, 1994.

\bibitem{c00} P. J. Cameron, Sequences realized by oligomorphic
permutation groups, Article 00.1.5, Vol. \textbf{3}
\emph{J. Integer Seq.}, 2000, published electronically at \\
\emph{\htmladdnormallink{http://www.research.att.com/\~{}njas/sequences/JIS/VOL3/groups.html}
{http://www.research.att.com/\~{}njas/sequences/JIS/VOL3/groups.html}}.


\bibitem{cl96} G. Chartrand and L. Lesniak,
{\em Graphs \& Digraphs}, 3ed, Chapman \& Hall, 1996.

\bibitem{cmm00dm} E.~J.~Cockayne, D.~McCrea and C.~M.~Mynhardt,
Nordhaus-Gaddum result for CO-irredundance in graphs
\emph{Disc.\  Math.} \textbf{211} (2000), 209--215.


\bibitem{cm89dm} E.~J.~Cockayne and C.~M.~Mynhardt,
On the product of upper irredundance numbers of a graph and its complement,
\emph{Disc.\ Math.} \textbf{76} (1989), 117--121.


\bibitem{d97} R.~Diestel,
\emph{Graph Theory}, Springer, 1997.
(Second edition, 2000)
Available at
 \emph{\htmladdnormallink{Graph Theory,2ed}
{http://www.math.uni-hamburg.de/home/diestel/}},
\textup{www.math.uni-hamburg.de/home/diestel/}
%\textbf{www.math.uni-hamburg.de/home/diestel/}



\bibitem{cse}  Encyclopedia of Combinatorial Structures,
\textup{http://algo.inria.fr/bin/encyclopedia}.


\bibitem{f68} H. J. Finck, On the chromatic number of a graph and
its complement, in P. Erd\"os and G. Katona, eds.,
\emph{Theory of Graphs, Proceedings of the
Colloquium held at Tihany, Hungary, 1966}, 
Academic Press, 1968, pp.\ 99--113.

\bibitem{f55} E. Fix and J. L. Hodges, Jr., Significance
probabilities of the Wilcoxon test, \emph{Ann.\ Math.\ Stat.}
\textbf{26} (1955), 301--312.

\bibitem{f97} W. Fulton, \emph{Young Tableaux}, London Mathematics
Society Student Text Vol.\ 35, Cambridge University Press, 1997.

\bibitem{gsww92} S.~Getu, L.~W.~Shapiro, W.-J.~Woan, and L.~C.~Woodson,
How to guess a generating function, \emph{SIAM J.\ Disc.\ Math.}
\textbf{5} (1992), 497--499.


\bibitem{ggl95v2}  R.~L.~Graham, M.~Gr\"otschel and L.~Lovasz, eds.,
\emph{Handbook of Combinatorics, Volume 2},
Elsevier Science, 1995.


\bibitem{gkp89} R.~L.~Graham, D.~E.~Knuth and O.~Patashnik, {\em Concrete
Mathematics}, Addison-Wesley, 1989. 

\bibitem{h69} F. Harary, \emph{Graph Theory}, Addison-Wesley, 1969.

\bibitem{jm00amm} T. Jenkyns and E. Muller,
Triangular triples from ceilings to floors,
\emph{Amer.\ Math.\ Monthly} \textbf{107} (2000),
635--639.

\bibitem{m74amm} M.~J.~Marsden,
triangles with integer-valued sides,
\emph{Amer.\ Math.\  Monthly} \textbf{81} (1974), 373--376.

\bibitem{m90} R. E. Mickens, \emph{Difference Equations}, 2nd
edition, Van Nostrand, 1990.


\bibitem{ms65cjm} T.~S.~Motzkin and E.~G.~Straus,
Maxima for graphs and a new proof of a theorem of Tur\'an,
\emph{Canad.\ J.\ Math.} \textbf{17} (1965), 533--540.

\bibitem{ng56} E. A. Nordhaus and J. W. Gaddum,
On complementary graphs,
\emph{Amer.\ Math.\ Monthly}, \textbf{63} (1956), 175-177.

\bibitem{pw00} P.~Peart and W.-J.~Woan,
Generating functions via Hankel and Stieltjes matrices, Article 00.2.1, Vol. \textbf{3}
\emph{J. Integer Seq.}, 2000, published electronically at \\
\emph{\htmladdnormallink{http://www.research.att.com/\~{}njas/sequences/JIS/VOL3/peart1.html}
{http://www.research.att.com/\~{}njas/sequences/JIS/VOL3/peart1.html}}.

\bibitem{p56} G.~P\'olya,
On picture-writing,
\emph{Amer. Math. Monthly}, \textbf{63} (1956), 689--697.
Reprinted in I. Gessel and G.-C. Rota, eds., 
\emph{Classic Papers in Combinatorics},
Birkh\"auser, 1987, 249--257.

\bibitem{r78} J.~Riordan,
\emph{An Introduction to Combinatorial Analysis},
Princeton University Press, 1978.

\bibitem{s61cjm} C.~Schensted,
Longest increasing and decreasing subsequences,
\emph{Canad.\ J.\ Math.} \textbf{13}  (1961), 179--191.
Reprinted in I. Gessel and G.-C. Rota, eds.,
\emph{Classic Papers in Combinatorics},
Birkh\"auser, 1987, 299--311.

\bibitem{OEIS} N. J. A. Sloane,
\emph{\htmladdnormallink{The On-Line Encyclopedia of Integer Sequences}
{http://www.research.att.com/~njas/sequences}}, published electronically at \\
\textup{http://www.research.att.com/\~{}njas/sequences/}, 2000.

\bibitem{class} N. J. A. Sloane,
\emph{\htmladdnormallink{Classic Sequences}
{http://www.research.att.com/~njas/sequences/classic.html}}, published electronically at \\
\textup{http://www.research.att.com/\~{}njas/sequences/classic.html}, 2000.

\bibitem{EIS} N. J. A. Sloane and S.~Plouffe,
\emph{The Encyclopedia of Integer Sequences},
Academic Press, 1995. 


\bibitem{s00} S. E. Speed, The integer sequence A027434 and lower
antagonistic functions, in preparation.

\bibitem{sw86} D. Stanton and D. White,
\emph{Constructive Combinatorics}, Springer-Verlag, 1986.

\end{thebibliography}

\bigskip
\hrule
\bigskip


\noindent 2000 {\it Mathematics Subject Classification}: 
05A15, 05A18, 05C35, 05C69, 05E10, 05D05, 06B99.

\noindent \emph{Keywords: 
Antagonistic functions, graph theory, domination
number, MAPLE, Nordhaus-Gaddum inequality, Tur\'an's number, partitions of
integers, Young tableaux, Robinson-Schensted-Knuth algorithm}



\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence \seqnum{A002620}.)


\vspace*{+.1in} \noindent Received January 10, 2001;
revised versions received  March 19, 2002; February 26, 2003.
Published in {\it Journal of Integer Sequences} March 2, 2003.



\end{document}


.
