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.

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

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 9, 15, 25, 40, 64, 104, 169, 273, 441, 714, 1156, 1870, 3025, 4895, 7921, 12816, 20736, 33552, 54289, 87841, 142129, 229970, 372100, 602070, 974169, 1576239, 2550409, 4126648, 6677056, 10803704, 17480761, 28284465, 45765225, 74049690, 119814916
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of compositions of n into 1's, 3's and 4's. - Len Smiley, May 08 2001
The sum of any two alternating terms (terms separated by one term) produces a number from the Fibonacci sequence. (e.g. 4+9=13, 9+25=34, 6+15=21, etc.) Taking square roots starting from the first term and every other term after, we get the Fibonacci sequence. - Sreyas Srinivasan (sreyas_srinivasan(AT)hotmail.com), May 02 2002
(1 + x + 2*x^2 + x^3)/(1 - x - x^3 - x^4) = 1 + 2*x + 4*x^2 + 6*x^3 + 9*x^4 + 15*x^5 + 25*x^6 + 40*x^7 + ... is the g.f. for the number of binary strings of length where neither 101 nor 111 occur. [Lozansky and Rousseau] Or, equivalently, where neither 000 nor 010 occur.
Equivalently, a(n+2) is the number of length-n binary strings with no two set bits with distance 2; see fxtbook link. - Joerg Arndt, Jul 10 2011
a(n) is the number of words written with the letters "a" and "b", with the following restriction: any "a" must be followed by at least two letters, the second of which is a "b". - Bruno Petazzoni (bpetazzoni(AT)ac-creteil.fr), Oct 31 2005. [This is also equivalent to the previous two conditions.]
Let a(0) = 1, then a(n) = partial products of Product_{n>2} (F(n)/F(n-1))^2 = 1*1*2*2*(3/2)*(3/2)*(5/3)*(5/3)*(8/5)*(8/5)*.... E.g., a(7) = 15 = 1*1*1*2*2*(3/2)*(3/2)*(5/3). - Gary W. Adamson, Dec 13 2009
Number of permutations satisfying -k <= p(i) - i <= r and p(i)-i not in I, i=1..n, with k=1, r=3, I={1}. - Vladimir Baltic, Mar 07 2012
The 2-dimensional version, which counts sets of pairs no two of which are separated by graph-distance 2, is A273461. - Gus Wiseman, Nov 27 2019
a(n+1) is the number of multus bitstrings of length n with no runs of 4 ones. - Steven Finch, Mar 25 2020

Examples

			G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 6*x^5 + 9*x^6 + 15*x^7 + 25*x^8 + 40*x^9 + ...
From _Gus Wiseman_, Nov 27 2019: (Start)
The a(2) = 1 through a(7) = 15 subsets with no two elements differing by 2:
  {}  {}   {}     {}     {}     {}
      {1}  {1}    {1}    {1}    {1}
           {2}    {2}    {2}    {2}
           {1,2}  {3}    {3}    {3}
                  {1,2}  {4}    {4}
                  {2,3}  {1,2}  {5}
                         {1,4}  {1,2}
                         {2,3}  {1,4}
                         {3,4}  {1,5}
                                {2,3}
                                {2,5}
                                {3,4}
                                {4,5}
                                {1,2,5}
                                {1,4,5}
(End)

References

  • E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see pp. 157 and 172.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A060945 (for 1's, 2's and 4's). Essentially the same as A074677.
Diagonal sums of number triangle A059259.
Cf. A000032, A000034, A000045, A001654, A007598, A209398.
Numbers whose binary expansion has no subsequence (1,0,1) are A048716.
Cf. A003242, A005251, A027383, A167606, A261041, A273461, A329860, A329871.

Programs

  • Haskell
    a006498 n = a006498_list !! n
a006498_list = 1 : 1 : 1 : 2 : zipWith (+) (drop 3 a006498_list)
   (zipWith (+) (tail a006498_list) a006498_list)
-- Reinhard Zumkeller, Apr 07 2012
  • Magma
    [ n eq 1 select 1 else n eq 2 select 1 else n eq 3 select 1 else n eq 4 select 2 else Self(n-1)+Self(n-3)+ Self(n-4): n in [1..40] ]; // Vincenzo Librandi, Aug 20 2011
  • Mathematica
    LinearRecurrence[{1,0,1,1},{1,1,1,2},50] (* Harvey P. Dale, Jul 13 2011 *)
Table[Fibonacci[Floor[n/2] + 2]^Mod[n, 2]*Fibonacci[Floor[n/2] + 1]^(2 - Mod[n, 2]), {n, 0, 40}] (* David Nacin, Feb 29 2012 *)
a[ n_] := Fibonacci[ Quotient[ n+2, 2]] Fibonacci[ Quotient[ n+3, 2]] (* Michael Somos, Jan 19 2014 *)
Table[Length[Select[Subsets[Range[n]],!MatchQ[#,{_,x_,_,y_,_}/;x+2==y]&]],{n,10}] (* Gus Wiseman, Nov 27 2019 *)
  • PARI
    {a(n) = fibonacci( (n+2)\2 ) * fibonacci( (n+3)\2 )} /* Michael Somos, Mar 10 2004 */
  • PARI
    Vec(1/(1-x-x^3-x^4)+O(x^66))
  • Python
    def a(n, adict={0:1, 1:1, 2:1, 3:2}):
    if n in adict:
        return adict[n]
    adict[n]=a(n-1)+a(n-3)+a(n-4)
    return adict[n] # David Nacin, Mar 07 2012

Formula

G.f.: 1 / ((1 + x^2) * (1 - x - x^2)); a(2*n) = F(n+1)^2, a(2*n - 1) = F(n+1)*F(n). a(n) = a(-4-n) * (-1)^n. - Michael Somos, Mar 10 2004
The g.f. -(1+z+2*z^2+z^3)/((z^2+z-1)*(1+z^2)) for the truncated version 1, 2, 4, 6, 9, 15, 25, 40, ... was given in the Simon Plouffe thesis of 1992. [edited by R. J. Mathar, May 13 2008]
From Vladeta Jovovic, May 03 2002: (Start)
a(n) = round((-(1/5)*sqrt(5) - 1/5)*(-2*1/(-sqrt(5)+1))^n/(-sqrt(5)+1) + ((1/5)*sqrt(5) - 1/5)*(-2*1/( sqrt(5)+1))^n/(sqrt(5)+1)).
G.f.: 1/(1-x-x^2)/(1+x^2). (End)
a(n) = (-i)^n*Sum{k=0..n} U(n-2k, i/2) where i^2=-1. - Paul Barry, Nov 15 2003
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*F(n-2k+1). - Paul Barry, Oct 12 2007
F(floor(n/2) + 2)^(n mod 2)*F(floor(n/2) + 1)^(2 - (n mod 2)) where F(n) is the n-th Fibonacci number. - David Nacin, Feb 29 2012
a(2*n - 1) = A001654(n), a(2*n) = A007598(n+1). - Michael Somos, Mar 10 2004
a(n+1)*a(n+3) = a(n)*a(n+2) + a(n+1)*a(n+2) for all n in Z. - Michael Somos, Jan 19 2014
a(n) = round(1/(1/F(n+2) + 2/F(n+3))), where F(n) = A000045, and 0.5 is rounded to 1. - Richard R. Forberg, Aug 04 2014
5*a(n) = (-1)^floor(n/2)*A000034(n+1) + A000032(n+2). - R. J. Mathar, Sep 16 2017
a(n) = Sum_{j=0..floor(n/3)} Sum_{k=0..j} binomial(n-3j,k)*binomial(j,k)*2^k. - Tony Foster III, Sep 18 2017
E.g.f.: (2*cos(x) + sin(x) + exp(x/2)*(3*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2)))/5. - Stefano Spezia, Mar 12 2024

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

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