A353047 Number of length n words on alphabet {0,1,2} that contain each of the subwords 01, 02, 10, 12, 20, and 21 as (not necessarily contiguous) subwords.

12, 108, 600, 2664, 10404, 37476, 127920, 420768, 1348476, 4242204, 13169160, 40490712, 123635028, 375623892, 1137095520, 3433306896, 10347106860, 31141984140, 93639862200, 281372571720, 845074016772, 2537235316548, 7615933808400, 22856659795584, 68588501433564

Offset: 5

Author

Geoffrey Critzer, Apr 19 2022

Keywords

• nonn
• easy

Comments

Let A be an alphabet containing m letters. Let S be the set of m^2-m ordered two-tuples of distinct letters in A. The generating function for the number of length n words on A that contain each two-tuple in S as a (not necessarily contiguous) subword is m*(m-1)!^2*x^(2*m-1)/((1-m*x)*Product_{k=1..m-1} (1-k*x)^2).

Appears to equal 12 times A222993, except that sequence only has a conjectured formula. - N. J. A. Sloane, Jun 17 2022

Examples

			a(5) = 12 because we have: {0, 1, 2, 0, 1}, {0, 1, 2, 1, 0}, {0, 2, 1, 0, 2}, {0, 2, 1, 2, 0}, {1, 0, 2, 0, 1}, {1, 0, 2, 1, 0}, {1, 2, 0, 1, 2}, {1, 2, 0, 2, 1}, {2, 0, 1, 0, 2}, {2, 0, 1, 2, 0}, {2, 1, 0, 1, 2}, {2, 1, 0, 2, 1}.
		

Links

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

Crossrefs

Cf. A058809, A222993, A005803 (binary words).

Programs

Mathematica

nn = 15; vertices = Level[Outer[ List, {a, b, c}, {d, e, f}, {h, i, j}, {k, l, m}, {n, o, p}, {q, r, s}], {6}]; x = {a -> b, d -> e, i -> j, o -> p}; y = {b -> c, h -> i, k -> l, r -> s}; z = {e -> f, l -> m, n -> o, q -> r}; replacementlist = Table[vertices[[kk]] -> kk, {kk, 1, 729}]; G= Normal[SparseArray[Flatten[Table[Normal[Merge[ Map[{mm, vertices[[mm]] /. # /. replacementlist} -> 1 &, {x, y, z}], Total]], {mm, 1, 729}]]]]; Iwg =
Inverse[IdentityMatrix[729] - w G]; CoefficientList[ Series[Iwg[[1, 729]], {w, 0, nn}], w]

Formula

G.f.: (12*x^5)/((1 - 2*x)^2*(1 - x)^2*(1 - 3*x)).