OFFSET
3,1
COMMENTS
This sequence can be thought of as the number of ways of rolling n 3-sided dice (with sides "A", "B", and "C") and obtaining at least one A and at least two B's.
The general formula is readily proved true by counting arguments.
LINKS
Vasily V. Zolotukhin, Table of n, a(n) for n = 3..2000
Index entries for linear recurrences with constant coefficients, signature (9,-31,51,-40,12).
FORMULA
a(n) = 3^n - 2^(n+1) - n*2^(n-1) + n + 1.
G.f.: x^3*(-3 + 5*x)/((-1 + 3*x)*(1 - 3*x + 2*x^2)^2). - Michael De Vlieger, Jul 04 2019.
a(n) = 9*a(n-1) - 31*a(n-2) + 51*a(n-3) - 40*a(n-4) + 12*a(n-5) for n > 7. - Stefano Spezia, Jul 05 2019
EXAMPLE
Suppose three-sided dice each have sides labeled A,B,C.
If there are three dice, then ABB, BAB, and BBA are the three strings resulting from rolling the dice satisfying the property of at least one A and at least two B's, hence a(3)=3 [Note a(0)=a(1)=a(2)=0].
If there are four such dice, there are 22 such permutations, hence a(4)=22: AABB, ABAB, ABBA, ABBB, ABBC, ABCB, ACBB, BAAB, BABA, BABB, BABC, BACB, BBAA, BBAB, BBAC, BBBA, BBCA, BCAB, BCBA, CABB, CBAB, CBBA.
MATHEMATICA
Array[3^# - 2^(# + 1) - # 2^(# - 1) + # + 1 &, 27, 3] (* or *)
CoefficientList[Series[(-3 + 5 x)/((-1 + 3 x) (1 - 3 x + 2 x^2)^2), {x, 0, 26}], x] (* Michael De Vlieger, Jul 04 2019 *)
PROG
(Python) [3**n-2**(n+1)-n*2**(n-1)+n+1 for n in range(3, 20)]
(Magma) [3^n-2^(n+1)-n*2^(n-1)+n+1: n in [3..40]]; // Vincenzo Librandi, Jul 05 2019
(SageMath) [3^n-2^(n+1)-n*2^(n-1)+n+1 for n in (3..40)] # Vasily V. Zolotukhin, Oct 09 2025
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Adam Vellender, Jul 04 2019
STATUS
approved