

A001224


If F(n) is the nth Fibonacci number, then a(2n)=(F(2n+1)+F(n+2))/2 and a(2n+1)=(F(2n+2)+F(n+1))/2.
(Formerly M0318 N0117)


10



1, 2, 2, 4, 5, 9, 12, 21, 30, 51, 76, 127, 195, 322, 504, 826, 1309, 2135, 3410, 5545, 8900, 14445, 23256, 37701, 60813, 98514, 159094, 257608, 416325, 673933, 1089648, 1763581, 2852242, 4615823, 7466468, 12082291, 19546175, 31628466
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Arises from 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 lefttoright mirror images are not regarded as distinct.  N. J. A. Sloane, Mar 30 2015
Slavik V. Jablan (jablans(AT)yahoo.com) observes that this is also number of generating rational knots and links. See reference.
Also the number of distinct binding configurations on an nsite onedimensional linear lattice, where the molecules cannot touch each other. This number determines the order of recurrence for the partition function of binding to a twodimensional n X m lattice.
From Petros Hadjicostas, Jan 08 2018: (Start)
Consider C. 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[k1](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)*(1xx^3)/((1xx^2)*(1x^2x^4)), which equals Bower's g.f. in the formula section below.
(End)


REFERENCES

S. Golomb, Polyominoes, Princeton Univ. Press 1994.
Jablan S. and Sazdanovic R., 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, 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 nonintegrability: Hard hexagons and hard squares compared, arXiv preprint 1406.5566 [mathph], 2014.
C. G. Bower, Transforms (2)
S. V. Jablan, Geometry of Links, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29 (1999), no. 3, 121139.
Y. Kong, General recurrence theory of ligand binding on a threedimensional lattice, J. Chem. Phys. Vol. 111 (1999), pp. 47904799. (Table I)
W. E. Patten (proposer) and S. W. Golomb (solver), Problem E1470, "Covering a 2Xn rectangle with dominoes", Amer. Math. Monthly, 69 (1962), 6162.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.
J. Riordan, Letter, Jul 13 1970
N. J. A. Sloane, Annotated scan of Monthly problem E1470 with illustration of a(4)=4 (Page 1)
N. J. A. Sloane, Annotated scan of Monthly problem E1470 with illustration of a(4)=4 (Page 2)
Index entries for sequences related to dominoes
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*(1xx^2)) + (1+x+x^2)*(x^2+x^4)/(2*(1x^2x^4)).
"BIK" transform of x+x^2. (End)
If F(n) is the nth 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)*(1xx^3)/((1xx^2)*(1x^2x^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 C. 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

# Maple code for A060312 and A001224 from N. J. A. Sloane, Mar 30 2015
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:=(1z+2*z**2+z**3+z**4+z**5)/(z**4+z**21)/(z**2+z1); # conjectured by Simon Plouffe in his 1992 dissertation
a:= n> (Matrix([[5, 4, 2, 2, 1, 1]]). Matrix(6, (i, j)> if (i=j1) 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}] (* JeanFrançois Alcover, Oct 06 2011, after formula *)
LinearRecurrence[{1, 2, 1, 0, 1, 1}, {1, 2, 2, 4, 5, 9}, 38] (* JeanFranç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

Essentially the same as A060312, A068928 and A102526.
Sequence in context: A124280 A088518 * A102526 A050192 A191786 A007147
Adjacent sequences: A001221 A001222 A001223 * A001225 A001226 A001227


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


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



