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

%I #15 Jun 03 2013 11:23:59

%S 0,0,0,0,0,0,0,0,1,9,54,276,1282,5585,23223,93146,362928,1380535,

%T 5145692,18846775,67982489,241940204,850777688,2959796467,10197732687,

%U 34828459508,118003182174,396897710483,1326018464696,4402883891950,14536059784925,47737688829399

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

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

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

%H Paul Tek, <a href="/A188428/b188428.txt">Table of n, a(n) for n = 1..2000</a>

%H Paul Tek, <a href="/A188428/a188428.txt">PERL program for this sequence</a>

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

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

%Y Cf. A000295, A062714, A180632, A224986.

%K nonn

%O 1,10

%A _Nathaniel Johnston_, Mar 30 2011