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

Author

Nathaniel Johnston, Mar 30 2011

Keywords

• nonn

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

Examples

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

Links

• Paul Tek, Table of n, a(n) for n = 1..2000
• Paul Tek, PERL program for this sequence

Crossrefs

Cf. A000295, A062714, A180632, A224986.