|
%I M1005 #149 Mar 12 2024 09:30:31
%S 1,1,1,2,4,6,9,15,25,40,64,104,169,273,441,714,1156,1870,3025,4895,
%T 7921,12816,20736,33552,54289,87841,142129,229970,372100,602070,
%U 974169,1576239,2550409,4126648,6677056,10803704,17480761,28284465,45765225,74049690,119814916
%N a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.
%C Number of compositions of n into 1's, 3's and 4's. - _Len Smiley_, May 08 2001
%C 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
%C (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.
%C 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
%C 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.]
%C 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
%C 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
%C 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
%C a(n+1) is the number of multus bitstrings of length n with no runs of 4 ones. - _Steven Finch_, Mar 25 2020
%D E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see pp. 157 and 172.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A006498/b006498.txt">Table of n, a(n) for n = 0..500</a>
%H Katharine A. Ahrens, <a href="https://repository.lib.ncsu.edu/bitstream/handle/1840.20/37364/etd.pdf">Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis</a>, Ph. D. thesis, North Carolina State University (2020).
%H D. Applegate, M. LeBrun, and N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Sloane/carry2.html">Dismal Arithmetic</a>, J. Int. Seq. 14 (2011) # 11.9.8.
%H Said Amrouche and Hacène Belbachir, <a href="https://doi.org/10.3906/mat-1811-109">Unimodality and linear recurrences associated with rays in the Delannoy triangle</a>, Turkish Journal of Mathematics (2019) Vol. 44, 118-130.
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 14.10.1, p.320.
%H Vladimir Baltic, <a href="http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135.
%H G. E. Bergum and V. E. Hoggatt, Jr., <a href="http://www.fq.math.ca/Scanned/16-2/bergum.pdf">A combinatorial problem involving recursive sequences and tridiagonal matrices</a>, Fib. Quart., 16 (1978), 113-118.
%H M. El-Mikkawy, T. Sogabe, <a href="https://doi.org/10.1016/j.amc.2009.12.069">A new family of k-Fibonacci numbers</a>, Appl. Math. Comput. 215 (2010) 4456-4461.
%H K. Edwards, <a href="http://www.fq.math.ca/Papers1/46_47-1/Edwards11-08.pdf">A Pascal-like triangle related to the tribonacci numbers</a>, Fib. Q., 46/47 (2008/2009), 18-25.
%H Steven Finch, <a href="https://arxiv.org/abs/2003.09458">Cantor-solus and Cantor-multus distributions</a>, arXiv:2003.09458 [math.CO], 2020.
%H T. Guardia and D. Jiménez, <a href="http://arxiv.org/abs/1509.03177">Fiboquadratic Sequences and Extensions of the Cassini Identity Raised From the Study of Rithmomachia</a>, arXiv preprint arXiv:1509.03177 [math.HO], 2015-2016.
%H Andreas M. Hinz and Paul K. Stockmeyer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Hinz/hinz5.html">Precious Metal Sequences and Sierpinski-Type Graphs</a>, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H M. Tetiva, <a href="http://www.jstor.org/stable/10.4169/math.mag.84.4.296">Subsets that make no difference d</a>, Mathematics Magazine 84 (2011), no. 4, 300-301.
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,1).
%F 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
%F 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]
%F From _Vladeta Jovovic_, May 03 2002: (Start)
%F 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)).
%F G.f.: 1/(1-x-x^2)/(1+x^2). (End)
%F a(n) = (-i)^n*Sum{k=0..n} U(n-2k, i/2) where i^2=-1. - _Paul Barry_, Nov 15 2003
%F a(n) = Sum_{k=0..floor(n/2)} (-1)^k*F(n-2k+1). - _Paul Barry_, Oct 12 2007
%F 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
%F a(2*n - 1) = A001654(n), a(2*n) = A007598(n+1). - _Michael Somos_, Mar 10 2004
%F 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
%F 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
%F 5*a(n) = (-1)^floor(n/2)*A000034(n+1) + A000032(n+2). - _R. J. Mathar_, Sep 16 2017
%F 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
%F 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
%e 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 + ...
%e From _Gus Wiseman_, Nov 27 2019: (Start)
%e The a(2) = 1 through a(7) = 15 subsets with no two elements differing by 2:
%e {} {} {} {} {} {}
%e {1} {1} {1} {1} {1}
%e {2} {2} {2} {2}
%e {1,2} {3} {3} {3}
%e {1,2} {4} {4}
%e {2,3} {1,2} {5}
%e {1,4} {1,2}
%e {2,3} {1,4}
%e {3,4} {1,5}
%e {2,3}
%e {2,5}
%e {3,4}
%e {4,5}
%e {1,2,5}
%e {1,4,5}
%e (End)
%t LinearRecurrence[{1,0,1,1},{1,1,1,2},50] (* _Harvey P. Dale_, Jul 13 2011 *)
%t 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 *)
%t a[ n_] := Fibonacci[ Quotient[ n+2, 2]] Fibonacci[ Quotient[ n+3, 2]] (* _Michael Somos_, Jan 19 2014 *)
%t Table[Length[Select[Subsets[Range[n]],!MatchQ[#,{___,x_,___,y_,___}/;x+2==y]&]],{n,10}] (* _Gus Wiseman_, Nov 27 2019 *)
%o (PARI) {a(n) = fibonacci( (n+2)\2 ) * fibonacci( (n+3)\2 )} /* _Michael Somos_, Mar 10 2004 */
%o (PARI) Vec(1/(1-x-x^3-x^4)+O(x^66))
%o (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
%o (Python)
%o def a(n, adict={0:1, 1:1, 2:1, 3:2}):
%o if n in adict:
%o return adict[n]
%o adict[n]=a(n-1)+a(n-3)+a(n-4)
%o return adict[n] # _David Nacin_, Mar 07 2012
%o (Haskell)
%o a006498 n = a006498_list !! n
%o a006498_list = 1 : 1 : 1 : 2 : zipWith (+) (drop 3 a006498_list)
%o (zipWith (+) (tail a006498_list) a006498_list)
%o -- _Reinhard Zumkeller_, Apr 07 2012
%Y Cf. A060945 (for 1's, 2's and 4's). Essentially the same as A074677.
%Y Diagonal sums of number triangle A059259.
%Y Cf. A000032, A000034, A000045, A001654, A007598, A209398.
%Y Numbers whose binary expansion has no subsequence (1,0,1) are A048716.
%Y Cf. A003242, A005251, A027383, A167606, A261041, A273461, A329860, A329871.
%K nonn,easy,nice
%O 0,4
%A _N. J. A. Sloane_
|
