|
| |
|
|
A005178
|
|
Number of domino tilings of 4 X (n-1) board.
(Formerly M3813)
|
|
27
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
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
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
|
|
|
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
|
|
|
|
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->infinity} 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
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)
|
|
|
EXAMPLE
|
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
|
|
|
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 *)
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;
|
|
|
PROG
|
(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 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Amalgamated with (former) A003692, Dec 30 1995
Name changed and 0 prepended by T. D. Noe, Dec 22 2008
|
|
|
STATUS
|
approved
|
| |
|
|
