cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A116694 Array read by antidiagonals: number of ways of dividing an n X m rectangle into integer-sided rectangles.

Original entry on oeis.org

1, 2, 2, 4, 8, 4, 8, 34, 34, 8, 16, 148, 322, 148, 16, 32, 650, 3164, 3164, 650, 32, 64, 2864, 31484, 70878, 31484, 2864, 64, 128, 12634, 314662, 1613060, 1613060, 314662, 12634, 128, 256, 55756, 3149674, 36911922, 84231996, 36911922, 3149674, 55756, 256
Offset: 1

Views

Author

Helena Verrill (verrill(AT)math.lsu.edu), Feb 23 2006

Keywords

Examples

			Array begins:
   1,    2,      4,        8,         16,           32, ...
   2,    8,     34,      148,        650,         2864, ...
   4,   34,    322,     3164,      31484,       314662, ...
   8,  148,   3164,    70878,    1613060,     36911922, ...
  16,  650,  31484,  1613060,   84231996,   4427635270, ...
  32, 2864, 314662, 36911922, 4427635270, 535236230270, ...

Links

Crossrefs

Columns (or rows) 1-10 give: A011782, A034999, A208215, A220297, A220298, A220299, A220300, A220301, A220302, A220303.
Main diagonal gives A182275.
For irreducible or "tight" pavings, see also A285357.
Triangular version: A333476.
A(2n,n) gives A333495.

Programs

  • Maple
    M:= proc(n) option remember; local k; k:= 2^(n-2);
      `if`(n=1, Matrix([2]), Matrix(2*k, (i, j)->`if`(i<=k,
      `if`(j<=k, M(n-1)[i, j], B(n-1)[i, j-k]),
      `if`(j<=k, B(n-1)[i-k, j], 2*M(n-1)[i-k, j-k]))))
    end:
B:= proc(n) option remember; local k; k:=2^(n-2);
      `if`(n=1, Matrix([1]), Matrix(2*k, (i,j)->`if`(i<=k,
      `if`(j<=k, B(n-1)[i, j], B(n-1)[i, j-k]),
      `if`(j<=k, B(n-1)[i-k, j], M(n-1)[i-k, j-k]))))
    end:
A:= proc(n, m) option remember; `if`(n=0 or m=0, 1, `if`(m>n, A(m, n),
      add(i, i=map(rhs, [op(op(2, M(m)^(n-1)))]))))
    end:
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);  # Alois P. Heinz, Dec 13 2012
  • Mathematica
    M[n_] := M[n] = Module[{k = 2^(n-2)}, If[n == 1, {{2}}, Table[If[i <= k, If[j <= k, M[n-1][[i, j]], B[n-1][[i, j-k]]], If[j <= k, B[n-1][[i-k, j]], 2*M[n-1][[i-k, j-k]]]], {i, 1, 2k}, {j, 1, 2k}]]]; B[n_] := B[n] = Module[{k = 2^(n-2)}, If[n == 1, {{1}}, Table[If[i <= k, If[j <= k, B[n-1][[i, j]], B[n-1][[i, j-k]]], If[j <= k, B[n-1][[i-k, j]], M[n-1][[i-k, j-k]]]], {i, 1, 2k}, {j, 1, 2k}]]]; A[0, 0] = 1; A[n_ , m_ ] /; m>n := A[m, n]; A[n_ , m_ ] :=MatrixPower[M[m], n-1] // Flatten // Total; Table[Table[A[n, 1+d-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Feb 23 2015, after Alois P. Heinz *)
  • PARI
    A116694(m,n)=#fill(m,n) \\ where fill() below computes all tilings. - M. F. Hasler, Jan 22 2018
fill(m,n,A=matrix(m,n),i=1,X=1,Y=1)={while((Y>n&&X++&&!Y=0)||A[X,Y], X>m&&return([A]); Y++); my(N=n,L=[]); for(x=X,m, A[x,Y]&&break; for(y=Y,N, if(A[x,y],for(j=y,N,for(k=X,x-1,A[k,j]=0));N=y-1;break); for(j=X,x,A[j,y]=i); L=concat(L,fill(m,n,A,i+1,X,y+1))); x

Extensions

Edited and more terms from Alois P. Heinz, Dec 09 2012

A182275 Number of ways of dividing an n X n square into rectangles of integer side lengths.

Original entry on oeis.org

1, 1, 8, 322, 70878, 84231996, 535236230270, 18100579400986674, 3250879178100782348462, 3097923464622249063718465240, 15657867573050419014814618149422562, 419678195343896524683571751908598967042082, 59647666241586874002530830848160043213559146735474
Offset: 0

Views

Author

Matthew C. Russell, Apr 23 2012

Keywords

Examples

			For n=2 the a(2) = 8 ways to divide are:
._ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _
|   | | | | |_ _| | |_| |_| | |_ _| |_|_| |_|_|
|_ _| |_|_| |_ _| |_|_| |_|_| |_|_| |_ _| |_|_|

Links

Crossrefs

Main diagonal of A116694 and of A333476.
Cf. A034999.

Formula

a(n) = A116694(n,n) for n > 0.

Extensions

a(11)-a(12) from Steve Butler, Mar 14 2014

A333476 Triangle read by rows: T(n,k) gives the number of ways to partition an n X k grid into rectangles of integer side lengths with 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 8, 1, 4, 34, 322, 1, 8, 148, 3164, 70878, 1, 16, 650, 31484, 1613060, 84231996, 1, 32, 2864, 314662, 36911922, 4427635270, 535236230270, 1, 64, 12634, 3149674, 846280548, 233276449488, 64878517290010, 18100579400986674
Offset: 0

Views

Author

Peter Kagey, Mar 23 2020

Keywords

Examples

			Triangle begins:
n\k| 0   1     2       3         4           5             6
---+--------------------------------------------------------
  0| 1;
  1| 1,  1;
  2| 1,  2,    8;
  3| 1,  4,   34,    322;
  4| 1,  8,  148,   3164,    70878;
  5| 1, 16,  650,  31484,  1613060,   84231996;
  6| 1, 32, 2864, 314662, 36911922, 4427635270, 535236230270;
     ...

Links

Crossrefs

Triangular version of A116694.
Columns 0-10 are given by: A000012, A011782, A034999, A208215, A220297, A220298, A220299, A220300, A220301, A220302, A220303.
Main diagonal is given by A182275.
T(2n,n) gives A333495.

Programs

  • Maple
    M:= proc(n) option remember; local k; k:= 2^(n-2);
      `if`(n=1, Matrix([2]), Matrix(2*k, (i, j)->`if`(i<=k,
      `if`(j<=k, M(n-1)[i, j], B(n-1)[i, j-k]),
      `if`(j<=k, B(n-1)[i-k, j], 2*M(n-1)[i-k, j-k]))))
    end:
B:= proc(n) option remember; local k; k:=2^(n-2);
      `if`(n=1, Matrix([1]), Matrix(2*k, (i, j)->`if`(i<=k,
      `if`(j<=k, B(n-1)[i, j], B(n-1)[i, j-k]),
      `if`(j<=k, B(n-1)[i-k, j], M(n-1)[i-k, j-k]))))
    end:
T:= proc(n, m) option remember; `if`((s-> 0 in s or s={1})(
      {n, m}), 1, `if`(m>n, T(m, n), add(i, i=map(rhs,
       [op(op(2, M(m)^(n-1)))]))))
    end:
seq(seq(T(n, k), k=0..n), n=0..8);  # Alois P. Heinz, Mar 23 2020
  • Mathematica
    M[n_] := M[n] = Module[{k = 2^(n - 2)}, If[n == 1, {{2}}, Table[If[i <= k, If[j <= k, M[n - 1][[i, j]], B[n - 1][[i, j - k]]], If[j <= k, B[n - 1][[i - k, j]], 2 M[n - 1][[i - k, j - k]]]], {i, 1, 2k}, {j, 1, 2k}]]];
B[n_] := B[n] = Module[{k = 2^(n - 2)}, If[n == 1, {{1}}, Table[If[i <= k, If[j <= k, B[n - 1][[i, j]], B[n - 1][[i, j - k]]], If[j <= k, B[n - 1][[i - k, j]], M[n - 1][[i - k, j - k]]]], {i, 1, 2k}, {j, 1, 2k}]]];
T[_, 0] = 1;
T[n_, k_] /; k > n := T[k, n];
T[n_, k_] := MatrixPower[M[k], n-1] // Flatten // Total;
Table[Table[T[n, k], {k, 0, n}], {n, 0, 8}] // Flatten (* Jean-François Alcover, Nov 23 2020, after Alois P. Heinz *)

Formula

T(n,k) = A116694(n,k).

A208215 Number of ways of dividing a 3 X n rectangle into rectangles of integer side lengths.

Original entry on oeis.org

1, 4, 34, 322, 3164, 31484, 314662, 3149674, 31544384, 315981452, 3165414034, 31710994234, 317682195692, 3182564368244, 31883205466534, 319408833724882, 3199866987994304, 32056562443839284, 321145602837871522, 3217266324544621714, 32230871396722195484
Offset: 0

Views

Author

Matthew C. Russell, Apr 23 2012

Keywords

Examples

			For n=1 the a(1) = 4 ways to divide are:
._   _   _   _
|_| |_| | | | |
|_| | | |_| | |
|_| |_| |_| |_|

Links

Crossrefs

Cf. A034999, A116694, A182275.

Programs

  • Mathematica
    Join[{1}, LinearRecurrence[{15, -55, 51}, {4, 34, 322}, 20]] (* Bruno Berselli, Apr 24 2012 *)

Formula

a(n) = 18*a(n-1) -100*a(n-2) +216*a(n-3) -153*a(n-4) with n>4 (see paper in Link lines, p. 1).
G.f.: 1+2*x*(2-13*x+16*x^2) / (1-15*x+55*x^2-51*x^3) = 1+2*x*(2-19*x+55*x^2-48*x^3) / (1-18*x+100*x^2-216*x^3+153*x^4). [Bruno Berselli, Apr 24 2012]
a(n) = 15*a(n-1) -55*a(n-2) +51*a(n-3) with n>3. [Bruno Berselli, Apr 24 2012]

Extensions

More terms from Bruno Berselli, Apr 24 2012
a(0) added by Alois P. Heinz, Dec 10 2012

A347825 Number of ways to cut a 2 X n rectangle into rectangles with integer sides up to symmetries of the rectangle.

Original entry on oeis.org

1, 2, 6, 17, 61, 220, 883, 3597, 15232, 65130, 282294, 1229729, 5384065, 23630332, 103922707, 457561989, 2016346540, 8890227762, 39212714934, 173001054449, 763388725141, 3368934926716, 14868728620387, 65626328874621, 289666423135048, 1278582804528090
Offset: 0

Views

Author

Thomas Garrison, Jan 26 2022

Keywords

Comments

If all rotations and reflections are considered, a(2)=4 instead of 6.

Examples

			The a(2) = 6 ways to partition are:
  +-------+    +---+---+    +-------+
  |       |    |   |   |    |       |
  |       |    |   |   |    +-------+
  |       |    |   |   |    |       |
  +-------+    +---+---+    +-------+
.
  +---+---+    +-------+    +---+---+
  |   |   |    |       |    |   |   |
  |   +---+    +---+---+    +---+---+
  |   |   |    |   |   |    |   |   |
  +---+---+    +---+---+    +---+---+

Links

Crossrefs

The 1 X n case is A005418.
Cf. A034999, A068911 (fully symmetric).

Programs

  • PARI
    \\ here c(n) is A034999(n)
c(n) = polcoef((1-x)*(1-3*x)/(1-6*x+7*x^2) + O(x*x^n), n)
a(n) = if(n==0, 1, (c(n) + 2*3^(n-1) + c((n+1)\2) + c((n+2)\2))/4) \\ Andrew Howroyd, Feb 08 2022
  • Python
    # By Soumil Mukherjee
# Algebraic solutions to the number of ways to tile a 2 X n grid
import sys
# Total number of tilings
# Counts different reflections and rotations as distinct
counts = [1,2,8]
def tilings(n):
    if (n < len(counts)): return counts[n]
    for i in range(len(counts), n+1):
        val = 6 * counts[i-1] - 7 * counts[i-2]
        counts.append(val)
    return counts[n]
def getCounts(n):
  return counts[n]
def horizontallySymmetric(i):
    if i == 0: return 1
    return 2 * (3 ** (i-1))
def verticallySymmetric(i):
    if i == 0: return 1
    k = i//2
    if (i % 2 == 0):
        return counts[k+1] - counts[k]
    else:
        return counts[k+1]
def rotationallySymmetric(i):
    if i == 0: return 1
    k = i//2
    if (i % 2 == 0):
        return 2 * counts[k]
    else:
        return counts[k+1]
def perfectlySymmetric(i):
    if i == 0: return 1
    k = i//2
    if (i % 2 == 0):
        return 4 * (3 ** (k-1))
    else:
        return 2 * (3 ** k)
def asymmetric(i):
    return (
        counts[i]
        - verticallySymmetric(i)
        - horizontallySymmetric(i)
        - rotationallySymmetric(i)
        + (2 * perfectlySymmetric(i))
    )
def equivalenceClasses(i):
    tilings(i)
    return (
        (
          counts[i]
          + verticallySymmetric(i)
          + horizontallySymmetric(i)
          + rotationallySymmetric(i)
        )//4
        )

Formula

Define V(n) to be the set of tilings that are vertically symmetric.
Define H(n) to be the set of tilings that are horizontally symmetric.
Define R(n) to be the set of tilings that are rotationally symmetric.
a(n) = (c(n) + |V(n)| + |H(n)| + |R(n)|)/4 for n > 0, where:
c(n) = A034999(n),
|H(n)| = 2 * (3^n-1),
|V(n)| = c(n/2+1) - c(n/2) for even n; otherwise c(floor(n/2)+1),
|R(n)| = 2*c(n/2) for even n; otherwise c(floor(n/2)+1).
From Andrew Howroyd, Feb 08 2022: (Start)
a(n) = (c(n) + 2*3^(n-1) + c(floor((n+1)/2)) + c(floor((n+2)/2)))/4 for n > 0, where c(n) = A034999(n).
a(n) = 9*a(n-1) - 19*a(n-2) - 33*a(n-3) + 143*a(n-4) - 63*a(n-5) - 175*a(n-6) + 147*a(n-7) for n > 7.
G.f.: (1 - 7*x + 7*x^2 + 34*x^3 - 55*x^4 - 31*x^5 + 66*x^6 - 7*x^7)/((1 - 3*x)*(1 - 6*x + 7*x^2)*(1 - 6*x^2 + 7*x^4)).
(End)
a(n) ~ k*(3 + sqrt(2))^n, where k = (4 + sqrt(2))/56. - Stefano Spezia, Feb 17 2022

A222659 Table a(m,n) read by antidiagonals, m, n >= 1, where a(m,n) is the number of divide-and-conquer partitions of an m X n rectangle into integer sub-rectangles.

Original entry on oeis.org

1, 2, 2, 4, 8, 4, 8, 34, 34, 8, 16, 148, 320, 148, 16, 32, 650, 3118, 3118, 650, 32, 64, 2864, 30752, 68480, 30752, 2864, 64, 128, 12634, 304618, 1525558, 1525558, 304618, 12634, 128
Offset: 1

Views

Author

Arsenii Abdrafikov, May 29 2013

Keywords

Comments

The divide-and-conquer partition of an integer-sided rectangle is one that can be obtained by repeated bisections into adjacent integer-sided rectangles.
The table is symmetric: a(m,n) = a(n,m).

Examples

			Table begins:
1,      2,       4,       8,      16,     32,      64, ...
2,      8,      34,     148,     650,   2864,   12634, ...
4,     34,     320,    3118,   30752, 304618, 3022112, ...
8,    148,    3118,   68480, 1525558, ...
16,   650,   30752, 1525558, ...
32,  2864,  304618, ...
64, 12634, 3022112, ...
Not every partition (cf. A116694) into integer sub-rectangles is divide-and-conquer. For example, the following partition of a 3 X 3 rectangle into 5 sub-rectangles is not divide-and-conquer:
112
342
355

Crossrefs

a(1,n) = a(n,1) = A000079(n-1)
a(2,n) = a(n,2) = A034999(n)
Cf. A116694 (all partitions).
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.