A113881 -id:A113881 - cp's OEIS frontend

A219924 Number A(n,k) of tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 6, 5, 1, 1, 1, 1, 8, 13, 13, 8, 1, 1, 1, 1, 13, 28, 40, 28, 13, 1, 1, 1, 1, 21, 60, 117, 117, 60, 21, 1, 1, 1, 1, 34, 129, 348, 472, 348, 129, 34, 1, 1, 1, 1, 55, 277, 1029, 1916, 1916, 1029, 277, 55, 1, 1

Offset: 0

Alois P. Heinz, Dec 01 2012

For drawings of A(1,1), A(2,2), ..., A(5,5) see A224239.

			A(3,3) = 6, because there are 6 tilings of a 3 X 3 rectangle using integer-sided squares:
  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
  |     |  |   |_|  |_|   |  |_|_|_|  |_|_|_|  |_|_|_|
  |     |  |___|_|  |_|___|  |_|   |  |   |_|  |_|_|_|
  |_____|  |_|_|_|  |_|_|_|  |_|___|  |___|_|  |_|_|_|
Square array A(n,k) begins:
  1,  1,  1,   1,    1,    1,     1,      1, ...
  1,  1,  1,   1,    1,    1,     1,      1, ...
  1,  1,  2,   3,    5,    8,    13,     21, ...
  1,  1,  3,   6,   13,   28,    60,    129, ...
  1,  1,  5,  13,   40,  117,   348,   1029, ...
  1,  1,  8,  28,  117,  472,  1916,   7765, ...
  1,  1, 13,  60,  348, 1916, 10668,  59257, ...
  1,  1, 21, 129, 1029, 7765, 59257, 450924, ...

Alois P. Heinz, Antidiagonals n = 0..30, flattened
Steve Butler, Jason Ekstrand, Steven Osborne, Counting Tilings by Taking Walks in a Graph, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 169.

Columns (or rows) k=0+1, 2-10 give: A000012, A000045(n+1), A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Main diagonal gives A045846.
Cf. A113881, A226545.

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then 0 elif n=0 or l=[] then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; s:=0;
         for i from k to nops(l) while l[i]=0 do s:=s+
           b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])
         od; s
      fi
    end:
A:= (n, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
seq(seq(A(n, d-n), n=0..d), d=0..14);
# The following is a second version of the program that lists the actual dissections. It produces a list of pairs for each dissection:
b:= proc(n, l, ll) local i, k, s, t;
      if max(l[])>n then 0 elif n=0 or l=[] then lprint(ll); 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l), ll)
    else for k do if l[k]=0 then break fi od; s:=0;
         for i from k to nops(l) while l[i]=0 do s:=s+
           b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)],
            [ll[],[k,1+i-k]])
         od; s
      fi
    end:
A:= (n, k)-> b(k, [0$n], []):
A(5,5);
# In each list [a,b] means put a square with side length b at
leftmost possible position with upper corner in row a.  For example
[[1,3], [4,2], [4,2], [1,2], [3,1], [3,1], [4,1], [5,1]], gives:
 ___.___.
|     |   |
|     |_|
|___|_|_|
|   |   |_|
|_|___|_|

b[n_, l_List] := b[n, l] = Module[{i, k, s, t}, Which[Max[l] > n, 0, n == 0 || l == {}, 1, Min[l] > 0, t = Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1][[1, 1]]; s = 0; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s + b[n, Join[l[[1;; k-1]], Table[1+i-k, {j, k, i}], l[[i+1;; -1]] ] ] ]; s]]; a[n_, k_] := If[n >= k, b[n, Array[0&, k]], b[k, Array[0&, n]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from 1st Maple program *)

A219158 Minimum number of integer-sided squares needed to tile an m X n rectangle.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 2, 4, 1, 5, 4, 4, 5, 1, 6, 3, 2, 3, 5, 1, 7, 5, 5, 5, 5, 5, 1, 8, 4, 5, 2, 5, 4, 7, 1, 9, 6, 3, 6, 6, 3, 6, 7, 1, 10, 5, 6, 4, 2, 4, 6, 5, 6, 1, 11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1, 12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1, 13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1

Offset: 1

David Radcliffe, Nov 12 2012

Triangular array read by rows. m=1,2,...,n; n=1,2,3,...

			T(6,5) = 5 because a 6 X 5 rectangle can be subdivided into two 3 X 3 squares and three 2 X 2 squares.
Triangle begins:
   1;
   2, 1;
   3, 3, 1;
   4, 2, 4, 1;
   5, 4, 4, 5, 1;
   6, 3, 2, 3, 5, 1;
   7, 5, 5, 5, 5, 5, 1;
   8, 4, 5, 2, 5, 4, 7, 1;
   9, 6, 3, 6, 6, 3, 6, 7, 1;
  10, 5, 6, 4, 2, 4, 6, 5, 6, 1;
  11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1;
  12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1;
  13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1;
  14, 7, 7, 5, 7, 5, 2, 5, 7, 5, 7, 5, 7, 1;
  15, 9, 5, 7, 3, 4, 8, 8, 4, 3, 7, 5, 8, 7, 1;

Massimo Ortolano, Table of n, a(n) for n = 1..75466, rows 1..388 of triangle, flattened. Corrected version provided by Qizheng He.
Gary Antonick, Matt Enlow's Rectangle Division Puzzle, The New York Times, June 15, 2015.
Bertram Felgenhauer, Filling rectangles with integer-sided squares
Richard J. Kenyon, Tiling a rectangle with the fewest squares, Combin. Theory Ser. A 76 (1996), no. 2, 272-291.
M. Ortolano, M. Abrate, and L. Callegaro, On the synthesis of Quantum Hall Array Resistance Standards, arXiv preprint arXiv:1311.0756 [physics.ins-det], 2013.
Mark Walters, Rectangles as sums of squares, Discrete Math. 309 (2009), no. 9, 2913-2921.

First 19 terms agree with A049834.
Columns m=1..10 give A001477, A030451, A226576, A226577, A226578, A226579, A226580, A226581, A226582, A226583.
Cf. A113881, A338861.

A226545 Number A(n,k) of squares in all tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 5, 3, 0, 0, 4, 12, 12, 4, 0, 0, 5, 25, 34, 25, 5, 0, 0, 6, 50, 98, 98, 50, 6, 0, 0, 7, 96, 256, 386, 256, 96, 7, 0, 0, 8, 180, 654, 1402, 1402, 654, 180, 8, 0, 0, 9, 331, 1625, 4938, 6940, 4938, 1625, 331, 9, 0

Offset: 0

Alois P. Heinz, Jun 10 2013

			A(3,3) = 1 + 6 + 6 + 6 + 6 + 9 = 34:
  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
  |     |  |   |_|  |_|   |  |_|_|_|  |_|_|_|  |_|_|_|
  |     |  |___|_|  |_|___|  |_|   |  |   |_|  |_|_|_|
  |_____|  |_|_|_|  |_|_|_|  |_|___|  |___|_|  |_|_|_|
Square array A(n,k) begins:
  0, 0,   0,    0,     0,      0,       0,        0, ...
  0, 1,   2,    3,     4,      5,       6,        7, ...
  0, 2,   5,   12,    25,     50,      96,      180, ...
  0, 3,  12,   34,    98,    256,     654,     1625, ...
  0, 4,  25,   98,   386,   1402,    4938,    16936, ...
  0, 5,  50,  256,  1402,   6940,   33502,   157279, ...
  0, 6,  96,  654,  4938,  33502,  221672,  1426734, ...
  0, 7, 180, 1625, 16936, 157279, 1426734, 12582472, ...

Alois P. Heinz, Antidiagonals n = 0..30, flattened

Columns (or rows) k=0-10 give: A000004, A001477, A067331(n-1) for n>0, A226546, A226547, A226548, A226549, A226550, A226551, A226552, A226553.
Main diagonal gives A226554.
Cf. A113881, A219924.

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then [0,0] elif n=0 or l=[] then [1,0]
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; s:=[0$2];
         for i from k to nops(l) while l[i]=0 do s:=s+(h->h+[0, h[1]])
           (b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)]))
         od; s
      fi
    end:
A:= (n, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n]))[2]:
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, l_List] := b[n, l] = Module[{i, k, s, t}, Which[Max[l] > n, {0, 0}, n == 0 || l == {}, {1, 0}, Min[l] > 0, t=Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1][[1, 1]]; s={0, 0}; For[i=k, i <= Length[l] && l[[i]] == 0, i++, s = s + Function[h, h+{0, h[[1]]}][b[n, Join[l[[1 ;; k-1]], Table[1+i-k, {j, k, i}], l[[i+1 ;; -1]]]]] ]; s]]; a[n_, k_] := If[n >= k, b[n, Array[0&, k]], b[k, Array[0&, n]]][[2]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

A285721 Square array read by antidiagonals: A(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k, read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

Original entry on oeis.org

0, 1, 1, 2, 0, 2, 3, 2, 2, 3, 4, 1, 0, 1, 4, 5, 3, 3, 3, 3, 5, 6, 2, 3, 0, 3, 2, 6, 7, 4, 1, 4, 4, 1, 4, 7, 8, 3, 4, 2, 0, 2, 4, 3, 8, 9, 5, 4, 4, 5, 5, 4, 4, 5, 9, 10, 4, 2, 1, 4, 0, 4, 1, 2, 4, 10, 11, 6, 5, 5, 4, 6, 6, 4, 5, 5, 6, 11, 12, 5, 5, 3, 5, 3, 0, 3, 5, 3, 5, 5, 12, 13, 7, 3, 5, 1, 2, 7, 7, 2, 1, 5, 3, 7, 13, 14, 6, 6, 2, 6, 3, 5, 0, 5, 3, 6, 2, 6, 6, 14

Offset: 1

Antti Karttunen, May 03 2017

			The top left 18 X 18 corner of the array:
   0, 1, 2, 3, 4, 5, 6, 7, 8,  9, 10, 11, 12, 13, 14, 15, 16, 17
   1, 0, 2, 1, 3, 2, 4, 3, 5,  4,  6,  5,  7,  6,  8,  7,  9,  8
   2, 2, 0, 3, 3, 1, 4, 4, 2,  5,  5,  3,  6,  6,  4,  7,  7,  5
   3, 1, 3, 0, 4, 2, 4, 1, 5,  3,  5,  2,  6,  4,  6,  3,  7,  5
   4, 3, 3, 4, 0, 5, 4, 4, 5,  1,  6,  5,  5,  6,  2,  7,  6,  6
   5, 2, 1, 2, 5, 0, 6, 3, 2,  3,  6,  1,  7,  4,  3,  4,  7,  2
   6, 4, 4, 4, 4, 6, 0, 7, 5,  5,  5,  5,  7,  1,  8,  6,  6,  6
   7, 3, 4, 1, 4, 3, 7, 0, 8,  4,  5,  2,  5,  4,  8,  1,  9,  5
   8, 5, 2, 5, 5, 2, 5, 8, 0,  9,  6,  3,  6,  6,  3,  6,  9,  1
   9, 4, 5, 3, 1, 3, 5, 4, 9,  0, 10,  5,  6,  4,  2,  4,  6,  5
  10, 6, 5, 5, 6, 6, 5, 5, 6, 10,  0, 11,  7,  6,  6,  7,  7,  6
  11, 5, 3, 2, 5, 1, 5, 2, 3,  5, 11,  0, 12,  6,  4,  3,  6,  2
  12, 7, 6, 6, 5, 7, 7, 5, 6,  6,  7, 12,  0, 13,  8,  7,  7,  6
  13, 6, 6, 4, 6, 4, 1, 4, 6,  4,  6,  6, 13,  0, 14,  7,  7,  5
  14, 8, 4, 6, 2, 3, 8, 8, 3,  2,  6,  4,  8, 14,  0, 15,  9,  5
  15, 7, 7, 3, 7, 4, 6, 1, 6,  4,  7,  3,  7,  7, 15,  0, 16,  8
  16, 9, 7, 7, 6, 7, 6, 9, 9,  6,  7,  6,  7,  7,  9, 16,  0, 17
  17, 8, 5, 5, 6, 2, 6, 5, 1,  5,  6,  2,  6,  5,  5,  8, 17,  0

Antti Karttunen, Table of n, a(n) for n = 1..10585; the first 145 antidiagonals of the array

One less than A072030.
Row 2 & column 2: A028242 (but with starting offset 1).
Row 3 & column 3 (from zero onward) seems to be A226576.
Cf. A003989, A285722, A285732.
Compare also to arrays A049834, A113881, A219158.

def A(n, k): return 0 if n==k else 1 + A(abs(n - k), min(n, k))
for n in range(1, 21): print([A(n - k + 1, k) for k in range(1, n + 1)]) # Indranil Ghosh, May 03 2017

(define (A285721 n) (A285721bi (A002260 n) (A004736 n)))
(define (A285721bi row col) (cond ((= row col) 0) ((> row col) (+ 1 (A285721bi (- row col) col))) (else (+ 1 (A285721bi row (- col row))))))
;; Alternatively:
(define (A285721bi row col) (if (= row col) 0 (+ 1 (A285721bi (abs (- row col)) (min col row)))))
;; Another implementation, as an one-dimensional sequence:
(definec (A285721 n) (if (zero? (A285722 n)) 0 (+ 1 (A285721 (A285722 n)))))

If n = k, then A(n,k) = 0, if n > k, then A(n,k) = 1 + A(n-k,k), otherwise [when n < k], A(n,k) = 1 + A(n,k-n).
Or alternatively, when n <> k, A(n,k) = 1 + A(abs(n-k),min(n,k)).
A(n,k) = A072030(n,k)-1.
As an one-dimensional sequence:
a(n) = 0 if A285722(n) = 0, otherwise a(n) = 1 + a(A285722(n)). [Here A285722 is also used as an one-dimensional sequence.]

A338573 Array read by ascending antidiagonals: T(m,n) (m, n >= 1) is the minimum number of unit resistors needed to produce resistance m/n.

Original entry on oeis.org

1, 2, 2, 3, 1, 3, 4, 3, 3, 4, 5, 2, 1, 2, 5, 6, 4, 4, 4, 4, 6, 7, 3, 4, 1, 4, 3, 7, 8, 5, 2, 5, 5, 2, 5, 8, 9, 4, 5, 3, 1, 3, 5, 4, 9, 10, 6, 5, 5, 5, 5, 5, 5, 6, 10, 11, 5, 3, 2, 5, 1, 5, 2, 3, 5, 11, 12, 7, 6, 6, 5, 5, 5, 5, 6, 6, 7, 12, 13, 6, 6, 4, 6, 4, 1, 4, 6, 4, 6, 6, 13

Offset: 1

Rainer Rosenthal, Nov 05 2020

Karnofsky (2004, p. 5): "[...] if some circuit has resistance m/n then some other circuit likely has n/m. In fact, for 9 or fewer resistors, this symmetry is perfect. However, for 10 resistors the following values are achieved, but not their inverses: 95/106, 101/109, 98/103, 97/98, 103/101, 97/86, 110/91, 103/83, 130/101, 103/80, 115/89, 106/77, 109/77, 98/67, 101/67". That means, that T(m,n) = T(n,m), if T(m,n) <= 9.
This starts with the values of A113881, but the Karnofsky comment says that T(n,m) is not symmetric, whereas the count of tiles in A113881 is. - R. J. Mathar, Nov 06 2020
The first difference where T(m,n) = T(n,m), but differs from the corresponding entry of A113881 occurs for (n,m) = (154,167) and (n,m) = (167,154), both representable by networks with non-planar graphs of 11 resistors, whereas A113881 counts 12 tiles. See Pfoertner link for illustration of more differences. - Hugo Pfoertner, Nov 13 2020

			T(1,2) = 2: at least 2 unit resistors in parallel are needed for resistance 1/2.
T(2,1) = 2: at least 2 unit resistors in series are needed for resistance 2 = 2/1.
T(11,13) = 6: the following "bridge" has resistance Bri(Par(1,1),1,1,1,1) = 11/13 (see A337516 for definitions):
.
                  (+)
                  / \
              ---*   \
             /  /     \
           (1)(1)     (1)
             \ |       |
              \|       |
               *--(1)--*
                \     /
                (1) (1)
                  \ /
                  (-)
.
T(13,11) = 6: Bri(Ser(1,1),1,1,1,1) = 13/11.
T(95,106) = 10, but T(106,95) > 10: Karnofsky (2004, p. 5), see comment.

Technology Review's Puzzle Corner, How many different resistances can be obtained by combining 10 one ohm resistors? Oct 3, 2003.

Joel Karnofsky, Solution of problem from Technology Review's Puzzle Corner Oct 3, 2003, Feb 23 2004.
Hugo Pfoertner, Where A338573 differs from A113881, x,y <= 380.
Index to sequences related to resistances.

Cf. A048211, A113881, A180414, A174283, A337516, A337517.

Non-reciprocal ratios: A338601/A338602 (10 resistors), A338581/A338591 (11 resistors), A338582/A338592 (12 resistors).

A030451 a(2n) = n, a(2n+1) = n+2.

Original entry on oeis.org

0, 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8, 7, 9, 8, 10, 9, 11, 10, 12, 11, 13, 12, 14, 13, 15, 14, 16, 15, 17, 16, 18, 17, 19, 18, 20, 19, 21, 20, 22, 21, 23, 22, 24, 23, 25, 24, 26, 25, 27, 26, 28, 27, 29, 28, 30, 29, 31, 30, 32, 31, 33, 32, 34, 33, 35, 34, 36, 35, 37, 36, 38, 37

Offset: 0

Daniel Smith (2true(AT)gte.net)

Previous name was: Once started, this mixes the natural numbers and the natural numbers shifted by 1.
Smallest number of integer-sided squares needed to tile a 2 X n rectangle. a(5) = 4:
..._...
|   |   |_|
|_|___||. - _Alois P. Heinz, Jun 12 2013

Index entries for two-way infinite sequences.
Index entries for linear recurrences with constant coefficients, signature (1, 1, -1).

Cf. A168361 (first differences), A198442 (partial sums).
Cf. A008619, A110570.
Row m=2 of A113881, A219158.
Essentially the same as A028242.

a:= n-> iquo(n, 2, 'r') +[0, 2][r+1]:
seq(a(n), n=0..80);  # Alois P. Heinz, Jun 12 2013

Riffle[# + 1, #] &@ Range[0, 37] (* or *)
Table[3/4 - (-1)^n 3/4 + n/2, {n, 0, 72}] (* or *)
CoefficientList[Series[(2 x - x^2)/((1 - x) (1 - x^2)), {x, 0, 72}], x] (* Michael De Vlieger, Apr 25 2016 *)

PARI
```
a(n)=n\2+2*(n%2)
```

a(n) = 3/4 -(-1)^n*3/4 +n/2.
G.f.: (2*x-x^2)/((1-x)*(1-x^2)).
a(2n) = n, a(2n+1) = n+2.
a(n+2) = a(n)+1.
a(n) = -a(-3-n).
a(n) = A110570(n,2) for n>1. - Reinhard Zumkeller, Jul 28 2005
a(n) = (n+1)-a(n-1) with n>0, a(0)=0. - Vincenzo Librandi, Nov 18 2010
a(n) = Sum_{k=1..n} (-1)^(n+k)*(k+1). - Arkadiusz Wesolowski, Nov 23 2012
a(n+1) = (a(0) + a(1) + ... + a(n))/a(n) for n>0. This formula with different initial conditions produces A008619. - Ivan Neretin, Apr 25 2016
E.g.f.: (x*exp(x) + 3*sinh(x))/2. - Ilya Gutkovskiy, Apr 25 2016
Sum_{n>=1} (-1)^n/a(n) = 1. - Amiram Eldar, Oct 04 2022

New name (using existing formula) from Joerg Arndt, Apr 26 2016

A226576 Smallest number of integer-sided squares needed to tile a 3 X n rectangle.

Original entry on oeis.org

0, 3, 3, 1, 4, 4, 2, 5, 5, 3, 6, 6, 4, 7, 7, 5, 8, 8, 6, 9, 9, 7, 10, 10, 8, 11, 11, 9, 12, 12, 10, 13, 13, 11, 14, 14, 12, 15, 15, 13, 16, 16, 14, 17, 17, 15, 18, 18, 16, 19, 19, 17, 20, 20, 18, 21, 21, 19, 22, 22, 20, 23, 23, 21, 24, 24, 22, 25, 25, 23, 26

Offset: 0

Alois P. Heinz, Jun 12 2013

			a(8) = 5:
  ._._._._._._._._.
  |     |     |   |
  |     |     |___|
  |_____|_____|_|_| .

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).

Cf. row m=3 of A113881, A219158.

a:= n-> iquo(n, 3, 'r') +[0, 3, 3][r+1]:
seq(a(n), n=0..80);

CoefficientList[Series[(3 x - 2 x^3)/(1 - x - x^3 + x^4), {x, 0, 70}], x] (* Michael De Vlieger, Oct 01 2017 *)

concat(0, Vec((3*x-2*x^3)/(1-x-x^3+x^4) + O(x^50))) \\ Felix Fröhlich, Oct 02 2017

G.f.: (3*x-2*x^3)/(1-x-x^3+x^4).
a(n) = 1 + a(n-3) for n>2; a(0)=0, a(1)=a(2)=3.
a(n) = (3*n+15+6*cos(2*(n-2)*Pi/3)-8*sqrt(3)*sin(2*(n-2)*Pi/3))/9. - Wesley Ivan Hurt, Oct 01 2017
a(n) = 3*floor((n+2)/3) - 2*floor(n/3). - Ridouane Oudra, Jan 25 2024

A160911 a(n) is the number of arrangements of n square tiles with coprime sides in a rectangular frame, counting reflected, rotated or rearranged tilings only once.

Original entry on oeis.org

1, 1, 2, 5, 11, 29, 84, 267, 921, 3481, 14322, 62306, 285845, 1362662, 6681508, 33483830

Offset: 1

Kevin Johnston, Feb 11 2016

There is only one arrangement of 1 square tile: a 1 X 1 rectangle. There is also only 1 arrangement of 2 square tiles: a 2 X 1 rectangle. There are 2 arrangements of 3 square tiles: a 3 X 1 rectangle (three 1 X 1 tiles) and a 3 X 2 rectangle (a 2 X 2 tile and two 1 X 1 tiles).
Short notation for the 2 possible 3-tile solutions:
  3 X 1: 1,1,1
  3 X 2: 2,1,1
More examples see below.
The smallest tile is not always a unit tile, e.g., one of the solutions for 5 tiles is: 6 X 5: 3,3,2,2,2.
My definition of a unique solution is the "signature" string in this notation: the rectangle size for nonsquares and the list of coprime tile sizes sorted largest to smallest. Rotations and reflections of a known solution are not new solutions; rearrangements of the same size tiles within the same overall boundary are not new solutions. But reorganizations of the same size tiles in different boundaries are unique solutions, such as 4 X 1: 1,1,1,1 and 2 X 2: 1,1,1,1.
From Rainer Rosenthal, Dec 23 2022: (Start)
The above description can be abbreviated as follows:
a(n) is the number of (2+n)-tuples (p X q: t_1,...,t_n) of positive integers, such that:
0. p >= q.
1. gcd(t_1,...,t_n) = 1 and t_i >= t_j for i < j and Sum_{i=1..n} t_i^2 = p * q.
2. Any p X q matrix is the disjoint union of contiguous t_i X t_i minors, i = 1..n. (For contiguous minors resp. submatrices see comments in A350237.)
.
The rectangle size p X q may have gcd(p,q) > 1, as seen in the examples for 3 X 2 and 6 X 4. Therefore a(n) >= A210517(n) for all n, and a(6) > A210517(6).
(End)

			From _Rainer Rosenthal_, Dec 24 2022, updated May 09 2024: (Start)
.
                                 |A|
     |A B|                       |B|
     |C D|  (2 X 2: 1,1,1,1)     |C|    (4 X 1: 1,1,1,1)
                                 |D|
.
                                 |A A|
    |A A A|                      |A A|
    |A A A|                      |B B|
    |A A A| (4 X 3: 3,1,1,1)     |B B|  (5 X 2: 2,2,1,1)
    |B C D|                      |C D|
.
    |A A A|
    |A A A|  <=================   3 X 3 minor A
    |A A A|                       2 X 2 minor B
    |B B C|  (5 X 3: 3,2,1,1)     1 X 1 minor C
    |B B D|                       1 X 1 minor D
  ________________________________________________________
       a(4) = 5 illustrated as (p X q: t_1,t_2,t_3,t_4)
         and as p X q matrices with t_i X t_i minors
.
Example configurations for a(6) = 29:
.
                                    |A A A A|
                                    |A A A A|
                                    |A A A A|
      |A A B|         |A B|         |A A A A|
      |A A C|         |C D|         |B B C D|
      |D E F|         |E F|         |B B E F|
   ______________________________________________
      (3 X 3:        (3 X 2:         (6 X 4:
    2,1,1,1,1,1)   1,1,1,1,1,1)    4,2,1,1,1,1)
.                                       _________________________
      |A A A A A A B B B B B B B|      |           |             |
      |A A A A A A B B B B B B B|      |           |             |
      |A A A A A A B B B B B B B|      |    6      |             |
      |A A A A A A B B B B B B B|      |           |      7      |
      |A A A A A A B B B B B B B|      |           |             |
      |A A A A A A B B B B B B B|      |___________|             |
      |C C C C C D B B B B B B B|      |         |1|_____________|
      |C C C C C E E E E F F F F|      |         |       |       |
      |C C C C C E E E E F F F F|      |    5    |  4    |  4    |
      |C C C C C E E E E F F F F|      |         |       |       |
      |C C C C C E E E E F F F F|      |_________|_______|_______|
     _____________________________    _____________________________
         (13 X 11: 7,6,5,4,4,1)           (13 X 11: 7,6,5,4,4,1)
         [rotated by 90 degrees]         [alternate visualization]
.(End)

See A002839 and A217156 for further references and links.

Stuart E. Anderson, Perfect Squared Rectangles and Squared Squares

Cf. A002839, A005670, A113881, A210517, A217156, A219924, A221843, A221844, A221845, A340726, A342558, A350237.

a(15)-a(16) from Kevin Johnston, Feb 11 2016

Title changed from Rainer Rosenthal, Dec 28 2022

A226577 Smallest number of integer-sided squares needed to tile a 4 X n rectangle.

Original entry on oeis.org

0, 4, 2, 4, 1, 5, 3, 5, 2, 6, 4, 6, 3, 7, 5, 7, 4, 8, 6, 8, 5, 9, 7, 9, 6, 10, 8, 10, 7, 11, 9, 11, 8, 12, 10, 12, 9, 13, 11, 13, 10, 14, 12, 14, 11, 15, 13, 15, 12, 16, 14, 16, 13, 17, 15, 17, 14, 18, 16, 18, 15, 19, 17, 19, 16, 20, 18, 20, 17, 21, 19, 21, 18

Offset: 0

Alois P. Heinz, Jun 12 2013

			a(11) = 6:
._._._._._._._._._._._.
|       |       |     |
|       |       |     |
|       |       |_____|
|_______|_______|_|_|_|

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Row m=4 of A113881, A219158.

a:= n-> iquo(n, 4, 'r') +[0, 4, 2, 4][r+1]:
seq(a(n), n=0..80);

RecurrenceTable[{a[0] == 0, a[1] == 4, a[2] == 2, a[3] == 4, a[n] == 1 + a[n - 4]}, a[n], {n, 0, 80}] (* Bruno Berselli, Jun 12 2013 *)
LinearRecurrence[{1,0,0,1,-1},{0,4,2,4,1},90] (* Harvey P. Dale, Jul 03 2019 *)

makelist(5+(2*n-1-(2+(-1)^n)*(11+2*%i^(n*(n+1))))/8, n, 0, 80); /* Bruno Berselli, Jun 12 2013 */

G.f.: (-3*x^4+2*x^3-2*x^2+4*x)/(x^5-x^4-x+1).
a(n) = 1 + a(n-4) for n>3.
a(n) = 5 + (2*n - 1 - (2 + (-1)^n)*(11 + 2*i^(n*(n+1))))/8, where i=sqrt(-1). [Bruno Berselli, Jun 12 2013]

A226578 Smallest number of integer-sided squares needed to tile a 5 X n rectangle.

Original entry on oeis.org

0, 5, 4, 4, 5, 1, 5, 5, 5, 6, 2, 6, 6, 6, 7, 3, 7, 7, 7, 8, 4, 8, 8, 8, 9, 5, 9, 9, 9, 10, 6, 10, 10, 10, 11, 7, 11, 11, 11, 12, 8, 12, 12, 12, 13, 9, 13, 13, 13, 14, 10, 14, 14, 14, 15, 11, 15, 15, 15, 16, 12, 16, 16, 16, 17, 13, 17, 17, 17, 18, 14, 18, 18

Offset: 0

Alois P. Heinz, Jun 12 2013

			a(11) = 6:
._._._._._._._._._._._.
|         |     |     |
|         |     |     |
|         |_____|_____|
|         |   |   |   |
|_________|___|___|___|

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1)

Row m=5 of A113881, A219158.

a:= n-> `if`(n=1, 5, iquo(n, 5, 'r') +[0, 4$3, 5][r+1]):
seq(a(n), n=0..80);

G.f.: x*(x^6-x^5-4*x^4+x^3-x+5)/(x^6-x^5-x+1).

a(n) = 1 + a(n-5) for n>6.

cp's OEIS Frontend

A219924 Number A(n,k) of tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A219158 Minimum number of integer-sided squares needed to tile an m X n rectangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A226545 Number A(n,k) of squares in all tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A285721 Square array read by antidiagonals: A(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k, read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Scheme

Formula

A338573 Array read by ascending antidiagonals: T(m,n) (m, n >= 1) is the minimum number of unit resistors needed to produce resistance m/n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A030451 a(2*n) = n, a(2*n+1) = n+2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A226576 Smallest number of integer-sided squares needed to tile a 3 X n rectangle.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A160911 a(n) is the number of arrangements of n square tiles with coprime sides in a rectangular frame, counting reflected, rotated or rearranged tilings only once.

Views

Author

Keywords

Comments

A030451 a(2n) = n, a(2n+1) = n+2.