A309000 Number of strings of length n from a 3-symbol alphabet (A,B,C, say) containing at least one "A" and at least two "B"s.

3, 22, 105, 416, 1491, 5034, 16365, 51892, 161799, 498686, 1524705, 4635528, 14037627, 42391378, 127763925, 384536924, 1156232175, 3474201510, 10434138825, 31326533680, 94029932643, 282194655482, 846802070205, 2540859195396, 7623517110231, 22872497487694

Offset: 3

Author

Adam Vellender, Jul 04 2019

Keywords

• nonn
• easy

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.

Examples

			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.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (9,-31,51,-40,12).

Crossrefs

Cf. A269914, A269915, A269916, A269917, A186244, A186314.

Programs

Magma

[3^n-2^(n+1)-n*2^(n-1)+n+1: n in [3..40]]; // Vincenzo Librandi, Jul 05 2019

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 *)

Python

[3**n-2**(n+1)-n*2**(n-1)+n+1 for n in range(3,20)]

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