A243862 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.

216, 2160, 14544, 78840, 374568, 1623420, 6580848, 25350384, 93835368, 336429336, 1175333232, 4019312448, 13502627088, 44688347724, 146041135932, 472142876544, 1512373800624, 4806068123880, 15168176407512, 47586553527408, 148517566558116, 461424138047280

Offset: 10

Author

Geoffrey Critzer, Jun 12 2014

Keywords

• nonn

Comments

The expected wait time (average number of digits necessary) to see all 9 of the 2 bit strings is 18850259/711620 (approximately 26.4892).

Links

• Alois P. Heinz, Table of n, a(n) for n = 10..1000

Crossrefs

Cf. A242206, A242167, A242257, A242323.

Programs

Maple

b:= proc(n, t, s) option remember; `if`(s={}, 3^n, `if`(nops(s)>n,
       0, add(b(n-1, j, s minus {3*t+j}), j=0..2)))
    end:
a:= n-> 3*b(n-1, 0, {$0..8}):
seq(a(n), n=10..40);  # Alois P. Heinz, Jun 13 2014

Mathematica

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}];
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};
S = 1/(1 - 3z - a - b - c - d - e - f - g - h - i);
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}];
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]

Formula

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