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,2

Comments

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

Links

Table of n, a(n) for n=0..32.

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.

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

Crossrefs

Cf. A006156.

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

Sequence in context: A261584 A347990 A002842 * A192626 A294782 A002906

Adjacent sequences: A051038 A051039 A051040 * A051042 A051043 A051044

Keyword

nonn

Author

Eric W. Weisstein

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

Status

approved