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

## Rectangular and Trapezoidal Arrangements

### T. VerhoeffFaculty of Mathematics and Computing ScienceEindhoven University of Technology Den Dolech 2, 5612 AZ  EINDHOVEN, Netherlands E-mail addres: Tom.Verhoeff@acm.org July 1998, revised November 1998

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.

O O O O O
O O O O O
O O O O O
Figure 1: Rectangular arrangement of 15 go stones

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.

O
O O
O O O
O O O O
O O O O O
Figure 2: Triangular arrangement of 15 go stones

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
where n is the number of stones on the triangle's base. Such a number can be split into groups of consecutive sizes starting at size 1. Again, all well known to me.

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?

O O O O
O O O O O
O O O O O O

O O O O O O O
O O O O O O O O
Figure 3: Two trapezoidal arrangements of 15 go stones

## 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
We introduce the notation S.a.b for the sum of the numbers from a to and excluding b:
S.a.b = (SUM i: a<=i<b: i) = (b-a)(a+b-1)/2
The k-row trapezoid whose shortest row has a stones, contains a total of S.a.(a+k) stones. We have the following summation formula for stacking `matched' trapezoids:
S.a.b + S.b.c = S.a.c
Substituting a:=1 and transferring S.a.b to the other side, yields
S.b.c = S.1.c - S.1.b           (1)
Note that S.1.n are the triangular numbers. Therefore, each trapezoidal arrangement corresponds to the difference of two triangular numbers and vice versa.

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)
On account of (1), T.n is also the number of ways to write n as the difference of two triangular numbers. Here is a table of T.n for 1<=n<=20 (in appendix A, we present some programs to compute T.n):
 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
Is there any order to be discovered behind T.n? Let L.T.t be the least number that allows exactly t trapezoidal arrangements, that is,
L.T.t = (MIN n: 1<=n AND T.n=t: n)           (2)
Here is a table of L.T.t for 1<=t<=10:
 t 1 2 3 4 5 6 7 8 9 10 L.T.t: 1 3 9 15 81 45 729 105 225 405
It is not self-evident that L.T.t is well defined for all t. Can all n with given T.n=t be simply characterized, especially for t=1 and t=2? The values n with T.n=1 can be called `trapezoid-free', because they only allow a degenerate trapezoidal arrangement in a single row.

## 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)
Function L defined by (2) can be applied to R as well: L.R.r is the least number that allows exactly r rectangular arrangements. Here is a table for R.n with 1<=n<=20:
 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
And a table for L.R.r with 1<=r<=10:
 r 1 2 3 4 5 6 7 8 9 10 L.R.t: 1 4 12 24 36 60 192 120 180 240
Again, but this time more to my surprise, these sequences do not appear in [Slo95].

As already noted in the introduction, we have:

R.n=1 if and only if n is one or prime
To compute R.n in general, consider the prime factorization of n:
n = 2e2 * 3e3 * 5e5 * ...           (3)
with 0<=ep for all primes p, and 0<ep for only finitely many. Each divisor d of n is of the form
d = 2f2 * 3f3 * 5f5 * ...
where 0<=fp<=ep. Thus, the number D.n of divisors of n in (3) can be computed by
D.n = (e2+1)(e3+1)(e5+1)...           (4)
Note that all divisors come in pairs d and n/d, except that d=n/d when n is a square. Note that n is a square if and only if each ep is even, and hence if and only if D.n is odd. For R.n we are not interested in all divisors, only those at most Sqrt.n; thus, we have
R.n = Ceiling.(D.n / 2)
Hence, to compute L.R.r for a given r, we need to find the least n with D.n=2r-1 or D.n=2r, that is,
L.R.r = L.D.(2r-1) MIN L.D.(2r)
where L.D.d is the least number with exactly d divisors. Sequence L.D is listed in [Slo95], but without additional information.

L.D.d exists for every d, because n=2d-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 = (e2+1)(e3+1)(e5+1)...           (5)
Note that for p<q and e<=f we have
pe qf = pe qf-e qe > pe pf-e qe = pf qe
Thus, when computing L.D.d, we can restrict ourselves to n satisfying
e2 >= e3 >= e5 >= ...           (6)
Each of the---finitely many---factorizations of d satisfying (5) and (6) contributes exactly one candidate n. It is, in general, not the case that the sorted prime factorization of d yields the least n. For example, for d=8 there are three factorizations to consider:
 d: 8 4*2 2*2*2 n: 27 23*31 21*31*51 128 24 30
L.D.8=24 is obtained from the factorization 8=4*2.

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

O O O O
O O O O O
O O O O O O

O O O O O O O
O O O O O O O O
Figure 4: Two right-angled trapezoidal arrangements of 15 go stones

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.

O O b+1 b b c b

O O O b+1 b c c<=b c b+c b-c+1
Figure 5: Cutting a cx (2b+1) rectangle into two stackable trapezoids

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
where D'.n is the number of odd divisors of n. When n is written as in (3), D'.n can be computed by
D'.n = (e3+1)(e5+1)...           (7)
that is, all factors two are ignored. From this we infer:
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
The ascending sequence of all n with T.n=2, that is, all products of an odd prime and a power of two, is not listed in [Slo95]. L.D'.d exists for every d, because n=3d-1, having exactly d odd divisors on account of (7), is an upper bound. L.T.t can be determined in a way analogous to L.D.d. Since factors two in n do not contribute to the number of odd divisors, the least numbers n with exactly a given number of odd divisors have no factors two. This explains why in the table for L.T.n shown earlier, only numbers with factors three and five appear (for a factor seven to appear, n must be larger than listed).

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

Abbr. Nr. in [EIS] Description
S.1.n A000217 Triangular numbers: S.a.b=(SUM i:a<=i<b:i)
T.n A001227 # trapezoidal arrangements of n,
(# a,b:1<=a<b:n=S.a.b), # odd divisors of n
L.T.t A038547+ Least n with T.n=t
R.n A038548+ # rectangular arrangements of n modulo rotation,
(# a,b:1<=a<=b:n=a*b), # divisors <= Sqrt.n of n
L.R.r A038549+ Least n with R.n=r
D.n A000005 # divisors of n
L.D.d A005179 Least n with D.n=d
T.n=1 A000079 Unique trapezoidal arrangements, powers of 2
T.n=2 A038550+ Exactly 2 trapezoidal arrangements,
odd prime times power of 2
Table 1: Sequences in this article with their absolute catalogue number in [
EIS]

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 }
```
A slightly different linear program can be derived by rewriting T.n to
T.n = (# a,k: 1<=a AND 1<=k: n=S.a.(a+k))
in which S.a.(a+k)=k(2a+k-1)/2 is ascending in both a and k. This program can be further refined to an O(Sqrt.n) program to compute T.n:
```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.