|
| |
|
|
A060961
|
|
Number of compositions (ordered partitions) of n into 1's, 3's and 5's.
|
|
6
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
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
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
|
|
|
|
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))), n>0, a(0)=1. - Vladimir Kruchinin, Mar 11 2013
|
|
|
MATHEMATICA
|
LinearRecurrence[{1, 0, 1, 0, 1}, {1, 1, 1, 2, 3}, 50] (* Harvey P. Dale, Apr 21 2022 *)
|
|
|
PROG
|
(PARI) N=66; x='x+O('x^N); Vec(1/(1-x-x^3-x^5)) \\ Joerg Arndt, Oct 21 2012
(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
|
|
|
CROSSREFS
|
Cf. A060945 (compositions into 1's, 2's, and 4's).
Cf. A027907 (trinomial coefficients triangle).
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
