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,3

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

Table of n, a(n) for n=0..36.

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

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

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

Prog

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

Crossrefs

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

Sequence in context: A034063 A034073 A114623 * A355805 A073031 A114138

Adjacent sequences: A079968 A079969 A079970 * A079972 A079973 A079974

Keyword

nonn

Author

Vladimir Baltic, Feb 17 2003

Extensions

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

Status

approved