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,1

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

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

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]

Crossrefs

Cf. A242206, A242167, A242257, A242323.

Sequence in context: A370693 A323801 A222694 * A223559 A017055 A299859

Adjacent sequences: A243859 A243860 A243861 * A243863 A243864 A243865

Keyword

nonn

Author

Geoffrey Critzer, Jun 12 2014

Status

approved