OFFSET
0,6
COMMENTS
a(n) is the number of ways to split [n] into 2 intervals and perform the following:
1) in the first interval choose 2 subintervals and in the remaining subintervals (if there are any left), perform one of 2 possible tasks;
2) in the second interval choose 2 subintervals and in the remaining subintervals (if there are any left), perform one of 3 possible tasks.
LINKS
Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (15,-93,305,-558,540,-216).
FORMULA
a(n) = 15*a(n-1) - 93*a(n-2) + 305*a(n-3) - 558*a(n-4) + 540*a(n-5) - 216*a(n-6), n >= 6, a(0)=a(1)=a(2)=a(3)=0, a(4)=1, a(5)=15.
a(n) = Sum_{k=2..n-2} C(k,2)*2^(k-2)*C(n-k,2)*3^(n-k-2).
a(n) = 3^n * (n^2/6 - 17*n/6 + 15) - 2^n * (n^2/4 + 13*n/4 + 15). - Robert Israel, Jan 22 2024
EXAMPLE
The following diagrams illustrate the 890 cases for n = 7, where the bar separates intervals, x represents a chosen subinterval, and i represents i possible tasks that can be performed in the subinterval, i = 2,3.
Case, number of cases:
x x 2 2 2 | x x, 80;
x x 2 2 | x x 3, 216;
x x 2 | x x 3 3, 324;
x x| x x 3 3 3, 270.
MAPLE
seq( 3^n * (n^2/6 - 17 * n/6 + 15) - 2^n * (n^2/4 + 13*n/4 + 15), n=0..40); # Robert Israel, Jan 22 2024
MATHEMATICA
LinearRecurrence[{15, -93, 305, -558, 540, -216}, {0, 0, 0, 0, 1, 15}, 30] (* Paolo Xausa, Feb 23 2024 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Enrique Navarrete, Jan 22 2024
STATUS
approved