%I #28 Jul 03 2023 07:50:54
%S 1,3,9,25,71,201,569,1611,4561,12913,36559,103505,293041,829651,
%T 2348889,6650121,18827671,53304473,150914409,427265435,1209664161,
%U 3424773601,9696140959,27451493281,77720042081,220039211683,622970000809,1763738467065,4993456147431
%N Lengths of successive words (starting with a) under the substitution: {a -> aab, b -> aac, c -> a}.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2, 2, 1).
%F a(n) = 2*a(n-1) + 2*a(n-2) + a(n-3).
%F G.f.: (1+x+x^2) / (1-2*x-2*x^2-x^3).
%F a(n-1) = sum(k=1..n, sum(m=0..n-k, (sum(j=0..k, binomial(j, n-m-3*k+2*j) *binomial(k, j))) *sum(i=ceiling(m/2)..m, binomial(i, m-i)*binomial(k+i-1, k-1)))). - _Vladimir Kruchinin_, May 05 2011
%e a => aab => aabaabaac => aabaabaacaabaabaacaabaaba, thus a(0) = 1, a(1) = 3, a(2) = 9, a(3) = 25.
%p a:= n-> (<<0|1|0>, <0|0|1>, <1|2|2>>^n. <<1, 3, 9>>)[1, 1]:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, May 06 2011
%t Length/@SubstitutionSystem[{a->{a,a,b},b->{a,a,c},c->a},{a},15] (* The program generates the first 16 terms of the sequence. To generate more, increase the final ("15") constant. *) (* _Harvey P. Dale_, Sep 05 2022 *)
%o (Maxima) a(n):=b(n+1);
%o b(n):= sum(sum((sum(binomial(j,n+1-m-3*k+2*j) *binomial(k,j), j,0, k)) *sum(binomial(i,m-i) *binomial(k+i-1,k-1),i,ceiling(m/2),m), m,0, n+1-k), k,1,n+1); /* _Vladimir Kruchinin_, May 05 2011 */
%Y Cf. A101399, A101400.
%K easy,nonn
%O 0,2
%A _Jeroen F.J. Laros_, Jan 22 2005
|