A188428 Number of strings of length n on three symbols containing all permutations of those three symbols as substrings (factors), divided by six.

0, 0, 0, 0, 0, 0, 0, 0, 1, 9, 54, 276, 1282, 5585, 23223, 93146, 362928, 1380535, 5145692, 18846775, 67982489, 241940204, 850777688, 2959796467, 10197732687, 34828459508, 118003182174, 396897710483, 1326018464696, 4402883891950, 14536059784925, 47737688829399

Offset

1,10

Comments

Division by six is performed so that strings that are identical up to swapping the symbols are not double-counted.

The corresponding sequence for strings of length n on two symbols is given by a(n) = 2^(n-1) - n = A000295(n-1).

Links

Paul Tek, Table of n, a(n) for n = 1..2000

Paul Tek, PERL program for this sequence

Example

a(9) = 1 because there are 6 strings of length 9 on the three symbols "1", "2", and "3" containing each of "123", "132", "213", "231", "312", and "321" as substrings: they are "123121321" and the five other strings obtained by swapping the roles of "1", "2", and "3" in that string.
The substrings must be contiguous -- if they were allowed to be non-contiguous (i.e., subsequences) then there would be a valid string of length 7: "1232132" (see A062714).

Crossrefs

Cf. A000295, A062714, A180632, A224986.

Sequence in context: A027472 A022637 A001392 * A243415 A276602 A079764

Adjacent sequences: A188425 A188426 A188427 * A188429 A188430 A188431

Keyword

nonn

Author

Nathaniel Johnston, Mar 30 2011

Status

approved