|
%I M0318 N0117 #146 Dec 06 2022 10:00:07
%S 1,2,2,4,5,9,12,21,30,51,76,127,195,322,504,826,1309,2135,3410,5545,
%T 8900,14445,23256,37701,60813,98514,159094,257608,416325,673933,
%U 1089648,1763581,2852242,4615823,7466468,12082291,19546175,31628466
%N 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.
%C 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
%C 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
%C Slavik V. Jablan observes that this is also the number of generating rational knots and links. See reference.
%C 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.
%C From _Petros Hadjicostas_, Jan 08 2018: (Start)
%C 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.
%C 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.)
%C 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))).
%C 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)
%D S. Golomb, Polyominoes, Princeton Univ. Press 1994.
%D S. Jablan S. and R. Sazdanovic, LinKnot: Knot Theory by Computer, World Scientific Press, 2007.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A001224/b001224.txt">Table of n, a(n) for n = 1..500</a>
%H Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar, and Marko Petkovšek, <a href="http://arxiv.org/abs/1407.4962">Vertex and edge orbits of Fibonacci and Lucas cubes</a>, arXiv:1407.4962 [math.CO], 2014.
%H M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard, and B. M. McCoy, <a href="http://arxiv.org/abs/1406.5566">Integrability vs non-integrability: Hard hexagons and hard squares compared</a>, arXiv preprint 1406.5566 [math-ph], 2014.
%H Christian G. Bower, <a href="/transforms2.html">Transforms (2)</a>.
%H Petros Hadjicostas, <a href="https://doi.org/10.2140/moscow.2020.9.173">Generalized colored circular palindromic compositions</a>, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
%H S. V. Jablan, <a href="http://www.ams.org./preprints/57/199706/199706-57-001-199706-57-001.html">Geometry of Links</a>, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29(3) (1999), 121-139. [Broken link]
%H S. V. Jablan, <a href="http://www.emis.de/journals/NSJOM/Papers/29_3/NSJOM_29_3_121_139.pdf">Geometry of Links</a>, XII Yugoslav Geometric Seminar (Novi Sad, 1998), Novi Sad J. Math. 29(3) (1999), 121-139.
%H Y. Kong, <a href="http://dx.doi.org/10.1063/1.479242">General recurrence theory of ligand binding on a three-dimensional lattice</a>, J. Chem. Phys. Vol. 111 (1999), 4790-4799. (Table I)
%H W. E. Patten (proposer) and S. W. Golomb (solver), <a href="http://www.jstor.org/stable/2312751">Problem E1470</a>, "Covering a 2Xn rectangle with dominoes", Amer. Math. Monthly, 69 (1962), 61-62.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H J. Riordan, <a href="/A001224/a001224.pdf">Letter, Jul 13 1970</a>.
%H N. J. A. Sloane, <a href="/A001224/a001224.png">Annotated scan of Monthly problem E1470 with illustration of a(4)=4 (Page 1)</a>.
%H N. J. A. Sloane, <a href="/A001224/a001224_1.png">Annotated scan of Monthly problem E1470 with illustration of a(4)=4 (Page 2)</a>.
%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1,0,-1,-1).
%F a(2n+1) = A051450(n+1) and a(2n) = A005207(n+1).
%F From _Christian G. Bower_, May 09 2000: (Start)
%F 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)).
%F "BIK" transform of x+x^2. (End)
%F 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.
%F 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
%e From _Petros Hadjicostas_, Jan 08 2018: (Start)
%e 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.
%e 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.
%e When n = 5, we have the following configurations of boxes: 11111, 2111, 1211, 221, and 212. Hence, a(5) = 5.
%e When n = 6, we have: 111111, 21111, 12111, 11211, 2211, 2121, 2112, 1221, and 222. Hence, a(6) = 9. (End)
%p # Maple code for A060312 and A001224 from _N. J. A. Sloane_, Mar 30 2015
%p with(combinat); F:=fibonacci;
%p f:=proc(n) option remember;
%p if n=2 then 1 # change this to 2 to get A001224
%p elif (n mod 2) = 0 then (F(n+1)+F(n/2+2))/2;
%p else (F(n+1)+F((n+1)/2))/2; fi; end;
%p [seq(f(n),n=1..50)];
%p 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
%p 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
%t 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 *)
%t LinearRecurrence[{1, 2, -1, 0, -1, -1}, {1, 2, 2, 4, 5, 9}, 38] (* _Jean-François Alcover_, Sep 21 2017 *)
%o (Magma) [(1/2)*((Fibonacci(n+1))+Fibonacci(((n+3+(-1)^n) div 2))): n in [1..40]]; // _Vincenzo Librandi_, Nov 23 2014
%Y Essentially the same as A060312, A068928 and A102526.
%K nonn,nice,easy
%O 1,2
%A _N. J. A. Sloane_
%E More terms from _Christian G. Bower_, May 09 2000
%E Typo in references corrected by _Jernej Azarija_, Oct 23 2013
%E Edited by _N. J. A. Sloane_, Mar 30 2015
|
