A060961 Number of compositions (ordered partitions) of n into 1's, 3's and 5's.

1, 1, 1, 2, 3, 5, 8, 12, 19, 30, 47, 74, 116, 182, 286, 449, 705, 1107, 1738, 2729, 4285, 6728, 10564, 16587, 26044, 40893, 64208, 100816, 158296, 248548, 390257, 612761, 962125, 1510678, 2371987, 3724369, 5847808, 9181920, 14416967, 22636762, 35543051

Offset: 0

Author

Len Smiley, May 08 2001

Keywords

• nonn
• easy

Comments

Lim_{n->infinity} a(n)/a(n-1) = 1.57014... = A293506. This is the largest absolute value of a root of the characteristic polynomial of the recursion (x^5 - x^4 - x^2 - 1), same as the inverse of smallest absolute value of a root of the reciprocal (here -x^5 - x^3 - x + 1, the denominator of the g.f.) of the characteristic polynomial. - Bob Selcoe, Jun 09 2013

From Bob Selcoe, May 01 2014: (Start)

Since a(n) is a recurrence of the form: a(n) = Sum_(a(n-Fi)), i=1..z; where F(i)-F(i-1) is constant (C), and seed values are a(0)=1 and a(<0)=0 exclusively; then apply the following definitions:

I. For T-nomial triangles T(m,k), let T be defined as the number of terms in the recurrence equaling a(n). That is, T => z => ((Fz-F1)/C)+1. In this sequence, F1=1, C=2 and T => z => ((5-1)/2)+1 = 3. Therefore, the applicable triangle is trinomial for this sequence.

II. Let m' be defined as the maxval of m and k' the minval of k such that n = m'*F1+k'*C. For example, in this sequence: n=7: m'=7 and k'=0 because 7*1+0*2=7. (Note that m' always equals n and k' always equals 0 when F1=1)

III. THEN: a(n) = Sum_T((m'-C*j/G),(k'+F1*j/G)), j=0..q; where (m'-C*q)) is the floor and (k'+F1*q) the ceiling for the T-nomial triangle, and G is the greatest common factor of all Fi. In general, T, F1, C and G are invariant across n; while m', k' and q vary (the exception being k' always equaling 0 when F1=1). In this sequence, T=3, F1=1, C=2, G=1 and k'=0; m' and q vary with a(n).

Example 1. a(11): T=3, F1=1, C=2, G=1, k'=0 (invariant); m'=11, q=4. a(11) = 74 => T(11,0) + T(9,1) + T(7,2) + T(5,3) + T(3,4) for T==trinomial triangle. T(11,0)=1, T(9,1)=9, T(7,2)=28, T(5,3)=30 and T(3,4)=6. 1+9+28+30+6 = 74 (Note that T(3,4) is the final term because the ostensible next term [T(1,5)] is not contained in the trinomial triangle. Therefore q=4.)

Example 2. a(14): m'=14, q=5. a(14) = 286 => T(14,0) + T(12,1) + T(10,2) + T(8,3) + T(6,4) + T(4,5) => 1+12+55+112+90+16 = 286. (End)

Links

• Harry J. Smith, Table of n, a(n) for n = 0..500
• Sergey Dovgal and Sergey Kirgizov, Structure and growth of R-bonacci words, arXiv:2310.01213 [math.CO], 2023. See p. 5.
• Index entries for linear recurrences with constant coefficients, signature (1,0,1,0,1).

Crossrefs

Cf. A293506 (growth power).

Cf. A060945 (compositions into 1's, 2's, and 4's).

Cf. A027907 (trinomial coefficients triangle).

Programs

Mathematica

CoefficientList[Series[ 1 /(1 - z - z^3 - z^5), {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jun 10 2011 *)
LinearRecurrence[{1,0,1,0,1},{1,1,1,2,3},50] (* Harvey P. Dale, Apr 21 2022 *)

Maxima

a(n):=sum((sum(binomial(j,3*n-5*m+2*j)*binomial(2*m-n,j),j,0,2*m-n)),m,floor((n+1)/2),n); /* Vladimir Kruchinin, Mar 11 2013 */

PARI

my(N=66, x='x+O('x^N)); Vec(1/(1-x-x^3-x^5)) \\ Joerg Arndt, Oct 21 2012

Formula

a(n) = a(n-1) + a(n-3) + a(n-5).

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

a(n) = Sum_{m=floor((n+1)/2)..n} Sum_{j=0..2*m-n} binomial(j,3*n-5*m+2*j)*binomial(2*m-n,j). - Vladimir Kruchinin, Mar 11 2013

Extensions

a(0)=1 prepended by Joerg Arndt, Oct 21 2012