A051450 -id:A051450 - cp's OEIS frontend

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.

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

N. J. A. Sloane

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)

			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)

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

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

Essentially the same as A060312, A068928 and A102526.

Cf. A000045.

[(1/2)*((Fibonacci(n+1))+Fibonacci(((n+3+(-1)^n) div 2))): n in [1..40]]; // Vincenzo Librandi, Nov 23 2014

# 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

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

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)

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

A056014 a(n) = (Fibonacci(2n-1) - Fibonacci(n+1))/2.

Original entry on oeis.org

0, 0, 0, 1, 4, 13, 38, 106, 288, 771, 2046, 5401, 14212, 37324, 97904, 256621, 672336, 1760997, 4611642, 12075526, 31617520, 82781215, 216732890, 567428401, 1485570024, 3889310328, 10182407328, 26657986681, 69791674108

Offset: 0

Asher Auel, Jun 06 2000

With a(0)=0, a(1)=1, a(2)=1, a(3)=2, this recurrence produces a(n)=A000045(n) (Fibonacci numbers).

Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 1, s(n) = 4. - Herbert Kociemba, Jun 16 2004

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Éva Czabarka, Rigoberto Flórez, and Leandro Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), Article 15.1.6.
Henrik Eriksson and Markus Jonsson, Level sizes of the Bulgarian solitaire game tree, Fib. Q., 35:3 (2017), 243-251.
Hideyuki Othsuka, Problem B-1345, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 62, No. 1 (2024), p. 85.
Index entries for linear recurrences with constant coefficients, signature (4,-3,-2,1).

Cf. A000045, A000079, A051450, A056015, A094966.

a(1-2n)=A059512(2n), a(-2n)=A027994(2n-1).

I:=[0, 0, 0, 1]; [n le 4 select I[n] else 4*Self(n-1)-3*Self(n-2)-2*Self(n-3)+Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jun 23 2012

Table[(Fibonacci[2n-1]-Fibonacci[n+1])/2,{n,0,40}]  (* Harvey P. Dale, Mar 24 2011 *)
LinearRecurrence[{4,-3,-2,1},{0,0, 0,1},40] (* Vincenzo Librandi, Jun 23 2012 *)

a(n)=(fibonacci(2*n-1)-fibonacci(n+1))/2

a(n) = 4*a(n-1) - 3*a(n-2) - 2*a(n-3) + a(n-4), a(0)=a(1)=a(2)=0, a(3)=1.
Convolution of Fibonacci numbers F(n) with F(2n). - Benoit Cloitre, Jun 07 2004
G.f.: x^3/((1 - x - x^2)*(1 - 3*x + x^2)). - Herbert Kociemba, Jun 16 2004
Binomial transform of x^3/(1-3x^2+x^4), or (essentially) F(2n) with interpolated zeros. a(n)=sum{k=0..n, binomial(n, k)((3/2-sqrt(5)/2)^(k/2)((sqrt(5)/20+1/4)(-1)^k-sqrt(5)/20-1/4)+ (sqrt(5)/2+3/2)^(k/2)((sqrt(5)/20-1/4)(-1)^k-sqrt(5)/20+1/4))}. - Paul Barry, Jul 26 2004
Convolution of the powers of 2 (A000079) with the number of positive rational knots with 2n+1 crossings (A051450), with three leading zeros. - Graeme McRae, Jun 28 2006
a(n) = (A001519(n) - A000045(n+1))/2. - R. J. Mathar, Jun 24 2011
a(n) = Sum_{k=1..n-1} binomial(n-1, k) * A094966(k-1) (Othsuka, 2024). - Amiram Eldar, Feb 29 2024

A078477 Number of rational knots with n crossings and unknotting number = 1 (chiral pairs counted only once).

Original entry on oeis.org

1, 1, 1, 3, 3, 6, 7, 15, 15, 30, 31, 63, 63, 126, 127, 255, 255, 510, 511, 1023, 1023, 2046, 2047, 4095, 4095, 8190, 8191, 16383, 16383, 32766, 32767, 65535, 65535, 131070, 131071, 262143, 262143, 524286, 524287, 1048575, 1048575, 2097150, 2097151

Offset: 3

Ralf Stephan, Jan 03 2003

From Alexander Adamchuk, Nov 16 2009: (Start)
For n>1 a(2n+1) = 2^(n-1) - 1 = A000225(n-1).
For n>1 a(4n) = a(4n+1) - 1 = 2^(2n-1) - 2.
For n>0 a(4n+2) = a(4n+3) = 2^(2n) - 1. (End)

Andrey Zabolotskiy, Table of n, a(n) for n = 3..1000
A. Stoimenow, Generating Functions, Fibonacci Numbers and Rational Knots, Journal of Algebra, 310 (2007), 491-525; arXiv:math/0210174 [math.GT], 2002.
Index entries for linear recurrences with constant coefficients, signature (0,2,0,1,0,-2).

Cf. A000225, A018240, A089891, A089892, A089797, A051449, A214927, A051450, A078478.

CoefficientList[Series[(2 x^7 + 2 x^6 - x^5 + x^3 - x^2 + x + 1) / ((x-1) (x+1) (x^2+1) (2 x^2-1)), {x, 0, 50}], x] (* Vincenzo Librandi, May 17 2013 *)

Vec(x^3*(1+x-x^2+x^3-x^5+2*x^6+2*x^7)/((1-x)*(1+x)*(1+x^2)*(1-2*x^2)) + O(x^60)) \\ Colin Barker, Dec 26 2015

G.f.: x^3*(1+x-x^2+x^3-x^5+2*x^6+2*x^7) / ((1-x)*(1+x)*(1+x^2)*(1-2*x^2)).

a(n) = 2*a(n-2)+a(n-4)-2*a(n-6) for n>10. - Colin Barker, Dec 26 2015

A102526 Antidiagonal sums of Losanitsch's triangle (A034851).

Original entry on oeis.org

1, 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: 0

Gerald McGarvey, Feb 24 2005

This is an interleaving of A005207 and A051450. Thus a(2*m) = A005207(m) = (F(2*m-1) + F(m+1)) / 2, a(2*m - 1) = A051450(m) = (F(2*m) + F(m)) / 2 where F() are Fibonacci numbers (A000045). - Max Alekseyev, Jun 28 2006
The Kn11(n) and Kn21(n) sums, see A180662 for their definitions, of Losanitsch's triangle A034851 equal a(n), while the Kn12(n) and Kn22(n) sums equal (a(n+2)-A000012(n)) and the Kn13(n) and Kn23(n) sums equal (a(n+4)-A008619(n+4)). - Johannes W. Meijer, Jul 14 2011
a(n) is the number of homeomorphically irreducible caterpillars with n + 3 edges. - Christian Barrientos, Sep 12 2020

Jablan S. and Sazdanovic R., LinKnot: Knot Theory by Computer, World Scientific Press, 2007.

Johann Cigler, Some remarks on Rogers-Szegö polynomials and Losanitsch's triangle, arXiv:1711.03340 [math.CO], 2017.
Index entries for linear recurrences with constant coefficients, signature (1,2,-1,0,-1,-1).

Cf. A034851.

Essentially the same as A001224, A060312 and A068928.

with(combinat): A102526 :=proc(n): if type(n, even) then (fibonacci(n+1)+fibonacci(n/2+2))/2 else (fibonacci(n+1)+fibonacci((n+1)/2))/2 fi: end: seq(A102526(n), n=0..38); # Johannes W. Meijer, Jul 14 2011

LinearRecurrence[{1, 2, -1, 0, -1, -1}, {1, 1, 2, 2, 4, 5}, 40] (* Jean-François Alcover, Nov 17 2017 *)

Vec((1+x)*(1-x-x^3)/(x^2+x-1)/(x^4+x^2-1)+O(x^99)) \\ Charles R Greathouse IV, Nov 17 2017

a(n)=([0,1,0,0,0,0; 0,0,1,0,0,0; 0,0,0,1,0,0; 0,0,0,0,1,0; 0,0,0,0,0,1; -1,-1,0,-1,2,1]^n*[1;1;2;2;4;5])[1,1] \\ Charles R Greathouse IV, Nov 17 2017

G.f.: -(1+x)*(x^3+x-1) / ( (x^2+x-1)*(x^4+x^2-1) ). - R. J. Mathar, Nov 09 2013

a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-5) - a(n-6). - Wesley Ivan Hurt, Sep 17 2020

A192464 Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) = 1 + x^n + x^(2n).

Original entry on oeis.org

2, 4, 7, 16, 38, 95, 242, 624, 1619, 4216, 11002, 28747, 75170, 196652, 514607, 1346880, 3525566, 9229063, 24160402, 63250168, 165586907, 433505384, 1134920882, 2971243731, 7778788418, 20365086100, 53316412567, 139584058864, 365435613974, 956722540271

Offset: 1

Clark Kimberling, Jul 01 2011

For an introduction to reductions of polynomials by substitutions such as x^2->x+1, see A192232. The coefficient of x in the reduction by x^2->x+1 of the polynomial p(n,x) = 1 + x^n + x^(2n) is 2*A051450.

			The first four polynomials p(n,x) and their reductions are as follows:
p(1,x) = 1 + x   + x^2 ->  2 +  2x
p(2,x) = 1 + x^2 + x^4 ->  4 +  4x
p(3,x) = 1 + x^3 + x^6 ->  7 + 10x
p(4,x) = 1 + x^4 + x^8 -> 16 + 24x.
From these, read
A192464 = (2, 4, 7, 16, ...) and 2*A051450 = (2, 4, 10, 24, ...).

Index entries for linear recurrences with constant coefficients, signature (5,-7,1,3,-1).

Cf. A000045, A192232, A051450.

Remove["Global`*"];
q[x_] := x + 1; p[n_, x_] := 1 + x^n + x^(2 n);
Table[Simplify[p[n, x]], {n, 1, 5}]
reductionRules = {x^y_?EvenQ -> q[x]^(y/2),
   x^y_?OddQ -> x q[x]^((y - 1)/2)};
t = Table[FixedPoint[Expand[#1 /. reductionRules] &, p[n, x]], {n, 1, 30}]
Table[Coefficient[Part[t, n], x, 0], {n, 1, 30}]
(* A192464 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 30}]
(* 2*A051450 *)
Table[Coefficient[Part[t, n]/2, x, 1], {n, 1, 30}]
(* A051450 *)
Table[1-Fibonacci[n]+Fibonacci[1+n]-Fibonacci[2n]+Fibonacci[1+2n], {n, 1, 29}]
(* Friedjof Tellkamp, Nov 22 2021 *)

G.f.: -x*(3*x^4-7*x^3-x^2+6*x-2)/((x-1)*(x^2-3*x+1)*(x^2+x-1)). - Colin Barker, Nov 12 2012

a(n) = 1 - Fibonacci(n) + Fibonacci(1+n) - Fibonacci(2n) + Fibonacci(1+2n). - Friedjof Tellkamp, Nov 22 2021

A062135 Odd-numbered columns of Losanitsch triangle A034851 formatted as triangle with an additional first column.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 2, 6, 3, 1, 0, 3, 10, 12, 4, 1, 0, 3, 19, 28, 20, 5, 1, 0, 4, 28, 66, 60, 30, 6, 1, 0, 4, 44, 126, 170, 110, 42, 7, 1, 0, 5, 60, 236, 396, 365, 182, 56, 8, 1, 0, 5, 85, 396, 868, 1001, 693, 280, 72, 9, 1

Offset: 0

Wolfdieter Lang, Jun 19 2001

Because the sequence of column m=2*k, k >= 1, of A034851 is the partial sum sequence of the one of column m=2*k-1 the present triangle is essentially Losanitsch's triangle A034851.

Row sums give A051450 with A051450(0) := 1. Column sequences (without leading zeros) are for m=0..6: A000007, A008619, A005993, A005995, A018211, A018213, A062136.

			Triangle begins:
  {1};
  {0,1};
  {0,1,1};
  {0,2,2,1};
  ...
Pe(4,x^2)=1+6*x^2+x^4.

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows n = 0..150, flattened)

Cf. A034851, A034839.

t[n_?EvenQ, k_?OddQ] := Binomial[n, k]/2; t[n_, k_] := (Binomial[n, k] + Binomial[Quotient[n, 2], Quotient[k, 2]])/2; Flatten[Table[t[n - 1 + m, n - m], {n, 0, 12}, {m, 0, n}]] (* Michael De Vlieger, Sep 28 2024, after Jean-François Alcover at A034851  *)

T(n, m) = A034851(n-1+m, n-m), n >= m >= 0; A034851(n-1, n) := 0, n >= 1, A034851(-1, 0) := 1.
T(n, m) = 0 if n= 1; T(n, m) = T(n-1, m)+sum(T(k, m-1), k=m-1..n-1) if n+m even and T(n, m) = T(n-1, m)+sum(T(k, m-1), k=m-1..n-1)-binomial((n+m-3)/2, m-1) if n+m odd, n >= m >= 1.
G.f. for column m: x^m*Pe(m, x^2)/(((1-x)^(2*m))*(1+x)^m), m >= 0, with Pe(m, x^2)= sum(A034839(m, k)*x^(2*k), k=0..floor(n/2)), the row polynomial of array A034839 (even-indexed entries of the rows of Pascal's triangle).

More terms from Michael De Vlieger, Sep 28 2024

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A056014 a(n) = (Fibonacci(2n-1) - Fibonacci(n+1))/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A078477 Number of rational knots with n crossings and unknotting number = 1 (chiral pairs counted only once).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A102526 Antidiagonal sums of Losanitsch's triangle (A034851).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A192464 Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) = 1 + x^n + x^(2n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A062135 Odd-numbered columns of Losanitsch triangle A034851 formatted as triangle with an additional first column.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A094039 Binomial transform of (Jacobsthal(n) + 2^n*Jacobsthal(-n))/2.

Views

Author

Keywords