A051041 Number of squarefree quaternary words of length n.

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

Offset: 0

Author

Eric W. Weisstein

Keywords

• nonn

Comments

a(n), n > 0, is a multiple of 4 by symmetry. - Michael S. Branicky, Jun 20 2022

Examples

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

Links

• A. M. Shur, Growth properties of power-free languages, Computer Science Review, Vol. 6 (2012), 187-208.
• A. M. Shur, Numerical values of the growth rates of power-free languages, arXiv:1009.4415 [cs.FL], 2010.
• Eric Weisstein's World of Mathematics, Squarefree Word.

Crossrefs

Cf. A006156.

Third column of A215075, multiplied by 24 (except for the first three terms). - Arseny Shur, Apr 26 2015

Programs

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
print(aupton(14)) # Michael S. Branicky, Jun 20 2022

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

Extensions

More terms from David Wasserman, Feb 27 2002

a(13)-a(15) from John W. Layman, Mar 03 2004

a(16)-a(25) from Max Alekseyev, Jul 03 2006

a(26)-a(30) from Giovanni Resta, Mar 20 2020