OFFSET
0,3
COMMENTS
Number of compositions of n of the form d_1+d_2+...+d_k=n where d_i is in {1,2,4} if i>1 and d_1 is any positive integer.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..2000
Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1,-1).
FORMULA
G.f.: x/((1-x)*(1-x-x^2-x^4)).
a(n) = Sum_{m=0..n-1} Sum_{r=0..floor(m/4)} Sum_{j=0..floor((m-4*r)/2)} binomial(m-3*r-j,r)*binomial(m-4*r-j,j).
a(n) = 1+a(n-1)+a(n-2)+a(n-4) where a(0)=0, a(1)=1, a(2)=2, a(3)=4.
a(n) = A274110(n+1) - 1.
MAPLE
a:= proc(n) option remember;
`if`(n<1, 0, 1+add(a(n-j), j=[1, 2, 4]))
end:
seq(a(n), n=0..37); # Alois P. Heinz, Dec 20 2023
MATHEMATICA
LinearRecurrence[{2, 0, -1, 1, -1}, {0, 1, 2, 4, 7}, 38] (* Stefano Spezia, Dec 21 2023 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Kassie Archer, Dec 20 2023
STATUS
approved