login
Expansion of (1 - x) / (1 - x - x^3) in powers of x.
36

%I #107 May 12 2023 21:37:37

%S 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 1873,2745,4023,5896,8641,12664,18560,27201,39865,58425,85626,125491,

%U 183916,269542,395033,578949,848491,1243524,1822473,2670964,3914488,5736961,8407925

%N Expansion of (1 - x) / (1 - x - x^3) in powers of x.

%C Number of compositions of n into parts >= 3. - _Milan Janjic_, Jun 28 2010

%C From _Adi Dani_, May 22 2011: (Start)

%C Number of compositions of number n into parts of the form 3*k+1, k >= 0.

%C For example, a(10)=19 and all compositions of 10 in parts 1,4,7 or 10 are

%C (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 a(n+1) is for n >= 0 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 Taylor L. Booth, Sequential Machines and Automata Theory, John Wiley and Sons, Inc., 1967, page 331ff.

%H Vincenzo Librandi, <a href="/A078012/b078012.txt">Table of n, a(n) for n = 0..1000</a>

%H 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 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 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 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 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 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 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1).

%F a(n) = Sum_{i=0..(n-3)/3} binomial(n-3-2*i, i), n >= 1, a(0) = 1.

%F From _Michael Somos_, May 03 2011: (Start)

%F Euler transform of A065417.

%F G.f.: (1 - x) / (1 - x - x^3).

%F a(n) = a(n-1) + a(n-3).

%F a(-n) = A077961(n). a(n+3) = A000930(n).

%F a(n+5) = A068921(n). (End)

%F a(n+1) = A013979(n-3) + A135851(n) + A107458(n), n >= 3.

%F a(n) = a(n-1) + a(n-3) for n >= 4. - _Jaroslav Krizek_, May 07 2011

%F G.f.: 1/(1 - Sum_{k>=3} x^k). - _Joerg Arndt_, Aug 13 2012

%F 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 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

%e 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 := 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

%t CoefficientList[ Series[(1-x)/(1-x-x^3), {x,0,50}], x] (* _Robert G. Wilson v_, May 25 2011 *)

%t LinearRecurrence[{1,0,1}, {1,0,0}, 50] (* _Vladimir Joseph Stephan Orlovsky_, Feb 24 2012 *)

%t 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 (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 (Haskell)

%o a078012 n = a078012_list !! n

%o a078012_list = 1 : 0 : 0 : 1 : zipWith (+) a078012_list

%o (zipWith (+) (tail a078012_list) (drop 2 a078012_list))

%o -- _Reinhard Zumkeller_, Mar 23 2012

%o (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 (Sage) ((1-x)/(1-x-x^3)).series(x, 50).coefficients(x, sparse=False) # _G. C. Greubel_, Jun 28 2019

%o (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 Cf. A000930, A065417, A068921, A077961.

%Y Cf. A135851, A257234.

%K nonn,easy

%O 0,7

%A _N. J. A. Sloane_, Nov 17 2002, Mar 08 2008

%E Deleted certain dangerous or potentially dangerous links. - _N. J. A. Sloane_, Jan 30 2021