A214943 - OEIS

%I #22 Jul 09 2024 19:42:09

%S 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,

%T 42,0,9,56,252,720,1140,696,60,0,10,72,392,1470,3480,4260,1848,78,0,

%U 11,90,576,2688,8610,16680,15960,4848,108,0,12,110,810,4536,18480,50190,80040

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

%C Table starts

%C .2..3...4....5.....6.....7......8......9.....10......11......12......13......14

%C .2..6..12...20....30....42.....56.....72.....90.....110.....132.....156.....182

%C .2.12..36...80...150...252....392....576....810....1100....1452....1872....2366

%C .0.18..96..300...720..1470...2688...4536...7200...10890...15840...22308...30576

%C .0.30.264.1140..3480..8610..18480..35784..64080..107910..172920..265980..395304

%C .0.42.696.4260.16680.50190.126672.281736.569520.1068210.1886280.3169452.5108376

%C Empirical: row n is a polynomial of degree n

%C Coefficients for rows 1-12, highest power first:

%C ...1...1

%C ...1...1...0

%C ...1...1...0...0

%C ...1...1..-1..-1...0

%C ...1...1..-2..-1...1...0

%C ...1...1..-3..-2...2...1...0

%C ...1...1..-4..-3...5...2..-2...0

%C ...1...1..-5..-4...8...4..-4..-1...0

%C ...1...1..-6..-5..12...8..-9..-4...2...0

%C ...1...1..-7..-6..17..12.-17..-7...6...0...0

%C ...1...1..-8..-7..23..17.-28.-13..10...2...2...0

%C ...1...1..-9..-8..30..23.-45.-23..25...3..-2...4...0

%C Terms in column k are multiples of k+1 due to symmetry. - _Michael S. Branicky_, May 20 2021

%H R. H. Hardin, <a href="/A214943/b214943.txt">Table of n, a(n) for n = 1..245</a>

%H A. M. Shur, <a href="http://dx.doi.org/10.1007/978-3-642-13182-0_35">Growth of Power-Free Languages over Large Alphabets</a>, CSR 2010, LNCS vol. 6072, 350-361.

%H A. M. Shur, <a href="http://arxiv.org/abs/1009.4415">Numerical values of the growth rates of power-free languages</a>, arXiv:1009.4415 [cs.FL], 2010.

%F From _Arseny Shur_, Apr 26 2015: (Start)

%F 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).

%F Exact values of L_k for small k, rounded up to several decimal places:

%F L_2=1.30176..., L_3=2.6215080..., L_4=3.7325386... (for L_5,...,L_14 see Shur arXiv:1009.4415).

%F 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.

%F (End)

%e Some solutions for n=6 k=4

%e ..0....1....1....0....4....4....4....0....2....2....1....2....1....4....1....1

%e ..2....0....4....4....3....0....0....4....1....3....4....0....0....2....0....3

%e ..1....4....2....1....2....3....2....1....0....4....3....2....2....1....2....1

%e ..4....3....4....2....3....1....4....2....4....1....2....4....4....3....4....4

%e ..1....0....3....0....0....4....2....3....2....0....1....3....0....4....2....3

%e ..0....2....1....3....1....0....3....1....4....4....0....0....1....3....0....1

%o (Python)

%o from itertools import product

%o def T(n, k):

%o   if n == 1: return k+1

%o   symbols = "".join(chr(48+i) for i in range(k+1))

%o   squares = ["".join(u)*2 for r in range(1, n//2 + 1)

%o     for u in product(symbols, repeat = r)]

%o   words = ("0" + "".join(w) for w in product(symbols, repeat=n-1))

%o   return (k+1)*sum(all(s not in w for s in squares) for w in words)

%o def atodiag(maxd): # maxd antidiagonals

%o   return [T(n, d+1-n) for d in range(1, maxd+1) for n in range(1, d+1)]

%o print(atodiag(11)) # _Michael S. Branicky_, May 20 2021

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

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

%K nonn,tabl

%O 1,1

%A _R. H. Hardin_, Jul 30 2012