Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.6

Abstract: We study rectangular and trapezoidal arrangements of identical objects and answer the following questions. How many such arrangements are possible with n objects? For which numbers k, does there exist a number n of objects that allows exactly k such arrangements? In those cases where it exists, what is the least such number n?

1. Introduction

Dehaene shows in his excellent book The Number Sense [Deh97] that children have considerably more built-in knowledge about numbers than previously assumed. Careful experiments have overthrown several of Piaget's theories about the cognitive development of children. For mathematically inclined parents, this will not come as a surprise, because they are not afraid to challenge their children from an early age on. This article was inspired by such a challenge.

My three-year-old daughter Iris likes to play with the stones of my go set. Counting them is no longer a challenge for her. Nowadays we consider groupings. Having given her 15 stones, I let her make groups of three stones, then ask how many groups there are. At first, the idea of counting the groups, instead of the stones, seems a bit confusing, but Iris soon caught on. Another task is to make three groups of five stones each, then counting the total number. The relationship between these two groupings---five groups of three and three groups of five---can be visualized by arranging the 15 stones in a three by five rectangular array (see Figure 1). In one case, the rows, in the other, the columns can be viewed as groups.

Playing with rectangles leads to multiplication and division. (But I do not bother Iris with those words.) If, as a father, you want to pick a number of go stones that allows your daughter to make many rectangular arrangements, then you need a number with many factors. Prime numbers are a particularly bad choice, because they only allow a degenerate rectangle. Prime numbers, which can be called `rectangle-free', are rather sparse. All this is well known to me.

There are other appealing arrangements of go stones, such as equilateral triangles. The 15 stones can be arranged in a base-five triangle as shown in Figure 2. Unfortunately, each number allows only at most one such triangular arrangement, and most numbers are `triangle-free'. The triangular numbers are given by

1+2+...+n = n(n+1)/2

The next thing that crossed my mind were trapezoidal arrangements. These offer more freedom than triangular numbers. Figure 3 shows two such arrangements with 15 stones. Some of the questions that intrigued me are: How many trapezoidal arrangements are there for a given number of stones? Does there exist, for each number k, a number that allows exactly k such arrangements? What is the smallest such number for a given k?

2. Definitions

A trapezoidal arrangement of n stones, in the sense that we study it here, consists of some rows of stones, where each next row contains one more stone than the row it succeeds. If the first row contains a stones and there are k rows, then the total number of stones is

a + (a+1) + ... + (a+k-1) = k(2a+k-1)/2

S.a.b = (SUM i: a<=i<b: i) = (b-a)(a+b-1)/2

S.a.b + S.b.c = S.a.c

S.b.c = S.1.c - S.1.b           (1)

Let T.n be the number of trapezoidal arrangements of n for 1<=n:

T.n = (# a,b: 1<=a<b: n=S.a.b)

n:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
T.n:	1	1	2	1	2	2	2	1	3	2	2	2	2	2	4	1	2	3	2	2

L.T.t = (MIN n: 1<=n AND T.n=t: n)           (2)

t	1	2	3	4	5	6	7	8	9	10
L.T.t:	1	3	9	15	81	45	729	105	225	405

3. Analysis

From the table above for T.n, one might conjecture that T.n=1 if and only if n is a power of two. The values for L.T.t, given in the table above, have factors three and five only. Is there an explanation? Note that these sequences do not appear in [Slo95].

3.1. Rectangular arrangements

First we consider these questions for rectangular arrangements. Define R.n as the number of rectangular arrangements of n stones, modulo rotation:

R.n = (# a,b: 1<=a<=b: n=ab)

n:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
R.n:	1	1	1	2	1	2	1	2	2	2	1	3	1	2	2	3	1	3	1	3

r	1	2	3	4	5	6	7	8	9	10
L.R.t:	1	4	12	24	36	60	192	120	180	240

As already noted in the introduction, we have:

R.n=1 if and only if n is one or prime

n = 2^e₂ * 3^e₃ * 5^e₅ * ...           (3)

d = 2^f₂ * 3^f₃ * 5^f₅ * ...

D.n = (e₂+1)(e₃+1)(e₅+1)...           (4)

R.n = Ceiling.(D.n / 2)

L.R.r = L.D.(2r-1) MIN L.D.(2r)

L.D.d exists for every d, because n=2^d-1, having exactly d divisors on account of (4), is an upper bound. L.D.d can be computed as follows. On account of (4), for given d, L.D.d is the least n satisfying (3) and

d = (e₂+1)(e₃+1)(e₅+1)...           (5)

p^e q^f = p^e q^f-e q^e > p^e p^f-e q^e = p^f q^e

e₂ >= e₃ >= e₅ >= ...           (6)

d:	8	4*2	2*2*2
n:	27	23*31	21*31*51
	128	24	30

3.2. Trapezoidal arrangements

Every trapezoidal arrangement of n stones can be associated with a rectangular arrangement of n stones. This is easy to see when the rows in the trapezoid are all shifted horizontally, say to the left, to introduce a right angle. Figure 4 shows the two trapezoids of Figure 3 in that format.

In a trapezoid with an odd number of rows, say 2k+1, the triangle sticking out over the bottom k rows can be rotated to fill the `missing' triangle on the top k rows. If the shortest row has a stones, then the resulting rectangle has height 2k+1 and width a+k (the average length of the rows in the trapezoid). In the example above, this transformation applies to the trapezoid on the left, and it yields a 3x5 rectangle (the rotated triangle consists of a single stone).

In a trapezoid with an even number of rows, say 2m, the top m rows can be rotated to the right, matching the the slanted side of the bottom m rows. If the shortest row has a stones, then the resulting rectangle has height m and width 2a+2m-1 (the length of the shortest plus the longest row). In the example above, this transformation applies to the trapezoid on the right, and it yields a 1x15 rectangle.

For both of these transformations, the resulting rectangle has an odd side: 2k+1 in the first case, and 2(a+m-1)+1 in the second. The resulting odd sides are unique, because if they were equal, the other sides would be equal as well, and hence k=a+m+1 and also a+k=m, which is impossible.

Conversely, each rectangular arrangement of n stones with an odd side can be transformed into a trapezoidal arrangement of n stones. Assume the rectangle has odd width 2b+1 and (arbitrary) height c (see Figure 5). The rectangle can be cut diagonally into two trapezoids, one with a shortest row of b+1 stones, one with a longest row of b stones. These two trapezoids have `matching' shortest and longest rows. When stacked together by rotating one on top of the other, the result is a single trapezoid. If b<c, the resulting trapezoids stands `sideways', with 2b+1 (vertical) rows and a shortest row of c-b stones. If c<=b, the resulting trapezoid has 2c rows and a shortest row of b-c+1 stones. In case b=c-1 or b=c, the resulting trapezoid is a triangle.

The transformations from trapezoid to rectangle and back are each other's inverse. Consequently, each odd divisor of n yields a unique trapezoidal arrangement of n stones, and we have

T.n = D'.n

D'.n = (e₃+1)(e₅+1)...           (7)

T.n=1 if and only if n is a power of two
T.n=2 if and only if n is an odd prime times a power of two

Conclusion

For positive integer n, we have defined the numbers R.n and T.n of, respectively, rectangular arrangements (modulo rotation) and trapezoidal arrangements of n identical objects. R.n trivially equals the number of divisors of n that are at most Sqrt.n. It turns out that T.n equals the number of odd divisors of n. Note that T.n also equals the number of ways that n can be written as the difference of two triangular numbers (considering zero a triangular number).

The numbers that allow exactly one trapezoidal arrangement, that is, numbers n with T.n=1, are the powers of two, a well-known sequence. The numbers n with T.n=2 are the products of an odd prime and a power of two. Concerning the difference of triangular numbers, Dickson [Dic66] refers only to [Bar10,Bar11]. However, Barbette's analysis is incorrect, claiming that T.N equals ``1, 2, or more than 2 ... according as N is a power of 2, an odd prime, or a composite number not a power of 2'' [Dic66,p. 373].

For each positive integer k, there exists an n that allows exactly k such arrangements. The least such numbers n form another sequence, which is not monotonic.

None of these sequences, except the powers of two, appears in [Slo95]. Afterwards, we did find T.n in [EIS]. Table 1 gives an overview of all sequences featured in this article. The leftmost column lists our notation, the middle column gives the absolute catalogue number in [EIS], + denoting newly contributed sequences.

A. Programs

Exploiting that S.a.b is descending in a and ascending in b, an O(n) program to determine T.n without multiplicative operators can be derived in the style of [Kal90]:

function T(const n: integer): integer
  { assumes 1<=n ; returns T.n }
; var t, x, y, s: integer
  { let U.x.y = (# a,b: x<=a<b AND y<=b: n=S.a.b),
    then T.n=U.1.2, and U.x.y=0 for x>n }
; begin
    t:=0 ; x:=1 ; y:=2 ; s:=1
    { inv: t+U.x.y=T.n and s=S.a.b }
  ; while x<=n do
      if s<n then begin s:=s+y ; y:=y+1 end
      else if s>n then begin s:=s-x ; x:=x+1 end
      else { s=n } begin t:=t+1 ; s:=s-x+y ; x:=x+1 ; y:=y+1 end
  end { function T }

T.n = (# a,k: 1<=a AND 1<=k: n=S.a.(a+k))

function T(const n: integer): integer
  { assumes 1<=n ; returns T.n }
; var t, i, h: integer
  { let U.i = (# a,k: 1<=a AND 1<=k<i: n=S.a.(a+k)),
    then T.n=U.i if S.1.(i+1)>n }
; begin
    t:=0 ; i:=1 ; h:=1
    { inv: t=U.i and h=S.1.(i+1) }
  ; while h<=n do begin
      if (n-h) mod i = 0 then t:=t+1
    ; i:= i+1 ; h:=h+i
    end { while }
  end { function T }

References

[Bar10]

E. Barbette. Les sommes de p-ièmes puissances distinctes ègales à une p-ième puissance. Paris: Gauthier-Villars, 1910.

[Bar11]

E. Barbette. Sur la décomposition des nombres en facteurs. L'enseignement mathématique, 13 (1911), 261-277.

[Deh97]

S. Dehaene. The Number Sense: How the Mind Creates Mathematics. Oxford University Press, 1997.

[Dic66]

L. E. Dickson. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. Chelsea Publishing Company, 1966 (reprinted).

[EIS]

N. J. A. Sloane. Sloane's On-Line Encyclopedia of Integer Sequences. http://oeis.org.

[Kal90]

A. Kaldewaij. Programming: The Derivation of Algorithms. Prentice-Hall, 1990.

[Slo95]

N. J. A. Sloane and Simon Plouffe. The Encyclopedia of Integer Sequences. Academic Press, 1995.