%%\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 $kn+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)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}