A107458 -id:A107458 - cp's OEIS frontend

A135851 a(n) = n-1, if n <= 2, otherwise A107458(n-1) + A107458(n-2).

-1, 0, 1, 0, 0, 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961, 8407925

Offset: 0

N. J. A. Sloane, Mar 08 2008

			G.f. = -1 + x^2 + x^5 + x^6 + x^7 + 2*x^8 + 3*x^9 + 4*x^10 + 6*x^11 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
C. K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc. 10 (1997), no. 1, 139-167. [Page 156, f_n.]
Index entries for linear recurrences with constant coefficients, signature (1,0,1).

Cf. A000930, A013979, A077961, A078012, A107458.

a135851 n = a135851_list !! n
a135851_list = -1 : 0 : 1 : zipWith (+) a135851_list (drop 2 a135851_list)
-- Reinhard Zumkeller, Mar 23 2012

[n le 3 select n-2 else Self(n-1) + Self(n-3): n in [1..61]]; // G. C. Greubel, Aug 01 2022

LinearRecurrence[{1,0,1},{-1,0,1},50] (* Vladimir Joseph Stephan Orlovsky, Jan 31 2012 *)
a[ n_] := If[ n < 3, SeriesCoefficient[ 1 / (1 + x^2 - x^3), {x, 0, 2 - n}], SeriesCoefficient[ x^5 / (1 - x - x^3), {x, 0, n}]]; (* Michael Somos, Jan 08 2014 *)

{a(n) = if( n<3, polcoeff( 1 / (1 + x^2 - x^3) + x * O(x^(2-n)), 2-n), polcoeff( x^5 / (1 - x - x^3) + x * O(x^n), n))}; /* Michael Somos, Jan 08 2014 */

def A000930(n): return sum(binomial(n-2*j,j) for j in (0..(n//3)))
def A135851(n): return A000930(n+2) -2*A000930(n)
[A135851(n) for n in (0..60)] # G. C. Greubel, Aug 01 2022

From R. J. Mathar, Jul 26 2010: (Start)
a(n) = +a(n-1) +a(n-3).
a(n) = A078012(n-2), for n>=2.
G.f.: (-1 + x + x^2) / (1 - x - x^3). (End)
From Michael Somos, Jan 08 2014: (Start)
a(n) = A077961(2-n) for all n in Z.
a(n)^2 - a(n-1)*a(n+1) = A077961(n-5). (End)
a(n) = A000930(n+2) - 2*A000930(n). - G. C. Greubel, Aug 01 2022

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.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961, 8407925

Offset: 0

N. J. A. Sloane, Nov 17 2002, Mar 08 2008

Number of compositions of n into parts >= 3. - Milan Janjic, Jun 28 2010
From Adi Dani, May 22 2011: (Start)
Number of compositions of number n into parts of the form 3*k+1, k >= 0.
For example, a(10)=19 and all compositions of 10 in parts 1,4,7 or 10 are
(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)
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

			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 + ...

Taylor L. Booth, Sequential Machines and Automata Theory, John Wiley and Sons, Inc., 1967, page 331ff.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Christian Ballot, On Functions Expressible as Words on a Pair of Beatty Sequences, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.2.
C. K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc. 10 (1997), no. 1, 139-167. [Page 156, f_n.]
Taras Goy, On identities with multinomial coefficients for Fibonacci-Narayana sequence, Annales Mathematicae et Informaticae, Vol. 49 (2018), 75-84.
Bahar Kuloğlu, Engin Özkan, and Marin Marin, On the period of Pell-Narayana sequence in some groups, arXiv:2305.04786 [math.CO], 2023.
J. D. Opdyke, A unified approach to algorithms generating unrestricted.., J. Math. Model. Algor. 9 (2010) 53-97.
Yüksel Soykan, Summing Formulas For Generalized Tribonacci Numbers, arXiv:1910.03490 [math.GM], 2019.
Index entries for linear recurrences with constant coefficients, signature (1,0,1).

Cf. A000930, A065417, A068921, A077961.

Cf. also A135851, A257234.

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

a078012 n = a078012_list !! n
a078012_list = 1 : 0 : 0 : 1 : zipWith (+) a078012_list
   (zipWith (+) (tail a078012_list) (drop 2 a078012_list))
-- Reinhard Zumkeller, Mar 23 2012

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

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
# second Maple program:
a:= n-> (<<0|1|0>, <0|0|1>, <1|0|1>>^n)[1, 1]:
seq(a(n), n=0..46);  # Alois P. Heinz, May 08 2025

CoefficientList[ Series[(1-x)/(1-x-x^3), {x,0,50}], x] (* Robert G. Wilson v, May 25 2011 *)
LinearRecurrence[{1,0,1}, {1,0,0}, 50] (* Vladimir Joseph Stephan Orlovsky, Feb 24 2012 *)
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 *)

{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 */

((1-x)/(1-x-x^3)).series(x, 50).coefficients(x, sparse=False) # G. C. Greubel, Jun 28 2019

a(n) = Sum_{i=0..(n-3)/3} binomial(n-3-2*i, i), n >= 1, a(0) = 1.
From Michael Somos, May 03 2011: (Start)
Euler transform of A065417.
G.f.: (1 - x) / (1 - x - x^3).
a(-n) = A077961(n). a(n+3) = A000930(n).
a(n+5) = A068921(n). (End)
a(n+1) = A013979(n-3) + A135851(n) + A107458(n), n >= 3.
G.f.: 1/(1 - Sum_{k>=3} x^k). - Joerg Arndt, Aug 13 2012
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
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
a(-n) = a(n)*a(n+3) - a(n+1)*a(n+2) for all n in Z. - Greg Dresden, May 07 2025

Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

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

A013979 Expansion of 1/(1 - x^2 - x^3 - x^4) = 1/((1 + x)*(1 - x - x^3)).

Original entry on oeis.org

1, 0, 1, 1, 2, 2, 4, 5, 8, 11, 17, 24, 36, 52, 77, 112, 165, 241, 354, 518, 760, 1113, 1632, 2391, 3505, 5136, 7528, 11032, 16169, 23696, 34729, 50897, 74594, 109322, 160220, 234813, 344136, 504355, 739169, 1083304, 1587660, 2326828, 3410133, 4997792, 7324621

Offset: 0

N. J. A. Sloane

For n>0, number of compositions (ordered partitions) of n into 2's, 3's and 4's. - Len Smiley, May 08 2001
Diagonal sums of trinomial triangle A071675 (Riordan array (1, x*(1+x+x^2))). - Paul Barry, Feb 15 2005
For n>1, a(n) is number of compositions of n-2 into parts 1 and 2 with no 3 consecutive 1's. For example: a(7) = 5 because we have: 2+2+1, 2+1+2, 1+2+2, 1+2+1+1, 1+1+2+1. - Geoffrey Critzer, Mar 15 2014
In the same way [per 2nd comment for A006498, by Sreyas Srinivasan] that the sum of any two alternating terms (terms separated by one term) of A006498 produces a term from A000045 (the Fibonacci sequence), so it could therefore be thought of as a "metaFibonacci," the sum of any two (nonalternating) terms of this sequence produces a term from A000930 (Narayana’s cows), so this sequence could analogously be called "meta-Narayana’s cows" (e.g. 4+5=9, 5+8=13, 8+11=19, 11+17=28). - Michael Cohen and Yasuyuki Kachi, Jun 13 2024

			G.f. = 1 + x^2 + x^3 + 2*x^4 + 2*x^5 + 4*x^6 + 5*x^7 + 8*x^8 + 11*x^9 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Michael Cohen and Yasuyuki Kachi, Recurrence Relations Rhythm. In: Noll, T., Montiel, M., Gómez, F., Hamido, O.C., Besada, J.L., Martins, J.O. (eds) Mathematics and Computation in Music. MCM 2024. Lecture Notes in Computer Science, vol. 14639. Springer, Cham.
C. K. Fan, A Hecke algebra quotient and some combinatorial applications, J. Algebraic Combin. 5 (1996), no. 3, 175-189.
C. K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc. 10 (1997), no. 1, 139-167. [Page 156, f^0_n.]
R. Mullen, On Determining Paint by Numbers Puzzles with Nonunique Solutions, JIS 12 (2009) 09.6.5.
Index entries for linear recurrences with constant coefficients, signature (0,1,1,1).

Cf. A060945 (Ordered partitions into 1's, 2's and 4's).
First differences of A023435.
Cf. A000045, A000930, A001634, A006498, A071675, A077889, A078012, A097333, A107458.

a013979 n = a013979_list !! n
a013979_list = 1 : 0 : 1 : 1 : zipWith (+) a013979_list
   (zipWith (+) (tail a013979_list) (drop 2 a013979_list))
-- Reinhard Zumkeller, Mar 23 2012

R:=PowerSeriesRing(Integers(), 50); Coefficients(R!( 1/((1+x)*(1-x-x^3)) )); // G. C. Greubel, Jul 17 2023

a[n_]:= If[n<0, SeriesCoefficient[x^4/(1 +x +x^2 -x^4), {x, 0, -n}], SeriesCoefficient[1/(1 -x^2 -x^3 -x^4), {x,0,n}]]; (* Michael Somos, Jun 20 2015 *)
LinearRecurrence[{0,1,1,1}, {1,0,1,1}, 50] (* G. C. Greubel, Jul 17 2023 *)

@CachedFunction
def b(n): return 1 if (n<3) else b(n-1) + b(n-3) # b = A000930
def A013979(n): return ((-1)^n +2*b(n) -b(n-1) +b(n-2) -int(n==1))/3
[A013979(n) for n in (0..50)] # G. C. Greubel, Jul 17 2023

a(n) = Sum_{k=0..floor(n/2)} Sum_{i=0..floor(n/2)} C(k, 2i+3k-n)*C(2i+3k-n, i). - Paul Barry, Feb 15 2005
a(n) = a(n-4) + a(n-3) + a(n-2). - Jon E. Schoenfield, Aug 07 2006
a(n) + a(n+1) = A000930(n+1). - R. J. Mathar, Mar 14 2011
a(n) = (1/3)*(A000930(n) + A097333(n-2) + (-1)^n), n>1. - Ralf Stephan, Aug 15 2013
a(n) = (-1)^n * A077889(-4-n) = A107458(n+4) for all n in Z. - Michael Somos, Jun 20 2015
a(n) = Sum_{i=0..floor(n/2)} A078012(n-2*i). - Paul Curtz, Aug 18 2021
a(n) = (1/3)*((-1)^n + 2*b(n) - b(n-1) + b(n-2) - [n=1]), where b(n) = A000930(n). - G. C. Greubel, Jul 17 2023

A001634 a(n) = a(n-2) + a(n-3) + a(n-4), with initial values a(0) = 0, a(1) = 2, a(2) = 3, a(3) = 6.

Original entry on oeis.org

0, 2, 3, 6, 5, 11, 14, 22, 30, 47, 66, 99, 143, 212, 308, 454, 663, 974, 1425, 2091, 3062, 4490, 6578, 9643, 14130, 20711, 30351, 44484, 65192, 95546, 140027, 205222, 300765, 440795, 646014, 946782, 1387574, 2033591, 2980370, 4367947, 6401535, 9381908

Offset: 0

N. J. A. Sloane

E.-B. Escott, Reply to Query 1484, L'Intermédiaire des Mathématiciens, 8 (1901), 63-64.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..500
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Gregory T. Minton, Linear recurrence sequences satisfying congruence conditions, Proc. Amer. Math. Soc. 142 (2014), no. 7, 2337--2352. MR3195758.
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
Index entries for linear recurrences with constant coefficients, signature (0, 1, 1, 1).

Cf. A013979, A107458.

a001634 n = a001634_list !! n
a001634_list = 0 : 2 : 3 : 6 : zipWith (+) a001634_list
   (zipWith (+) (tail a001634_list) (drop 2 a001634_list))
-- Reinhard Zumkeller, Mar 23 2012

A001634:=-z*(2+3*z+4*z**2)/(1+z)/(z**3+z-1); # Simon Plouffe in his 1992 dissertation
a:= n-> (Matrix([[0,4,-1,-1]]). Matrix(4, (i,j)-> if (i=j-1) then 1 elif j=1 then [0,1,1,1][i] else 0 fi)^n)[1,1]: seq(a(n), n=0..40); # Alois P. Heinz, Aug 01 2008

LinearRecurrence[{0, 1, 1, 1}, {0, 2, 3, 6}, 100] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)
CoefficientList[Series[x (2+3x+4x^2)/(1-x^2-x^3-x^4),{x,0,50}],x] (* Harvey P. Dale, Mar 26 2023 *)

a(n):=(sum(sum(binomial(j,n-2*k-j-1)*binomial(k+1,j),j,0,k+1)/(k+1),k,0,(n-1)/2))*(n+1); /* Vladimir Kruchinin, Mar 22 2016 */

a(n)=if(n<0,0,polcoeff(x*(2+3*x+4*x^2)/(1-x^2-x^3-x^4)+x*O(x^n),n))

G.f.: x(2 + 3x + 4x^2)/(1 - x^2 - x^3 - x^4).

a(n) = Sum_{k=0..(n-1)/2}(Sum_{j=0..k+1}(binomial(j,n-2*k-j-1)*binomial(k+1,j))/(k+1))*(n+1). - Vladimir Kruchinin, Mar 22 2016

cp's OEIS Frontend

A135851 a(n) = n-1, if n <= 2, otherwise A107458(n-1) + A107458(n-2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

SageMath

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A013979 Expansion of 1/(1 - x^2 - x^3 - x^4) = 1/((1 + x)*(1 - x - x^3)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

SageMath

Formula

A001634 a(n) = a(n-2) + a(n-3) + a(n-4), with initial values a(0) = 0, a(1) = 2, a(2) = 3, a(3) = 6.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

Formula