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

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

Links

Table of n, a(n) for n=5..29.

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

Formula

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

Example

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

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]

Crossrefs

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

Sequence in context: A154671 A321672 A241230 * A037972 A111990 A053469

Adjacent sequences: A353044 A353045 A353046 * A353048 A353049 A353050

Keyword

nonn,easy

Author

Geoffrey Critzer, Apr 19 2022

Status

approved