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

1, 1, 2, 3, 5, 9, 15, 26, 44, 75, 128, 218, 372, 634, 1081, 1843, 3142, 5357, 9133, 15571, 26547, 45260, 77164, 131557, 224292, 382396, 651948, 1111508, 1895013, 3230813, 5508222, 9390983, 16010713, 27296709, 46538235, 79343166, 135272384

Offset: 0

Author

Vladimir Baltic, Feb 17 2003

Keywords

• nonn

Comments

Number of ways of ordered sequences of nickels, dimes and quarters that add to 5n cents.

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

References

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

Links

• Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135
• Index entries for sequences related to making change.
• Index entries for linear recurrences with constant coefficients, signature (1,1,0,0,1).

Crossrefs

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014, A073031.

Programs

Maple

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

Mathematica

LinearRecurrence[{1, 1, 0, 0, 1}, {1, 1, 2, 3, 5}, 40] (* Jean-François Alcover, Nov 11 2015 *)

Maxima

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

Formula

Recurrence: a(n) = a(n-1)+a(n-2)+a(n-5).

G.f.: 1/(1-x-x^2-x^5).

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

With offset 1, the INVERT transform of (1 + x + x^4). - Gary W. Adamson, Apr 01 2017

Extensions

Entry revised by N. J. A. Sloane, Feb 23 2006