|
%I #25 Jun 13 2014 10:13:27
%S 216,2160,14544,78840,374568,1623420,6580848,25350384,93835368,
%T 336429336,1175333232,4019312448,13502627088,44688347724,146041135932,
%U 472142876544,1512373800624,4806068123880,15168176407512,47586553527408,148517566558116,461424138047280
%N Number of length n sequences on alphabet {0,1,2} that contain all of 00, 01, 02, 10, 11, 12, 20, 21, 22 as (possibly overlapping) contiguous subsequences.
%C The expected wait time (average number of digits necessary) to see all 9 of the 2 bit strings is 18850259/711620 (approximately 26.4892).
%H Alois P. Heinz, <a href="/A243862/b243862.txt">Table of n, a(n) for n = 10..1000</a>
%F G.f.: 12 *x^10 *(4*x^31 -29*x^30 +4*x^29 +137*x^28 -47*x^27 -414*x^26 +1491*x^25 +338*x^24 -6524*x^23 +1928*x^22 +7881*x^21 -4257*x^20 +7086*x^19 -2814*x^18 -28437*x^17 +30193*x^16 +18744*x^15 -47298*x^14 +17738*x^13 +13339*x^12 -14197*x^11 +18725*x^10 -17810*x^9 -13496*x^8 +35794*x^7 -19124*x^6 -6133*x^5 +12494*x^4 -6834*x^3 +1932*x^2 -288*x +18) / ((x-1) *(3*x-1) *(2*x-1) *(x+1) *(2*x^2-1) *(x^2+2*x-1) *(x^2+x-1) *(x^2-3*x+1) *(x^3+x^2+x-1) *(x^3-x^2-2*x+1) *(x^3-2*x^2-x+1) *(x^3+2*x-1) *(x^3-x^2+2*x-1) *(x^3+x^2-1) *(2*x^2+2*x-1) *(x^3+x-1) *(x^3+2*x^2+x-1) *(x^3-2*x^2+3*x-1)). - _Alois P. Heinz_, Jun 13 2014
%p b:= proc(n, t, s) option remember; `if`(s={}, 3^n, `if`(nops(s)>n,
%p 0, add(b(n-1, j, s minus {3*t+j}), j=0..2)))
%p end:
%p a:= n-> 3*b(n-1, 0, {$0..8}):
%p seq(a(n), n=10..40); # _Alois P. Heinz_, Jun 13 2014
%t sol = Solve[{a == va(z^2 + z a + z d + z g),b == vb(z^2 + z a + z d + z g), c == vc (z^2 + z a + z d + z g), d == vd(z^2 + z b + z e + z h), e == ve(z^2 + z b + z e + z h), f == vf(z^2 + z b + z e + z h), g == vg(z^2 + z c + z f + z i), h == vh(z^2 + z c + z f + z i), i == vi(z^2 + z c + z f + z i)}, {a, b, c, d, e, f, g, h, i}];
%t vsub = {va -> ua - 1, vb -> ub - 1, vc -> uc - 1, vd -> ud - 1, ve -> ue - 1, vf -> uf - 1, vg -> ug - 1, vh -> uh - 1, vi -> ui - 1};
%t S = 1/(1 - 3z - a - b - c - d - e - f - g - h - i);
%t Fz[ua_, ub_, uc_, ud_, ue_, uf_, ug_, uh_, ui_] = S/.sol/.vsub; tn = Table[Total[Map[Apply[Fz, #] &, Select[Tuples[{0, 1}, 9], Count[#, 0] == n &]]], {n, 1, 9}];
%t Drop[Flatten[CoefficientList[Series[1/(1 - 3z) - (Simplify[tn[[1]] - tn[[2]] + tn[[3]] - tn[[4]] + tn[[5]] - tn[[6]] + tn[[7]] - tn[[8]]] + tn[[9]]), {z, 0, 40}], z]], 10]
%Y Cf. A242206, A242167, A242257, A242323.
%K nonn
%O 10,1
%A _Geoffrey Critzer_, Jun 12 2014
|
