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-10 of 19 results. Next

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:
._ _   _ _   _ _   _ _   _ _   _ _   _ _   _ _
|   | | | | |_ _| | |_| |_| | |_ _| |_|_| |_|_|
|_ _| |_|_| |_ _| |_|_| |_|_| |_|_| |_ _| |_|_|
		

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

A360629 Triangle read by rows: T(n,k) is the number of sets of integer-sided rectangular pieces that can tile an n X k rectangle, 1 <= k <= n.

Original entry on oeis.org

1, 2, 4, 3, 10, 21, 5, 22, 73, 192, 7, 44, 190, 703, 2035, 11, 91, 510, 2287, 8581, 27407, 15, 172, 1196, 6738, 30209, 118461, 399618, 22, 326, 2895, 19160, 102092, 462114
Offset: 1

Views

Author

Pontus von Brömssen, Feb 14 2023

Keywords

Comments

Pieces are free to rotate by 90 degrees, i.e., an r X s piece and an s X r piece are equivalent. See A360451 for the case when the pieces are fixed.

Examples

			Triangle begins:
   n\k|  1   2    3    4     5      6      7
   ---+--------------------------------------
   1  |  1
   2  |  2   4
   3  |  3  10   21
   4  |  5  22   73  192
   5  |  7  44  190  703  2035
   6  | 11  91  510 2287  8581  27407
   7  | 15 172 1196 6738 30209 118461 399618
   ...
T(2,2) = 4, because a 2 X 2 rectangle can be tiled by: one 2 X 2 piece; two 1 X 2 pieces; one 1 X 2 piece and two 1 X 1 pieces; four 1 X 1 pieces.
The T(3,2) = 10 sets of pieces that can tile a 3 X 2 rectangle are shown in the table below. (Each column on the right gives a set of pieces.)
   length X width |  number of pieces
   ---------------+--------------------
        2 X 3     | 1 0 0 0 0 0 0 0 0 0
        2 X 2     | 0 1 1 0 0 0 0 0 0 0
        1 X 3     | 0 0 0 2 1 1 0 0 0 0
        1 X 2     | 0 1 0 0 1 0 3 2 1 0
        1 X 1     | 0 0 2 0 1 3 0 2 4 6
		

Crossrefs

Cf. A000041 (column k=1), A116694, A224697 (square pieces), A360451 (fixed pieces), A360630 (main diagonal), A360631 (column k=2), A360632 (column k=3).

Extensions

T(7,7) and T(8,k) for k = 1..6 added by Robin Visser, May 09 2025

A285357 Square array read by antidiagonals: T(m,n) = the number of tight m X n pavings (defined below).

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 11, 11, 1, 1, 26, 64, 26, 1, 1, 57, 282, 282, 57, 1, 1, 120, 1071, 2072, 1071, 120, 1, 1, 247, 3729, 12279, 12279, 3729, 247, 1, 1, 502, 12310, 63858, 106738, 63858, 12310, 502, 1, 1, 1013, 39296, 305464, 781458, 781458, 305464, 39296, 1013, 1
Offset: 1

Views

Author

Don Knuth, Apr 17 2017

Keywords

Comments

A tight m X n paving is a dissection of an m X n rectangle into m+n-1 rectangles, having m+1 distinct boundary lines in one dimension and n+1 distinct boundary lines in another.
There's another characterization of tight pavings (cf. the lemma in the solution reference).
The 2nd column are the Eulerian numbers A000295(n+1) = 2^(n+1) - n - 2. The 3rd column/diagonal is given in A285361. - M. F. Hasler, Jan 11 2018
Related to the dissection of rectangles into smaller rectangles, see Knuth's Stanford lecture video. Sequence A116694 gives the number of these dissections. - M. F. Hasler, Jan 22 2018

Examples

			There are 1071 tight pavings when m = 3 and n = 5. Two of them have their seven rectangles in the trivial patterns 11111|22222|34567 and 12345|12346|12347; a more interesting example is 11122|34422|35667.
The array begins:
  1   1    1    1    1    1    1  ...
  1   4   11   26   57  120  ...
  1  11   64  282 1071  ...
  1  26  282 2072  ...
  1  57 1071  ...
  1 120  ...
  ...
		

Crossrefs

Cf. A000295 (m=2), A116694, A285361 (m=3), A298362, A298432 (diagonal sums), A298433 (main diagonal), A336732 (m=4), A336734 (m=5).

Programs

  • PARI
    /* List all 2 X n tight pavings, where 0 = |, 1 = ┥, 2 = ┙, 3 = ┑ */ nxt=[[0,1,2,3],[0],[1,2,3],[1,2,3]]; T2(n,a=0,d=a%10)={if(n>1,concat(apply(t->T2(n-1,a*10+t),nxt[d+1+(!d&&a)])),[a*10+(d>1||!a)])} \\ M. F. Hasler, Jan 20 2018
    for(n=1, 20, print1(#T2(n),", ")) \\ gives row T(2,n) - Georg Fischer, Jul 30 2020

Formula

From M. F. Hasler, Jul 30 2020: (Start)
T(1,n) = 1.
T(2,n) = A000295(n+1) = 2^(n+1) - n - 2.
T(3,n) = A285361(n) = (3^(n+3) - 5*2^(n+4) + 4*n^2 + 26*n + 53)/4. (End)
From Roberto Tauraso, Aug 02 2020: (Start)
T(4,n) = A336732(n) = (4^(n+5) + (n-42)*3^(n+4) - 9*(2*n-27)*2^(n+5) - 36*n^3-486*n^2 - 2577*n - 5398)/36.
T(5,n) = A336734(n) = (5^(n+7) + (2*n-66)*4^(n+6) + (16*n^2-1432*n+13164)*3^(n+3) + (303*n-1505)*2^(n+10) + 576*n^4 + 13248*n^3 + 129936*n^2 + 646972*n + 1377903)/576. (End)

Extensions

Edited by M. F. Hasler, Jan 13 2018 and by N. J. A. Sloane, Jan 14 2018
a(29)-a(55) from Hugo Pfoertner, Jan 19 2018
a(51) corrected by Hugo Pfoertner, Jul 29 2020

A034999 Number of ways to cut a 2 X n rectangle into rectangles with integer sides.

Original entry on oeis.org

1, 2, 8, 34, 148, 650, 2864, 12634, 55756, 246098, 1086296, 4795090, 21166468, 93433178, 412433792, 1820570506, 8036386492, 35474325410, 156591247016, 691227204226, 3051224496244, 13468756547882, 59453967813584, 262442511046330, 1158477291582892
Offset: 0

Views

Author

Keywords

Comments

Hankel transform is 1, 4, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... . - Philippe Deléham, Dec 10 2011

Examples

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

Crossrefs

Column 2 of A116694. - Alois P. Heinz, Dec 10 2012

Formula

a(n) = 1+3^(n-1) + Sum_{i=1..n-1} (1+3^(i-1)) a(n-i).
a(n) = 6a(n - 1) - 7a(n - 2), a(n) = ((4 + sqrt(2)) (3 + sqrt(2))^n + (4 - sqrt(2)) (3 - sqrt(2))^n)/14. - N. Sato, May 10 2006
G.f.: (1-x)*(1-3*x)/(1-6*x+7*x^2). - Richard Stanley, Dec 09 2011
E.g.f.: (3 + exp(3*x)*(4*cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x)))/7. - Stefano Spezia, Feb 17 2022
a(n) = 2*A086351(n-1), n>0. - R. J. Mathar, Apr 07 2022

Extensions

a(0) added by Richard Stanley, Dec 09 2011

A078469 Number of different compositions of the ladder graph L_n.

Original entry on oeis.org

1, 2, 12, 74, 456, 2810, 17316, 106706, 657552, 4052018, 24969660, 153869978, 948189528, 5843007146, 36006232404, 221880401570, 1367288641824, 8425612252514, 51920962156908, 319951385193962, 1971629273320680
Offset: 0

Views

Author

Ralf Stephan, Jan 02 2003

Keywords

Comments

This is equally the number of partitions of a 2 x n rectangle into connected pieces consisting of unit squares cut along lattice lines, like a 2-d analog of a partition into integers. - Hugo van der Sanden, Mar 23 2009

Crossrefs

Cf. A108808, A110476. - Brian Kell, Oct 21 2008

Programs

  • Magma
    I:=[1, 2, 12]; [n le 3 select I[n] else 6*Self(n-1)+Self(n-2): n in [1..30]]; // Vincenzo Librandi, May 17 2013
  • Mathematica
    Join[{1},LinearRecurrence[{6,1},{2,12},30]] (* Harvey P. Dale, Jul 22 2013 *)

Formula

a(n) = 6*a(n-1) + a(n-2).
G.f.: 1 + 2*x/(1 - 6*x - x^2).
a(n) = ((3 + s)^n - (3 - s)^n)/s, where s = sqrt(10) (assumes a(0) = 0).
Asymptotic to (3 + sqrt(10))^n/sqrt(10). - Ralf Stephan, Jan 03 2003
Let p[i] = Fibonacci(3*i) and A be the Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], if i <= j; A[i,j] = -1, if i = j + 1; and A[i,j] = 0, otherwise. Then, for n >= 1, a(n) = det(A). - Milan Janjic, May 08 2010
a(n) = 2*A005668(n), n > 0. - R. J. Mathar, Nov 29 2015
a(n) >= A116694(2,n). - R. J. Mathar, Nov 29 2015

Extensions

a(0) changed from 0 to 1 by N. J. A. Sloane, Sep 21 2009, at the suggestion of Hugo van der Sanden

A220297 Number of ways to cut a 4 X n rectangle into rectangles with integer sides.

Original entry on oeis.org

1, 8, 148, 3164, 70878, 1613060, 36911922, 846280548, 19415751782, 445550465628, 10225294476962, 234675373081668, 5385967300825942, 123612245431357148, 2837003283963428562, 65111601723938370628, 1494366038587416919782, 34296959750113321113308
Offset: 0

Views

Author

Alois P. Heinz, Dec 10 2012

Keywords

Examples

			a(1) = 8:
  ._.  ._.  ._.  ._.  ._.  ._.  ._.  ._.
  | |  |_|  | |  | |  |_|  |_|  | |  |_|
  | |  | |  |_|  | |  |_|  | |  |_|  |_|
  | |  | |  | |  |_|  | |  |_|  |_|  |_|
  |_|  |_|  |_|  |_|  |_|  |_|  |_|  |_|
.
		

Crossrefs

Column m=4 of A116694.

Programs

  • Maple
    gf:= (3832*x^6 -8492*x^5 +6722*x^4 -2468*x^3 +441*x^2 -36*x+1) / (11680*x^6 -20980*x^5 +13840*x^4 -4280*x^3 +645*x^2 -44*x+1):
    a:= n-> coeff(series(gf, x, n+1), x, n):
    seq(a(n), n=0..20);

Formula

G.f.: see Maple program.

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;
     ...
		

Crossrefs

Triangular version of A116694.
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:
._   _   _   _
|_| |_| | | | |
|_| | | |_| | |
|_| |_| |_| |_|
		

Crossrefs

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

A220298 Number of ways to cut a 5 X n rectangle into rectangles with integer sides.

Original entry on oeis.org

1, 16, 650, 31484, 1613060, 84231996, 4427635270, 233276449488, 12300505521832, 648782777031100, 34223109012944482, 1805323555104984956, 95234889270955121716, 5023877415526067785580, 265022449692240368203598, 13980623266954069411358904
Offset: 0

Views

Author

Alois P. Heinz, Dec 10 2012

Keywords

Examples

			a(1) = 16:
  ._. ._. ._. ._. ._. ._. ._. ._. ._. ._. ._. ._. ._. ._. ._. ._.
  | | |_| | | | | | | |_| |_| |_| | | | | | | |_| |_| |_| | | |_|
  | | | | |_| | | | | |_| | | | | |_| |_| | | |_| |_| | | |_| |_|
  | | | | | | |_| | | | | |_| | | |_| | | |_| |_| | | |_| |_| |_|
  | | | | | | | | |_| | | | | |_| | | |_| |_| | | |_| |_| |_| |_|
  |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_| |_|
.
		

Crossrefs

Column m=5 of A116694.

Programs

  • Maple
    gf:= (39672144*x^10 -110891556*x^9 +124284414*x^8 -74544838*x^7 +26669637*x^6 -5961522*x^5 +841659*x^4 -73608*x^3 +3769*x^2 -100*x+1)/
    (135762480*x^10 -326041524*x^9 +320708934*x^8 -170972730*x^7 +54776249*x^6 -11002298*x^5 +1395665*x^4 -109292*x^3 +4975*x^2 -116*x +1):
    a:= n-> coeff(series(gf, x, n+1), x, n):
    seq(a(n), n=0..20);

Formula

G.f.: see Maple program.

A220299 Number of ways to cut a 6 X n rectangle into rectangles with integer sides.

Original entry on oeis.org

1, 32, 2864, 314662, 36911922, 4427635270, 535236230270, 64878517290010, 7871769490695758, 955411617212520670, 115973945786899746170, 14078248409306427591814, 1709004742525016740261850, 207462778992946779638832746, 25184765957310295151583128422
Offset: 0

Views

Author

Alois P. Heinz, Dec 10 2012

Keywords

Crossrefs

Column m=6 of A116694.

Programs

  • Maple
    gf:= (916798938728006656*x^20 -3962057190907156288*x^19 +7644699117821849592*x^18 -8795707489604640136*x^17 +6787540243858479914*x^16 -3741365942249935792*x^15 +1530293206620422033*x^14 -475918767335413756*x^13
    +114321113226304761*x^12 -21415445169034874*x^11 +3143712388922139*x^10 -361909626897452*x^9 +32569667881308*x^8 -2274379347082*x^7 +121717789540*x^6 -4898404600*x^5 +144102468*x^4 -2968032*x^3 +39908*x^2 -308*x +1)/
    (3488260147244630016*x^20 -13785403213649739264*x^19 +24571927550599277952*x^18 -26305901575283773400*x^17 +18988035581731414180*x^16 -9828185761768234778*x^15
    +3785664669818771697*x^14 -1111033817019987980*x^13 +252212834590208135*x^12 -44688005447169948*x^11 +6207093806210985*x^10 -676048684437666*x^9 +57526055007906*x^8 -3794064844276*x^7 +191447789306*x^6 -7247125678*x^5 +199881354*x^4 -3842502*x^3 +47924*x^2 -340*x +1):
    a:= n-> coeff(series(gf, x, n+1), x, n):
    seq(a(n), n=0..20);

Formula

G.f.: see Maple program.
Showing 1-10 of 19 results. Next