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-5 of 5 results.

A005178 Number of domino tilings of 4 X (n-1) board.

Original entry on oeis.org

0, 1, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, 51205, 145601, 413351, 1174500, 3335651, 9475901, 26915305, 76455961, 217172736, 616891945, 1752296281, 4977472781, 14138673395, 40161441636, 114079985111, 324048393905
Offset: 0

Views

Author

N. J. A. Sloane, David Singmaster, Frans J. Faase

Keywords

Comments

Or, number of perfect matchings in graph P_4 X P_{n-1}.
a(0) = 0, a(1) = 1 by convention.
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 = x + 4x^2 + 2x^3 + 3x^4 + 2x^5 + 3x^6 + 2x^7 + 3x^8 + ... = x + 4x^2 + x^3*(2+3x)/(1-x^2); then g.f. = 1/(1-g) = (1-x^2)/(1-x-5x^2-x^3+x^4). - Emeric Deutsch, Oct 16 2006
This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m). - T. D. Noe, Dec 22 2008
From Artur Jasinski, Dec 20 2008: (Start)
All numbers in this sequence are:
congruent to 0 mod 100 if n is congruent to 14 or 29 mod 30
congruent to 1 mod 100 if n is congruent to 0 or 1 or 12 or 16 or 27 or 28 mod 30
congruent to 5 mod 100 if n is congruent to 2 or 11 or 17 or 26 mod 30
congruent to 11 mod 100 if n is congruent to 3 or 25 mod 30
congruent to 36 mod 100 if n is congruent to 4 or 9 or 19 or 24 mod 30
congruent to 45 mod 100 if n is congruent to 8 or 20 mod 30
congruent to 51 mod 100 if n is congruent to 13 or 15 mod 30
congruent to 61 mod 100 if n is congruent to 10 or 18 mod 30
congruent to 81 mod 100 if n is congruent to 6 or 7 or 21 or 22 mod 30
congruent to 95 mod 100 if n is congruent to 5 or 23 mod 30
(End)
This is the case P1 = 1, P2 = -7, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 31 2014

Examples

			For n=2 the graph is
  o-o-o-o
and there is one perfect tiling:
  o-o o-o
For n=3 the graph is
  o-o-o-o
  | | | |
  o-o-o-o
and there are five perfect tilings:
  o o o o
  | | | |
  o o o o
two like:
  o o o-o
  | | ...
  o o o-o
and this
  o-o o-o
  .......
  o-o o-o
and this
  o o-o o
  | ... |
  o o-o o
a(n+1)=r(n)-r(n-2), r(n)=if n=0 then 1 else sum(sum(binomial(k,j)*sum(binomial(j,i-j)*5^(i-j)*binomial(k-j,n-i-3*(k-j))*(-1)^(n-i-3*(k-j)),i,j,n-k+j),j,0,k),k,1,n), n>1. - _Vladimir Kruchinin_, Sep 08 2010

References

  • F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • R. P. Stanley, Enumerative Combinatorics I, p. 292.

Links

Crossrefs

Row 4 of array A099390.
For all matchings see A033507.
Cf. A003775, A028468, A028469, A028470.
Cf. A003757. - T. D. Noe, Dec 22 2008
Bisection (odd part) gives A188899. - Alois P. Heinz, Oct 28 2012
Column k=2 of A250662.

Programs

  • Maple
    a[0]:=1: a[1]:=1: a[2]:=5: a[3]:=11: for n from 4 to 26 do a[n]:=a[n-1]+5*a[n-2]+a[n-3]-a[n-4] od: seq(a[n],n=0..26); # Emeric Deutsch, Oct 16 2006
A005178:=-(-1-4*z-z**2+z**3)/(1-z-5*z**2-z**3+z**4) # conjectured (correctly) by Simon Plouffe in his 1992 dissertation; gives sequence apart from an initial 1
  • Mathematica
    CoefficientList[Series[x(1-x^2)/(1-x-5x^2-x^3+x^4), {x,0,30}], x] (* T. D. Noe, Dec 22 2008 *)
LinearRecurrence[{1, 5, 1, -1}, {0, 1, 1, 5}, 28] (* Robert G. Wilson v, Aug 08 2011 *)
a[0] = 0; a[n_] := Product[2(2+Cos[2j Pi/5]+Cos[2k Pi/n]), {k, 1, (n-1)/2}, {j, 1, 2}] // Round;
Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Aug 20 2018 *)
  • Maxima
    r(n):=if n=0 then 1 else sum(sum(binomial(k,j)*sum(binomial(j,i-j)*5^(i-j)*binomial(k-j,n-i-3*(k-j))*(-1)^(n-i-3*(k-j)),i,j,n-k+j),j,0,k),k,1,n); a(n):=r(n)-r(n-2); /* Vladimir Kruchinin, Sep 08 2010 */

Formula

a(n) = a(n-1) + 5*a(n-2) + a(n-3) - a(n-4).
G.f.: x*(1 - x^2)/(1 - x - 5*x^2 - x^3 + x^4).
Limit_{n->oo} a(n)/a(n-1) = (1 + sqrt(29) + sqrt(14 + 2*sqrt(29)))/4 = 2.84053619409... - Philippe Deléham, Jun 12 2005
a(n) = (5*sqrt(29)/145)*(((1+sqrt(29)+sqrt(14+2*sqrt(29)))/4)^n+((1+sqrt(29)-sqrt(14+2*sqrt(29)))/4)^n-((1-sqrt(29)+sqrt(14-2*sqrt(29)))/4)^n-((1-sqrt(29)-sqrt(14-2*sqrt(29)))/4)^n). - Tim Monahan, Jul 30 2011
From Peter Bala, Mar 31 2014: (Start)
a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = (1 + sqrt(29))/4 and beta = (1 - sqrt(29))/4 and T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 7/4; 1, 1/2].
a(n) = U(n-1,i*(1 + sqrt(5))/4)*U(n-1,i*(1 - sqrt(5))/4), where U(n,x) denotes the Chebyshev polynomial of the second kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)
a(n) = A129113(n+2) - A129113(n). - R. J. Mathar, May 03 2021

Extensions

Amalgamated with (former) A003692, Dec 30 1995
Name changed and 0 prepended by T. D. Noe, Dec 22 2008
Edited by N. J. A. Sloane, Nov 15 2009

A210662 Triangle read by rows: T(n,k) (1 <= k <= n) = number of monomer-dimer tilings of an n X k board.

Original entry on oeis.org

1, 2, 7, 3, 22, 131, 5, 71, 823, 10012, 8, 228, 5096, 120465, 2810694, 13, 733, 31687, 1453535, 65805403, 2989126727, 21, 2356, 196785, 17525619, 1539222016, 135658637925, 11945257052321, 34, 7573, 1222550, 211351945, 36012826776, 6158217253688, 1052091957273408, 179788343101980135
Offset: 1

Views

Author

N. J. A. Sloane, Mar 28 2012

Keywords

Comments

The triangle is half of a symmetric square array, since T(n,k) = T(k,n).
Equivalently, ways of paving n X k grid cells using only singletons and dominoes. Also, the number of tilings of an n X k chessboard with the two polyominoes (0,0) and (0,0)+(0,1).
Also, matchings of the n X k grid graph. The n X k grid graph is also denoted P_m X P_n. For k=2, this is called the ladder graph L_n.
In statistical mechanics, this is a special case of the Monomer-Dimer Problem, which deals with monomer-dimer coverings of a finite patch of a lattice.
Right hand diagonal is A028420. Left hand diagonal is A000045.
Taken as a full square array, columns (and rows) 1-7 respectively match A000045(n+1), A030186, A033506(n-1), A033507(n-1), A033508(n-1), A033509(n-1), A033510(n-1), and have recurrences of order 2 3 6 9 20 36 72. - R. H. Hardin, Dec 11 2012

Examples

			Triangle begins:
1
2 7
3 22 131
5 71 823 10012
8 228 5096 120465 2810694
13 733 31687 1453535 65805403 2989126727
21 2356 196785 17525619 1539222016 135658637925 11945257052321
34 7573 1222550 211351945 36012826776 6158217253688 1052091957273408 179788343101980135...
The 7 matchings of the P(2) X P(2)-graph are:
  . .   .-.   . .   . .   . .   . .   .-.
              |       |         | |
  . .   . .   . .   . .   .-.   . .   .-.

References

  • Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
  • Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Links

Programs

  • Sage
    from sage.combinat.tiling import TilingSolver, Polyomino
def T(n, k):
    p = Polyomino([(0, 0)])
    q = Polyomino([(0, 0), (0, 1)])
    T = TilingSolver([p, q], box=[n, k], reusable=True)
    return T.number_of_solutions()
# Ralf Stephan, May 22 2014

Formula

T(1,n) = A000045(n+1), T(2,n) = A030186(n), T(3,n) = A033506(n), T(4,n) = A033507(n), T(5,n) = A033508(n), T(6,n) = A033509(n), T(7,n) = A033510(n), T(8,n) = A033511(n), T(9,n) = A033512(n), T(10,n) = A033513(n), T(11,n) = A033514(n), T(n,n) = A028420(n).

Extensions

Typo in term 27 corrected by Alois P. Heinz, Dec 03 2012
Reviewed by Ralf Stephan, May 22 2014

A033506 Number of matchings in graph P_{3} X P_{n}.

Original entry on oeis.org

1, 3, 22, 131, 823, 5096, 31687, 196785, 1222550, 7594361, 47177097, 293066688, 1820552297, 11309395995, 70254767718, 436427542283, 2711118571311, 16841658983944, 104621568809247, 649916534985369, 4037327172325542
Offset: 0

Views

Author

Per H. Lundow

Keywords

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 50, 999.
  • Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Links

Crossrefs

Column 3 of triangle A210662. Row sums of A100245.
Cf. A030186, A033507, A033508, A033509, A033510, A033511.

Programs

  • GAP
    a:=[1,3,22,131,823,5096];; for n in [7..30] do a[n]:=4*a[n-1] +14*a[n-2]-10*a[n-4]+a[n-6]; od; a; # G. C. Greubel, Oct 26 2019
  • Magma
    R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)) )); // G. C. Greubel, Oct 26 2019
  • Maple
    seq(coeff(series((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5 )), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 26 2019
  • Mathematica
    CoefficientList[Series[(1-2x-x^2)(1+x-x^2)/((1+x)(1-5x-9x^2+9x^3+x^4-x^5) ), {x, 0, 30}], x] (* Harvey P. Dale, Dec 05 2014 *)
LinearRecurrence[{4, 14, 0, -10, 0, 1}, {1, 3, 22, 131, 823, 5096}, 30] (* Harvey P. Dale, Dec 05 2014 *)
Table[RootSum[-1 +# +9#^2 -9#^3 -5#^4 +#^5 &, 1436541#^n + 3941068#^(n+1) -6086452#^(n+2) -2800519#^(n+3) +591744#^(n+4) &]/10204570 -(-1)^n/5, {n, 20}] (* Eric W. Weisstein, Oct 02 2017 *)
  • PARI
    my(x='x+O('x^30)); Vec((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2 +9*x^3+x^4-x^5))) \\ G. C. Greubel, Oct 26 2019
  • Sage
    def A033506_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)) ).list()
A033506_list(30) # G. C. Greubel, Oct 26 2019

Formula

G.f.: (1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)). - Sergey Perepechko, Apr 19 2013

A100265 Triangle read by rows: T(n,k) is the number of k-matchings in the P_4 X P_n lattice graph.

Original entry on oeis.org

1, 1, 3, 1, 1, 10, 29, 26, 5, 1, 17, 102, 267, 302, 123, 11, 1, 24, 224, 1044, 2593, 3388, 2150, 552, 36, 1, 31, 395, 2696, 10769, 25835, 36771, 29580, 12181, 2111, 95, 1, 38, 615, 5566, 31106, 111882, 261965, 395184, 372109, 206206, 60730, 7852, 281, 1, 45
Offset: 0

Views

Author

Emeric Deutsch, Dec 28 2004

Keywords

Comments

Row sums yield A033507. T(n,2n) yields A005178.

Examples

			T(2,4)=5 because in the graph P_4 X P_2 with vertices a(0,0), b(0,1), c(0,2),
d(0,3),a'(1,0),b'(1,1),c'(1,2),d'(1,3), we have the following 4-matchings
{aa',bb',cc',dd'},{aa',bb',cd,c'd'},{ab,a'b',cc',dd'},{ab,a'b',cd,c'd'} and {aa',bc,b'c',dd'} (perfect matchings, of course).
Triangle starts:
1;
1, 3, 1;
1, 10, 29, 26, 5;
1, 17, 102, 267, 302, 123, 11;
1, 24, 224, 1044, 2593, 3388, 2150, 552, 36;

References

  • H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices, J. Math. Physics 26 (1985) 157-167 (eq. (46) and Table VI).

Crossrefs

Cf. A033507, A005178.

Programs

  • Maple
    G:= - (1 + 3*z^3*t^4 + 11*z^3*t^5 + 6*z^3*t^6 - 2*z*t - 2*z*t^2 - 3*z^2*t^2 - 9*z^2*t^3 - 3*z^2*t^4 + z^7*t^14 + 3*z^4*t^6 + 5*z^4*t^7 + 2*z^4*t^8 - 3*z^5*t^8 - 3*z^5*t^9 - 5*z^5*t^10 - 2*z^6*t^11)/( - 1 + z + t^18*z^9 + z^3*t^2 + 4*z^3*t^3 - 4*z^3*t^4 - 27*z^3*t^5 - 15*z^3*t^6 + 5*z*t + 3*z*t^2 + 2*z^2*t + 13*z^2*t^2 + 21*z^2*t^3 + 5*z^2*t^4 - 2*z^7*t^11 - 3*z^7*t^12 - 9*z^7*t^13 - 9*z^7*t^14 - 3*z^4*t^4 - 18*z^4*t^5 - 41*z^4*t^6 - 40*z^4*t^7 - 9*z^4*t^8 - z^8*t^14 - z^8*t^16 + z^8*t^15 + 3*z^5*t^6 + 14*z^5*t^7 + 29*z^5*t^8 + 24*z^5*t^9 + 21*z^5*t^10 - z^6*t^8 + 6*z^6*t^10 + 19*z^6*t^11 + 5*z^6*t^12):
Gser:=simplify(series(G,z=0,11)): P[0]:=1: for n from 1 to 8 do P[n]:=coeff(Gser,z^n) od:for n from 0 to 8 do seq(coeff(t*P[n],t^k),k=1..2*n + 1) od; # yields sequence in triangular form

Formula

G.f.= (1 - zt^2)(z^6*t^12 + z^5*t^10 - 2z^5*t^9 - 4z^4*t^8 - 5z^4*t^7 - 3z^4*t^6 - 2z^3*t^6 + 4z^2*t^4 + 11z^2*t^3 + 3z^2*t^2 + zt^2 + 2zt - 1)/( - 1 + z + t^18*z^9 + z^3*t^2 + 4z^3*t^3 - 4z^3*t^4 - 27z^3*t^5 - 15z^3*t^6 + 5z*t + 3zt^2 + 2tz^2 + 13z^2*t^2 + 21z^2*t^3 + 5z^2*t^4 - 2z^7*t^11 - 3z^7*t^12 - 9z^7*t^13 - 9z^7*t^14 - 3z^4*t^4 - 18z^4*t^5 - 41z^4*t^6 - 40z^4*t^7 - 9z^4*t^8 - z^8*t^14 - z^8*t^16 + z^8*t^15 + 3z^5*t^6 + 14z^5*t^7 + 29z^5*t^8 + 24z^5*t^9 + 21z^5*t^10 - z^6*t^8 + 6z^6*t^10 + 19z^6*t^11 + 5z^6*t^12).
The row generating polynomials A[n] satisfy A[n] = (5t + 1 + 3t^2)A[n - 1] + (13t^2 + 21t^3 + 5t^4 + 2t)A[n - 2] + ( - 27t^5 - 15t^6 + t^2 - 4t^4 + 4t^3)A[n - 3] + ( - 40t^7 - 9t^8 - 41t^6 - 18t^5 - 3t^4)A[n - 4] + (29t^8 + 21t^10 + 3t^6 + 24t^9 + 14t^7)A[n - 5] + (6t^10 + 5t^12 - t^8 + 19t^11)A[n - 6] + ( - 9t^13 - 2t^11 - 3t^12 - 9t^14)A[n - 7] + ( - t^16 - t^14 + t^15)A[n - 8] + t^18*A[n - 9]

A260034 Number of configurations of the general monomer-dimer model for a 4 X 2n square lattice.

Original entry on oeis.org

1, 71, 10012, 1453535, 211351945, 30734932553, 4469527322891, 649966808093412, 94519361817920403, 13745178487929574337, 1998848998552669987841, 290676277692731170734063, 42270676011348793634137996, 6147079027705968859829472231, 893919476535411566264300633833
Offset: 0

Views

Author

N. J. A. Sloane, Jul 19 2015

Keywords

Links

Crossrefs

Bisection (even part) of A033507.

Programs

  • Mathematica
    LinearRecurrence[{163, -2641, 12479, -22577, 16705, -5331, 769, -47, 1}, {1, 71, 10012, 1453535, 211351945, 30734932553, 4469527322891, 649966808093412, 94519361817920403}, 20] (* Jean-François Alcover, Dec 15 2018 *)

Formula

G.f.: -(x^8 -36*x^7 +432*x^6 -2033*x^5 +4000*x^4 -3389*x^3 +1080*x^2 -92*x +1) / (x^9 -47*x^8 +769*x^7 -5331*x^6 +16705*x^5 -22577*x^4 +12479*x^3 -2641*x^2 +163*x -1). - Alois P. Heinz, Mar 07 2016

Extensions

a(0), a(5)-a(14) from Alois P. Heinz, Mar 07 2016
Showing 1-5 of 5 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.