|
|
A051041
|
|
Number of squarefree quaternary words of length n.
|
|
4
|
|
|
1, 4, 12, 36, 96, 264, 696, 1848, 4848, 12768, 33480, 87936, 230520, 604608, 1585128, 4156392, 10895952, 28566216, 74887056, 196322976, 514662960, 1349208600, 3536962584, 9272217936, 24307198464, 63721617888, 167046745992, 437914664688, 1147996820376, 3009483583056, 7889385389784, 20682088837608, 54218261608896
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
Let L be the limit lim a(n)^{1/n}, which exists because a(n) is a submultiplicative sequence. Then L=2.6215080... (Shur 2010). See (Shur 2012) for the methods of estimating such limits. - Arseny Shur, Apr 26 2015
|
|
EXAMPLE
|
There are 96 quaternary squarefree words of length 4: each of the words 0102, 0120, 0121, 0123 has 4!=24 images under the permutations of the set {0,1,2,3}. - Arseny Shur, Apr 26 2015
G.f. = 1 + 4*x + 12*x^2 + 36*x^3 + 96*x^4 + 264*x^5 + 696*x^6 + 1848*x^7 + ....
|
|
PROG
|
(Python)
def isf(s): # incrementally squarefree (check factors ending in last letter)
for l in range(1, len(s)//2 + 1):
if s[-2*l:-l] == s[-l:]: return False
return True
def aupton(nn, verbose=False):
alst, sfs = [1], set("1")
for n in range(1, nn+1):
an = 4*len(sfs)
sfsnew = set(s+i for s in sfs for i in "0123" if isf(s+i))
alst, sfs = alst+[an], sfsnew
if verbose: print(n, an)
return alst
|
|
CROSSREFS
|
Third column of A215075, multiplied by 24 (except for the first three terms). - Arseny Shur, Apr 26 2015
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|