A060945 -id:A060945 - cp's OEIS frontend

A006498 a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.

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, 74049690, 119814916

Offset: 0

N. J. A. Sloane

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

			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)

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

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).
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 16, 18.
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.
V. Baltic, Applications of the finite state automata for counting restricted permutations and variations, Yug. J. Oper. Res. 22 (2012) 183-198, Sec. 3
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.
John Konvalina, Yi-Hsin Liu, subsets without q-separation and binomial products of Fibonacci numbers, J. Comb. Theo. A 57 (2) (1991) 306-310, T_n.
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.
Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.
Index entries for sequences related to Chebyshev polynomials.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Cf. A060945 (for 1's, 2's and 4's). Essentially the same as A074677.
Diagonal sums of number triangle A059259.
Cf. A000032, A000034, A000045, A001654, A007598, A209398.
Numbers whose binary expansion has no subsequence (1,0,1) are A048716.
Cf. A003242, A005251, A027383, A167606, A261041, A273461, A329860, A329871.

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

[ 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

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 *)

{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))
```

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

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

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

A017818 Expansion of 1/(1-x^3-x^4-x^5).

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 1, 2, 3, 3, 4, 6, 8, 10, 13, 18, 24, 31, 41, 55, 73, 96, 127, 169, 224, 296, 392, 520, 689, 912, 1208, 1601, 2121, 2809, 3721, 4930, 6531, 8651, 11460, 15182, 20112, 26642, 35293, 46754, 61936, 82047

Offset: 0

N. J. A. Sloane

Compositions of n into parts 3, 4, and 5. - David Neil McGrath, Jul 28 2014

The number of ways a T2 triangle can cover a row length of T1(n) triangles. - Craig Knecht, Mar 06 2025

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, Predators and altruists arriving on jammed Riviera, arXiv:2401.01225 [math.CO], 2024. See p. 14.
Craig Knecht, The number of ways a T2 triangle can cover a row of T1 triangles.
Index entries for linear recurrences with constant coefficients, signature (0,0,1,1,1).

m:=50; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(1/(1-x^3-x^4-x^5))); // Vincenzo Librandi, Jun 27 2013

I:=[1,0,0,1,1]; [n le 5 select I[n] else Self(n-3)+Self(n-4)+Self(n-5): n in [1..50]]; // Vincenzo Librandi, Jun 27 2013

CoefficientList[Series[1 / (1 - x^3 - x^4 - x^5), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 27 2013 *)
LinearRecurrence[{0,0,1,1,1},{1,0,0,1,1},50] (* Harvey P. Dale, Oct 03 2020 *)

a(n) = (1/10)*(2*A001608(n) + 2*A000931(n+2) + (-1)^floor(n/2) - 3(-1)^floor((n-1)/2)). - Ralf Stephan, Jun 09 2005
a(n) = a(n-5) + a(n-4) + a(n-3). - Jon E. Schoenfield, Aug 07 2006
a(2n+3) = A060945(n). - Yasuyuki Kachi, Jul 06 2024

A060961 Number of compositions (ordered partitions) of n into 1's, 3's and 5's.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 8, 12, 19, 30, 47, 74, 116, 182, 286, 449, 705, 1107, 1738, 2729, 4285, 6728, 10564, 16587, 26044, 40893, 64208, 100816, 158296, 248548, 390257, 612761, 962125, 1510678, 2371987, 3724369, 5847808, 9181920, 14416967, 22636762, 35543051

Offset: 0

Len Smiley, May 08 2001

Lim_{n->infinity} a(n)/a(n-1) = 1.57014... = A293506. This is the largest absolute value of a root of the characteristic polynomial of the recursion (x^5 - x^4 - x^2 - 1), same as the inverse of smallest absolute value of a root of the reciprocal (here -x^5 - x^3 - x + 1, the denominator of the g.f.) of the characteristic polynomial. - Bob Selcoe, Jun 09 2013
From Bob Selcoe, May 01 2014: (Start)
Since a(n) is a recurrence of the form: a(n) = Sum_(a(n-Fi)), i=1..z; where F(i)-F(i-1) is constant (C), and seed values are a(0)=1 and a(<0)=0 exclusively; then apply the following definitions:
I.  For T-nomial triangles T(m,k), let T be defined as the number of terms in the recurrence equaling a(n).  That is, T => z => ((Fz-F1)/C)+1.  In this sequence, F1=1, C=2 and T => z => ((5-1)/2)+1 = 3.  Therefore, the applicable triangle is trinomial for this sequence.
II.  Let m' be defined as the maxval of m and k' the minval of k such that n = m'*F1+k'*C.  For example, in this sequence:  n=7: m'=7 and k'=0 because 7*1+0*2=7. (Note that m' always equals n and k' always equals 0 when F1=1)
III.  THEN:  a(n) = Sum_T((m'-C*j/G),(k'+F1*j/G)), j=0..q; where (m'-C*q)) is the floor and (k'+F1*q) the ceiling for the T-nomial triangle, and G is the greatest common factor of all Fi.  In general, T, F1, C and G are invariant across n; while m', k' and q vary (the exception being k' always equaling 0 when F1=1). In this sequence, T=3, F1=1, C=2, G=1 and k'=0;  m' and q vary with a(n).
Example 1.  a(11):  T=3, F1=1, C=2, G=1, k'=0 (invariant);  m'=11, q=4.  a(11) = 74 => T(11,0) + T(9,1) + T(7,2) + T(5,3) + T(3,4) for T==trinomial triangle.  T(11,0)=1, T(9,1)=9, T(7,2)=28, T(5,3)=30 and T(3,4)=6.  1+9+28+30+6 = 74  (Note that T(3,4) is the final term because the ostensible next term [T(1,5)] is not contained in the trinomial triangle.  Therefore q=4.)
Example 2.  a(14):  m'=14, q=5.  a(14) = 286 => T(14,0) + T(12,1) + T(10,2) + T(8,3) + T(6,4) + T(4,5) => 1+12+55+112+90+16 = 286. (End)

Harry J. Smith, Table of n, a(n) for n = 0..500
Sergey Dovgal and Sergey Kirgizov, Structure and growth of R-bonacci words, arXiv:2310.01213 [math.CO], 2023. See p. 5.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,0,1).

Cf. A293506 (growth power).
Cf. A060945 (compositions into 1's, 2's, and 4's).
Cf. A027907 (trinomial coefficients triangle).

CoefficientList[Series[ 1 /(1 - z - z^3 - z^5), {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jun 10 2011 *)
LinearRecurrence[{1,0,1,0,1},{1,1,1,2,3},50] (* Harvey P. Dale, Apr 21 2022 *)

a(n):=sum((sum(binomial(j,3*n-5*m+2*j)*binomial(2*m-n,j),j,0,2*m-n)),m,floor((n+1)/2),n); /* Vladimir Kruchinin, Mar 11 2013 */

my(N=66, x='x+O('x^N)); Vec(1/(1-x-x^3-x^5)) \\ Joerg Arndt, Oct 21 2012

a(n) = a(n-1) + a(n-3) + a(n-5).
G.f.: 1 / (1-(x+x^3+x^5)).
a(n) = Sum_{m=floor((n+1)/2)..n} Sum_{j=0..2*m-n} binomial(j,3*n-5*m+2*j)*binomial(2*m-n,j). - Vladimir Kruchinin, Mar 11 2013

a(0)=1 prepended by Joerg Arndt, Oct 21 2012

A077930 Expansion of (1-x)^(-1)/(1+2*x+x^2+x^3).

Original entry on oeis.org

1, -1, 2, -3, 6, -10, 18, -31, 55, -96, 169, -296, 520, -912, 1601, -2809, 4930, -8651, 15182, -26642, 46754, -82047, 143983, -252672, 443409, -778128, 1365520, -2396320, 4205249, -7379697, 12950466, -22726483, 39882198, -69988378, 122821042, -215535903, 378239143, -663763424

Offset: 0

N. J. A. Sloane, Nov 17 2002

Signed version of A060945: a(n) = (-1)^n * A060945(n).

Index entries for linear recurrences with constant coefficients, signature (-1,1,0,1).

All of A060945, A077930, A181532 are variations of the same sequence. - N. J. A. Sloane, Mar 04 2012

CoefficientList[Series[1/(1-x)/(1+2x+x^2+x^3),{x,0,50}],x] (* or *) LinearRecurrence[ {-1,1,0,1},{1,-1,2,-3},50] (* Harvey P. Dale, Feb 20 2013 *)

Vec((1-x)^(-1)/(1+2*x+x^2+x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 24 2012

a(n+1)-a(n) = (-1)^(n+1)*A005314(n+2). - R. J. Mathar, Mar 14 2011

a(0)=1, a(1)=-1, a(2)=2, a(3)=-3, a(n)=-a(n-1)+a(n-2)+a(n-4). - Harvey P. Dale, Feb 20 2013

A181532 a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2; a(n) = a(n-1) + a(n-2) + a(n-4).

Original entry on oeis.org

0, 1, 1, 2, 3, 6, 10, 18, 31, 55, 96, 169, 296, 520, 912, 1601, 2809, 4930, 8651, 15182, 26642, 46754, 82047, 143983, 252672, 443409, 778128, 1365520, 2396320, 4205249, 7379697, 12950466, 22726483, 39882198, 69988378, 122821042, 215535903, 378239143, 663763424

Offset: 0

Gary W. Adamson, Oct 28 2010

Essentially the same as A060945: a(0)=0 and a(n)=A060945(n-1) for n>=1.
lim(n->infinity) a(n+1)/a(n) = A109134 = 1.754877666..., the square of the absolute value of one of the complex-valued roots of the characteristic polynomial. [R. J. Mathar, Nov 01 2010]
The Ze4 sums, see A180662 for the definition of these sums, of the ‘Races with Ties’ triangle A035317 lead to this sequence. [Johannes W. Meijer, Jul 20 2011]

			a(7) = 18 = a(6) + a(5) + a(3) = 10 + 6 + 2.
a(7) = 18 = (1 0, 2, 0, 2, 0, 3) dot (10, 6, 3, 2, 1, 1, 1) = (10 + 3 + 2 + 3).

Index entries for linear recurrences with constant coefficients, signature (1,1,0,1). [From _R. J. Mathar_, Oct 29 2010]

All of A060945, A077930, A181532 are variations of the same sequence. - N. J. A. Sloane, Mar 04 2012

LinearRecurrence[{1,1,0,1},{0,1,1,2},40] (* Harvey P. Dale, Jun 20 2015 *)

a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2; a(n) = a(n-1) + a(n-2) + a(n-4).
G.f.: x/(1-x-x^2-x^4). [Franklin T. Adams-Watters, Feb 25 2011]
a(n) = |A077930(n)| = ( |A056016(n+2)|-(-1)^n)/5. [R. J. Mathar, Oct 29 2010]
a(n) = A060945(n-1), n>1. [R. J. Mathar, Nov 03 2010]

Values from a(9) on changed by R. J. Mathar, Oct 29 2010

Edited and a(0) added by Franklin T. Adams-Watters, Feb 25 2011

A097472 Number of different candle trees having a total of m edges.

Original entry on oeis.org

1, 3, 10, 31, 96, 296, 912, 2809, 8651, 26642, 82047, 252672, 778128, 2396320, 7379697, 22726483, 69988378, 215535903, 663763424, 2044122936, 6295072048, 19386276329, 59701891739, 183857684514, 566207320575, 1743689586432

Offset: 0

Alexander Malkis, Sep 18 2004

A candle tree is a graph on the plane square lattice Z X Z whose edges have length one with the following properties: (a) It contains a line segment ("trunk") of length from 0 to m on the vertical axis, its lowest node is at the origin. (b) It contains horizontal line segments ("branches"); each of them intersects the trunk. (c) Each branch is allowed to have "candles", which are vertical edges of length 1, whose lower node is on a branch.

Row sums of triangle in A238241. - Philippe Deléham, Feb 21 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Alexander Malkis, Polyedges, polyominoes and the 'Digit' game, diploma thesis in computer science, Universität des Saarlandes, 2003, Saarbrücken.
Index entries for linear recurrences with constant coefficients, signature (3,1,-2,-1).

Bisection of A060945 and |A077930|.

CoefficientList[Series[1/(x^4+2x^3-x^2-3x+1),{x,0,30}],x] (* or *) LinearRecurrence[{3,1,-2,-1},{1,3,10,31},30] (* Harvey P. Dale, Jun 14 2011 *)

a(n):=sum(sum(binomial(k,n-m-k+1)*binomial(k+2*m-1,2*m-1),k,1,n-m+1),m,1,n)+1; /* Vladimir Kruchinin, May 12 2011 */

a(n)=sum(m=1,n,sum(k=1,n-m+1,binomial(k,n-m-k+1)*binomial(k+2*m-1,2*m-1))) \\ Charles R Greathouse IV, Jun 17 2013

a(n) = Sum_{s, d, k>=0 with s+d+k=m} binomial(s+2d+1, s)*binomial(s, k);
generating function = 1/((1-x)*(1-2*x-3*x^2-x^3)).
a(n) = 3*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4);
a(n) = 1 + Sum_{m=1..n} Sum_{k=1..n-m+1} binomial(k, n-m-k+1)*binomial(k+2*m-1,2*m-1). - Vladimir Kruchinin, May 12 2011
a(n) = Sum_{k=0..n} A238241(n,k). - Philippe Deléham, Feb 21 2014
a(n) - a(n-1) = A218836(n). - R. J. Mathar, Jun 17 2020

A238236 Expansion of (1-x-x^2)/((x-1)(x^3+3x^2+2*x-1)).

Original entry on oeis.org

1, 2, 6, 18, 55, 169, 520, 1601, 4930, 15182, 46754, 143983, 443409, 1365520, 4205249, 12950466, 39882198, 122821042, 378239143, 1164823609, 3587185688, 11047081345, 34020543362, 104769516446, 322647744322, 993624581343, 3059961912097, 9423445312544

Offset: 0

Philippe Deléham, Feb 20 2014

Row sums of the triangle in A152440.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (3,1,-2,-1).

Cf. A097472, A152440, A099098 (first differences).

CoefficientList[Series[(1 - x - x^2)/(1 - 3 x - x^2 + 2 x^3 + x^4), {x, 0, 40}], x ](* Vincenzo Librandi, Feb 22 2014 *)

G.f.: (1-x-x^2)/(1-3*x-x^2+2*x^3+x^4).
a(n) = 3*a(n-1) + a(n-2) -2*a(n-3) - a(n-4), a(0) = 1, a(1) = 2, a(2) = 6, a(3) = 18.
a(n) = A097472(n) - A097472(n-1) - A097472(n-2).
a(n) = A060945(2*n).
a(n)-a(n-1) = A099098(n). - R. J. Mathar, Jun 17 2020

A246690 Number A(n,k) of compositions of n into parts of the k-th list of distinct parts in the order given by A246688; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 2, 0, 1, 0, 1, 1, 0, 3, 1, 1, 0, 1, 0, 1, 1, 5, 0, 1, 0, 1, 1, 0, 2, 0, 8, 1, 1, 0, 1, 0, 1, 0, 3, 0, 13, 0, 1, 0, 1, 0, 1, 1, 1, 4, 1, 21, 1, 1, 0, 1, 1, 0, 1, 2, 0, 6, 0, 34, 0, 1, 0, 1, 1, 2, 0, 1, 3, 0, 9, 0, 55, 1, 1, 0

Offset: 0

Alois P. Heinz, Sep 01 2014

The first lists of distinct parts in the order given by A246688 are: 0:[], 1:[1], 2:[2], 3:[1,2], 4:[3], 5:[1,3], 6:[4], 7:[1,4], 8:[2,3], 9:[5], 10:[1,2,3], 11:[1,5], 12:[2,4], 13:[6], 14:[1,2,4], 15:[1,6], 16:[2,5], 17:[3,4], 18:[7], 19:[1,2,5], 20:[1,3,4], ... .

			Square array A(n,k) begins:
  1, 1, 1,  1, 1,  1, 1,  1, 1, 1,   1, 1, 1, 1,   1, ...
  0, 1, 0,  1, 0,  1, 0,  1, 0, 0,   1, 1, 0, 0,   1, ...
  0, 1, 1,  2, 0,  1, 0,  1, 1, 0,   2, 1, 1, 0,   2, ...
  0, 1, 0,  3, 1,  2, 0,  1, 1, 0,   4, 1, 0, 0,   3, ...
  0, 1, 1,  5, 0,  3, 1,  2, 1, 0,   7, 1, 2, 0,   6, ...
  0, 1, 0,  8, 0,  4, 0,  3, 2, 1,  13, 2, 0, 0,  10, ...
  0, 1, 1, 13, 1,  6, 0,  4, 2, 0,  24, 3, 3, 1,  18, ...
  0, 1, 0, 21, 0,  9, 0,  5, 3, 0,  44, 4, 0, 0,  31, ...
  0, 1, 1, 34, 0, 13, 1,  7, 4, 0,  81, 5, 5, 0,  55, ...
  0, 1, 0, 55, 1, 19, 0, 10, 5, 0, 149, 6, 0, 0,  96, ...
  0, 1, 1, 89, 0, 28, 0, 14, 7, 1, 274, 8, 8, 0, 169, ...

Alois P. Heinz, Antidiagonals n = 0..140

Columns k=0-21, 23, 25-28 give: A000007, A000012, A059841, A000045(n+1), A079978, A000930, A121262, A003269(n+1), A182097, A079998, A000073(n+2), A003520, A079977, A079979, A060945, A005708, A001687(n+1), A017817, A082784, A079971, A006498, A005709, A052920, A120400, A060961, A005710, A013979.
Main diagonal gives A246691.
Cf. A246688, A246720 (the same for partitions).

b:= proc(n, i) b(n, i):= `if`(n=0, [[]], `if`(i>n, [],
      [map(x->[i, x[]], b(n-i, i+1))[], b(n, i+1)[]]))
    end:
f:= proc() local i, l; i, l:=0, [];
      proc(n) while n>=nops(l)
        do l:=[l[], b(i, 1)[]]; i:=i+1 od; l[n+1]
      end
    end():
g:= proc(n, l) option remember; `if`(n=0, 1,
      add(`if`(i>n, 0, g(n-i, l)), i=l))
    end:
A:= (n, k)-> g(n, f(k)):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, i_] := b[n, i] = If[n == 0, {{}}, If[i>n, {}, Join[Prepend[#, i]& /@ b[n - i, i + 1], b[n, i + 1]]]];
f = Module[{i = 0, l = {}}, Function[n, While[n >= Length[l], l = Join[l, b[i, 1]]; i++]; l[[n + 1]]]];
g[n_, l_] := g[n, l] = If[n==0, 1, Sum[If[i>n, 0, g[n - i, l]], {i, l}]];
A[n_, k_] := g[n, f[k]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 07 2020, after Alois P. Heinz *)

A001641 A Fielder sequence: a(n) = a(n-1) + a(n-2) + a(n-4).

Original entry on oeis.org

1, 3, 4, 11, 16, 30, 50, 91, 157, 278, 485, 854, 1496, 2628, 4609, 8091, 14196, 24915, 43720, 76726, 134642, 236283, 414645, 727654, 1276941, 2240878, 3932464, 6900996, 12110401, 21252275, 37295140, 65448411, 114853952, 201554638, 353703730, 620706779

Offset: 1

N. J. A. Sloane

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 = 1..1000
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
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.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Wikipedia, Companion matrix.
A. V. Zarelua, On Matrix Analogs of Fermat's Little Theorem, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no.
6, 2006, pp. 840-855.
Index entries for linear recurrences with constant coefficients, signature (1,1,0,1).

Cf. A001609, A001634 - A001636, A001638 - A001645, A001648, A001649, A060945.

I:=[1,3,4,11]; [n le 4 select I[n] else Self(n-1) + Self(n-2) + Self(n-4): n in [1..30]]; // G. C. Greubel, Jan 09 2018

A001641:=-(1+2*z+4*z**3)/(z+1)/(z**3-z**2+2*z-1); # conjectured by Simon Plouffe in his 1992 dissertation

LinearRecurrence[{1, 1, 0, 1}, {1, 3, 4, 11}, 50] (* T. D. Noe, Aug 09 2012 *)

a(n):=(sum(sum(binomial(j,n-4*k+3*j)*binomial(k,j),j,floor((4*k-n)/3),floor((4*k-n)/2))/k,k,1,n))*n; /* Vladimir Kruchinin, May 25 2011 */

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

G.f.: x*(1+2*x+4*x^3)/(1-x-x^2-x^4).
a(n) = n*Sum_{k=1..n} Sum_{j=floor((4*k-n)/3)..floor((4*k-n)/2)} binomial(j,n-4*k+3*j)*binomial(k,j)/k. - Vladimir Kruchinin, May 25 2011
a(n) = Trace(M^n), where M = [0, 0, 0, 1; 1, 0, 0, 0; 0, 1, 0, 1; 0, 0, 1, 1] is the companion matrix to the monic polynomial x^4 - x^3 - x^2 - 1. It follows that the sequence satisfies the Gauss congruences: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for positive integers n and r and all primes p. See Zarelua. - Peter Bala, Dec 31 2022

cp's OEIS Frontend

A006498 a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

PARI

Python

Formula

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

A017818 Expansion of 1/(1-x^3-x^4-x^5).

Views

Author

Keywords

Comments

Links

Programs

Magma

Magma

Mathematica

Formula

A060961 Number of compositions (ordered partitions) of n into 1's, 3's and 5's.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

A077930 Expansion of (1-x)^(-1)/(1+2*x+x^2+x^3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A181532 a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2; a(n) = a(n-1) + a(n-2) + a(n-4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A097472 Number of different candle trees having a total of m edges.

A238236 Expansion of (1-x-x^2)/((x-1)(x^3+3x^2+2*x-1)).