Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.6 
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?
Dehaene shows in his excellent book The Number Sense [Deh97] that children have considerably more builtin 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 
My threeyearold 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 groupingsfive groups of three and three groups of fivecan 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 `rectanglefree', 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 
There are other appealing arrangements of go stones, such as equilateral triangles. The 15 stones can be arranged in a basefive triangle as shown in Figure 2. Unfortunately, each number allows only at most one such triangular arrangement, and most numbers are `trianglefree'. The triangular numbers are given by
1+2+...+n = n(n+1)/2where 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?


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+k1) = k(2a+k1)/2We 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) = (ba)(a+b1)/2The krow 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.cSubstituting 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):
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,
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)Here is a table of L.T.t for 1<=t<=10:
It is not selfevident 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 `trapezoidfree', because they only allow a degenerate trapezoidal arrangement in a single row.
t 1 2 3 4 5 6 7 8 9 10 L.T.t: 1 3 9 15 81 45 729 105 225 405
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].
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:
And a table for L.R.r with 1<=r<=10:
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
Again, but this time more to my surprise, these sequences do not appear in [Slo95].
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 primeTo compute R.n in general, consider the prime factorization of n:
n = 2^{e2} * 3^{e3} * 5^{e5} * ... (3)with 0<=e_{p} for all primes p, and 0<e_{p} for only finitely many. Each divisor d of n is of the form
d = 2^{f2} * 3^{f3} * 5^{f5} * ...where 0<=f_{p}<=e_{p}. Thus, the number D.n of divisors of n in (3) can be computed by
D.n = (e_{2}+1)(e_{3}+1)(e_{5}+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 e_{p} 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=2r1 or D.n=2r, that is,
L.R.r = L.D.(2r1) 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=2^{d1}, 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_{2}+1)(e_{3}+1)(e_{5}+1)... (5)Note that for p<q and e<=f we have
p^{e} q^{f} = p^{e} q^{fe} q^{e} > p^{e} p^{fe} q^{e} = p^{f} q^{e}Thus, when computing L.D.d, we can restrict ourselves to n satisfying
e_{2} >= e_{3} >= e_{5} >= ... (6)Each of thefinitely manyfactorizations 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:
L.D.8=24 is obtained from the factorization 8=4*2.
d: 8 4*2 2*2*2 n: 2^{7} 2^{3}*3^{1} 2^{1}*3^{1}*5^{1} 128 24 30
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+2m1 (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+m1)+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 cb stones. If c<=b, the resulting trapezoid has 2c rows and a shortest row of bc+1 stones. In case b=c1 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'.nwhere 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 = (e_{3}+1)(e_{5}+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 twoThe 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=3^{d1}, 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).
T.n=2 if and only if n is an odd prime times a power of two
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 wellknown 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 
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.
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]:
A slightly different linear program can be derived by rewriting T.n tofunction 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:=sx ; x:=x+1 end else { s=n } begin t:=t+1 ; s:=sx+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))in which S.a.(a+k)=k(2a+k1)/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 (nh) mod i = 0 then t:=t+1 ; i:= i+1 ; h:=h+i end { while } end { function T }