cp's OEIS Frontend

A078012 a(n) = a(n-1) + a(n-3) for n >= 3, with a(0) = 1, a(1) = a(2) = 0. This recurrence can also be used to define a(n) for n < 0.

%I A078012 #127 May 12 2025 00:25:15
%S A078012 1,0,0,1,1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406,595,872,1278,
%T A078012 1873,2745,4023,5896,8641,12664,18560,27201,39865,58425,85626,125491,
%U A078012 183916,269542,395033,578949,848491,1243524,1822473,2670964,3914488,5736961,8407925
%N A078012 a(n) = a(n-1) + a(n-3) for n >= 3, with a(0) = 1, a(1) = a(2) = 0. This recurrence can also be used to define a(n) for n < 0.
%C A078012 Number of compositions of n into parts >= 3. - _Milan Janjic_, Jun 28 2010
%C A078012 From _Adi Dani_, May 22 2011: (Start)
%C A078012 Number of compositions of number n into parts of the form 3*k+1, k >= 0.
%C A078012 For example, a(10)=19 and all compositions of 10 in parts 1,4,7 or 10 are
%C A078012 (1,1,1,1,1,1,1,1,1,1), (1,1,1,1,1,1,4), (1,1,1,1,1,4,1), (1,1,1,1,4,1,1), (1,1,1,4,1,1,1), (1,1,4,1,1,1,1), (1,4,1,1,1,1,1), (4,1,1,1,1,1,1), (1,1,4,4), (1,4,1,4), (1,4,4,1), (4,1,1,4),(4,1,4,1), (4,4,1,1), (1,1,1,7), (1,1,7,1), (1,7,1,1), (7,1,1,1), (10). (End)
%C A078012 For n >= 0 a(n+1) is the number of 00's in the Narayana word NW(n); equivalently the number of two neighboring 0's at level n of the Narayana tree. See A257234. This implies that if a(0) is put to 0 then a(n) is the number of -1's in the Narayana word NW(n), and also at level n of the Narayana tree. - _Wolfdieter Lang_, Apr 24 2015
%D A078012 Taylor L. Booth, Sequential Machines and Automata Theory, John Wiley and Sons, Inc., 1967, page 331ff.
%H A078012 Vincenzo Librandi, <a href="/A078012/b078012.txt">Table of n, a(n) for n = 0..1000</a>
%H A078012 Christian Ballot, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Ballot/ballot22.html">On Functions Expressible as Words on a Pair of Beatty Sequences</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.2.
%H A078012 C. K. Fan, <a href="http://dx.doi.org/10.1090/S0894-0347-97-00222-1">Structure of a Hecke algebra quotient</a>, J. Amer. Math. Soc. 10 (1997), no. 1, 139-167. [Page 156, f_n.]
%H A078012 Taras Goy, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_49_from75to84.pdf">On identities with multinomial coefficients for Fibonacci-Narayana sequence</a>, Annales Mathematicae et Informaticae, Vol. 49 (2018), 75-84.
%H A078012 Bahar Kuloğlu, Engin Özkan, and Marin Marin, <a href="https://arxiv.org/abs/2305.04786">On the period of Pell-Narayana sequence in some groups</a>, arXiv:2305.04786 [math.CO], 2023.
%H A078012 J. D. Opdyke, <a href="http://dx.doi.org/10.1007/s10852-009-9116-2">A unified approach to algorithms generating unrestricted..</a>, J. Math. Model. Algor. 9 (2010) 53-97.
%H A078012 Yüksel Soykan, <a href="https://arxiv.org/abs/1910.03490">Summing Formulas For Generalized Tribonacci Numbers</a>, arXiv:1910.03490 [math.GM], 2019.
%H A078012 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1).
%F A078012 a(n) = Sum_{i=0..(n-3)/3} binomial(n-3-2*i, i), n >= 1, a(0) = 1.
%F A078012 From _Michael Somos_, May 03 2011: (Start)
%F A078012 Euler transform of A065417.
%F A078012 G.f.: (1 - x) / (1 - x - x^3).
%F A078012 a(-n) = A077961(n). a(n+3) = A000930(n).
%F A078012 a(n+5) = A068921(n). (End)
%F A078012 a(n+1) = A013979(n-3) + A135851(n) + A107458(n), n >= 3.
%F A078012 G.f.: 1/(1 - Sum_{k>=3} x^k). - _Joerg Arndt_, Aug 13 2012
%F A078012 G.f.: Q(0)*(1-x)/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + x^2)/( x*(4*k+3 + x^2) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Sep 08 2013
%F A078012 0 = -1 + a(n)*(a(n)*(a(n) + a(n+2)) + a(n+1)*(a(n+1) - 3*a(n+2))) + a(n+1)*(+a(n+1)*(+a(n+1) + a(n+2)) + a(n+2)*(-2*a(n+2))) + a(n+2)^3 for all n in Z. - _Michael Somos_, Feb 03 2018
%F A078012 a(-n) = a(n)*a(n+3) - a(n+1)*a(n+2) for all n in Z. - _Greg Dresden_, May 07 2025
%e A078012 G.f. = 1 + x^3 + x^4 + x^5 + 2*x^6 + 3*x^7 + 4*x^8 + 6*x^9 + 9*x^10 + 13*x^11 + ...
%p A078012 A078012 := proc(n): if n=0 then 1 else add(binomial(n-3-2*i,i),i=0..(n-3)/3) fi: end: seq(A078012(n), n=0..46); # _Johannes W. Meijer_, Aug 11 2011
%p A078012 # second Maple program:
%p A078012 a:= n-> (<<0|1|0>, <0|0|1>, <1|0|1>>^n)[1, 1]:
%p A078012 seq(a(n), n=0..46);  # _Alois P. Heinz_, May 08 2025
%t A078012 CoefficientList[ Series[(1-x)/(1-x-x^3), {x,0,50}], x] (* _Robert G. Wilson v_, May 25 2011 *)
%t A078012 LinearRecurrence[{1,0,1}, {1,0,0}, 50] (* _Vladimir Joseph Stephan Orlovsky_, Feb 24 2012 *)
%t A078012 a[ n_]:= If[ n >= 0, SeriesCoefficient[ (1-x)/(1-x-x^3), {x, 0, n}], SeriesCoefficient[1/(1+x^2-x^3), {x, 0, -n}]]; (* _Michael Somos_, Feb 03 2018 *)
%o A078012 (PARI) {a(n) = if( n<0, n = -n; polcoeff( 1 / (1 + x^2 - x^3) + x * O(x^n), n), polcoeff( (1 - x) / (1 - x - x^3) + x * O(x^n), n))}; /* _Michael Somos_, May 03 2011 */
%o A078012 (Haskell)
%o A078012 a078012 n = a078012_list !! n
%o A078012 a078012_list = 1 : 0 : 0 : 1 : zipWith (+) a078012_list
%o A078012    (zipWith (+) (tail a078012_list) (drop 2 a078012_list))
%o A078012 -- _Reinhard Zumkeller_, Mar 23 2012
%o A078012 (Magma) I:=[1,0,0]; [n le 3 select I[n] else Self(n-1) + Self(n-3): n in [1..50]]; // _G. C. Greubel_, Jan 19 2018
%o A078012 (Sage) ((1-x)/(1-x-x^3)).series(x, 50).coefficients(x, sparse=False) # _G. C. Greubel_, Jun 28 2019
%o A078012 (GAP) a:=[1,0,0];; for n in [4..50] do a[n]:=a[n-1]+a[n-3]; od; a; # _G. C. Greubel_, Jun 28 2019
%Y A078012 Cf. A000930, A065417, A068921, A077961.
%Y A078012 Cf. also A135851, A257234.
%K A078012 nonn,easy
%O A078012 0,7
%A A078012 _N. J. A. Sloane_, Nov 17 2002, Mar 08 2008
%E A078012 Deleted certain dangerous or potentially dangerous links. - _N. J. A. Sloane_, Jan 30 2021
%E A078012 Entry revised by _N. J. A. Sloane_, May 11 2025, making use of comments from _Michael Somos_, May 03 2011 and _Greg Dresden_, May 11 2025