The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A006498 a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2. (Formerly M1005) 58
 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 (list; graph; refs; listen; history; text; internal format)
 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 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 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 24 17:17 EDT 2022. Contains 356945 sequences. (Running on oeis4.)