A353047 - OEIS

%I #27 Jun 17 2022 15:55:17

%S 12,108,600,2664,10404,37476,127920,420768,1348476,4242204,13169160,

%T 40490712,123635028,375623892,1137095520,3433306896,10347106860,

%U 31141984140,93639862200,281372571720,845074016772,2537235316548,7615933808400,22856659795584,68588501433564

%N 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.

%C 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).

%C Appears to equal 12 times A222993, except that sequence only has a conjectured formula. - _N. J. A. Sloane_, Jun 17 2022

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (9,-31,51,-40,12).

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

%e 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}.

%t 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 =

%t Inverse[IdentityMatrix[729] - w G]; CoefficientList[ Series[Iwg[[1, 729]], {w, 0, nn}], w]

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

%K nonn,easy

%O 5,1

%A _Geoffrey Critzer_, Apr 19 2022