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

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

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

Examples

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

Links

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

Crossrefs

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.

Programs

Haskell

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

Magma

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

Mathematica

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

SageMath

@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

Formula

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