\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{pstricks}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

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

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Connell Sum Sequence
}
\vskip 1cm
\large
Grady D. Bullington\\
Department of Mathematics\\
University of Wisconsin, Oshkosh\\
Oshkosh, Wisconsin 54901\\
USA\\
\href{mailto:bullingt@uwosh.edu}{\tt bullingt@uwosh.edu} \\
\end{center}

\vskip .2 in
\begin{abstract} The Connell sum sequence refers to the
partial sums of the Connell sequence.    In this paper, the Connell
sequence, Connell sum sequence and generalizations from Iannucci and
Mills-Taylor are interpreted as sums of
elements of triangles, relating them to polygonal number-stuttered
arithmetic progressions. The $n$-th element of the Connell sum
sequence is established as a sharp upper bound for the value of a
gamma-labeling of a graph of size $n$. The limiting behavior and a
explicit formula for the Connell $(m,r)$-sum sequence are also given.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{observation}{Observation}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 
\newtheorem{example}{Example}[section]
\newtheorem{exam}[theorem]{Example}
\newenvironment{examp}{\begin{exam}\normalfont\quad}{\normalsize\end{exam}}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\normalsize\end{defin}}
\newenvironment{defn}{\begin{defin}\normalfont\quad}{\normalsize\end{defin}}

% Shortcuts
\def\l{\left}
\def\r{\right}
\def\a{\lambda}
\def\b{\beta}
\def\ld{\ldots}
\def\sset{\subseteq}
\def\gm{\gamma}
\def\nid{\noindent}
\def\pr{\prime}
\def\bc{\begin{center}}
\def\ec{\end{center}}


\section{Background and Reformulations}

Ian Connell~\cite{AMM1} challenged readers to find an explicit formula
for \bc $C(n) : 1,2,4,5,7,9,10,12,14,16,17,\ldots,$\ec now
known as the \textit{Connell sequence} (\underline{A001614}). The
list of solvers~\cite{AMM2} who found
$C(n)=2n-\lfloor\frac{1+\sqrt{8n-7}}{2}\rfloor$ included some famous
names.

 \begin{examp} \label{ex1}
Each term of the Connell sequence can be described as the sum of
elements of the following triangles.

\begin{pspicture}(1.2,1)(12,4)

\psset{dotsize=2pt 0}

\put(1.2,3){$1$}

\put(2.7,3){$1$}%
\put(2.5,2.7){$1$}

\put(4.0,3){$1$}%
\put(3.8,2.7){$1$} \put(4.2,2.7){$2$}

\put(5.5,3){$1$}%
\put(5.3,2.7){$1$} \put(5.7,2.7){$1$}%
\put(5.1,2.4){$2$}

\put(7,3){$1$}%
\put(6.8,2.7){$1$} \put(7.2,2.7){$1$}%
\put(6.6,2.4){$1$}\put(7.0,2.4){$3$}

\put(8.5,3){$1$}%
\put(8.3,2.7){$1$} \put(8.7,2.7){$1$}%
\put(8.1,2.4){$1$}\put(8.5,2.4){$1$}\put(8.85,2.4){$4$}

\put(10.4,3){$1$}%
\put(10.2,2.7){$1$} \put(10.6,2.7){$1$}%
\put(10,2.4){$1$}\put(10.4,2.4){$1$}\put(10.8,2.4){$1$}%
\put(9.8,2.05){$4$}

\put(12.4,3){$1$}%
\put(12.2,2.7){$1$} \put(12.6,2.7){$1$}%
\put(12,2.4){$1$}\put(12.4,2.4){$1$}\put(12.8,2.4){$1$}%
\put(11.8,2.05){$1$}\put(12.2,2.05){$5$}


\psdots[dotstyle=*](13.7,2.7)(13.9,2.7)(14.1,2.7)


\end{pspicture}\vspace{-25pt}

\nid The $n$-th element of the Connell sequence is
 $n-1+\underline{A122797}(n)$ where $\underline{A122797}(n): 1,1,2,2,3,4,4,5,6,7,7,8,9,10,11,11,\ldots$.
\end{examp}
\bigskip

Conway and Guy~\cite[p. 44--45]{Numbers} use projections of
tetrahedrons to facilitate calculations involving tetrahedral
numbers ($\mbox{Tet}(n)=\frac{1}{6}n(n+1)(n+2)$).  Visualize the
fifth tetrahedron as the ``pyramid" built from 35 cannonballs, the
base being a triangle of 15 cannonballs.  The fifth tetrahedral
number (35) is the sum of elements in the triangle
 \bc
\begin{pspicture}(10.7,1.8)(12.3,3.5)
\psset{dotsize=2pt 0}
\put(11.5,3){5}%
\put(11.3,2.7){4} \put(11.7,2.7){4}%
\put(11.1,2.4){3}\put(11.5,2.4){3}\put(11.9,2.4){3}%
\put(10.9,2.1){2}\put(11.3,2.1){2}\put(11.7,2.1){2}\put(12.1,2.1){2}
\put(10.7,1.8){1}\put(11.1,1.8){1}\put(11.5,1.8){1}\put(11.9,1.8){1}\put(12.3,1.8){1}
\end{pspicture}\ec
of the fifth tetrahedron. To see this, project any given side of the
tetrahedron onto the base. Count the number of cannonballs included
in the projection to each cannonball in the base to obtain the
elements of the triangle above. For instance, the number $5$ in the
picture is the number of cannonballs along the edge from the top
cannonball to the base.

\bigskip

\begin{examp}\label{ex2} Using the representations of the terms of the
Connell sequences from Example~\ref{ex1}, notice how the fifth
partial sum of the Connell sequence is the sum of the five largest
elements in the projection of the fifth tetrahedron:


\hspace{30pt}
\begin{pspicture}(1.2,2)(10.5,4)

\psset{dotsize=1.2pt 0}

\put(1.2,3){$1$}

\put(3.2,3){$1$}%
\put(3,2.7){$1$}

\put(5,3){$1$}%
\put(4.8,2.7){$1$} \put(5.2,2.7){$2$}

\put(7,3){$1$}%
\put(6.8,2.7){$1$} \put(7.2,2.7){$1$}%
\put(6.6,2.4){$2$}

\put(9,3){$1$}%
\put(8.8,2.7){$1$} \put(9.2,2.7){$1$}%
\put(8.6,2.4){$1$}\put(9.0,2.4){$3$}

\put(11.5,3){$5$}%
\put(11.3,2.7){$4$} \put(11.7,2.7){$4$}%
\put(11.1,2.4){$3$}\put(11.5,2.4){$3$}

\psdots(12.2,2.4)

\put(10.1,2.7){$=$}

\put(2,2.7){$+$}

\put(3.9,2.7){$+$}

\put(5.9,2.7){$+$}

\put(7.8,2.7){$+$}
\end{pspicture}
\end{examp}

\psshadowbox{\begin{tabular}{l}
 In general, the $n$-th partial sum of the Connell sequence is the sum \\ of the $n$
 highest elements in the
projection of the $n$-th tetrahedron.\end{tabular}}\bigskip

Iannucci and Mills-Taylor~\cite{GenConnellseq} built on a prior
generalization of the Connell sequence from Stevens
~\cite{Connelllikeseq} by providing the following definition.

\begin{definition}\label{defn1} For integers $m\ge 2$ and
$r\ge 1$, the \textit{Connell $(m,r)$-sequence}  is the sequence of
elements of an infinite triangle (read left to right and down, row
by row) having the following properties:

\nid (i) The first element (or peak) is 1;

\nid (ii) If row ends with element $e$, the next row begins with
element $e+1$;

\nid (iii) Elements in each row increase consecutively by $m$;

\nid (iv)  The $j$-th row has $1+r(j-1)$ elements.
\end{definition}
\par\nid
(Case $r=1$ was developed by Stevens~\cite{Connelllikeseq}. The
original Connell sequence is the case $(m,r)=(2,1)$.)\bigskip

\begin{examp}\label{ex4}
 The Connell $(5,3)$-sequence
 $C_{5,3}$
 \mbox{\emph{(\underline{A045929})}}
is given by the elements of the triangle \vspace{-5pt} \bc $1$

$2$ $7$ $12$ $17$

$18$ $23$ $28$ $33$ $38$ $43$ $48$

$49$ $54$ $59$ $64$ $69$ $74$ $79$ $84$ $89$ $94$

\hspace{-155pt}$95$ \ldots

\ec so that $C_{5,3}: 1, 2, 7, 12, 17,18, 23, 28, 33, 38, 43
,48\ldots$.

\end{examp}

\begin{defn}\label{kgonal} (cf.,~\cite{Numbers},~\cite{GenConnellseq})
The $n$-th $k$-gonal (i.e., $k$-sided polygonal) number is given by
the formula $P_{k}(n)=\frac{n((k-2)n-k+4)}{2}$. As a special case,
let $\Delta(n)$ denote the $n$-th triangle number,
$P_{3}(n)$.\end{defn}

The two following identities from Iannucci and
Mills-Taylor~\cite{GenConnellseq} display the relationship between
polygonal numbers and Connell $(m,r)$-sequences. (For our  purposes,
they are useful later in the proofs of
Theorems~\ref{connection},~\ref{connectionsum},
Lemma~\ref{sumsforpoly} and Theorem~\ref{directformula}.)

For integers $m\ge 2$, $r\ge1$ and $j\ge 1$,
\begin{equation}\label{eqn2}
C_{m,r}(P_{r+2}(j)+i)=C_{m,r}(P_{r+2}(j))+1+(i-1)m
\end{equation} for $1\le i\le rj+1$.  Also,
\begin{equation} \label{eqn1}
C_{m,r}(P_{r+2}(j))=P_{rm+2}(j)
\end{equation} for any $j\ge 1$.
(Identity~\ref{eqn1} is a nice generalization of the geometric
observation that $C(\Delta(n))=n^2$ from the original Connell
sequence.) 

For later reference, we include two additional observations.

\begin{observation}\label{one}
For any positive integer $n$,
$j=\lfloor\frac{(k-4)+\sqrt{(k-4)^2+8(k-2)n}}{2(k-2)}\rfloor$ is the
largest integer $q$ such that $P_k(q)\le n$.  To see this when
$P_k(q)=n$, observe by Definition~\ref{kgonal} that
$(k-2)q^2-(k-4)q-2n=0$.  Therefore,
$q=\frac{(k-4)+\sqrt{(k-4)^2+8(k-2)n}}{2(k-2)}$ by the quadratic
formula.

Also, $P_k(q) < n$ $\Leftrightarrow$ $q<
\frac{(k-4)+\sqrt{(k-4)^2+8(k-2)n}}{2(k-2)}$. (The implication
$\Rightarrow$ follows from an analogous argument of the above. The
implication $\Leftarrow$ follows since
$\frac{(k-4)+\sqrt{(k-4)^2+8(k-2)P_k(q)}}{2(k-2)}=q <
\frac{(k-4)+\sqrt{(k-4)^2+8(k-2)n}}{2(k-2) }$ implies $P_k(q) < n$
algebraically.)\vspace{12pt}

 In any case, it follows that $j=
\left\lfloor\frac{(r-2)+\sqrt{(r-2)^2+8rn}}{2r}\right\rfloor$ gives
the largest integer $j$ such that $P_{r+2}(j)\le n$.
\end{observation}\vspace{6pt}

\begin{observation}\label{sumofkgonalnumbers}
The sum of the first $n$ of the $k$-gonal numbers is given by
\begin{center}
$\mathbb{T}_{k}(n):=\frac{n(n+1)((k-2)(n-1)+3)}{6}$.
\end{center}\vspace{12pt}

This follows from an induction argument.   Note that
$\mathbb{T}_3(n)$ is the $n$-th tetrahedral number.

\end{observation}

Similar to the earlier treatment of the Connell sequence, elements
of the Connell $(m,r)$-sequence and their partial sums can also be
expressed as the sum of elements of triangles.

\begin{examp} \label{ex7} The elements of the Connell $(5,3)$-sequence are
sums of the following triangles.

\hspace{-9pt}
\begin{pspicture}(1.2,1)(12,4)

\psset{dotsize=2pt 0}

 \put(1.2,3){$1$}

\put(2.3,3){$1$}%
\put(2.3,2.65){$1$}

\put(3.6,3){$1$}%
\put(3.6,2.65){$1,5$}

\put(5.1,3){$1$}%
\put(5.1,2.65){$1,1,9$}

\put(6.6,3){$1$}%
\put(6.6,2.65){$1,1,1,13$}

\put(8.6,3){$1$}%
\put(8.6,2.65){$1,1,1,1$} \put(8.6,2.2){$13$}

\put(10.4,3){$1$}%
\put(10.4,2.65){$1,1,1,1$} \put(10.4,2.2){$1,17$}

\put(12.4,3){$1$}%
\put(12.4,2.65){$1,1,1,1$} \put(12.4,2.2){$1,1,21$}

\psdots[dotstyle=*](14.2,2.7)(14.4,2.7)(14.6,2.7)

\psset{dotsize=1.2pt 0}

\psdots[dotstyle=*](14.8,2)
%\psline[linarc=0.25]%

\end{pspicture}%\vspace{-30pt}

The sixth partial sum of the Connell $(5,3)$-sequence (i.e., 57) is
the sum of elements of the right-hand triangle:

\end{examp}\vspace{-7pt}

\hspace{15pt}
\begin{pspicture}(1.2,1)(12,4)

\psset{dotsize=1.2pt 0}

\put(1.2,3){1}

\put(1.8,2.65){+}

\put(2.5,3){1}%
\put(2.5,2.65){1}

\put(3.1,2.65){+}

\put(3.8,3){1}%
\put(3.8,2.65){1,5}

\put(4.6,2.65){+}

\put(5.2,3){1}%
\put(5.2,2.65){1,1,9}

\put(6.35,2.65){+}

\put(7,3){1}%
\put(7,2.65){1,1,1,13}

\put(8.6,2.65){+}

\put(9.2,3){1}%
\put(9.2,2.65){1,1,1,1} \put(9.2,2.2){13}

\put(10.7,2.65){=}

\put(11.4,3){6}%
\put(11.4,2.65){5,8,11,14} \put(11.4,2.2){13}

\psdots(13.2,2.2)

\end{pspicture}%\vspace{-25pt}

\par\nid
We pause to make the following definitions.

\begin{definition}\label{arithdefn}
For integers $b\ge 1$ and $k\ge 3$, define the $P_k$-stuttered
arithmetic progression $A_{b,k}$ as the sequence with the following
properties:

\nid
(i) The first element is $1$;%

\nid (ii) If $n$ is a $k$-gonal number, then
$A_{b,k}(n+1)=A_{b,k}(n)$;%

\nid (iii) If $n$ is not a $k$-gonal number, then
$A_{b,k}(n+1)=A_{b,k}(n)+b$.

(This sequence can be altered so that the first element is any real
number $a$, resulting in the sequence $\{a-1 +A_{b,k}(n)\}$.)
\end{definition}


\begin{definition}\label{stutter}
For integers $m\ge2$ and $r\ge 1$, let the \textit{Connell sum
$(m,r)$-sequence} $S_{m,r}$ be the sequence of partial sums of the
Connell $(m,r)$-sequence. Let the Connell sum sequence $S$ be the
partial sums of the Connell sequence.
\end{definition}

The next two theorems give general characterizations of what was
seen in Examples~\ref{ex1},~\ref{ex2} and~\ref{ex7}. Their proofs
being straightforward induction arguments using equations
(\ref{eqn2}) and $(\ref{eqn1})$ are left to the reader.
\bigskip

\begin{theorem}\label{connection} The $n$-th element of the Connell
$(m,r)$-sequence is
\begin{center}
$C_{m,r}(n)=n-1+A_{m-1,r+2}(n)$.\end{center}
\end{theorem}\bigskip

\begin{theorem} \label{connectionsum} The $n$-th partial sum of the Connell $(m,r)$-sequence is the
sum of the first $n$ elements (read left to right, row by row) of
the triangle having the following properties:

\nid (i) The peak element is $n$;

\nid (ii) If a row j  ends with element $e$, then row $j+1$ begins
with element $e-1$;

\nid (iii) Elements in each row increases consecutively by $m-2$;

\nid (iv)  The $j$-th row has $1+r(j-1)$ elements.

\nid (Case $m=2$, $r=1$ gives the projection of the $n$-th
tetrahedron.)
\end{theorem}\bigskip

By Theorem~\ref{connection}, the $n$-th partial sum of the
$P_k$-stuttered arithmetic progression $A_{b,k}$ is
\begin{equation}\label{lastone}
\sum^{n}_{i=1}A_{b,k}(i)=
S_{b+1,k-2}(n)-\Delta(n)+n.\end{equation}\bigskip

\section{An Application to Graph Theory}

Recently, a lot of research in graph theory has come from the
following definition introduced by Chartrand, Erwin, VanderJagt and
Zhang~\cite{Chartrand1}.\bigskip

\begin{definition} Let
$G$ be a graph of size $n$ (i.e., $|E(G)|=n$).  A $\gamma$-labeling
of $G$ is a one-to-one function $f: V(G)\rightarrow \{0,1,2,\ld,n\}$
that induces a labeling $f^{\pr}: E(G)\rightarrow \{1,2\ld,n\}$ of
the edges of $G$ defined by $f^{\pr}(e)=|f(u)-f(v)|$ for each edge
$e=uv$ of $G$.  The value of a $\gamma$-labeling $f$ on $G$ is
$val(f)=\sum_{e\in E(G)}f^{\pr}(e)$.\end{definition}\bigskip

The authors~\cite{Chartrand1},~\cite{Chartrand2} study the maximum
$\gamma$-labeling values that can be acquired on certain classes of
graphs.  As the next result shows, the $\gamma$-label value is
generally bounded by an element of the Connell sum sequence.\bigskip

\begin{theorem}\label{gammaupperbound} Any $\gamma$-labeling value on a graph of size
$n$ is bounded above by the $n$-th element of the Connell sum
sequence,  $S(n)$.\end{theorem}\bigskip

\nid {\bf Proof.}  For $n$, let
$j=\l\lfloor(-1+\sqrt{1+8n})/2\r\rfloor$ and $k=n-\Delta(j)$. In a
$\gamma$-labeling on a graph of size $n$, there can be at most one
edge with induced label $n$ --- namely the edge with incident
vertices labeled $0$ and $n$. Carrying this further, for each
$i\in\{1,2,\ld,n\}$, there can be at most $i$ edges with induced
label $n-i+1$.  So, the value of a $\gamma$-labeling on a graph of
size $n$ cannot exceed \bc
 $\displaystyle\sum^j_{i=1}i(n-i+1)+k(n-j)$.\ec

Revisiting Example~\ref{ex2} and Theorem~\ref{connectionsum}, recall
that $S(n)$ is the sum of the $n$ largest elements in the projection
of the $n$-th tetrahedron.  By Observation~\ref{one}, $j$ is the
largest integer $q$ such that $\Delta(q)\le n$, so $S(n)$ is the sum
of all elements in the first $j$ rows and $k=n-\Delta(j)$ elements
in the $j+1$-st row of the projection.  Since the $i$-th row of the
projection is filled with the number $n-i+1$, $S(n)$ equals
$\sum^j_{i=1}i(n-i+1)+k(n-j)$ which is the sum above. $\Box$\bigskip

\begin{examp} For $n=5$, the only $\gamma$-labelings
(on connected graphs) that attain value $S(5)=19$ are as
follows.\vspace{-8pt}

\bc
\begin{pspicture}(0,0)(12,4)
% Dots
\psdots[dotstyle=*](1,1)(1,2)(1,3)(3,1)(3,2)(3,3)

\psdots[dotstyle=*](5,1)(5,2)(5,3)(7,2)(7,3)

\psdots[dotstyle=*](9,2)(9,3)(11,1)(11,2)(11,3)

% Lines for the first graph
\psline(1,3)(3,1)\psline(1,3)(3,2)\psline(1,3)(3,3)
\psline(3,3)(1,1)\psline(3,3)(1,2)\psline(3,3)(1,1)

% Lines for the second graph
\psline(5,1)(7,3)\psline(5,2)(7,3)\psline(5,2)(7,2)
\psline(5,3)(7,3)\psline(5,3)(7,2)

% Line for the third graph
\psline(9,2)(11,3)\psline(9,3)(11,3)
\psline(5,3)(7,3)\psline(5,3)(7,2)\psline(9,3)(11,3)\psline(9,3)(11,2)
\psline(9,3)(11,1)\psline(9,2)(11,2)

% Labelings for the first graph
\put(0.7,2.9){$0$} \put(0.7,1.9){$1$}\put(0.7,0.9){$2$}
\put(3.15,2.9){$5$} \put(3.15,1.9){$4$}\put(3.15,0.9){$3$}

% Labelings for the second graph
\put(4.7,2.9){$0$} \put(4.7,1.9){$1$}\put(4.7,0.9){$2$}
\put(7.15,2.9){$5$} \put(7.15,1.9){$4$}

% Labelings for the third graph
\put(8.7,2.9){$0$} \put(8.7,1.9){$1$} \put(11.15,2.9){$5$}
\put(11.15,1.9){$4$} \put(11.15,0.9){$3$}
\end{pspicture}
\ec\vspace{-8pt} \nid Each of these graphs has one edge with induced
label $5$, two edges with label $4$ and two edges with label $3$.
Notice that there are two non-isomorphic, connected, underlying
graphs.
\end{examp}\bigskip

\begin{theorem}
For $n\in \mathbb{Z}^+$, let
$j=\l\lfloor\frac{-1+\sqrt{1+8n}}{2}\r\rfloor$ and $k=n-\Delta(j)$.
\begin{enumerate}
\item[(a)] The number of distinct $\gamma$-labelings (on their
respective underlying connected graphs) with value $S(n)$ is
${j+1\choose{k}}$.\vspace{12pt}

\item[(b)] The number of distinct, connected graphs that accommodate
at least one of the $\gamma$-labelings counted in (a) is given by
\bc $\tau(n)=\l\{\begin{array}{l} \frac{1}{2}{j+1 \choose{k}},
\hspace{6pt}
\mbox{\rm if $j$ and $k$ are odd;} \\
\\
                                \frac{1}{2}\l[{j+1\choose{k}}+{\lceil j/2\rceil \choose{\lfloor k/2\rfloor}}\r],\hspace{6pt}   \mbox{\rm otherwise.} \\
                                \end{array}\r.$\ec
\end{enumerate}

\end{theorem}\bigskip

\nid {\bf Proof.} (a) By the proof of Theorem~\ref{gammaupperbound},
any $\gamma$-labeling on a graph of size $n$ having value $S(n)$
must include $i$ edge(s) labeled $n-i+1$ for each $i\in
\{1,2,\ld,n\}$ and $k$ edges labeled $n-j$. So, by construction, we
can describe each possible $\gamma$-labeling with value $S(n)$ as a
subgraph of the complete bipartite graph $K_{j+1,j+1}$. Label
vertices in the first partite set of $K_{j+1,j+1}$ with
$0,1,2,\ld,j$ and the vertices in the other partite set with
$n,n-1,n-2,\ld,n-(j-1)$.  For each $l \in \{0,1,\ld,j-1\}$,
highlight (in your favorite color) the edges having vertex label $l$
and $n,n-1,\ld,n-(j-1)+l$, respectively.  If $n\ne \Delta(j)$,
highlight (i.e., choose) an additional $k=n-\Delta(j)$ from the
$j+1$ edges with edge label $n-j$. The subgraph induced by the
highlighted edges has a $\gamma$-labeling with value $S(n)$.
Conversely, any connected graph with $\gamma$-label value $S(n)$
must be one of the ${j+1\choose{k}}$ possible $\gamma$-labelings
constructed in this manner.\bigskip

(b) Notice that any $\gamma$-labeling described in the proof of (a)
is determined entirely by knowing which $l={j+1\choose{k}}$ of the
distinct vertices among the ones labeled $0,1,\ld,j$ are incident to
the ${j+1\choose{k}}$ edges (with induced label $n-j$) chosen at the
end of the proof.  Because of this, we can describe any
$\gamma$-labeling in $(a)$ by an $l$-tuple $(i_1,\ld,i_l)$, $0\le
i_1 < \ld < i_l\le j$. By considering degree, the only other
$\gamma$-labeling (among the possible constructions in the proof of
(a)) having an underlying connected subgraph that is isomorphic to
$H$ is described by $(j-i_l,j-i_{l-1},\ld,j-i_1)$. If
$(i_1,\ld,i_l)=(j-i_l,j-i_{l-1},\ld,j-i_1)$, call $(i_1,\ld,i_l)$ a
\textit{palindromic} description.  It is straightforward to check
that, among the ${j+1\choose{k}}$ descriptions, there are no
palindromic descriptions when $j$ and $k$ are odd and ${\lceil
j/2\rceil\choose{\lfloor k/2\rfloor}}$ palindromic descriptions
otherwise.  Therefore, the number of distinct, connected subgraphs
that can accommodate one of the $\gamma$-labels from (a)
is\vspace{12pt} \bc $\tau(n)=\l\{\begin{array}{l}
0+\frac{1}{2}{j+1\choose{k}}=\frac{1}{2}{j \choose{k}},
\hspace{12pt} \mbox{\rm
if $j$ and $k$ are odd;} \\ \\
                       {\lceil j/2\rceil \choose{\lfloor k/2\rfloor}}+\frac{1}{2}\l[{j+1\choose{k}}-{\lceil j/2\rceil \choose{\lfloor k/2\rfloor}}\r] =
 \frac{1}{2}\l[{j+1\choose{k}}+{\lceil j/2\rceil \choose{\lfloor k/2\rfloor}}\r], \hspace{6pt}
                          \mbox{\rm otherwise. $\Box$} \\
                                \end{array}\r.$ \ec\bigskip

\section{Limiting Behavior}

\begin{theorem} For integers $m\ge 2$ and $r\ge 1$,\bc
$\displaystyle\lim_{n\rightarrow\infty}\frac{S_{m,r}(n)}{n^2}=\frac{m}{2}$,
and so
$\displaystyle\lim_{n\rightarrow\infty}\frac{S_{m,r}(n)}{\Delta(n)}=m$.\ec

\end{theorem}\bigskip

\nid {\bf Proof.} By definition,
$S_{m,r}(n)=\sum^n_{i=1}C_{m,r}(i)$. By \cite{GenConnellseq},\bc
$C_{m,r}(i)=im-(m-1)\lfloor(3r-2+\sqrt{8r(i-1)+(r-2)^2})/2r\rfloor$.\ec
Notice that $A\le S_{m,r}(n)\le B$ where \bc
$A=\Delta(n)m-(m-1)n\lfloor(3r-2+\sqrt{8r(n-1)+(r-2)^2})/2r\rfloor$
and

$B=\Delta(n)m-(m-1)n\lfloor(3r-2+\sqrt{(r-2)^2})/2r\rfloor$.\ec
Since
$\displaystyle\lim_{n\rightarrow\infty}\frac{A}{n^2}=\lim_{n\rightarrow\infty}\frac{B}{n^2}=\frac{m}{2}$,
the assertion follows.  $\Box$\vspace{7pt}%\bigskip


\begin{cor} (cf. Definition~\ref{arithdefn} and equation~(\ref{lastone}))
 For integers $b\ge 1$ and $k\ge 3$,
\bc
$\displaystyle\lim_{n\rightarrow\infty}\frac{\sum^n_{i=1}A_{b,k}(i)}{n^2}=\frac{b}{2}$
and
$\displaystyle\lim_{n\rightarrow\infty}\frac{\sum^{n}_{i=1}A_{b,k}(i)}{\Delta(n)}=b$.\ec
\end{cor}\bigskip

\section{An Explicit Formula}

\begin{lemma}\label{sumsforpoly} For  integers $m\ge 2$,  $r\ge 1$ and $j\ge 1$,  the $P_{r+2}(j)$-th element of the Connell $(m,r)$-sum
sequence is given by\bc
$S_{m,r}(P_{r+2}(j))=m\Delta(P_{r+2}(j))+(m-1)\l[\mathbb{T}_{r+2}(j)-(j+1)P_{r+2}(j)\r]$\ec
where $\mathbb{T}_{r+2}(j)$ is defined in
Observation~\ref{sumofkgonalnumbers}.
\end{lemma}\bigskip

\nid {\bf Proof.}  By induction on $j$.  One easily checks that the assertion
holds for $j=1$.  Suppose that the assertion holds for $j=k$.
Letting \bc
$R(j)=m\Delta(P_{r+2}(j))+(m-1)\l[\mathbb{T}_{r+2}(j)-(j+1)P_{r+2}(j)\r]$,\ec
we show that
$S_{m,r}(P_{r+2}(k+1))-S_{m,r}(P_{r+2}(k))=R(k+1)-R(k)$.

By equations~(\ref{eqn2}) and~(\ref{eqn1}),

\begin{align*}
S_{m,r}(P_{r+2}(k+1))-S_{m,r}(P_{r+2}(k))&=\sum^{rk+1}_{i=1}C_{m,r}(P_{r+2}(k)+i)\\[5pt]
&=\sum^{rk+1}_{i=1}[C_{m,r}(P_{r+2}(k))+1+(i-1)m] \\[5pt]
&=(rk+1)C_{m,r}(P_{r+2}(k))+(rk+1)+m\Delta(rk)  \\[5pt]
&=(rk+1)\l[P_{mr+2}(k)+1+mrk/2\r] \\[5pt]
&=(rk+1)\l[\frac{mrk^2+2k+2}{2}\r].\end{align*}

Similarly, \begin{align*}
R(k+1)-R(k)&=m(\Delta(P_{r+2}(k+1))-\Delta(P_{r+2}(k)))+\\[5pt]
&\hspace{17pt}(m-1)\l[\mathbb{T}_{r+2}(k+1)-\mathbb{T}_{r+2}(k)-(k+2)P_{r+2}(k+1)+(k+1)P_{r+2}(k)\r]\\[5pt]
&=m\l[\frac{m(rk+1)(rk^2+2k+2)}{2}\r]+\\[5pt]
&\hspace{17pt}(m-1)\l[P_{r+2}(k+1)-(k+2)P_{r+2}(k+1)+(k+1)P_{r+2}(k)\r]\\[5pt]
&=(rk+1)\l[\frac{mrk^2+2k+2}{2}\r] \end{align*} which agrees with
the above. $\Box$\bigskip

\begin{theorem}\label{directformula} For integers $m\ge 2$ and $r\ge 1$,  the $n$-th element of the Connell $(m,r)$-sum
sequence is given by the direct formula\bc
$S_{m,r}(n)=(n-P_{r+2}(j))\l(P_{mr+2}(j)+1+\frac{(n-P_{r+2}(j)-1)m}{2}\r)+S_{m,r}(P_{r+2}(j))$
\ec where $S_{m,r}(P_{r+2}(j))$ is given in Lemma~\ref{sumsforpoly}
and $j=\l\lfloor\frac{(r-2)+\sqrt{(r-2)^2+8rn}}{2r}\r\rfloor$ (cf.
Observation~\ref{one}).
\end{theorem}\bigskip

\nid {\bf Proof.} Let $m$, $r$, $n$, and $j$ be as in the assertion,
and let  $0\le i < rj+1$. Using equations~(\ref{eqn2})
and~(\ref{eqn1}), \bc
$S_{m,r}(n)=S_{m,r}(P_{r+2}(j)+i)=\sum^i_{k=1}C_{m,r}(P_{r+2}(j)+k)+S_{m,r}(P_{r+2}(j))=$\ec
\bc $\sum^i_{k=1}(C_{m,r}(P_{r+2}(j))+1+(k-1)m)+S_{m,r}(P_{r+2}(j))
=$
$\sum^i_{k=1}(P_{mr+2}(j)+1+(k-1)m)+S_{m,r}(P_{r+2}(j))=i(P_{mr+2}(j)+1+(i-1)m/2)+S_{m,r}(P_{r+2}(j))$.\ec
Replacing $i$ with $n-P_{r+2}(j)$ gives \bc
$(n-P_{r+2}(j))(P_{mr+2}(j)+1+\frac{(n-P_{r+2}(j)-1)m}{2})+S_{m,r}(P_{r+2}(j))$.
$\Box$\ec\bigskip

\begin{cor} By equation~(\ref{lastone}),
Theorem~\ref{directformula} (indirectly) gives a direct formula for
the partial sums of $A_{b,k}$.

\end{cor}\bigskip

\section{An Open Question}

 Does there exist an $n$ such that all positive integers can be
written as a sum of $n$ or less (not necessarily distinct) elements
of Connell sum sequence? Some numbers  (e.g., the first being $37$)
cannot be written as a sum of three.\bigskip

\begin{thebibliography}{1}

\bibitem{AMM1}Elementary problem E1382, \textit{Amer. Math. Monthly} \textbf{66} (1959),
724.

\bibitem{AMM2}Solution to elementary problem E1382,
\textit{Amer. Math. Monthly}  \textbf{67} (1960), 380.

\bibitem{Numbers} J.~H.~Conway and R.~K.~Guy, \textit{The Book of Numbers,}
Springer, 1996.

\bibitem{GenConnellseq} D.~Iannucci and D.~Mills-Taylor,  
\href{http://www.cs.uwaterloo.ca/journals/JIS/IANN/iann1.html}{On
generalizing the Connell sequence}, \textit{J. Integer Seq.}
\textbf{2} (1999), Article 99.1.7.

\bibitem{Connelllikeseq}  G.~Stevens, 
\href{http://www.cs.uwaterloo.ca/journals/JIS/stevens.html}{A Connell-like sequence},
\textit{J. Integer Seq.}  \textbf{1} (1998), Article 98.1.4.

\bibitem{Chartrand1} G.~Chartrand, D.~Erwin,  D.~W.~VanderJagt and
P.~Zhang,  Gamma-labeling of graphs, \textit{Bull. Inst. Comb.
Appl.} \textbf{44} (2005), 51--68.

\bibitem{Chartrand2} G.~Chartrand,  D.~Erwin, D.~W.~VanderJagt and
P.~Zhang, On gamma-labeling of trees, \textit{Discuss. Math. Graph
Theory} \textbf{25} (2005), 363--383.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05C78; Secondary 11B25, 11B99.

\noindent \emph{Keywords: } Connell sequence, Connell
$(m,r)$-sequence, gamma-labeling.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001614},
\seqnum{A045928},
\seqnum{A045929},
\seqnum{A045930},
\seqnum{A122793},
\seqnum{A122794},
\seqnum{A122795},
\seqnum{A122796},
\seqnum{A122797},
\seqnum{A122798},
\seqnum{A122799}, and
\seqnum{A122800}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 27 2006;
revised version received January 22 2007. 
Published in {\it Journal of Integer Sequences}, January 23 2007.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}