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

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

Offset

0,4

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 A006498 = 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

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

T. D. Noe, Table of n, a(n) for n = 0..500

Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).

D. Applegate, M. LeBrun, and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.

Said Amrouche and Hacène Belbachir, Unimodality and linear recurrences associated with rays in the Delannoy triangle, Turkish Journal of Mathematics (2019) Vol. 44, 118-130.

Joerg Arndt, Matters Computational (The Fxtbook), section 14.10.1, p.320.

Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135.

G. E. Bergum and V. E. Hoggatt, Jr., A combinatorial problem involving recursive sequences and tridiagonal matrices, Fib. Quart., 16 (1978), 113-118.

M. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461.

K. Edwards, A Pascal-like triangle related to the tribonacci numbers, Fib. Q., 46/47 (2008/2009), 18-25.

Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.

T. Guardia and D. Jiménez, Fiboquadratic Sequences and Extensions of the Cassini Identity Raised From the Study of Rithmomachia, arXiv preprint arXiv:1509.03177 [math.HO], 2015-2016.

Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.

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

M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.

Index entries for sequences related to Chebyshev polynomials.

Index entries for two-way infinite sequences

Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

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

Example

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)

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

Prog

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

Crossrefs

Cf. A060945 (for 1's, 2's and 4's). Essentially the same as A074677.

Diagonal sums of number triangle A059259.

Cf. A001654, A007598.

Cf. A209398.

Numbers whose binary expansion has no subsequence (1,0,1) are A048716.

Cf. A003242, A005251, A027383, A167606, A261041, A273461, A329860, A329871.

Sequence in context: A157679 A057602 A171646 * A074677 A179997 A101756

Adjacent sequences: A006495 A006496 A006497 * A006499 A006500 A006501

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved