The Integer Sequence A002620 and Upper Antagonistic Functions

Sam E. Speed

Department of Mathematical Sciences University of Memphis Memphis, TN 38152-3240

Email address: speeds@msci.memphis.edu

Abstract

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án’s number. The computer algebra program MAPLE is used for solutions of linear recurrence and differential equations in some of the proofs. Chapter three of The Encyclopedia of Integer Sequences by Sloane and Plouffe describes the usefulness of apparently different expressions of an integer sequence.

Define ⌊r⌋, the floor of r, to be the largest integer less than or equal to a real number r, and ⌈r⌉, the ceiling of r, the smallest integer greater than or equal to r. For manipulations of floor and ceiling operations, see chapter three of [20], and for graph theory terms see [10, 13, 21].

Theorem 1.1 For n a positive integer the expressions in the following 29 paragraphs are equal. (for n = 0 see the comment at the end of this list)

1. 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, … which is sequence A002620 of the The On-Line Encyclopedia of Integer Sequences (OEIS) [31] without the leading zeros. See the comment at end of this list.

2. \begin{cases}k^{2}, & n = 2k−1 \\ k(k + 1), & n = 2k \end{cases} = \begin{cases}∑_{i=1}^{k}(2i − 1), & n = 2k−1 \\ ∑_{i=1}^{k} 2k, & n = 2k \end{cases} = \begin{cases}\frac{(n+1)^{2}}{4} , & n odd \\ \frac{(n+1)^{2}−1}{4}, & n even \end{cases} = \frac{n^{2}}{4} + \frac{n}{2} +

\frac{1−(−1)^{n}}{8} .

3. ⌊(\frac{n+1}{2})^{2}⌋ = ⌈\frac{(n+1)^{2}−1}{4}⌉ = ⌊(\frac{n+1}{2})⌋ + ⌊(\frac{n}{2})^{2}⌋ = ⌈(\frac{n−1}{2})⌉ + ⌈(\frac{n}{2})^{2}⌉.

4. ⌊\frac{n+1}{2}⌋ · ⌈\frac{n+1}{2}⌉ = ⌊\frac{n+1}{2}⌋ ·( ⌊\frac{n+1}{2}⌋ + \{ \begin{matrix}0, & if n odd \\ 1, & if n even \end{matrix} ) = ⌊\frac{n+1}{2}⌋ · ⌊\frac{n+2}{2}⌋ = ⌈\frac{n}{2}⌉ · ⌈\frac{n+1}{2}⌉ =

⌈\frac{n}{2}⌉ ·( ⌈\frac{n}{2}⌉ + \{ \begin{matrix}0, & if n odd \\ 1, & if n even \end{matrix} ) = ⌈\frac{n+1}{2}⌉ ·( ⌈\frac{n+1}{2}⌉ − \{ \begin{matrix}0, & if n odd \\ 1, & if n even \end{matrix} ).

5. ∑_{k=0}^{n−1} ⌊\frac{k+2}{2}⌋ = ∑_{k=1}^{n} ⌊\frac{k+1}{2}⌋ = ∑_{k=2}^{n+1} ⌊\frac{k}{2}⌋ = n + ∑_{k=2}^{n−1} ⌊\frac{k}{2}⌋ = ∑_{k=1}^{n} ⌈\frac{k}{2}⌉.

6. ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋}(n−2k) = n+(n−1) ⌊\frac{n−1}{2}⌋−⌊\frac{n−1}{2}⌋^{2} = (n+1−⌊\frac{n+1}{2}⌋ ) ⌊\frac{n+1}{2}⌋ = ∑_{k=⌊ \frac{n+1}{2} ⌋+1}^{n+1} (2k−n−2) =

∑_{k=0}^{⌈ \frac{n−1}{2} ⌉}(n−2k) = n+(n−1) ⌈\frac{n−1}{2}⌉−⌈\frac{n−1}{2}⌉^{2} = (n+1−⌈\frac{n+1}{2}⌉ ) ⌈\frac{n+1}{2}⌉ = ∑_{k=⌈ \frac{n+1}{2} ⌉+1}^{n+1} (2k−n−2) =

∑_{k=⌊ \frac{n+2}{2} ⌋}^{n} (2k−n) = ∑_{k=⌈ \frac{n+1}{2} ⌉}^{n} (2k−n) = ∑_{k=1}^{⌊ \frac{n+1}{2} ⌋}2k − \{ \begin{matrix}⌊ \frac{n+1}{2} ⌋, & if n odd \\ 0, & if n even \end{matrix} = ∑_{k=1}^{⌈ \frac{n+1}{2} ⌉}(2k−1) − \{ \begin{matrix}0, & if n odd \\ ⌈ \frac{n+1}{2} ⌉, & if n even \end{matrix} .

7. 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}} ∑_{k=1}^{∞} x^{2k−1}. This is the generating function of the sequence.

8. recurrence equations. The n^{th} term of the sequence ⟨a(k)⟩_{k=1}^{∞} which is the solution of any of the following recurrence equations for all positive integers k :

(a) a(k + 1) + a(k) = \binom{k+2}{2} = \frac{(k+2)(k+1)}{2} with a(1) = 1.

(b) a(k + 2) = a(k) + k + 2 with a(1) = 1, a(2) = 2.

(c) a(k + 3) = a(k + 2) + a(k + 1) − a(k) + 1 with a(1) = 1, a(2) = 2, a(3) = 4.

(d) a(k + 4) = 2a(k + 3) − 2a(k + 1) + a(k) with a(1) = 1, a(2) = 2, a(3) = 4,

a(4) = 6.

(e) (k + 1)a(k + 2) = 2a(k + 1) + (k + 3)a(k) with a(1) = 1, a(2) = 2.

(f) (k + 2)a(k + 3) = (k + 3)a(k + 2) + (k + 2)a(k + 1) − (k + 3)a(k) with a(1) = 1, a(2) = 2, a(3) = 4.

9. difference equations. The n^{th} term of the sequence ⟨a(k)⟩_{k=1}^{∞} which is the solution of any of the following difference equations for all positive integers k, where △a(k) = a(k + 1) − a(k) and △^{2}a(k) = △a(k + 1) − △a(k).

(a) △a(k) = 1, 2, 2, 3, 3, 4, 4, 5, 5, …, ⌈\frac{k+1}{2}⌉, … and with a(1) = 1. This difference sequence is like the sequence A004526 of OEIS [31].

(b) △^{2}a(k) = \{ \begin{matrix}1, & if k odd \\ 0, & if k even \end{matrix} with a(1) = △a(1) = 1.

(c) △a(k + 1) + △a(k) = k + 2 with a(1) = △a(1) = 1.

(d) △a(k + 2) = △a(k) + 1 with a(1) = △a(1) = 1, △a(2) = 2.

(e) △^{2}a(k + 1) + △^{2}a(k) = 1 with a(1) = △a(1) = △^{2}a(1) = 1.

(f) △^{3}a(k) + 2△^{2}a(k) = 1 with a(1) = △a(1) = △^{2}a(1) = 1.

10. differential equations.

(a) The coefficient of x^{n−1} in the power series expansion of the solution F (x) of the differential equation: (1 − x^{2})\frac{dF}{dx} (x) = 2(1 + 2x)F (x) with F (0) = 1.

The coefficient of x^{n} in the power series expansion of the solution F (x) of any of the following differential equations:

(b) (1 − x^{2})\frac{dF}{dx} (x) = (4 + 3x − 2x^{2} + x^{3})F (x) + 1 with F (0) = 0.

(c) (1 − x^{2})\frac{d^{2}F}{dx^{2}} (x) = (4 + 5x − 2x^{2} + x^{3})\frac{dF}{dx} (x) + (3 − 4x + 3x^{2})F (x) with F (0) = 0,

\frac{dF}{dx} (0) = 1.

The coefficient of x^{n+1} in the power series expansion of the solution F (x) of any of the following differential equations:

(d) (1 − x^{2})\frac{dF}{dx} (x) = (6 + 2x − 4x^{2} + 2x^{3})F (x) + 2x with F (0) = 0.

(e) x(1 − x^{2})\frac{d^{2}F}{dx^{2}} (x) = (1 + 6x + 3x^{2} − 4x^{3} + 2x^{4})\frac{dF}{dx} (x) + (−6 − 4x^{2} + 4x^{3})F (x)

with F (0) = 0 and \frac{d^{2}F}{d^{2}x} (0) = 2. (or \frac{dF}{dx} (−2) = \frac{−4}{27}, \frac{dF}{dx} (2) = \frac{28}{9})

11. Max_{k∈{1,...,n}} k · (n − k + 1).

12. Max_{𝔄∈Part(1..n)}|𝔄| · Max_{A∈𝔄}|A| where Part(1..n) is the collection of set partitions of the set {1, …, n}, |𝔄| is the number of blocks, and Max_{A∈𝔄}|A| is the size of the largest block of partition 𝔄.

13. Max_{α∈perm(n)} i(α)·d(α) where perm(n) is the set of permutations of {1, …, n}, i(α) is the length of the longest increasing subsequence and d(α) the longest decreasing subsequence of permutation α. See [30].

14. Max_{p∈S(n)} max(p) · len(p) 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 len(p) is the number of parts of p. See chapter 6 of [29].

15. Max_{P ∈ppart(n)} #rows(P) · #cols(P) where ppart(n) is the set of plane partitions or Young tableaux of n. See [8, p.217], [35, p.81], [17] and [30].

16. Max_{G∈graph(n)} χ(G) · χ(\overline{G}) where graph(n) is the set of simple graphs on n vertices, χ(G)

is the chromatic number and \overline{G} the complement of graph G.

17. Max_{G∈graph(n)} ω(G)·\overline{ω}(G) where graph(n) is the set of simple graphs on n vertices, \overline{ω}(G) =

ω(\overline{G}) is the independence number and ω(G) is the clique number of graph G.

18. Max_{G∈graph(n)}(1 + Δ(G)) · γ(G) where Δ(G) is the size of the largest degree of the vertices and γ(G) is the domination number of the simple graph G. (γ is the smallest size set of vertices of G, such that every vertex is in the set or adjacent to it.)

19. Max_{u∈Ω_{n}} f(u)·g(u) where ⟨Ω_{k}⟩_{k=1}^{∞} is a sequence of finite sets and for each positive integer k, there are functions f and g from Ω_{k} to {1, …, k} such that for all u ∈ Ω_{k}, f(u) + g(u) ≤ k+1, and there exist w ∈ Ω_{k}, such that f(w)+g(w) = k+1 and |f(w)−g(w)| ≤ 1. Note that this is a generalization of the above items 11 to 18, which are special cases; see section 2 below.

20. The number of graphs with multiple edges and loops on two vertices and n − 1 edges.

21. The number of connected bipartite graphs with part sizes n and 2. See Gordon Royle,

/www.cs.uwa.edu.au/~gordon/

22. The number of (noncongruent) integer-sided triangles with largest side n. See [22, 23] 23. 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.

24. The n^{th} term of the row 3 (and column 3) of Losanitsch’s array.

Losanitsch’s array, values of L(r, c) from [32]

r\ c 1 2 3 4 5 6 7 8 9 10 11  seq. no. in OEIS [31]
1 1 1 1 1 1 1 1 1 1  1  1 … A000012
2 1 1 2 2 3 3 4 4 5  5  6 … A004526
3 1 2 4 6 9 12 16 20 25 30 36 … A002620
4 1 2 6 10 19 28 44 60 85 110 146 … A005993
5 1 3 9 19 38 66 110 170 255 365 511 … A005994
6 1 3 12 28 66 126 236 396 651 1001 1512 … A005995

L(r, c) = L(r, c − 1) + L(r − 1, c)−\{ \begin{matrix}\binom{(r+c)/2}{c/2}, & if both r, c even \\ 0, & otherwise \end{matrix} and L(1, c) = L(r, 1) = 1 for all r, c positive integers.

25. 1 + |A_{n}| where A_{n} = { {i, j} ⊆ {1, …, n} | i ≠ j and n ≤ i + j } this is one more than the sum for n ≤ m ≤ 2n − 1 of the number of partitions of m with two distinct parts from {1, …, n}.

26. The sum of the n^{th} row of the following array.

n\ k 1 2 3 4 5 6 7 8 9
1 1
2 1 1
3 1 2 1
4 1 2 2 1
5 1 2 3 2 1
6 1 2 3 3 2 1
7 1 2 3 4 3 2 1
8 1 2 3 4 4 3 2 1
9 1 2 3 4 5 4 3 2 1

27. One more than the sum for n ≤ m ≤ 2n − 1 of the number of partitions of m with two

parts minus n − 1 choose 2 = 1 + ∑_{m=n}^{2n−1} ⌊\frac{m − 1}{2}⌋ − \binom{n − 1}{2} = 1 + ∑_{m=n}^{2n−1} ⌊\frac{m}{2}⌋ −

⌊\frac{n}{2}⌋ − \binom{n − 1}{2},

= 1 + ∑_{i=0}^{n−1} ⌊\frac{n − 1 + i}{2}⌋ − \binom{n − 1}{2} = 1 + ∑_{i=0}^{n−1} ⌈\frac{n − 2 + i}{2}⌉ − \binom{n − 1}{2},

= \begin{cases}f_{f}(n) + n, & if n odd \\ f_{f}(n), & if n even \end{cases} where f_{f}(n) = (n + ⌊n/2⌋)⌊n/2⌋ − \binom{n}{2},

= \begin{cases}f_{c}(n) − n, & if n odd \\ f_{c}(n), & if n even \end{cases} where f_{c}(n) = (n + ⌈n/2⌉)⌈n/2⌉ − \binom{n}{2}.

28. Turán’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 = \binom{n+1}{2} − \binom{⌊ \frac{n+1}{2} ⌋}{2} − \binom{⌊ \frac{n+2}{2} ⌋}{2} = \binom{n+1}{2} − \binom{⌈ \frac{n}{2} ⌉}{2} − \binom{⌈ \frac{n+1}{2} ⌉}{2} = \binom{⌊ \frac{n+2}{2} ⌋}{2} + \binom{⌊ \frac{n+3}{2} ⌋}{2} = \binom{⌈ \frac{n+1}{2} ⌉}{2} + \binom{⌈ \frac{n+2}{2} ⌉}{2} = \binom{⌊ \frac{n+2}{2} ⌋}{2} + \binom{⌈ \frac{n+2}{2} ⌉}{2}.

29. Max_{u∈[0,1]^{n+1}} ∑_{1≤i<j≤n+1}|u_{i}−u_{j}| 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 [4].

Other expressions. In OEIS [31] for this sequence, there is a reference to probability [16], and in [14] the Encyclopedia of Combinatorial Structures 105 there is a combinatorial structure for this sequence. In [9] this sequence counts orbits of permutation groups. The inverse image of diagonals (±i, ±i) under the spiral function of [20, Exercise 40, p.99] is sequence A002620. Comment. For all of the expressions in theorem 1.1, it could be argued (or defined) that they are zero for n = 0. In the OEIS [31] this sequence is preceded by two zeros. One reason for this may be that the lower triangular matrix given by the method of [18] for A002620 has a simpler form when this input sequence has at least two leading zeros. See [27] for more recent work on this method.

2 Antagonistic functions

Two integer functions which satisfy the conditions of item 19 of the main theorem, are antagonistic in the sense that, in general, they are not both too large at the same time.

Definition 2.1 Let n be a positive integer, Ω a finite set, then f and g are (upper) antagonistic on Ω of order n if

1. f and g are functions from Ω to {1, …, n},

2. for any u ∈ Ω, f(u) + g(u) ≤ n + 1,

3. Max_{u∈Ω} f(u) · g(u) = ⌊(\frac{n+1}{2})^{2}⌋.

This is related to the upper bound of the Nordhaus-Gaddum inequality [26]; see [15]. Examples of antagonistic functions are in items 11 to 18 of the main theorem. In this paper, only upper antagonistic functions are considered [34].

2.1 Examples which are not antagonistic

A. Let Ω_{n} = graph(n), the simple graphs on n vertices. Let f(G) = \overline{ω}(G), the independence number of graph G, and g(G) = 1+⌊\frac{1}{n} ∑_{v=1}^{n} deg(v)⌋. If n = 6, f and g are not antagonistic, because the graph G on 6 vertices which is the complement of K_{4}, has \overline{ω}(G) = 4 and 1 + ⌊\frac{1}{6} ∑_{v=1}^{6} deg(v)⌋ = 1 + ⌊\frac{18}{6}⌋ = 4. Thus f(G) + g(G) > n + 1 and the definition fails.

B. Let Ω_{n} = \{1, …, n\}, f(i) = i and g(i) = ⌈\frac{n}{i}⌉ for 1 ≤ i ≤ n. If 5 ≤ n, f and g are not antagonistic, since Max_{i∈\{1..n\}} f(i)·g(i) < ⌊(\frac{n+1}{2})^{2}⌋ and the definition fails.

2.2 Properties of antagonistic functions

Proposition 2.2 Let n be a positive integer, Ω a finite set, f and g functions from Ω to {1, …, n}, such that for every u ∈ Ω, f(u) + g(u) ≤ n + 1, then f and g are antagonistic of order n if and only if there is a w ∈ Ω such that ⌊(\frac{n+1}{2})^{2}⌋ ≤ f(w) · g(w).

Proof There exists w ∈ Ω such that f(w) · g(w) ≥ ⌊(\frac{n+1}{2})^{2}⌋ is the same as Max_{u∈Ω} f(u)·g(u) ≥

⌊(\frac{n+1}{2})^{2}⌋ and the opposite inequality follows from the AM-GM inequality ab ≤ ⌊(\frac{a+b}{2})^{2}⌋ and the assumption f(u) + g(u) ≤ n + 1. □

Lemma 2.3 Let i and j be positive integers, then |i − j| ≤ 1 ⟺ ⌊\frac{(i+j)^{2}}{4} ⌋ ≤ i·j

Proof. Let i and j be positive integers, |i − j| ≤ 1 ⟺ (i − j)^{2} ≤ 1 ⟺ (i − j)^{2} < 4 ⟺ (i + j)^{2} < 4(ij + 1) ⟺ \frac{(i+j)^{2}}{4} − 1 < ij ⟺ ⌊\frac{(i+j)^{2}}{4} ⌋ ≤ ij, for the last implication see [20, p.69]. □

Fact 2.4 The function m ↦ ⌊\frac{m^{2}}{4} ⌋ on the positive integers is

1. strictly increasing and thus is one-to-one, and

2. ⌊\frac{m^{2}}{4} ⌋ ≤ ⌊\frac{n^{2}}{4} ⌋ ⟹ m ≤ n for all m and n positive integers.

Lemma 2.5 Let n be a positive integer, Ω a finite set, f and g functions from Ω to {1, …, n}, such that for every u ∈ Ω, f(u) + g(u) ≤ n + 1, then for every w ∈ Ω,

⌊\frac{(n+1)^{2}}{4} ⌋ ≤ f(w) · g(w) if and only if f(w) + g(w) = n + 1 and |f(w) − g(w)| ≤ 1.

Proof. (⇒ left part) By AM-GM, ⌊\frac{(n+1)^{2}}{4} ⌋ ≤ f(w) · g(w) ⇒ ⌊\frac{(n+1)^{2}}{4} ⌋ ≤ ⌊\frac{(f(w)+g(w))^{2}}{4} ⌋ ⇒ n + 1 ≤ f(w) + g(w) the last by fact 2.4, and since f(w) + g(w) ≤ n + 1 by assumption, we get f(w) + g(w) = n + 1.

(right part) f(w)+g(w) ≤ n+1 and ⌊\frac{(n+1)^{2}}{4} ⌋ ≤ f(w)·g(w) ⇒ ⌊\frac{(f(w)+g(w))^{2}}{4} ⌋ ≤ f(w)·g(w) ⇒ |f(w) − g(w)| ≤ 1 by lemma 2.3. □ Proof. (⇐) (this is used several times in the following proof of the main theorem) By lemma 2.3 |f(w) − g(w)| ≤ 1 ⇒ ⌊\frac{(f(w)+g(w))^{2}}{4} ⌋ ≤ f(w) · g(w), but since f(w) + g(w) = n + 1 we get ⌊\frac{(n+1)^{2}}{4} ⌋ ≤ f(w) · g(w). □

In summary we have the following.

Proposition 2.6 (Characterization of antagonistic functions) Let n be a positive integer, Ω a finite set, and f and g functions from Ω to {1, …, n} such that f(u)+g(u) ≤ n+1 for all u ∈ Ω, then f and g are antagonistic of order n on Ω if and only if there exists w ∈ Ω such that f(w) + g(w) = n + 1 and |f(w) − g(w)| ≤ 1.

Note that, |f(w) − g(w)| ≤ 1 can be replaced by |f(w) − g(w)| = \{ \begin{matrix}0, & if n odd \\ 1, & if n even \end{matrix} and those w ∈ Ω for which the maximum is achieved are exactly those which satisfy the right hand conditions.

Fact 2.7 Let A and B be finite sets, f a function from A onto B, G a mapping from B to ℝ and for all a ∈ A, let F (a) = G(f(a)), then Max_{a∈A} F (a) = Max_{b∈B} G(b) and Min_{a∈A} F (a) =

Min_{b∈B} G(b).

In items 13 to 17, of the theorem Ω is a complemented lattice. It would be interesting to study those functions f from Ω to \{1, …, 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 Γ, irredundance IR [12], and CO-irredundance COIR [11] numbers)

We could count those elements which achieve the maximum in items 11 to 18 of the main theorem. Note, we must define when two elements are different.

• For items 14, the count is 1, 2, 1, 2, 1, 2, 1, 2, 1 ⋯ = \{ \begin{matrix}1, & if n odd \\ 2, & if n even \end{matrix} which is sequence A000034.

• For items 11, the count is 1, 2, 2, 6, 8, …

• For item 16, the count is 1, 2, 2, 6, 8, …

• For item 17, the count is 1, 2, 2, 6, 7, …

• For item 18, the count is 1, 2, 2, 5, 4, …

3 Proof of the theorem

Most of the expressions involving floors and ceilings in the theorem may be shown to be equal to item 2 by setting n = 2k and n = 2k − 1 and manipulating the resulting algebraic expression. Such examples are items 3, 4, 5, 6, 27, and 28. This is how many of these expressions were found.

• (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.

• (2) use \{ \begin{matrix}0, & if n odd \\ 1, & if n even \end{matrix} = \frac{1−(−1)^{n}}{2} for the last equality.

• (2 = 3) If n is odd, \frac{(n+1)^{2}}{4} = ⌊\frac{(n+1)^{2}}{4} ⌋ 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 = ⌊k^{2} + k + \frac{1}{4}⌋ = ⌊\frac{(2k+1)^{2}}{4} ⌋ = ⌊\frac{(n+1)^{2}}{4} ⌋.

• (2 = 4) if n even (n = 2k), then ⌊\frac{n+1}{2}⌋ · ⌈\frac{n+1}{2}⌉ = ⌊k + \frac{1}{2}⌋ · ⌈k + \frac{1}{2}⌉ = k(k + 1) and if n is odd (= 2k − 1), then ⌊\frac{n+1}{2}⌋ · ⌈\frac{n+1}{2}⌉ = k^{2}.

• (4) The expressions in this item are shown to equal by using ⌈\frac{m}{2}⌉ = ⌊\frac{m+1}{2}⌋, ⌈\frac{m}{2}⌉ − ⌊\frac{m}{2}⌋ = \{ \begin{matrix}1, & if m odd \\ 0, & if m even \end{matrix} and ⌈\frac{m+1}{2}⌉ = ⌈\frac{m}{2}⌉+ \{ \begin{matrix}0, & if m odd \\ 1, & if m even \end{matrix} from chapter 3 of [20].

• (4 = 5) item 5 = ∑_{k=1}^{n}⌈\frac{k}{2}⌉ = 2 (∑_{k=1}^{⌈n/2⌉} k) − \{ \begin{matrix}⌈n/2⌉, & if n odd \\ 0, & if n even \end{matrix}

= ⌈\frac{n}{2}⌉ (⌈\frac{n}{2}⌉ + 1) − \{ \begin{matrix}⌈n/2⌉, & if n odd \\ 0, & if n even \end{matrix} = ⌈\frac{n}{2}⌉(⌈\frac{n}{2}⌉+ \{ \begin{matrix}0, & if n odd \\ 1, & if n even \end{matrix} ) = item 4.

• (4 = 6) Use m = ⌊\frac{m}{2}⌋ + ⌈\frac{m}{2}⌉.

• (6) In the last line:

For n = 2m, ∑_{k=⌊ \frac{n+2}{2} ⌋}^{n} 2k − n = ∑_{k=m+1}^{2m} 2k − 2m = ∑_{i=1}^{m} 2i = ∑_{k=m+1}^{2m} 2k − 2m = ∑_{k=⌈ \frac{n+1}{2} ⌉}^{n} 2k − n.

For n = 2m − 1, ∑_{k=⌊ \frac{n+2}{2} ⌋}^{n} 2k−n = ∑_{k=m}^{2m−1} 2k−2m+1 = ∑_{i=1}^{m} 2i−1 = ∑_{k=m}^{2m−1} 2k−2m+1 = ∑_{k=⌈ \frac{n+1}{2} ⌉}^{n} 2k−n.

• (7 = (8a, …, 8d))

Use rsolve of Maple V Release 5 (or Maple 7) with generating function option as follows.

> 8(a) rsolve({f(n+1)+f(n)=(n+2)*(n+1)/2, f(1)=1}, f,'genfunc'(x)):factor(%);

−\frac{x}{(−1 + x)^{3} (1 + x)}

> 8(b) rsolve({f(n+2) = f(n)+n+2, f(1)=1,f(2)=2}, f,'genfunc'(x)):factor(%);

−\frac{x}{(−1 + x)^{3} (1 + x)}

> 8(c) 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(%);

−\frac{x}{(−1 + x)^{3} (1 + x)}

> 8(d) 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(%);

−\frac{x}{(−1 + x)^{3} (1 + x)}

The generating function option of rsolve is only valid for constant coefficients equations.

• (2 = 8) Use rsolve of Maple V Release 5 (or Maple 7) as follows.

> 8(a) rsolve({f(n+1)+f(n)=(n+2)*(n+1)/2, f(1)=1}, f):simplify(%);

\frac{1}{8} (−1)^{(n+1)} + \frac{1}{4} n^{2} + \frac{1}{2} n + \frac{1}{8}

> 8(b) rsolve({f(n+2) = f(n)+n+2, f(1)=1,f(2)=2}, f):simplify(%);

\frac{1}{8} (−1)^{(n+1)} + \frac{1}{4} n^{2} + \frac{1}{2} n + \frac{1}{8}

>  8(c)  rsolve({f(n+3) = f(n+2)+f(n+1)-f(n)+1, f(1)=1,f(2)=2,f(3)=4}, f):
simplify(%);

\frac{1}{8} (−1)^{(n+1)} + \frac{1}{2} n + \frac{1}{8} + \frac{1}{4} n^{2}

> 8(d)

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(%);

\frac{1}{8} (−1)^{(n+1)} + \frac{1}{4} n^{2} + \frac{1}{2} n + \frac{1}{8}

>  8(e)  rsolve({(n+1)*f(n+2) = 2*f(n+1)+(n+3)*f(n), f(1)=1,f(0)=0},
f):simplify(%);

\frac{1}{8} (−1)^{(n+1)} + \frac{1}{4} n^{2} + \frac{1}{2} n + \frac{1}{8}

> 8(f) rsolve({(n+2)*f(n+3)=
       (n+3)*f(n+2)+(n+2)*f(n+1)-(n+3)*f(n), f(2)=2,f(1) = 1, f(0) = 0},f);

−\frac{1}{8} (−1)^{n} + \frac{1}{8} + \frac{1}{2} n + \frac{1}{4} n^{2}

• (8) Using rectohomrec from the Maple V Release 5 share package gfun, 8a gives 8e, 8b gives 8f and 8c gives 8d.

• (5 = 9a) sum of difference, see [24].

• (7 = 9a) the generating function of the sequence in item 9a is \frac{x}{(1−x)(1−x^{2})} =

\frac{1}{(1−x)} ∑_{k=1}^{∞} x^{2k−1} = ∑_{k=1}^{∞}⌈\frac{k+1}{2}⌉x^{k}.

• (8 = 9) Easy to show 8b=9c and 8c=9d.

• (9) These are shown to be equal by simple manipulations of differences; see [24].

• (7 = 10) Show (using Maple) that the generating function satisfies the differential equation.

• (7 = 10) Use dsolve of Maple V Release 5 (or Maple 7) as follows.

 > 10(a) ode1:=(1-x^{2})*diff(F(x),x)=2*(1+2*x)*F(x);

ode1 := (1 − x^{2}) (\frac{∂}{∂x} F(x)) = 2 (1 + 2 x) F(x)

 > dsolve(\{ode1,F(0)=1\},F(x));  F(x) = −\frac{1}{(x + 1) (x − 1)^{3}}
 > 10(b) ode2:=(1-x^{2})*diff(F(x),x)=1+(4+3*x-2*x^{2}+x^{3})*F(x);

ode2 := (1 − x^{2}) (\frac{∂}{∂x} F(x)) = 1 + (4 + 3 x − 2 x^{2} + x^{3}) F(x)

 > simplify(dsolve(\{ode2,F(0)=0\},F(x)));  F(x) = −\frac{x}{(x + 1) (x − 1)^{3}}
 > 10(c) 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);

ode3 := (1−x^{2}) (\frac{∂^{2}}{∂x^{2}} F(x)) = (4+5 x−2 x^{2} +x^{3}) (\frac{∂}{∂x} F(x))+(3−4 x+3 x^{2}) F(x)

 > dsolve(\{ode3,F(0)=0,D(F)(0)=1\},F(x));  F(x) = −\frac{x}{(x + 1) (x − 1)^{3}}
 > 10(d) ode4:=(1-x^{2})*diff(F(x),x)=2x+(6+2*x-4*x^{2}+2*x^{3})*F(x);

ode4 := (1 − x^{2}) (\frac{∂^{2}}{∂x^{2}} F(x)) = 2x + (6 + 2 x − 4 x^{2} + 2 x^{3}) F(x)

 > dsolve(\{ode4,F(0)=0\},F(x));  F(x) = −\frac{x^{2}}{(x + 1) (x − 1)^{3}}
 > 10(e) 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);

ode5 := x(1−x^{2}) (\frac{∂^{2}}{∂x^{2}} F(x)) = (1+6 x+3 x^{2}−4 x^{3}+2 x^{4})(\frac{∂}{∂x} F(x))+(−6−4x^{2}+4x^{3}) F(x)

 > dsolve(\{ode5,F(0)=0,D(D(F))(0)=2\},F(x));  F(x) = −\frac{x^{2}}{(x + 1) (x − 1)^{3}}

• (1 = 10) listtodiffeq from Maple V R5 share package gfun was used to get 10a, 10b and 10d.

• (10) Using diffeqtohomdiffeq from Maple V Release 5 share package gfun, 10b gives 10c and 10d gives 10e.

• (4 = 11) A quadratic f(x) = ax^{2} + bx + c with integer coefficients and a negative has its maximum value at x = ⌊\frac{−b}{2a}⌋ and x = ⌈\frac{−b}{2a}⌉. So item 11 = Max_{k∈\{1..n\}} −k^{2} + (n + 1)k =

(n + 1 − ⌊\frac{n+1}{2}⌋)⌊\frac{n+1}{2}⌋ = ⌈\frac{n+1}{2}⌉⌊\frac{n+1}{2}⌋ = item 4, since m − ⌊\frac{m}{2}⌋ = ⌊\frac{m}{2}⌋+ \{ \begin{matrix}1, & if n odd \\ 0, & if n even \end{matrix} = ⌈\frac{m}{2}⌉.

Similarly for x = ⌈\frac{n+1}{2}⌉.

• (11 = 12) Since item 12 = Max_{𝔄∈Part(1..n)}|𝔄| · Max_{A∈𝔄}|A| = Max_{m∈{1..n}} m Max_{𝔄∈Part_{m}(1..n)} Max_{A∈𝔄}|A| = Max_{m∈{1..n}} m(n − m + 1) = item 11, where Part_{m}(1..n) are the set partitions of {1..n} with m blocks.

• (13 = 15) The Robinson-Schensted-Knuth algorithm [8, p.218], [35, p.94] gives a bijection between permutations of {1, …, 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. The RSK algorithm as used in C. C. Rousseau’s Partitions and q-series in combinatorics course at the University of Memphis in spring 2000.

Algorithm 3.1: RSK(n, ⟨a_{i}⟩_{i=1}^{n}) INPUT: n, a positive integer INPUT: (a_{i})_{i=1}^{n}, a permutation of {1..n} OUTPUT: (P, Q), a pair of standard Young tableaux of order n

and both of the same shape

P [ ,] := ∅, Q[ ,] := ∅ comment: these are empty 2D arrays for p := 1 to n

do \begin{cases}b := a_{p} \\ r := 1 \\ while & row r is not empty and b is not greater than the last cell in row r of P \\ do & \begin{cases}c := Min\{j | b ≤ P (r, j)\} \\ swap(b, P (r, c)) \\ r := r + 1 \end{cases} \\ comment: & add a new cell at end of row r of P and Q \\ c := 1 + the number of cells in row r \\ P (r, c) := b \\ Q(r, c) := p \end{cases}

return (P, Q)

For a partition of n, a, the #rows(shapeRSK(n, a) = the size of longest increasing subsequence of a and #cols(shapeRSK(n, a) = the size of longest decreasing subsequence of a.

The inverse of the RSK algorithm.

Algorithm 3.2: iRSK(n, ⟨P, Q⟩) INPUT: n, a positive integer INPUT: (P, Q), a pair of standard Young tableaux of order n

and both of the same shape OUTPUT: (a_{i})_{i=1}^{n}, a permutation of {1..n}

for p := n downto 1

do \begin{cases}(r, c) := find the row and column of the value of p in array Q \\ b := P (r, c) \\ delete cell (r, c) of P \\ while r ≠ 1 do \begin{cases}r := r − 1 \\ comment: & in row r of P put b in the correct spot \\ and pass back the bumped value as b \\ c := Max\{j | P (r, j) < b\} \\ swap(b, P (r, c)) \end{cases} \\ a_{p} := b \end{cases}

return ((a_{i})_{i=1}^{n})

For P, Q StdYoungTab of n with the same shape, then iRSK(n, (P, Q))^{−1} = iRSK(n, (Q, P))

• (12 = 14) Use fact 2.7.

• (14) use fact 2.7 to show that compositions and partitions of n give the same result.

• (4 = 14) The partitions (⌊\frac{n+1}{2}⌋, \underbrace{1, …, 1}_{⌈ \frac{n−1}{2} ⌉ 1’s}) and (⌈\frac{n+1}{2}⌉, \underbrace{1, …, 1}_{⌊ \frac{n−1}{2} ⌋ 1’s}) are (the only) partitions of n

which achieve the maximum value since ⌊\frac{n+1}{2}⌋ + ⌈\frac{n−1}{2}⌉ = n and ⌈\frac{n+1}{2}⌉ + ⌊\frac{n−1}{2}⌋ = n and they are equal if n is odd. But for the first partition, max·len = ⌊\frac{n+1}{2}⌋ · (⌈\frac{n−1}{2}⌉ + 1) = item 4, and for the second max·len = ⌈\frac{n+1}{2}⌉ · (⌊\frac{n−1}{2}⌋ + 1) = item 4.

• (14 = 15) Use fact 2.7.

• (4 = 16) It is known that χ(G) + χ(\overline{G}) ≤ n + 1 for any graph G with n vertices [26], [10, p. 232]. Now if G = K_{⌈ \frac{n+1}{2} ⌉} ⊎ (n − ⌈\frac{n+1}{2}⌉)K_{1}, then χ(G) = χ(K_{⌈ \frac{n+1}{2} ⌉}) = ⌈\frac{n+1}{2}⌉ and χ(\overline{G}) = χ(K_{n} − K_{⌈ \frac{n+1}{2} ⌉}) = n + 1 − ⌈\frac{n+1}{2}⌉ = ⌊\frac{n+1}{2}⌋. Now proposition 2.6.

• (3 = 17) Let G = (n − ⌈\frac{n}{2}⌉)·K_{1} ⊎ K_{⌈ \frac{n}{2} ⌉}, then ω(G) = ⌈\frac{n}{2}⌉ and, since n = ⌈\frac{n}{2}⌉ + ⌊\frac{n}{2}⌋, \overline{ω}(G) = ⌊\frac{n}{2}⌋+1, so \overline{ω}(G)−ω(G) = 1−(⌈\frac{n}{2}⌉−⌊\frac{n}{2}⌋) = \{ \begin{matrix}0, & if n odd \\ 1, & if n even \end{matrix} . We also have \overline{ω}(H)+ω(H) ≤ n+1 for every H ∈ graph(n), so use proposition 2.6.

• (4 = 18) It is known that 1 + Δ(G) + γ(\overline{G}) ≤ n + 1 for any graph G with n vertices [5, p. 304]. Let G = ⌈\frac{n−1}{2}⌉·K_{1} ⊎ K_{1,⌊ \frac{n−1}{2} ⌋}, then 1 + Δ(G) = 1 + ⌊\frac{n−1}{2}⌋ = ⌊\frac{n+1}{2}⌋ and γ(G) = 1 + ⌈\frac{n−1}{2}⌉ = ⌈\frac{n+1}{2}⌉. note that |V (G)| = ⌈\frac{n−1}{2}⌉ + ⌊\frac{n−1}{2}⌋ + 1 = n.

• (3 = 19) See proposition 2.6.

• (5 = 20) 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 (= ⌊\frac{m+2}{2}⌋). Of the n − 1 edges if k ∈ \{1, …, n − 1\} are between vertices, there are then ⌊\frac{n−1−k+2}{2}⌋ graphs with the remaining edges. Hence the total number of graphs is ∑_{k=0}^{n−1}⌊\frac{n−1−k+2}{2}⌋ = ∑_{k=0}^{n−1}⌊\frac{k+2}{2}⌋ which is item 5.

• (6 = 22) From the following table of the triangles with largest side n, we see that the total

number of triangles is ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋}(n−2k) which is item 6. n sides of triangle 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

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

• (1 = 22) See [22].

• (9c = 23) Let k = 1 in 23, see [2].

• (9a = 24) 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, … and L(2, 1) = 1, which is item 9a.

• (25 = 26) a_{n,k} = \{ \begin{matrix}1, & if k = 1 \\ |\{U∈A_{n}|min(U)=k−1\}|, & if k ≠ 1 \end{matrix} , where a_{n,k} is the values of the array in item 26, and A_{n} is as in item 25. (this is how the array in item 26 was found)

• (2 = 26) If n is even item 26 = 2 ∑k=1^{\frac{n}{2}} k = \frac{n}{2}(\frac{n}{2} + 1) = item 2. If n is odd item 26

= 2 ∑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 2.

• (2 = 27) Let n = 2k and = 2k − 1. See chapter 6 of [29] for partitions.

• (28) use: if n = 2k then ⌊\frac{n+1}{2}⌋ = ⌈\frac{n}{2}⌉ = k, ⌊\frac{n+2}{2}⌋ = ⌈\frac{n+1}{2}⌉ = k + 1, and ⌊\frac{n+3}{2}⌋ = ⌈\frac{n+2}{2}⌉ = k + 1.

if n = 2k+1 then ⌊\frac{n+1}{2}⌋ = ⌈\frac{n}{2}⌉ = k+1, ⌊\frac{n+2}{2}⌋ = ⌈\frac{n+1}{2}⌉ = k+1, and ⌊\frac{n+3}{2}⌋ = ⌈\frac{n+2}{2}⌉ = k+2.

• (4 = 28) Let s = 3 and m = n + 1 in Turán’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. Proposition 3.1 (Turán[1, 25]) Let 2 ≤ m, s be positive integers, then the following are equal.

1. \binom{m}{2} − ∑_{i=0}^{s−2} \binom{⌊\frac{m+i}{s−1}⌋}{2}, see [6, p.294],[7, p.54]

2. ∑_{0≤i<j<s−1} ⌊\frac{m + i}{s − 1}⌋ · ⌊\frac{m + j}{s − 1} ⌋, see [6, 294],[19, p.1234]

3. \frac{(s−2)(m^{2}−k^{2})}{2(s−1)} + \binom{k}{2} where k = mod (m, s − 1) = m − (s − 1)⌊\frac{m}{s−1}⌋, see [21, p.18] 4. ex(m; K_{s}^{(2)}) := the maximum number of 2-sets (edges) of {1, …, m} which have no s

cliques.

ex(m; K_{s}^{(2)})  sequence
s\m 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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 A002620
4 ↓ 3 5 8 12 16 21 27 33 40 48 56 65 75 A000212
5  ↓ 6 9 13 18 24 30 37 45 54 63 73 84 A033436
6  ↓ 10 14 19 25 32 40 48 57 67 78 90 A033437
7  ↓ 15 20 26 33 41 50 60 70 81 93
8  ↓ 21 27 34 42 51 61 72 84 96
9  ↓ 28 35 43 52 62 73 85 98

The numbers in the diagonal sequence 1, 3, 6, 10, 15, 21, 28, 36, … are the triangle numbers, sequence A000217 = lim_{s→∞} ex(m; K_{s}^{(2)}).

• (6 = 29) See proof in [4, Problem 97]. End of proof of the theorem. [figure]

Redundancy in the above illustrates different methods. Some of these methods may suggest ways to analyze other sequences, see [33, Ch.2].

Using ∑_{k=n}^{2n−1} \{ \begin{matrix}0, & if k odd \\ 1, & if k even \end{matrix} = ⌊\frac{n}{2}⌋, p_{2}(k) = p_{2}^{∗}(k) + \{ \begin{matrix}0, & if k odd \\ 1, & if k even \end{matrix} and 25 and 27 of the theorem we have.

Corollary 3.2 For n a positive integer.

∑_{k=0}^{n−1} (p_{2}^{∗}(n + k) − p_{2}^{∗}(max ≤ n, n + k)) = ∑_{k=0}^{n−1} p_{2}^{∗}(max > n, n + k) = \binom{n − 1}{2}

where p_{2}^{∗}(m) = the number of partitions of m with two distinct parts, and p_{2}^{∗}(max > n, m) = the number of partitions of m with two distinct parts, the largest part greater than n. See [3, Ch.12,13,14],[28],[29, Ch.6] for partitions.

4 Acknowledgements

Thanks to the referee for suggestions, and apologies to the editor for my delay in making the changes.

References

[1] M. Aigner, Turán’s graph theorem, Amer. Math. Monthly, 102 (1995), 808–816. 14

[2] G. L. Alexanderson et al., The William Powell Putnam Mathematical Competition - Problems and Solutions: 1965-1984, Mathematical Association of America,, 1985. (Problem A-1 of 27^{th} Competition) 14

[3] G. E. Andrews, Number Theory, Dover, 1994. Corrected reprint of 1971 edition. 15

[4] E. J. Barbeau, M. S. Klamkin, and W. O. J. Moser, Five Hundred Mathematical Challenges, Mathematical Association of America, 1995. 6, 15

[5] C. Berge, Graphs and Hypergraphs, North Holland, 1973. 13

[6] B. Bollobás, Extremal Graph Theory, Academic Press, 1978. 14

[7] B. Bollobás, Combinatorics, Cambridge University Press, 1986. 14

[8] P. J. Cameron, Combinatorics, Cambridge University Press, 1994. 4, 11

[9] P. J. Cameron, Sequences realized by oligomorphic permutation groups, Article 00.1.5, Vol. 3 J. Integer Seq., 2000, published electronically at http://www.research.att.com/˜ njas/sequences/JIS/VOL3/groups.html. 6

[10] G. Chartrand and L. Lesniak, Graphs & Digraphs, 3ed, Chapman & Hall, 1996. 1, 13

[11] E. J. Cockayne, D. McCrea and C. M. Mynhardt, Nordhaus-Gaddum result for COirredundance in graphs Disc. Math. 211 (2000), 209–215. 8

[12] E. J. Cockayne and C. M. Mynhardt, On the product of upper irredundance numbers of a graph and its complement, Disc. Math. 76 (1989), 117–121. 8

[13] R. Diestel, Graph Theory, Springer, 1997. (Second edition, 2000) Available at Graph Theory,2ed, www.math.uni-hamburg.de/home/diestel/ 1

[14] Encyclopedia of Combinatorial Structures, http://algo.inria.fr/bin/encyclopedia. 6

[15] H. J. Finck, On the chromatic number of a graph and its complement, in P. Erdös and G. Katona, eds., Theory of Graphs, Proceedings of the Colloquium held at Tihany, Hungary, 1966, Academic Press, 1968, pp. 99–113. 6

[16] E. Fix and J. L. Hodges, Jr., Significance probabilities of the Wilcoxon test, Ann. Math. Stat. 26 (1955), 301–312. 6

[17] W. Fulton, Young Tableaux, London Mathematics Society Student Text Vol. 35, Cambridge University Press, 1997. 4

[18] S. Getu, L. W. Shapiro, W.-J. Woan, and L. C. Woodson, How to guess a generating function, SIAM J. Disc. Math. 5 (1992), 497–499. 6

[19] R. L. Graham, M. Grötschel and L. Lovasz, eds., Handbook of Combinatorics, Volume 2, Elsevier Science, 1995. 14

[20] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989. 1, 6, 7, 9

[21] F. Harary, Graph Theory, Addison-Wesley, 1969. 1, 14

[22] T. Jenkyns and E. Muller, Triangular triples from ceilings to floors, Amer. Math. Monthly 107 (2000), 635–639. 4, 14 [23] M. J. Marsden, triangles with integer-valued sides, Amer. Math. Monthly 81 (1974), 373–376.

4

[24] R. E. Mickens, Difference Equations, 2nd edition, Van Nostrand, 1990. 10, 11

[25] T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math. 17 (1965), 533–540. 14

[26] E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly, 63 (1956), 175-177. 6, 13

[27] P. Peart and W.-J. Woan, Generating functions via Hankel and Stieltjes matrices, Article 00.2.1, Vol. 3 J. Integer Seq., 2000, published electronically at http://www.research.att.com/˜ njas/sequences/JIS/VOL3/peart1.html. 6

[28] G. Pólya, On picture-writing, Amer. Math. Monthly, 63 (1956), 689–697. Reprinted in I. Gessel and G.-C. Rota, eds., Classic Papers in Combinatorics, Birkhäuser, 1987, 249–257. 15

[29] J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, 1978. 4, 14, 15

[30] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191. Reprinted in I. Gessel and G.-C. Rota, eds., Classic Papers in Combinatorics, Birkhäuser, 1987, 299–311. 4

[31] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/˜ njas/sequences/, 2000. 2, 3, 5, 6

[32] N. J. A. Sloane, Classic Sequences, published electronically at http://www.research.att.com/˜ njas/sequences/classic.html, 2000. 5

[33] N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995. 15

[34] S. E. Speed, The integer sequence A027434 and lower antagonistic functions, in preparation. 6

[35] D. Stanton and D. White, Constructive Combinatorics, Springer-Verlag, 1986. 4, 11

2000 Mathematics Subject Classification: 05A15, 05A18, 05C35, 05C69, 05E10, 05D05, 06B99. Keywords: Antagonistic functions, graph theory, domination number, MAPLE, Nordhaus-Gaddum inequality, Turán’s number, partitions of integers, Young tableaux, Robinson-Schensted-Knuth algorithm

(Concerned with sequence \underline{A002620}.)

Received January 10, 2001; revised versions received March 19, 2002; February 26, 2003. Published in Journal of Integer Sequences March 2, 2003.