OFFSET
1,2
COMMENTS
Arises from a problem of finding the number of inequivalent ways to pack a 2 X n rectangle with dominoes. The official solution is given in A060312. The present sequence gives the correct answer provided n != 2, when it gives 2 instead of 1. To put it another way, the present sequence gives the number of tilings of a 2 x n rectangle with dominoes when left-to-right mirror images are not regarded as distinct. - N. J. A. Sloane, Mar 30 2015
Also the number of inequivalent ways to tile a 2 X n rectangle with a combination of squares with sides 1 or 2. - John Mason, Nov 30 3022
Slavik V. Jablan observes that this is also the number of generating rational knots and links. See reference.
Also the number of distinct binding configurations on an n-site one-dimensional linear lattice, where the molecules cannot touch each other. This number determines the order of recurrence for the partition function of binding to a two-dimensional n X m lattice.
From Petros Hadjicostas, Jan 08 2018: (Start)
Consider Christian G. Bower's theory of transforms given in a weblink below. For each positive integer k and each input sequence (b(n): n>=1) with g.f. B(x) = Sum_{n>=1} b(n)*x^n, let (a_k(n): n>=1) = BIK[k](b(n): n>=1). (We thus change some of the notation in Bower's weblink.) Here, BIK[k] is the "reversible, indistinct, unlabeled" transform for k boxes.
If BIK[k](x) = Sum_{n>=1} a_k(n)*x^n is the g.f. of the output sequence, then it can be proved that BIK[k](x) = (B(x)^k + B(x^2)^{k/2})/2, when k is even, and = B(x)*BIK[k-1](x), when k is odd. (We assume BIK[0](x) = 1.)
If (a(n): n>=1) = BIK(b(n): n>=1) with g.f. BIK(x) = 1 + Sum_{n>=1} a(n)*x^n, then BIK(x) = 1 + Sum_{k>=1} BIK[k](x). (The addition of the extra 1 in the g.f. seems arbitrary.) We then get BIK(x) = 1 + (1/2)*(B(x)/(1 - B(x)) + (B(x) + B(x^2))/(1 - B(x^2))).
For this sequence, the input sequence satisfies b(1) = b(2) = 1 and b(n) = 0 for n >= 3. Hence, B(x) = x + x^2 and BIK(x) = (1+x)*(1-x-x^3)/((1-x-x^2)*(1-x^2-x^4)), which equals Christian G. Bower's g.f. in the formula section below. (End)
REFERENCES
S. Golomb, Polyominoes, Princeton Univ. Press 1994.
S. Jablan S. and R. Sazdanovic, LinKnot: Knot Theory by Computer, World Scientific Press, 2007.
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
T. D. Noe, Table of n, a(n) for n = 1..500
Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar, and Marko Petkovšek, Vertex and edge orbits of Fibonacci and Lucas cubes, arXiv:1407.4962 [math.CO], 2014.
M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard, and B. M. McCoy, Integrability vs non-integrability: Hard hexagons and hard squares compared, arXiv preprint 1406.5566 [math-ph], 2014.
Christian G. Bower, Transforms (2).
Petros Hadjicostas, Generalized colored circular palindromic compositions, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
S. V. Jablan, Geometry of Links, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29(3) (1999), 121-139. [Broken link]
S. V. Jablan, Geometry of Links, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29(3) (1999), 121-139.
Y. Kong, General recurrence theory of ligand binding on a three-dimensional lattice, J. Chem. Phys. Vol. 111 (1999), 4790-4799. (Table I)
W. E. Patten (proposer) and S. W. Golomb (solver), Problem E1470, "Covering a 2Xn rectangle with dominoes", Amer. Math. Monthly, 69 (1962), 61-62.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
J. Riordan, Letter, Jul 13 1970.
Index entries for linear recurrences with constant coefficients, signature (1,2,-1,0,-1,-1).
FORMULA
From Christian G. Bower, May 09 2000: (Start)
G.f.: (2-(x+x^2)^2)/(2*(1-x-x^2)) + (1+x+x^2)*(x^2+x^4)/(2*(1-x^2-x^4)).
"BIK" transform of x+x^2. (End)
If F(n) is the n-th Fibonacci number, then a(2n) = (F(2n+1) + F(n+2))/2 and a(2n+1) = (F(2n+2) + F(n+1))/2.
G.f.: (1+x)*(1-x-x^3)/((1-x-x^2)*(1-x^2-x^4)). (See the Comments section above.) - Petros Hadjicostas, Jan 08 2018
EXAMPLE
From Petros Hadjicostas, Jan 08 2018: (Start)
We give some examples to explain _Christian G. Bower's theory of transforms given in the weblink above. We have boxes of two sizes here: boxes that can hold one ball and boxes that can hold two balls. (This is because we want the BIK transform of x + x^2. See the comments above.) Two boxes of the same size are considered identical (indistinct and unlabeled). We place the boxes in a line that can be read in either direction. Here, a(n) = total number of ways of placing such boxes in such a line so that the total number of balls in the boxes is n.
When we have 4 balls in total inside the boxes, we have the following configurations of boxes in a line that can be read in either direction: 1111, 121, 211, and 22. (Note that 211 = 112.) Hence, a(4) = 4.
When n = 5, we have the following configurations of boxes: 11111, 2111, 1211, 221, and 212. Hence, a(5) = 5.
When n = 6, we have: 111111, 21111, 12111, 11211, 2211, 2121, 2112, 1221, and 222. Hence, a(6) = 9. (End)
MAPLE
with(combinat); F:=fibonacci;
f:=proc(n) option remember;
if n=2 then 1 # change this to 2 to get A001224
elif (n mod 2) = 0 then (F(n+1)+F(n/2+2))/2;
else (F(n+1)+F((n+1)/2))/2; fi; end;
[seq(f(n), n=1..50)];
A001224:=-(-1-z+2*z**2+z**3+z**4+z**5)/(z**4+z**2-1)/(z**2+z-1); # conjectured by Simon Plouffe in his 1992 dissertation
a:= n-> (Matrix([[5, 4, 2, 2, 1, 1]]). Matrix(6, (i, j)-> if (i=j-1) then 1 elif j=1 then [1, 2, -1, 0, -1, -1][i] else 0 fi)^n)[1, 6]: seq(a(n), n=1..38); # Alois P. Heinz, Aug 26 2008
MATHEMATICA
a[n_?EvenQ] := (Fibonacci[n + 1] + Fibonacci[n/2 + 2])/2; a[n_?OddQ] := (Fibonacci[n + 1] + Fibonacci[(n + 1)/2])/2; Table[a[n], {n, 38}] (* Jean-François Alcover, Oct 06 2011, after formula *)
LinearRecurrence[{1, 2, -1, 0, -1, -1}, {1, 2, 2, 4, 5, 9}, 38] (* Jean-François Alcover, Sep 21 2017 *)
PROG
(Magma) [(1/2)*((Fibonacci(n+1))+Fibonacci(((n+3+(-1)^n) div 2))): n in [1..40]]; // Vincenzo Librandi, Nov 23 2014
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Christian G. Bower, May 09 2000
Typo in references corrected by Jernej Azarija, Oct 23 2013
Edited by N. J. A. Sloane, Mar 30 2015
STATUS
approved