|
%I #69 Oct 18 2023 12:23:19
%S 1,1,1,2,3,5,8,12,19,30,47,74,116,182,286,449,705,1107,1738,2729,4285,
%T 6728,10564,16587,26044,40893,64208,100816,158296,248548,390257,
%U 612761,962125,1510678,2371987,3724369,5847808,9181920,14416967,22636762,35543051
%N Number of compositions (ordered partitions) of n into 1's, 3's and 5's.
%C 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
%C From _Bob Selcoe_, May 01 2014: (Start)
%C 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:
%C 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.
%C 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)
%C 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).
%C 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.)
%C 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)
%H Harry J. Smith, <a href="/A060961/b060961.txt">Table of n, a(n) for n = 0..500</a>
%H Sergey Dovgal and Sergey Kirgizov, <a href="https://arxiv.org/abs/2310.01213">Structure and growth of R-bonacci words</a>, arXiv:2310.01213 [math.CO], 2023. See p. 5.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,0,1).
%F a(n) = a(n-1) + a(n-3) + a(n-5).
%F G.f.: 1 / (1-(x+x^3+x^5)).
%F 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))), n>0, a(0)=1. - _Vladimir Kruchinin_, Mar 11 2013
%t CoefficientList[Series[ 1 /(1 - z - z^3 - z^5), {z, 0, 100}], z] (* _Vladimir Joseph Stephan Orlovsky_, Jun 10 2011 *)
%t LinearRecurrence[{1,0,1,0,1},{1,1,1,2,3},50] (* _Harvey P. Dale_, Apr 21 2022 *)
%o (PARI) N=66; x='x+O('x^N); Vec(1/(1-x-x^3-x^5)) \\ _Joerg Arndt_, Oct 21 2012
%o (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
%Y Cf. A293506 (growth power).
%Y Cf. A060945 (compositions into 1's, 2's, and 4's).
%Y Cf. A027907 (trinomial coefficients triangle).
%K nonn,easy
%O 0,4
%A _Len Smiley_, May 08 2001
%E a(0)=1 prepended by _Joerg Arndt_, Oct 21 2012
|
