A116732 -id:A116732 - cp's OEIS frontend

A116201 a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4); a(0)=0, a(1)=1, a(2)=1, a(3)=1.

0, 1, 1, 1, 3, 4, 7, 13, 21, 37, 64, 109, 189, 325, 559, 964, 1659, 2857, 4921, 8473, 14592, 25129, 43273, 74521, 128331, 220996, 380575, 655381, 1128621, 1943581, 3347008, 5763829, 9925797, 17093053, 29435671, 50690692, 87293619, 150326929, 258875569

Offset: 0

R. K. Guy, Mar 23 2008

This is a divisibility sequence; that is, if n divides m then a(n) divides a(m). - T. D. Noe, Dec 22 2008
This is the case P1 = 1, P2 = -3, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 31 2014
Also, the inverse radii of a family of spheres defined as follows: the first three spheres have radius of 1 and touch each other and the common plane, while each subsequent sphere touches the three immediately preceding ones and the same plane. - Ivan Neretin, Sep 11 2018

			G.f. = x + x^2 + x^3 + 3*x^4 + 4*x^5 + 7*x^6 + 13*x^7 + 21*x^8 + ... - _Michael Somos_, Feb 26 2019

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
A. D. Mednykh, I. A. Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, arXiv preprint arXiv:1711.00175 [math.CO], 2017. See Section 4.
Wikipedia, Soddy-Gosset theorem.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (1,1,1,-1).

Cf. A100047, A116732, A135431.

a[0]:=0: a[1]:=1: a[2]:=1: a[3]:=1: for n from 4 to 35 do a[n]:= a[n-1]+a[n-2]+a[n-3]-a[n-4] end do: seq(a[n],n=0..35); # Emeric Deutsch, Apr 12 2008

a = {0, 1, 1, 1, 3}; Do[AppendTo[a, a[[ -1]]+a[[ -2]]+a[[ -3]]-a[[ -4]]], {80}]; a (* Stefan Steinerberger, Mar 24 2008 *)
CoefficientList[Series[(- x^3 + x)/(x^4 - x^3 - x^2 - x + 1), {x, 0, 50}], x] (* Vincenzo Librandi, Apr 02 2014 *)
a[ n_] := 1 - SeriesCoefficient[ (1 - 2 x) / (1 - 2 x + 2 x^4 - x^5), {x, 0, Abs@n}]; (* Michael Somos, Feb 26 2019 *)
LinearRecurrence[{1,1,1,-1},{0,1,1,1},50] (* Harvey P. Dale, Mar 26 2019 *)

{a(n) = n=abs(n); 1 - polcoeff( (1 - 2*x) / (1 - 2*x + 2*x^4 - x^5) + x * O(x^n), n)}; /* Michael Somos, Feb 26 2019 */

From R. J. Mathar, Mar 31 2008: (Start)
O.g.f: -x*(x-1)*(x+1)/(1 - x - x^2 - x^3 + x^4).
a(n) = A135431(n) - A135431(n-1). (End)
From Peter Bala, Mar 31 2014: (Start)
a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = (1 + sqrt(13))/4 and beta = (1 - sqrt(13))/4 and T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 3/4; 1, 1/2].
a(n) = U(n-1,(sqrt(3) + i)/4)*U(n-1,(sqrt(3) - i)/4), where U(n,x) denotes the Chebyshev polynomial of the second kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)
a(n) = a(-n) = A116732(n+2) - A116732(n), 0 = a(n) - 2*a(n+1) + 2*a(n+4) - a(n+5) for all n in Z. - Michael Somos, Feb 26 2019

A052527 Expansion of (1-x)/(1-x-x^2-x^3+x^4).

Original entry on oeis.org

1, 0, 1, 2, 2, 5, 8, 13, 24, 40, 69, 120, 205, 354, 610, 1049, 1808, 3113, 5360, 9232, 15897, 27376, 47145, 81186, 139810, 240765, 414616, 714005, 1229576, 2117432, 3646397, 6279400, 10813653, 18622018, 32068674, 55224945, 95101984

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

First differences of A116732 (shifted left 3 places). - R. J. Mathar, Nov 27 2011
a(n) is the number of ways to tile an n-board (a board with dimensions n X 1) using one type of domino, two types of straight tromino, and one type each of all other straight m-ominoes for m > 3. - Michael A. Allen, Sep 17 2020
Equivalently, a(n) is the number of compositions of n into parts >= 2 where there are two kinds of part 3. - Joerg Arndt, Sep 18 2020

G. C. Greubel, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 453
Index entries for linear recurrences with constant coefficients, signature (1,1,1,-1).

a:=[1,0,1,2];; for n in [5..40] do a[n]:=a[n-1]+a[n-2]+a[n-3] -a[n-4]; od; a; # G. C. Greubel, May 13 2019

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x)/(1-x-x^2-x^3+x^4) )); // G. C. Greubel, May 13 2019

spec := [S,{S=Sequence(Prod(Z,Z,Union(Z,Sequence(Z))))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

LinearRecurrence[{1,1,1,-1}, {1,0,1,2}, 40] (* G. C. Greubel, May 13 2019 *)

my(x='x+O('x^40)); Vec((1-x)/(1-x-x^2-x^3+x^4)) \\ G. C. Greubel, May 13 2019

((1-x)/(1-x-x^2-x^3+x^4)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 13 2019

G.f.: (1-x)/(1 - x - x^2 - x^3 + x^4).
a(n) = a(n+1) +a(n+2) +a(n+3) -a(n+4), a(0)=1, a(1)=0, a(2)=1, a(3)=2.
a(n) = Sum_{alpha = RootOf(1-x-x^2-x^3+x^4)} (1/39)*(2 + 11*alpha - 4*alpha^2 - alpha^3)*alpha^(-1-n).

More terms from James Sellers, Jun 05 2000

A135431 a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4) with a(0)=0, a(1)=1, a(2)=2 and a(3)=3.

Original entry on oeis.org

0, 1, 2, 3, 6, 10, 17, 30, 51, 88, 152, 261, 450, 775, 1334, 2298, 3957, 6814, 11735, 20208, 34800, 59929, 103202, 177723, 306054, 527050, 907625, 1563006, 2691627, 4635208, 7982216, 13746045, 23671842, 40764895, 70200566, 120891258, 208184877, 358511806

Offset: 0

Mohamed Bouhamida, Dec 13 2007

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1, 1, 1, -1).

LinearRecurrence[{1, 1, 1, -1}, {0, 1, 2, 3}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 03 2012 *)
nxt[{a_,b_,c_,d_}]:={b,c,d,d+c+b-a}; NestList[nxt,{0,1,2,3},40][[All,1]] (* Harvey P. Dale, Feb 28 2021 *)

From R. J. Mathar, Mar 31 2008: (Start)
O.g.f.: x*(1+x)/(1-x-x^2-x^3+x^4).
a(n) = A116732(n+1) + A116732(n+2). (End)

A239909 Arises from a construction of equiangular lines in complex space of dimension 2.

Original entry on oeis.org

1, 1, 2, 3, 5, 9, 15, 26, 45, 77, 133, 229, 394, 679, 1169, 2013, 3467, 5970, 10281, 17705, 30489, 52505, 90418, 155707, 268141, 461761, 795191, 1369386, 2358197, 4061013, 6993405, 12043229, 20739450, 35715071, 61504345, 105915637, 182395603, 314100514

Offset: 1

N. J. A. Sloane, Apr 09 2014

a(n+2) is the number of binary words of length n in which every run of zeros has length congruent to 1 modulo 3. - Ira M. Gessel, Jan 22 2025

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
G. McConnell, Some non-standard ways to generate SIC-POVMs in dimensions 2 and 3, arXiiv preprint arXiv:1402.7330, 2014, p. 4.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,-1).

Cf. A116732.

I:=[1,1,2,3]; [n le 4 select I[n] else Self(n-1)+Self(n-2)+Self(n-3)-Self(n-4): n in [1..50]];

LinearRecurrence[{1, 1, 1, -1}, {1, 1, 2, 3}, 40] (* or *) CoefficientList[Series[(1 - x^3)/(x^4 - x^3 - x^2 - x + 1), {x, 0, 100}], x] (* Vincenzo Librandi, Apr 09 2014 *)

From Vincenzo Librandi Apr 09 2014: (Start)
G.f.: x*(1-x^3)/(x^4-x^3-x^2-x+1).
a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4) for n>4.
a(n) = a(n-1) + 2*a(n-3) + A116732(n-5) for n>4. (End)

A260710 Expansion of 1/(1 - x - x^2 - x^4 + x^5 + x^7).

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 16, 25, 43, 69, 116, 188, 313, 511, 846, 1386, 2288, 3756, 6191, 10174, 16756, 27552, 45357, 74604, 122787, 201996, 332414, 546901, 899946, 1480699, 2436459, 4008858, 6596366, 10853563, 17858788, 29384804, 48350401, 79555943, 130902711

Offset: 0

David Neil McGrath, Jul 30 2015

This sequence counts partially ordered partitions of (n) into parts 1,2,3,4 where the order (position) of adjacent pairs of numbers (1,2);(2,3);(3,4) is unimportant. Alternatively the order of the complementary pairs (1,4);(1,3);(2,4) is important.

			There are 25 partially ordered partitions of 7, i.e., a(7) = 25. These are (43=34),(421=412),(124=214),(241),(142),(4111),(1411),(1141),(1114),(331),(313),(133),(1132=1123),(2131=1231),(1312=1321),(2311=3211),(31111),(13111),(11311),(11131),(11113),(2221=four),(22111=ten),(211111=six),(1111111).

Index entries for related partition-counting sequences
Index entries for linear recurrences with constant coefficients, signature (1,1,0,1,-1,0,-1).

Cf. A023435, A080239, A023434, A254685, A116732, A004695.

I:=[1,1,2,3,6,9,16]; [n le 7 select I[n] else Self(n-1)+Self(n-2)+Self(n-4)-Self(n-5)-Self(n-7): n in [1..40]]; // Vincenzo Librandi, Aug 04 2015

LinearRecurrence[{1, 1, 0, 1, -1, 0, -1}, {1, 1, 2, 3, 6, 9, 16}, 50] (* Vincenzo Librandi, Aug 04 2015 *)

Vec(1/(1 - x - x^2 - x^4 + x^5 + x^7) + O(x^50)) \\ Michel Marcus, Aug 06 2015

G.f: 1/(1 - x - x^2 - x^4 + x^5 + x^7).
a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-5) - a(n-7).
Construct the matrix array T(n,j) = [A^*j]*[S^*(j-1)] where A=(1,1,0,1,-1,0,-1) and S=(0,1,0,...) (A063524). [* is convolution operation] Define S^*0=I with I=(1,0,...). a(n) = Sum_{j=1..n} T(n,j).

cp's OEIS Frontend

A116201 a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4); a(0)=0, a(1)=1, a(2)=1, a(3)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A052527 Expansion of (1-x)/(1-x-x^2-x^3+x^4).

Views

Author

Keywords

Comments

Links

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A135431 a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4) with a(0)=0, a(1)=1, a(2)=2 and a(3)=3.

Views

Author

Keywords

Links

Programs

Mathematica

Formula

A239909 Arises from a construction of equiangular lines in complex space of dimension 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A260710 Expansion of 1/(1 - x - x^2 - x^4 + x^5 + x^7).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula