login
A214943
T(n,k) = Number of squarefree words of length n in a (k+1)-ary alphabet.
8
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
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 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
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
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Jul 30 2012
STATUS
approved