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.

%I A215075 #20 Apr 27 2015 17:54:38
%S A215075 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,
%T A215075 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,
%U A215075 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
%N 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.
%C A215075 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
%H A215075 R. H. Hardin, <a href="/A215075/b215075.txt">Table of n, a(n) for n = 1..345</a>
%H A215075 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 A215075 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 A215075 From _Arseny Shur_, Apr 26 2015: (Start)
%F A215075 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 A215075 Exact values of L_k for small k, rounded up to several decimal places:
%F A215075 L_2=1.30176..., L_3=2.6215080..., L_4=3.7325386... (for L_5,...,L_14 see Shur arXiv:1009.4415).
%F A215075 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 A215075 (End)
%e A215075 Table starts
%e A215075 .1..1....1.....1......1......1......1......1......1......1......1......1......1
%e A215075 .1..1....1.....1......1......1......1......1......1......1......1......1......1
%e A215075 .1..2....2.....2......2......2......2......2......2......2......2......2......2
%e A215075 .0..3....4.....4......4......4......4......4......4......4......4......4......4
%e A215075 .0..5...11....12.....12.....12.....12.....12.....12.....12.....12.....12.....12
%e A215075 .0..7...29....39.....40.....40.....40.....40.....40.....40.....40.....40.....40
%e A215075 .0.10...77...138....153....154....154....154....154....154....154....154....154
%e A215075 .0.13..202...503....638....659....660....660....660....660....660....660....660
%e A215075 .0.18..532..1864...2825...3085...3113...3114...3114...3114...3114...3114...3114
%e A215075 .0.24.1395..6936..12938..15438..15893..15929..15930..15930..15930..15930..15930
%e A215075 .0.34.3664.25868..60458..81200..86857..87599..87644..87645..87645..87645..87645
%e A215075 .0.44.9605.96512.285664.442206.502092.513649.514795.514850.514851.514851.514851
%e A215075 ...
%e A215075 Some solutions for n=6 k=4
%e A215075 ..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
%e A215075 ..1....1....1....1....1....1....1....1....1....1....1....1....1....1....1....1
%e A215075 ..2....2....2....2....2....2....2....2....2....2....0....2....2....2....0....2
%e A215075 ..3....3....0....0....1....3....0....3....1....0....2....3....3....3....2....1
%e A215075 ..1....2....3....3....0....0....3....1....3....2....1....4....1....4....0....0
%e A215075 ..0....0....1....0....3....3....2....3....1....1....2....1....2....0....1....2
%Y A215075 Column 2 is A060688(n-1), or A006156 divided by 6 (for n>1).
%Y A215075 Column 3 is A118311, or A051041 divided by 24 (for n>3).
%K A215075 nonn,tabl
%O A215075 1,9
%A A215075 _R. H. Hardin_, Aug 02 2012