A051041 -id:A051041 - cp's OEIS frontend

A215075 T(n,k) = Number of squarefree words of length n in a (k+1)-ary alphabet, with new values 0..k introduced in increasing order.

1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 3, 0, 1, 1, 2, 4, 5, 0, 1, 1, 2, 4, 11, 7, 0, 1, 1, 2, 4, 12, 29, 10, 0, 1, 1, 2, 4, 12, 39, 77, 13, 0, 1, 1, 2, 4, 12, 40, 138, 202, 18, 0, 1, 1, 2, 4, 12, 40, 153, 503, 532, 24, 0, 1, 1, 2, 4, 12, 40, 154, 638, 1864, 1395, 34, 0, 1, 1, 2, 4, 12, 40, 154, 659

Offset: 1

R. H. Hardin, Aug 02 2012

Alternative definition: for (k+1)-ary words u=u_1...u_n and v=v_1...v_n, let u~v if there exists a permutation t of the alphabet such that v_i=t(u_i), i=1,...,n. Then ~ preserves length and squarefreeness, and T(n,k) is the number of equivalence classes of (k+1)-ary squarefree words of length n. - Arseny Shur, Apr 26 2015

			Table starts
.1..1....1.....1......1......1......1......1......1......1......1......1......1
.1..1....1.....1......1......1......1......1......1......1......1......1......1
.1..2....2.....2......2......2......2......2......2......2......2......2......2
.0..3....4.....4......4......4......4......4......4......4......4......4......4
.0..5...11....12.....12.....12.....12.....12.....12.....12.....12.....12.....12
.0..7...29....39.....40.....40.....40.....40.....40.....40.....40.....40.....40
.0.10...77...138....153....154....154....154....154....154....154....154....154
.0.13..202...503....638....659....660....660....660....660....660....660....660
.0.18..532..1864...2825...3085...3113...3114...3114...3114...3114...3114...3114
.0.24.1395..6936..12938..15438..15893..15929..15930..15930..15930..15930..15930
.0.34.3664.25868..60458..81200..86857..87599..87644..87645..87645..87645..87645
.0.44.9605.96512.285664.442206.502092.513649.514795.514850.514851.514851.514851
...
Some solutions for n=6 k=4
..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
..1....1....1....1....1....1....1....1....1....1....1....1....1....1....1....1
..2....2....2....2....2....2....2....2....2....2....0....2....2....2....0....2
..3....3....0....0....1....3....0....3....1....0....2....3....3....3....2....1
..1....2....3....3....0....0....3....1....3....2....1....4....1....4....0....0
..0....0....1....0....3....3....2....3....1....1....2....1....2....0....1....2

R. H. Hardin, Table of n, a(n) for n = 1..345
A. M. Shur, Growth of Power-Free Languages over Large Alphabets, CSR 2010, LNCS vol. 6072, 350-361.
A. M. Shur, Numerical values of the growth rates of power-free languages, arXiv:1009.4415 [cs.FL], 2010.

Column 2 is A060688(n-1), or A006156 divided by 6 (for n>1).

Column 3 is A118311, or A051041 divided by 24 (for n>3).

From Arseny Shur, Apr 26 2015: (Start)
Let L_k be the limit lim T(n,k)^{1/n}, which exists because T(n,k) is a submultiplicative sequence for any k. Then L_k=k-1/k-1/k^3-O(1/k^5) (Shur, 2010).
Exact values of L_k for small k, rounded up to several decimal places:
L_2=1.30176..., L_3=2.6215080..., L_4=3.7325386... (for L_5,...,L_14 see Shur arXiv:1009.4415).
Empirical observation: for k=2 the O-term in the general formula is slightly bigger than 2/k^5, and for k=3,...,14 this O-term is slightly smaller than 2/k^5.
(End)

A214943 T(n,k) = Number of squarefree words of length n in a (k+1)-ary alphabet.

Original entry on oeis.org

2, 3, 2, 4, 6, 2, 5, 12, 12, 0, 6, 20, 36, 18, 0, 7, 30, 80, 96, 30, 0, 8, 42, 150, 300, 264, 42, 0, 9, 56, 252, 720, 1140, 696, 60, 0, 10, 72, 392, 1470, 3480, 4260, 1848, 78, 0, 11, 90, 576, 2688, 8610, 16680, 15960, 4848, 108, 0, 12, 110, 810, 4536, 18480, 50190, 80040

Offset: 1

R. H. Hardin, Jul 30 2012

Table starts
.2..3...4....5.....6.....7......8......9.....10......11......12......13......14
.2..6..12...20....30....42.....56.....72.....90.....110.....132.....156.....182
.2.12..36...80...150...252....392....576....810....1100....1452....1872....2366
.0.18..96..300...720..1470...2688...4536...7200...10890...15840...22308...30576
.0.30.264.1140..3480..8610..18480..35784..64080..107910..172920..265980..395304
.0.42.696.4260.16680.50190.126672.281736.569520.1068210.1886280.3169452.5108376
Empirical: row n is a polynomial of degree n
Coefficients for rows 1-12, highest power first:
...1...1
...1...1...0
...1...1...0...0
...1...1..-1..-1...0
...1...1..-2..-1...1...0
...1...1..-3..-2...2...1...0
...1...1..-4..-3...5...2..-2...0
...1...1..-5..-4...8...4..-4..-1...0
...1...1..-6..-5..12...8..-9..-4...2...0
...1...1..-7..-6..17..12.-17..-7...6...0...0
...1...1..-8..-7..23..17.-28.-13..10...2...2...0
...1...1..-9..-8..30..23.-45.-23..25...3..-2...4...0
Terms in column k are multiples of k+1 due to symmetry. - Michael S. Branicky, May 20 2021

			Some solutions for n=6 k=4
..0....1....1....0....4....4....4....0....2....2....1....2....1....4....1....1
..2....0....4....4....3....0....0....4....1....3....4....0....0....2....0....3
..1....4....2....1....2....3....2....1....0....4....3....2....2....1....2....1
..4....3....4....2....3....1....4....2....4....1....2....4....4....3....4....4
..1....0....3....0....0....4....2....3....2....0....1....3....0....4....2....3
..0....2....1....3....1....0....3....1....4....4....0....0....1....3....0....1

R. H. Hardin, Table of n, a(n) for n = 1..245
A. M. Shur, Growth of Power-Free Languages over Large Alphabets, CSR 2010, LNCS vol. 6072, 350-361.
A. M. Shur, Numerical values of the growth rates of power-free languages, arXiv:1009.4415 [cs.FL], 2010.

Cf. A006156 (column 2), A051041 (column 3), A214939 (column 4).

Cf. A002378 (row 2), A011379 (row 3), A047929(n+1) (row 4).

from itertools import product
def T(n, k):
  if n == 1: return k+1
  symbols = "".join(chr(48+i) for i in range(k+1))
  squares = ["".join(u)*2 for r in range(1, n//2 + 1)
    for u in product(symbols, repeat = r)]
  words = ("0" + "".join(w) for w in product(symbols, repeat=n-1))
  return (k+1)*sum(all(s not in w for s in squares) for w in words)
def atodiag(maxd): # maxd antidiagonals
  return [T(n, d+1-n) for d in range(1, maxd+1) for n in range(1, d+1)]
print(atodiag(11)) # Michael S. Branicky, May 20 2021

From Arseny Shur, Apr 26 2015: (Start)
Let L_k be the limit lim T(n,k)^{1/n}, which exists because T(n,k) is a submultiplicative sequence for any k. Then L_k=k-1/k-1/k^3-O(1/k^5) (Shur, 2010).
Exact values of L_k for small k, rounded up to several decimal places:
L_2=1.30176..., L_3=2.6215080..., L_4=3.7325386... (for L_5,...,L_14 see Shur arXiv:1009.4415).
Empirical observation: for k=2 the O-term in the general formula is slightly bigger than 2/k^5, and for k=3,...,14 this O-term is slightly smaller than 2/k^5.
(End)

A118311 Number of dissimilar squarefree quaternary words of length n.

Original entry on oeis.org

1, 1, 2, 4, 11, 29, 77, 202, 532, 1395, 3664, 9605, 25192, 66047, 173183, 453998, 1190259, 3120294, 8180124, 21444290, 56217025, 147373441, 386342414, 1012799936, 2655067412, 6960281083, 18246444362, 47833200849, 125395149294, 328724391241, 861753701567, 2259094233704

Offset: 1

Alford Arnold, Apr 22 2006

nonn

Sherman Stein and A006156 count ordered squarefree(twin-free) ternary words. A060688 counts the dissimilar cases essentially by dividing by 3! (the number of ways to permute a,b,c). A051041 counts ordered squarefree quaternary words. A118311 counts the dissimilar cases (beginning with the 4th term) by dividing A051041 by 4!.

			a(1) = 1 because a,b,c and d are similar.
a(2) = 1 because aa is not squarefree; so ab is the only valid case.
a(3) = 2 counting aba and abc.
a(4) = 4 counting abac, abca, abcb and abcd.
a(5) = 11 counting abaca,abacb,abcab,abcac,abcba,abacd,abcad,abcbd,abcda,abcdb and abcdc.

Sherman Stein, How The Other Half Thinks, 2001, page 149.

Cf. A006156, A060688, A051041.

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

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

A343421 Number of Dean words of length n, i.e., squarefree reduced words over {0,1,2,3}.

Original entry on oeis.org

4, 8, 16, 24, 40, 64, 104, 144, 216, 328, 496, 720, 1072, 1584, 2344, 3384, 4952, 7264, 10632, 15504, 22656, 33136, 48488, 70592, 103032, 150352, 219400, 319816, 466664, 680872, 993440, 1447952, 2111448, 3079464, 4491216, 6548936, 9550728, 13927840, 20311168

Offset: 1

Michel Marcus, Apr 15 2021

nonn

A Dean word is a reduced word that does not contain occurrences of ww for any nonempty w.

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

Martin Ehrenstein, Table of n, a(n) for n = 1..64
Richard A. Dean, A sequence without repeats on x, x^{-1}, y, y^{-1}, Amer. Math. Monthly 72, 1965. pp. 383-385. MR 31 #350.
Tero Harju, Avoiding Square-Free Words on Free Groups, arXiv:2104.06837 [math.CO], 2021.

Cf. A003324, A112658, A051041.

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 = [], set("0")
    for n in range(1, nn+1):
        an, eo = 4*len(sfs), ["02", "13"]
        sfsnew = set(s+i for s in sfs for i in eo[n%2] if isf(s+i))
        alst, sfs = alst+[an], sfsnew
        if verbose: print(n, an)
    return alst
print(aupton(30)) # Michael S. Branicky, Jun 20 2022

More terms from James Rayman, Apr 15 2021

cp's OEIS Frontend

A215075 T(n,k) = Number of squarefree words of length n in a (k+1)-ary alphabet, with new values 0..k introduced in increasing order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A214943 T(n,k) = Number of squarefree words of length n in a (k+1)-ary alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A118311 Number of dissimilar squarefree quaternary words of length n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Extensions

A343421 Number of Dean words of length n, i.e., squarefree reduced words over {0,1,2,3}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Extensions