The Connell Sum Sequence

Grady D. Bullington Department of Mathematics University of Wisconsin, Oshkosh Oshkosh, Wisconsin 54901 USA

                  bullingt@uwosh.edu

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.

1 Background and Reformulations

Ian Connell [1] challenged readers to find an explicit formula for

C(n) : 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, …,

now known as the Connell sequence (\underline{A001614}). The list of solvers [2] who found C(n) = 2n − ⌊\frac{1+\sqrt{8n−7}}{2}⌋ included some famous names.

Example 1.1. Each term of the Connell sequence can be described as the sum of elements of the following triangles.

1  1 1  1 1 2  1 1 1 2  1 1 1 1 3  1 1 1 1 1 4  1 1 1 1 1 1 4  1 1 1 1 1 1 1 5

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, . . ..

Conway and Guy [3, p. 44–45] use projections of tetrahedrons to facilitate calculations involving tetrahedral numbers (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

5 4 4 3 3 3 2 2 2 2 1 1 1 1 1

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.

Example 1.2. Using the representations of the terms of the Connell sequences from Example 1.1, 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:

1 1 1 1 1 2 1 1 1 2 1 1 1 1 3 5 4 4 3 3

= +  +  +  +

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.

Iannucci and Mills-Taylor [4] built on a prior generalization of the Connell sequence from Stevens [5] by providing the following definition.

Definition 1.3. For integers m ≥ 2 and r ≥ 1, the 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:

(i) The first element (or peak) is 1; (ii) If row ends with element e, the next row begins with element e + 1; (iii) Elements in each row increase consecutively by m; (iv) The j-th row has 1 + r(j − 1) elements.

(Case r = 1 was developed by Stevens [5]. The original Connell sequence is the case (m, r) = (2, 1).)

Example 1.4. The Connell (5, 3)-sequence C_{5,3} (\underline{A045929}) is given by the elements of the triangle

1 2 7 12 17 18 23 28 33 38 43 48 49 54 59 64 69 74 79 84 89 94

95 … so that C_{5,3} : 1, 2, 7, 12, 17, 18, 23, 28, 33, 38, 43, 48 . . ..

Definition 1.5. (cf., [3], [4]) 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 Δ(n) denote the n-th triangle number, P_{3}(n).

The two following identities from Iannucci and Mills-Taylor [4] display the relationship between polygonal numbers and Connell (m, r)-sequences. (For our purposes, they are useful later in the proofs of Theorems 1.9, 1.10, Lemma 4.1 and Theorem 4.1.)

For integers m ≥ 2, r ≥ 1 and j ≥ 1,

C_{m,r}(P_{r+2}(j) + i) = C_{m,r}(P_{r+2}(j)) + 1 + (i − 1)m  (1)

for 1 ≤ i ≤ rj + 1. Also,

C_{m,r}(P_{r+2}(j)) = P_{rm+2}(j)  (2)

for any j ≥ 1. (Identity 2 is a nice generalization of the geometric observation that C(Δ(n)) = n^{2} from the original Connell sequence.)

For later reference, we include two additional observations.

Observation 1.1. For any positive integer n, j = ⌊^{\frac{(k−4)+\sqrt{(k−4)^{2}+8(k−2)n}}{2(k−2)}}⌋ is the largest integer q such that P_{k}(q) ≤ n. To see this when P_{k}(q) = n, observe by Definition 1.5 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 ⇔ q < ^{\frac{(k−4)+\sqrt{(k−4)^{2}+8(k−2)n}}{2(k−2)}}. (The implication ⇒ follows from an

analogous argument of the above. The implication ⇐ 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.)

In any case, it follows that j = ⌊^{\frac{(r−2)+\sqrt{(r−2)^{2}+8rn}}{2r}}⌋ gives the largest integer j such that

P_{r+2}(j) ≤ n.

Observation 1.2. The sum of the first n of the k-gonal numbers is given by

𝕋_{k}(n) := \frac{n(n+1)((k−2)(n−1)+3)}{6}.

This follows from an induction argument. Note that 𝕋_{3}(n) is the n-th tetrahedral number.

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.

Example 1.6. The elements of the Connell (5, 3)-sequence are sums of the following triangles.

1  11  11, 5  11, 1, 9 11, 1, 1, 13 11, 1, 1, 1 13  11, 1, 1, 1 1, 17  11, 1, 1, 1 1, 1, 21

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

1 + 11 + 11,5 + 11,1,9 + 11,1,1,13 + 11,1,1,1 13  = 65,8,11,14 13

We pause to make the following definitions.

Definition 1.7. For integers b ≥ 1 and k ≥ 3, define the P_{k}-stuttered arithmetic progression A_{b,k} as the sequence with the following properties:

(i) The first element is 1; (ii) If n is a k-gonal number, then A_{b,k}(n + 1) = A_{b,k}(n); (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)}.)

Definition 1.8. For integers m ≥ 2 and r ≥ 1, let the 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.

The next two theorems give general characterizations of what was seen in Examples 1.1, 1.2 and 1.6. Their proofs being straightforward induction arguments using equations (1) and (2) are left to the reader.

Theorem 1.9. The n-th element of the Connell (m, r)-sequence is

C_{m,r}(n) = n − 1 + A_{m−1,r+2}(n).

Theorem 1.10. 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:

(i) The peak element is n; (ii) If a row j ends with element e, then row j + 1 begins with element e − 1; (iii) Elements in each row increases consecutively by m − 2; (iv) The j-th row has 1 + r(j − 1) elements. (Case m = 2, r = 1 gives the projection of the n-th tetrahedron.)

By Theorem 1.9, the n-th partial sum of the P_{k}-stuttered arithmetic progression A_{b,k} is

∑_{i=1}^{n} A_{b,k}(i) = S_{b+1,k−2}(n) − Δ(n) + n.  (3)

2 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 [6].

Definition 2.1. Let G be a graph of size n (i.e., |E(G)| = n). A γ-labeling of G is a oneto-one function f : V (G) → {0, 1, 2, …, n} that induces a labeling f′ : E(G) → {1, 2 …, n} of the edges of G defined by f′(e) = |f(u) − f(v)| for each edge e = uv of G. The value of a γ-labeling f on G is val(f) = ∑_{e∈E(G)} f′(e).

The authors [6], [7] study the maximum γ-labeling values that can be acquired on certain classes of graphs. As the next result shows, the γ-label value is generally bounded by an element of the Connell sum sequence.

Theorem 2.2. Any γ-labeling value on a graph of size n is bounded above by the n-th element of the Connell sum sequence, S(n).

Proof. For n, let j = ⌊(−1 + \sqrt{1 + 8n})/2⌋ and k = n − Δ(j). In a γ-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 ∈ {1, 2, …, n}, there can be at most i edges with induced label n − i + 1. So, the value of a γ-labeling on a graph of size n cannot exceed

∑_{i=1}^{j} i(n − i + 1) + k(n − j).

Revisiting Example 1.2 and Theorem 1.10, recall that S(n) is the sum of the n largest elements in the projection of the n-th tetrahedron. By Observation 1.1, j is the largest integer q such that Δ(q) ≤ n, so S(n) is the sum of all elements in the first j rows and k = n − Δ(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 ∑_{i=1}^{j} i(n − i + 1) + k(n − j) which is the sum above. □

Example 2.3. For n = 5, the only γ-labelings (on connected graphs) that attain value S(5) = 19 are as follows.

012  543  012  54  01  543

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.

Theorem 2.4. For n ∈ ℤ^{+}, let j = ⌊\frac{−1+\sqrt{1+8n}}{2}⌋ and k = n − Δ(j).

(a) The number of distinct γ-labelings (on their respective underlying connected graphs) with value S(n) is \binom{j+1}{k}.

(b) The number of distinct, connected graphs that accommodate at least one of the γlabelings counted in (a) is given by

τ(n) = \{ \begin{matrix}\frac{1}{2} \binom{j+1}{k}, if j and k are odd; \\ \frac{1}{2} [\binom{j+1}{k} + \binom{⌈j/2⌉}{⌊k/2⌋}] , otherwise. \end{matrix}

Proof. (a) By the proof of Theorem 2.2, any γ-labeling on a graph of size n having value S(n) must include i edge(s) labeled n−i+1 for each i ∈ {1, 2, …, n} and k edges labeled n−j. So, by construction, we can describe each possible γ-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, …, j and the vertices in the other partite set with n, n − 1, n − 2, …, n − (j − 1). For each l ∈ {0, 1, …, j − 1}, highlight (in your favorite color) the edges having vertex label l and n, n − 1, …, n − (j − 1) + l, respectively. If n ≠ Δ(j), highlight (i.e., choose) an additional k = n − Δ(j) from the j + 1 edges with edge label n − j. The subgraph induced by the highlighted edges has a γ-labeling with value S(n). Conversely, any connected graph with γ-label value S(n) must be one of the \binom{j+1}{k} possible γ-labelings constructed in this manner.

(b) Notice that any γ-labeling described in the proof of (a) is determined entirely by knowing which l = \binom{j+1}{k} of the distinct vertices among the ones labeled 0, 1, …, j are incident to the \binom{j+1}{k} edges (with induced label n − j) chosen at the end of the proof. Because of this, we can describe any γ-labeling in (a) by an l-tuple (i_{1}, …, i_{l}), 0 ≤ i_{1} < … < i_{l} ≤ j. By considering degree, the only other γ-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}, …, j −i_{1}). If (i_{1}, …, i_{l}) = (j −i_{l}, j −i_{l−1}, …, j −i_{1}), call (i_{1}, …, i_{l}) a palindromic description. It is straightforward to check that, among the \binom{j+1}{k} descriptions, there are no palindromic descriptions when j and k are odd and \binom{⌈j/2⌉}{⌊k/2⌋} palindromic descriptions otherwise. Therefore, the number of distinct, connected subgraphs that can accommodate one of the γ-labels from (a) is

τ(n) = \{ \begin{matrix}0 + \frac{1}{2} \binom{j+1}{k} = \frac{1}{2} \binom{j}{k}, if j and k are odd; \\ \binom{⌈j/2⌉}{⌊k/2⌋} + \frac{1}{2} [\binom{j+1}{k} − \binom{⌈j/2⌉}{⌊k/2⌋}] = \frac{1}{2} [\binom{j+1}{k} + \binom{⌈j/2⌉}{⌊k/2⌋}] , otherwise. □ \end{matrix}

3 Limiting Behavior

Theorem 3.1. For integers m ≥ 2 and r ≥ 1,

lim_{n→∞} \frac{S_{m,r}(n)}{n^{2}} = \frac{m}{2}, and so lim_{n→∞} \frac{S_{m,r}(n)}{Δ(n)} = m.

Proof. By definition, S_{m,r}(n) = ∑_{i=1}^{n} C_{m,r}(i). By [4],

C_{m,r}(i) = im − (m − 1)⌊(3r − 2 + \sqrt{8r(i − 1) + (r − 2)^{2}})/2r⌋.

Notice that A ≤ S_{m,r}(n) ≤ B where

A = Δ(n)m − (m − 1)n⌊(3r − 2 + \sqrt{8r(n − 1) + (r − 2)^{2}})/2r⌋ and
B = Δ(n)m − (m − 1)n⌊(3r − 2 + \sqrt{(r − 2)^{2}})/2r⌋.

Since lim_{n→∞} \frac{A}{n^{2}} = lim_{n→∞} \frac{B}{n^{2}} = \frac{m}{2}, the assertion follows. □

Corollary 3.1. (cf. Definition 1.7 and equation (3)) For integers b ≥ 1 and k ≥ 3,

lim_{n→∞} \frac{∑_{i=1}^{n} A_{b,k}(i)}{n^{2}} = \frac{b}{2} and lim_{n→∞} \frac{∑_{i=1}^{n} A_{b,k}(i)}{Δ(n)} = b.

4 An Explicit Formula

Lemma 4.1. For integers m ≥ 2, r ≥ 1 and j ≥ 1, the P_{r+2}(j)-th element of the Connell (m, r)-sum sequence is given by

S_{m,r}(P_{r+2}(j)) = mΔ(P_{r+2}(j)) + (m − 1) [𝕋_{r+2}(j) − (j + 1)P_{r+2}(j)]

where 𝕋_{r+2}(j) is defined in Observation 1.2.

Proof. By induction on j. One easily checks that the assertion holds for j = 1. Suppose that the assertion holds for j = k. Letting

R(j) = mΔ(P_{r+2}(j)) + (m − 1) [𝕋_{r+2}(j) − (j + 1)P_{r+2}(j)],

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 (1) and (2),

S_{m,r}(P_{r+2}(k + 1)) − S_{m,r}(P_{r+2}(k)) = ∑_{i=1}^{rk+1} C_{m,r}(P_{r+2}(k) + i)

= ∑_{i=1}^{rk+1}[C_{m,r}(P_{r+2}(k)) + 1 + (i − 1)m]

= (rk + 1)C_{m,r}(P_{r+2}(k)) + (rk + 1) + mΔ(rk)

= (rk + 1) [P_{mr+2}(k) + 1 + mrk/2]

= (rk + 1) [\frac{mrk^{2} + 2k + 2}{2}] .

Similarly,

R(k + 1) − R(k) = m(Δ(P_{r+2}(k + 1)) − Δ(P_{r+2}(k)))+

(m − 1) [𝕋_{r+2}(k + 1) − 𝕋_{r+2}(k) − (k + 2)P_{r+2}(k + 1) + (k + 1)P_{r+2}(k)]

= m [\frac{m(rk + 1)(rk^{2} + 2k + 2)}{2}] +

(m − 1) [P_{r+2}(k + 1) − (k + 2)P_{r+2}(k + 1) + (k + 1)P_{r+2}(k)]

= (rk + 1) [\frac{mrk^{2} + 2k + 2}{2}]

which agrees with the above. □

Theorem 4.1. For integers m ≥ 2 and r ≥ 1, the n-th element of the Connell (m, r)-sum sequence is given by the direct formula

S_{m,r}(n) = (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))

where S_{m,r}(P_{r+2}(j)) is given in Lemma 4.1 and j = ⌊^{\frac{(r−2)+\sqrt{(r−2)^{2}+8rn}}{2r}}⌋ (cf. Observa-

tion 1.1).

Proof. Let m, r, n, and j be as in the assertion, and let 0 ≤ i < rj + 1. Using equations (1) and (2),

S_{m,r}(n) = S_{m,r}(P_{r+2}(j) + i) = ∑_{k=1}^{i} C_{m,r}(P_{r+2}(j) + k) + S_{m,r}(P_{r+2}(j)) =
∑_{k=1}^{i}(C_{m,r}(P_{r+2}(j)) + 1 + (k − 1)m) + S_{m,r}(P_{r+2}(j)) =

∑_{k=1}^{i}(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)).

Replacing i with n − P_{r+2}(j) gives

(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)). □

Corollary 4.1. By equation (3), Theorem 4.1 (indirectly) gives a direct formula for the partial sums of A_{b,k}.

5 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.

References

[1] Elementary problem E1382, Amer. Math. Monthly 66 (1959), 724.

[2] Solution to elementary problem E1382, Amer. Math. Monthly 67 (1960), 380.

[3] J. H. Conway and R. K. Guy, The Book of Numbers, Springer, 1996.

[4] D. Iannucci and D. Mills-Taylor, On generalizing the Connell sequence, J. Integer Seq. 2 (1999), Article 99.1.7.

[5] G. Stevens, A Connell-like sequence, J. Integer Seq. 1 (1998), Article 98.1.4.

[6] G. Chartrand, D. Erwin, D. W. VanderJagt and P. Zhang, Gamma-labeling of graphs, Bull. Inst. Comb. Appl. 44 (2005), 51–68.

[7] G. Chartrand, D. Erwin, D. W. VanderJagt and P. Zhang, On gamma-labeling of trees, Discuss. Math. Graph Theory 25 (2005), 363–383.

2000 Mathematics Subject Classification: Primary 05C78; Secondary 11B25, 11B99. Keywords: Connell sequence, Connell (m, r)-sequence, gamma-labeling.

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

Received October 27 2006; revised version received January 22 2007. Published in Journal of Integer Sequences, January 23 2007.

Return to Journal of Integer Sequences home page.