OFFSET
0,5
COMMENTS
a(n) is the number of ways to split [n] into 2 intervals and perform the following:
1) in the first interval choose one subinterval and in the remaining subintervals (if there are any left), perform one of 3 possible tasks;
2) in the second interval choose 2 subintervals and in the remaining subintervals (if there are any left), perform one of 2 possible tasks.
LINKS
Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (12,-57,134,-156,72).
FORMULA
a(n) = 12*a(n-1) - 57*a(n-2) + 134*a(n-3) - 156*a(n-4) + 72*a(n-5), n >= 5, a(0)=a(1)=a(2)=0, a(3)=1, a(4)=12.
a(n) = Sum_{k=2..n-2} k*3^(k-1)*(n-k,2)*2^(n-k-2).
a(n) = 3^n*(n - 8) + 2^(n-2)*(n^2 + 9*n + 32). - Stefano Spezia, Jan 23 2024
EXAMPLE
The following diagrams illustrate the 87 cases for n = 5, 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 x 2 2, 24;
x 3| x x 2, 36;
x 3 3| x x, 27.
MATHEMATICA
LinearRecurrence[{12, -57, 134, -156, 72}, {0, 0, 0, 1, 12}, 30] (* Paolo Xausa, Feb 23 2024 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Enrique Navarrete, Jan 22 2024
STATUS
approved