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.

A001224 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.

Original entry on oeis.org

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
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

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 2022
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)

Examples

			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)

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

Crossrefs

Essentially the same as A060312, A068928 and A102526.
Cf. A000045.

Programs

  • Magma
    [(1/2)*((Fibonacci(n+1))+Fibonacci(((n+3+(-1)^n) div 2))): n in [1..40]]; // Vincenzo Librandi, Nov 23 2014
  • 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:=-(-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 *)

Formula

a(2n+1) = A051450(n+1) and a(2n) = A005207(n+1).
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
From Manfred Boergens, Aug 25 2025: (Start)
a(n) = (Fibonacci(n+1) + Fibonacci(floor((n+3+(-1)^n)/2)))/2.
a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-5) - a(n-6). (End)

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.