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

%I #96 Jun 17 2024 15:43:31

%S 1,0,1,1,2,2,4,5,8,11,17,24,36,52,77,112,165,241,354,518,760,1113,

%T 1632,2391,3505,5136,7528,11032,16169,23696,34729,50897,74594,109322,

%U 160220,234813,344136,504355,739169,1083304,1587660,2326828,3410133,4997792,7324621

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

%C For n>0, number of compositions (ordered partitions) of n into 2's, 3's and 4's. - _Len Smiley_, May 08 2001

%C Diagonal sums of trinomial triangle A071675 (Riordan array (1, x*(1+x+x^2))). - _Paul Barry_, Feb 15 2005

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

%C 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_, Jun 13 2024

%H Reinhard Zumkeller, <a href="/A013979/b013979.txt">Table of n, a(n) for n = 0..1000</a>

%H M. Cohen and Y. Kachi, <a href="https://doi.org/10.1007/978-3-031-60638-0_30">Recurrence Relations Rhythm</a>. 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.

%H C. K. Fan, <a href="http://dx.doi.org/10.1023/A:1022443327568">A Hecke algebra quotient and some combinatorial applications</a>, J. Algebraic Combin. 5 (1996), no. 3, 175-189.

%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^0_n.]

%H R. Mullen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Mullen/mullen2.html">On Determining Paint by Numbers Puzzles with Nonunique Solutions</a>, JIS 12 (2009) 09.6.5.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,1,1).

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

%F a(n) = a(n-4) + a(n-3) + a(n-2). - _Jon E. Schoenfield_, Aug 07 2006

%F a(n) + a(n+1) = A000930(n+1). - _R. J. Mathar_, Mar 14 2011

%F a(n) = (1/3)*(A000930(n) + A097333(n-2) + (-1)^n), n>1. - _Ralf Stephan_, Aug 15 2013

%F a(n) = (-1)^n * A077889(-4-n) = A107458(n+4) for all n in Z. - _Michael Somos_, Jun 20 2015

%F a(n) = Sum_{i=0..floor(n/2)} A078012(n-2*i). - _Paul Curtz_, Aug 18 2021

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

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

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

%t LinearRecurrence[{0,1,1,1}, {1,0,1,1}, 50] (* _G. C. Greubel_, Jul 17 2023 *)

%o (Haskell)

%o a013979 n = a013979_list !! n

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

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

%o -- _Reinhard Zumkeller_, Mar 23 2012

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 50); Coefficients(R!( 1/((1+x)*(1-x-x^3)) )); // _G. C. Greubel_, Jul 17 2023

%o (SageMath)

%o @CachedFunction

%o def b(n): return 1 if (n<3) else b(n-1) + b(n-3) # b = A000930

%o def A013979(n): return ((-1)^n +2*b(n) -b(n-1) +b(n-2) -int(n==1))/3

%o [A013979(n) for n in (0..50)] # _G. C. Greubel_, Jul 17 2023

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

%Y First differences of A023435.

%Y Cf. A000045, A000930, A001634, A006498, A071675, A077889, A078012, A097333, A107458.

%K nonn,easy

%O 0,5

%A _N. J. A. Sloane_