login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

LINKS

Alois P. Heinz, Rows n = 0..12, flattened

Joshua Smith and Helena Verrill, On dividing rectangles into rectangles

FORMULA

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

EXAMPLE

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;

     ...

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 *)

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.

Sequence in context: A275980 A343918 A156029 * A120026 A329280 A109089

Adjacent sequences:  A333473 A333474 A333475 * A333477 A333478 A333479

KEYWORD

nonn,tabl

AUTHOR

Peter Kagey, Mar 23 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 19 12:20 EDT 2022. Contains 353833 sequences. (Running on oeis4.)