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

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

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.

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)

Example

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

Prog

(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 anti-diagonals
  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

Crossrefs

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

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

Sequence in context: A118978 A194998 A215190 * A202864 A328880 A291290

Adjacent sequences: A214940 A214941 A214942 * A214944 A214945 A214946

Keyword

nonn,tabl

Author

R. H. Hardin, Jul 30 2012

Status

approved