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 14 results. Next

A002478 Bisection of A000930.

Original entry on oeis.org

1, 1, 3, 6, 13, 28, 60, 129, 277, 595, 1278, 2745, 5896, 12664, 27201, 58425, 125491, 269542, 578949, 1243524, 2670964, 5736961, 12322413, 26467299, 56849086, 122106097, 262271568, 563332848, 1209982081, 2598919345, 5582216355, 11990037126, 25753389181
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of ways to tile a 3 X n region with 1 X 1, 2 X 2 and 3 X 3 tiles.
Number of ternary words with subwords (0,0), (0,1) and (1,1) not allowed. - Olivier Gérard, Aug 28 2012
Diagonal sums of A063967. - Paul Barry, Nov 09 2005
Row sums of number triangle A116088. - Paul Barry, Feb 04 2006
Sequence is identical to its second differences negated, minus the first 3 terms. - Paul Curtz, Feb 10 2008
a(n) = term (3,3) in the 3 X 3 matrix [0,1,0; 0,0,1; 1,2,1]^n. - Gary W. Adamson, May 30 2008
a(n)/a(n-1) tends to 2.147899035..., an eigenvalue of the matrix and a root to x^3 - x^2 - 2x - 1 = 0. - Gary W. Adamson, May 30 2008
INVERT transform of (1, 2, 1, 0, 0, 0, ...) = (1, 3, 6, 13, 28, ...); such that (1, 2, 1, 0, 0, 0, ...) convolved with (1, 1, 3, 6, 13, 28, 0, 0, 0, ...) shifts to the left. - Gary W. Adamson, Apr 18 2010
a(n) is the top left entry in the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 0, 1; 1, 0, 0] or of the 3 X 3 matrix [1, 1, 1; 1, 0, 0; 1, 1, 0]. - R. J. Mathar, Feb 03 2014

Examples

			a(3)=6 as there is one tiling of a 3 X 3 region with only 1 X 1 tiles, 4 tilings with exactly one 2 X 2 tile and 1 tiling consisting of the 3 X 3 tile.

References

  • Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
  • L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 322.
  • S. Heubach, Tiling an m X n Area with Squares of Size up to k X k (m<=5), Congressus Numerantium 140 (1999), pp. 43-64.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000930, A054856, A054857, A025234, A078007, A078039, A226546, A077936 (INVERT transform), A008346 (inverse INVERT transform).

Programs

  • Magma
    I:=[1,1,3]; [n le 3 select I[n] else Self(n-1) +2*Self(n-2) +Self(n-3): n in [1..41]]; // G. C. Greubel, Apr 14 2023
  • Mathematica
    f[A_]:= Module[{til = A}, AppendTo[til, A[[-1]] + 2A[[-2]] + A[[-3]]]]; NumOfTilings[ n_ ]:= Nest[ f, {1,1,3}, n-2]; NumOfTilings[30]
LinearRecurrence[{1,2,1},{1,1,3},40] (* Vladimir Joseph Stephan Orlovsky, Jan 28 2012 *)
CoefficientList[Series[1/(1-x-2x^2-x^3),{x,0,40}],x] (* Harvey P. Dale, Oct 17 2024 *)
  • PARI
    a(n)=([0,1,0; 0,0,1; 1,2,1]^n*[1;1;3])[1,1] \\ Charles R Greathouse IV, Apr 08 2016
  • SageMath
    @CachedFunction
def a(n): # A002478
    if (n<3): return (1,1,3)[n]
    else: return sum(binomial(2,j)*a(n-j) for j in range(1,4))
[a(n) for n in (0..40)] # G. C. Greubel, Apr 14 2023

Formula

G.f.: 1 / (1-x-2*x^2-x^3). [Simon Plouffe in his 1992 dissertation.]
a(n) = a(n-1) + 2*a(n-2) + a(n-3).
a(n) = Sum_{k=0..n} binomial(2*n-2*k, k). - Paul Barry, Nov 13 2004
a(n) = Sum_{k=0..floor(n/2)} Sum_{j=0..n-k} C(j, n-k-j)*C(j, k). - Paul Barry, Nov 09 2005
a(n) = Sum_{k=0..n} C(2*k,n-k) = Sum_{k=0..n} C(n,k)*C(3*k,n)/C(3*k,k). - Paul Barry, Feb 04 2006
a(n) = A000930(n) + 2*Sum_{i=0..n-2} a(i)*A000930(n-2-i). - Michael Tulskikh, Jun 07 2020

Extensions

Additional comments from Silvia Heubach (silvi(AT)cine.net), Apr 21 2000

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.

Original entry on oeis.org

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

Views

Author

Alois P. Heinz, Dec 01 2012

Keywords

Comments

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

Examples

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

Links

Crossrefs

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.

Programs

  • Maple
    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:
 ___.___.
|     |   |
|     |_|
|___|_|_|
|   |   |_|
|_|___|_|
  • Mathematica
    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 *)

A054856 Number of ways to tile a 4 X n region with 1 X 1, 2 X 2, 3 X 3 and 4 X 4 tiles.

Original entry on oeis.org

1, 1, 5, 13, 40, 117, 348, 1029, 3049, 9028, 26738, 79183, 234502, 694476, 2056692, 6090891, 18038173, 53420041, 158203433, 468519406, 1387520047, 4109140098, 12169216863, 36039131181, 106729873498, 316080480394, 936072224321
Offset: 0

Views

Author

Silvia Heubach (silvi(AT)cine.net), Apr 21 2000

Keywords

Comments

It is easy to see that the g.f. for indecomposable tilings, i.e. those that cannot be split vertically into smaller tilings, is g=z+4*z^2+2*z^3+z^4+2*z^3/(1-z); then G.f.=1/(1-g). - Emeric Deutsch, Oct 16 2006

Examples

			a(2)=5 as there is one tiling of a 4 X 2 region with only 1 X 1 tiles, 3 tilings with exactly one 2 X 2 tile and 1 tiling with exactly two 2 X 2 tiles.

Links

Crossrefs

Cf. A002478, A054857, A226547.
Column k=4 of A219924. - Alois P. Heinz, Dec 01 2012

Programs

  • Maple
    a[0]:=1: a[1]:=1: a[2]:=5: a[3]:=13: a[4]:=40: for n from 5 to 26 do a[n]:=2*a[n-1]+3*a[n-2]-a[n-4]-a[n-5] od: seq(a[n],n=0..26); # Emeric Deutsch, Oct 16 2006
  • Mathematica
    f[ A_ ] := Module[ {til = A, sum}, sum = 2* Apply[ Plus, Drop[ til, -4 ] ]; AppendTo[ til, A[ [ -1 ] ] + 4A[ [ -2 ] ] + 4A[ [ -3 ] ] + 3A[ [ -4 ] ] + sum ] ]; NumOfTilings[ n_ ] := Nest[ f, {1, 1, 5, 13}, n - 2 ]; NumOfTilings[ 30 ]

Formula

a(n) = a(n-1)+4*a(n-2)+4*a(n-3)+3*a(n-4)+2*( a(n-5)+a(n-6)+...+a(0)), a(0)=a(1)=1, a(2)=5, a(3)=13
a(n) = 2*a(n-1)+3*a(n-2)-a(n-4)-a(n-5). G.f.=(1-z)/((1+z)*(1-3*z+z^4)). - Emeric Deutsch, Oct 16 2006

A359019 Number of inequivalent tilings of a 3 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 21, 39, 82, 163, 347, 717, 1533, 3232, 6927, 14748, 31645, 67690, 145322, 311535, 668997, 1435645, 3083301, 6619842, 14218066, 30533005, 65580338, 140847132, 302522253, 649759735, 1395611508, 2997573501, 6438470626, 13829057884, 29703388721, 63799607283, 137035047576, 294336860797, 632205714741
Offset: 0

Views

Author

John Mason, Dec 12 2022

Keywords

Examples

			a(4) is 6 because of:
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | | | | |
  +-+-+-+ +     + +   +-+ +   +-+ +   +-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | |   | |
  +-+-+-+ +     + +-+-+-+ +-+-+-+ +-+-+-+ +   +-+
  | | | | |     | |   | | | |   | | | | | |   | |
  +-+-+-+ +-+-+-+ +   +-+ +-+   + +-+-+-+ +-+-+-+
  | | | | |     | |   | | | |   | | | | | | | | |
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+

Links

Crossrefs

Column k = 3 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.
Cf. A000930.

Formula

For n <= 1, a(n)=1;
otherwise for odd n > 1, a(n)=(A002478(n) + A000930(n) + 2 * A002478((n - 1) / 2) + 2 * A002478((n - 3) / 2)) / 4
and for even n, a(n)=(A002478(n) + A000930(n) + 2 * A002478((n - 2) / 2) + 2 * A002478(n / 2)) / 4
Alternatively, from Walter Trump:
For n <= 1, a(n)=1;
otherwise for odd n > 1, a(n)=(A000930(2n) + A000930(n) + 2 * A000930(n - 1) + 2 * A000930(n - 3)) / 4
and for even n, a(n)=(A000930(2n) + 2 * A000930(n - 2) + 3 * A000930(n)) / 4

A359020 Number of inequivalent tilings of a 4 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 4, 6, 13, 39, 115, 295, 861, 2403, 7048, 20377, 60008, 175978, 519589, 1532455, 4531277, 13395656, 39639758, 117301153, 347248981, 1028011708, 3043852214, 9012879842, 26689014028, 79033362580, 234045889421, 693101137571, 2052569508948
Offset: 0

Views

Author

John Mason, Dec 12 2022

Keywords

Examples

			a(3) is 6 because of:
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | | | | |
  +-+-+-+ +     + +   +-+ +   +-+ +   +-+ +-+-+-+
  | | | | |     | |   | | |   | | |   | | |   | |
  +-+-+-+ +     + +-+-+-+ +-+-+-+ +-+-+-+ +   +-+
  | | | | |     | |   | | | |   | | | | | |   | |
  +-+-+-+ +-+-+-+ +   +-+ +-+   + +-+-+-+ +-+-+-+
  | | | | |     | |   | | | |   | | | | | | | | |
  +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+

Links

Crossrefs

Column k = 4 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

Formula

For even n > 4
a(n) = (A054856(n) + compo(n) + 4 * A054856((n - 2) / 2) +
2 * A054856((n - 4) / 2) + 2 * A054856(n / 2) +
2 * Sum_{k=0..(n - 2) / 2} (A054856(k))) / 4
For odd n > 4
a(n) = (A054856(n) + compo(n) + 2 * A054856((n - 3) / 2) +
2 * A054856((n - 1) / 2) + 2 * Sum_ {k=0..(n - 3) / 2} (A054856(k))) / 4
Where compo(n) is the number of distinct compositions of n as a sum of 1, 2, (1+1) and 4.

A359021 Number of inequivalent tilings of a 5 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 5, 10, 39, 77, 521, 1985, 8038, 32097, 130125, 525676, 2131557, 8635656, 35017970, 141968455, 575692056, 2334344849, 9465939422, 38384559168, 155652202456, 631178976378, 2559476952229, 10378857744374, 42087027204278, 170665938023137, 692062856184512
Offset: 0

Views

Author

John Mason, Dec 12 2022

Keywords

Examples

			a(2) is 5 because of:
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
  | | | |   | |   | |   | |   |
  +-+-+ +-+-+ +   + +   + +-+-+
  | | | |   | |   | |   | |   |
  +-+-+ +   + +-+-+ +-+-+ +   +
  | | | |   | |   | | | | |   |
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
  | | | |   | |   | | | | | | |
  +-+-+ +   + +   + +-+-+ +-+-+
  | | | |   | |   | | | | | | |
  +-+-+ +-+-+ +-+-+ +-+-+ +-+-+

Links

Crossrefs

Column k = 5 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.
Cf. A079975.

Formula

For even n > 5:
a(n) = (A054857(n) + A079975(n) + 2*A054857(n/2) + 2* fixed_md(n/2) + 2*A054857((n-4)/2) + 4*A054857((n-2)/2) + 2* (A054857((n/2)-1) + fixed_md((n/2)-1)))/4.
For odd n > 5:
a(n) = (A054857(n) + A079975(n) + 2*A054857((n-1)/2) + 4*A054857((n-3)/2) + 2*fixed_md((n-3)/2) + 2*A054857((n-5)/2) + 2*fixed_md((n-1)/2))/4.
where
fixed_md(1)=1, fixed_md(2)=3, fixed_md(3)=15 and for n > 3, fixed_md(n) = A054857(n-1) + A054857(n-2) + fixed_md(n-2)+ fixed_md(n-1) + 2*A054857(n-3) + fixed_md(n-3).

A359022 Number of inequivalent tilings of a 6 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 9, 21, 115, 521, 1494, 15129, 83609, 459957, 2551794, 14150081, 78597739
Offset: 0

Views

Author

John Mason, Dec 12 2022

Keywords

Crossrefs

Column k = 6 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359023 Number of inequivalent tilings of a 7 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 12, 39, 295, 1985, 15129, 56978, 861159, 6542578, 49828415
Offset: 0

Views

Author

John Mason, Dec 12 2022

Keywords

Crossrefs

Column k = 7 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359024 Number of inequivalent tilings of an 8 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 21, 82, 861, 8038, 83609, 861159, 4495023
Offset: 0

Views

Author

John Mason, Dec 12 2022

Keywords

Crossrefs

Column k = 8 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.

A359025 Number of inequivalent tilings of a 9 X n rectangle using integer-sided square tiles.

Original entry on oeis.org

1, 1, 30, 163, 2403, 32097, 459957, 6542578, 93604244
Offset: 0

Views

Author

John Mason, Dec 12 2022

Keywords

Crossrefs

Column k = 9 of A227690.
Sequences for fixed and free (inequivalent) tilings of m X n rectangles, for 2 <= m <= 10:
Fixed: A000045, A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
Free: A001224, A359019, A359020, A359021, A359022, A359023, A359024, A359025, A359026.
Showing 1-10 of 14 results. Next

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

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