login
Number of compositions (ordered partitions) of n into parts 1, 2, and 5.
3

%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