cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

A006156 Number of ternary squarefree words of length n.

Original entry on oeis.org

1, 3, 6, 12, 18, 30, 42, 60, 78, 108, 144, 204, 264, 342, 456, 618, 798, 1044, 1392, 1830, 2388, 3180, 4146, 5418, 7032, 9198, 11892, 15486, 20220, 26424, 34422, 44862, 58446, 76122, 99276, 129516, 168546, 219516, 285750, 372204, 484446, 630666, 821154
Offset: 0

Views

Author

Keywords

Comments

a(n), n > 0, is a multiple of 3 by symmetry. - Michael S. Branicky, Jul 21 2021

Examples

			Let the alphabet be {a,b,c}. Then:
a(1)=3: a, b, c.
a(2)=6: all xy except aa, bb, cc.
a(3)=12: aba, abc, aca, acb and similar words beginning with b and c, for a total of 12.
		

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Crossrefs

Second column of A215075, multiplied by 3!=6.

Programs

  • Mathematica
    (* A simple solution (though not at all efficient beyond n = 12) : *) a[0] = 1; a[n_] := a[n] = Length @ DeleteCases[Tuples[Range[3], n] , {a___, b__, b__, c___} ]; s = {}; Do[Print["a[", n, "] = ", a[n]]; AppendTo[s, a[n]], {n, 0, 12}]; s (* Jean-François Alcover, May 02 2011 *)
    Length/@NestList[DeleteCases[Flatten[Outer[Append, #, Range@3, 1], 1], {_, x__, x__, _}] &, {{}}, 20] (* Vladimir Reshetnikov, May 16 2016 *)
  • 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("0")
        for n in range(1, nn+1):
            an = 3*len(sfs)
            sfsnew = set(s+i for s in sfs for i in "012" if isf(s+i))
            alst, sfs = alst+[an], sfsnew
            if verbose: print(n, an)
        return alst
    print(aupton(40)) # Michael S. Branicky, Jul 21 2021

Formula

a(n) >= 2^(n/17), see Zeilberger. Let L = lim_{n->infinity} a(n)^(1/n); then L exists and Grimm proves 1.109999 < L < 1.317278. - Charles R Greathouse IV, Nov 29 2013
L exists since a(n) is submultiplicative; 1.3017597 < L < 1.3017619 (Shur 2012); the gap between the bounds can be made less than any given constant. - Arseny Shur, Apr 22 2015

Extensions

Links corrected by Eric Rowland, Sep 16 2010

A323487 Number of length-n ternary words that are bi-maximally squarefree.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 18, 0, 24, 0, 48, 42, 18, 12, 48, 78, 36, 66, 108, 102, 240, 222, 360, 330, 696, 690, 858, 1086, 1692, 1920, 2604, 3156, 4284, 5370, 7308, 9270, 12036, 15756, 20688, 26562, 34500, 44274, 59058, 75576
Offset: 1

Views

Author

Jeffrey Shallit, Jan 16 2019

Keywords

Comments

A word is squarefree if it contains no block of the form XX, where X is a nonempty block. A word is bi-maximally squarefree if it cannot be extended on either the left or right to a longer squarefree word.
All terms are multiples of 6 due to possible renamings of letters. - Michael S. Branicky, Sep 01 2021

Examples

			For n = 7 the six possibilities are 0102010 and all renamings of the letters.
For n = 15 the six possibilities are 010210120102101 and all renamings of the letters.
		

Crossrefs

Cf. A282212, which is the one-sided version of maximally squarefree.

Programs

  • Python
    def isf(w): # incrementally squarefree (check factors ending in last letter)
        for l in range(1, len(w)//2 + 1):
            if w[-2*l:-l] == w[-l:]: return False
        return True
    def is_bmsf(w, sfsnew): # is w bi-maximally squarefree
        lefts, rights = [c+w for c in "123"], [w+c for c in "123"]
        return all(x not in sfsnew for x in lefts + rights)
    def aupton(nn):
        alst, sfs = [], set("123")
        for n in range(1, nn+1):
            sfsnew = set(w+c for w in sfs for c in "123" if isf(w+c))
            an = len([w for w in sfs if is_bmsf(w, sfsnew)])
            alst.append(an)
            sfs = sfsnew
        return alst
    print(aupton(30)) # Michael S. Branicky, Sep 01 2021

Extensions

a(31)-a(58) from Michael S. Branicky, Sep 01 2021
Showing 1-2 of 2 results.