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

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

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.

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

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

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

Sequence in context: A143656 A141169 A343887 * A287417 A180177 A321196

Adjacent sequences: A215072 A215073 A215074 * A215076 A215077 A215078

Keyword

nonn,tabl

Author

R. H. Hardin, Aug 02 2012

Status

approved