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.

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

Offset: 1

Author

R. H. Hardin, Aug 02 2012

Keywords

• nonn
• tabl

Comments

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

Examples

			Table starts
.1..1....1.....1......1......1......1......1......1......1......1......1......1
.1..1....1.....1......1......1......1......1......1......1......1......1......1
.1..2....2.....2......2......2......2......2......2......2......2......2......2
.0..3....4.....4......4......4......4......4......4......4......4......4......4
.0..5...11....12.....12.....12.....12.....12.....12.....12.....12.....12.....12
.0..7...29....39.....40.....40.....40.....40.....40.....40.....40.....40.....40
.0.10...77...138....153....154....154....154....154....154....154....154....154
.0.13..202...503....638....659....660....660....660....660....660....660....660
.0.18..532..1864...2825...3085...3113...3114...3114...3114...3114...3114...3114
.0.24.1395..6936..12938..15438..15893..15929..15930..15930..15930..15930..15930
.0.34.3664.25868..60458..81200..86857..87599..87644..87645..87645..87645..87645
.0.44.9605.96512.285664.442206.502092.513649.514795.514850.514851.514851.514851
...
Some solutions for n=6 k=4
..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
..1....1....1....1....1....1....1....1....1....1....1....1....1....1....1....1
..2....2....2....2....2....2....2....2....2....2....0....2....2....2....0....2
..3....3....0....0....1....3....0....3....1....0....2....3....3....3....2....1
..1....2....3....3....0....0....3....1....3....2....1....4....1....4....0....0
..0....0....1....0....3....3....2....3....1....1....2....1....2....0....1....2
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..345
• 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

Column 2 is A060688(n-1), or A006156 divided by 6 (for n>1).

Column 3 is A118311, or A051041 divided by 24 (for n>3).

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)