login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

a(n) is the number of ways that n square tiles can be formed into two rectangles, such that those rectangles fit orthogonally into the minimal bounding square that can contain n such tiles, without overlap.
2

%I #18 Jun 24 2021 02:26:54

%S 0,1,1,1,2,2,2,1,1,4,2,4,2,2,1,2,4,4,4,4,3,2,2,1,2,6,5,6,2,7,2,3,2,2,

%T 1,3,6,6,6,5,4,6,4,2,3,2,2,1,3,8,4,10,4,6,3,9,2,4,2,3,2,2,1,4,5,10,6,

%U 6,8,4,4,9,4,2

%N a(n) is the number of ways that n square tiles can be formed into two rectangles, such that those rectangles fit orthogonally into the minimal bounding square that can contain n such tiles, without overlap.

%C Note that rectangles of size 0 are not accepted (i.e., the tiles may not be formed into a single rectangle).

%C Finding a(n) is equivalent to counting the positive integer solutions (x,y,z,w) of n = xy + zw such that:

%C i) x,y,z,w <= ceiling(sqrt(n))

%C ii) min(x,y) + min(w,z) <= ceiling(sqrt(n))

%C iii) x >= y,z,w

%C iv) z >= w

%C v) if x = z then y >= w

%C Note that ceiling(sqrt(n)) is the side length of the minimal bounding square into which n unit square tiles can be orthogonally placed, without overlap.

%C Therefore, i) states that neither rectangle should be longer than the bounding square, while ii) states that the two rectangles must fit side by side within this square.

%C iii)-v) ensure that rectangles are not double counted through permuting the values of the variables.

%H Thomas Oléron Evans, <a href="/A338664/b338664.txt">Table of n, a(n) for n = 1..9999</a>

%e a(18) = 4.

%e 18 unit square tiles fit orthogonally into a square of side length 5 (the minimum) without overlap. There are four possible pairs of rectangles that can be formed with the 18 tiles that can then be fit orthogonally into such a square without overlap:

%e 1) 4 X 3 and 3 X 2

%e 2) 4 X 4 and 2 X 1

%e 3) 5 X 2 and 4 X 2

%e 4) 5 X 3 and 3 X 1

%e Case 1 Case 2 Case 3 Case 4

%e 1 1 1 - - 1 1 1 1 - 1 1 1 1 1 1 1 1 - -

%e 1 1 1 - - 1 1 1 1 - 1 1 1 1 1 1 1 1 - 2

%e 1 1 1 2 2 1 1 1 1 2 - 2 2 2 2 1 1 1 - 2

%e 1 1 1 2 2 1 1 1 1 2 - 2 2 2 2 1 1 1 - 2

%e - - - 2 2 - - - - - - - - - - 1 1 1 - -

%e Note that other pairs of rectangles with total area 18, e.g., 3 X 3 and 3 X 3, or 6 X 2 and 3 X 2 are not counted, since they could not fit together into the minimal (5 X 5) bounding square.

%o (Python)

%o import numpy as np

%o # This sets the number of terms:

%o nits = 20

%o # This list will contain the complete sequence:

%o seq_entries = []

%o # i is the index of the term to be calculated:

%o for i in range(1, nits + 1):

%o # This variable counts the rectangle pairs:

%o count = 0

%o # Calculate the side length of the minimal bounding square:

%o bd_sq_side = np.ceil(np.sqrt(i))

%o # Looking for pairs of rectangles of sizes a x b and c x d (all integers)

%o # such that both can fit orthogonally into the minimal bounding square (integer side length)

%o # WLOG suppose that:

%o # a is the greatest of a, b, c, d...

%o # c >= d

%o # if a = c then b >= d

%o # a rectangle of size 0 X 0 is not acceptable

%o # The longest side length of either rectangle:

%o for a in np.arange(1,bd_sq_side + 1):

%o # The other side length of the same rectangle:

%o for b in np.arange(1,1 + min(a,np.floor(i/a))):

%o # Find the remaining area for the other rectangle:

%o area_1 = a*b

%o rem_area = i - area_1

%o # If there is no remaining area, the first rectangle is not valid:

%o if rem_area == 0:

%o continue

%o # The shorter side of the second rectangle:

%o for d in np.arange(1,1 + min(a,np.floor(np.sqrt(rem_area)))):

%o # The longer side of the second rectangle:

%o c = rem_area / d

%o # Check that the solution is valid:

%o if b + d <= bd_sq_side and c == int(c) and c <= bd_sq_side and c <= a and ((a != c) or (b >= d)):

%o count += 1

%o # Add the entry calculated to the list

%o seq_entries.append(count)

%o for an in seq_entries:

%o print(an)

%Y Cf. A338671, A055507 (where a(n) is the number of ordered ways to express n+1 as a*b+c*d with 1 <= a,b,c,d <= n).

%K nonn

%O 1,5

%A _Thomas Oléron Evans_, Apr 22 2021