%I #35 Dec 04 2023 01:01:50
%S 1,1,2,3,5,9,15,26,44,75,128,218,372,634,1081,1843,3142,5357,9133,
%T 15571,26547,45260,77164,131557,224292,382396,651948,1111508,1895013,
%U 3230813,5508222,9390983,16010713,27296709,46538235,79343166,135272384
%N Number of compositions (ordered partitions) of n into parts 1, 2, and 5.
%C Number of ways of ordered sequences of nickels, dimes and quarters that add to 5n cents.
%C Number of permutations satisfying -k <= p(i)-i <= r and p(i)-i not in I, i=1..n, with k=1, r=4, I={2,3}.
%D D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.
%H Vladimir Baltic, <a href="http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135
%H <a href="/index/Mag#change">Index entries for sequences related to making change.</a>
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,0,1).
%F Recurrence: a(n) = a(n-1)+a(n-2)+a(n-5).
%F G.f.: 1/(1-x-x^2-x^5).
%F a(n) = Sum_{k=0..n} Sum_{j=floor((5*k-n)/4)..k} C(j,n-5*k+4*j)*C(k,j). - _Vladimir Kruchinin_, Dec 15 2011
%F With offset 1, the INVERT transform of (1 + x + x^4). - _Gary W. Adamson_, Apr 01 2017
%p a:= n-> (Matrix(5, (i,j)-> if i+1=j or j=1 and member(i,[1, 2, 5]) then 1 else 0 fi)^n)[1, 1]: seq(a(n), n=0..40); # _Alois P. Heinz_, Oct 07 2008
%t LinearRecurrence[{1, 1, 0, 0, 1}, {1, 1, 2, 3, 5}, 40] (* _Jean-François Alcover_, Nov 11 2015 *)
%o (Maxima)
%o a(n):=sum(sum(binomial(j,n-5*k+4*j)*binomial(k,j),j,floor((5*k-n)/4),k),k,0,n); /* _Vladimir Kruchinin_, Dec 15 2011 */
%Y Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014, A073031.
%K nonn
%O 0,3
%A _Vladimir Baltic_, Feb 17 2003
%E Entry revised by _N. J. A. Sloane_, Feb 23 2006