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

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

Author

R. H. Hardin, Jul 30 2012

Keywords

• nonn
• tabl

Comments

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

Examples

			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
		

Links

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

Crossrefs

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

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

Programs

Python

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

Formula

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)