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

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

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

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

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

Example

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

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

Prog

(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<x>:=PowerSeriesRing(Integers(), 50); Coefficients(R!( 1/((1+x)*(1-x-x^3)) )); // 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

Crossrefs

Cf. A060945 (Ordered partitions into 1's, 2's and 4's).

First differences of A023435.

Cf. A000930, A001634, A071675, A077889, A078012, A097333, A107458.

Sequence in context: A240734 A328460 A238478 * A107458 A274142 A006206

Adjacent sequences: A013976 A013977 A013978 * A013980 A013981 A013982

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved