login
The OEIS is supported by the many generous donors to the OEIS Foundation.
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a051041 -id:a051041
Displaying 1-4 of 4 results found.
page 1
     Sort: relevance | references | number | modified | created      Format: long | short | data
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.
+10
9
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
(list; table; graph; refs; listen; history; text; internal format)
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).
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Aug 02 2012
STATUS
approved
A214943
T(n,k) = Number of squarefree words of length n in a (k+1)-ary alphabet.
+10
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
(list; table; graph; refs; listen; history; text; internal format)
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
R. H. Hardin, Table of n, a(n) for n = 1..245
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).
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Jul 30 2012
STATUS
approved
A118311
Number of dissimilar squarefree quaternary words of length n.
+10
2
1, 1, 2, 4, 11, 29, 77, 202, 532, 1395, 3664, 9605, 25192, 66047, 173183, 453998, 1190259, 3120294, 8180124, 21444290, 56217025, 147373441, 386342414, 1012799936, 2655067412, 6960281083, 18246444362, 47833200849, 125395149294, 328724391241, 861753701567, 2259094233704
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
Sherman Stein and A006156 count ordered squarefree(twin-free) ternary words. A060688 counts the dissimilar cases essentially by dividing by 3! (the number of ways to permute a,b,c). A051041 counts ordered squarefree quaternary words. A118311 counts the dissimilar cases (beginning with the 4th term) by dividing A051041 by 4!.
REFERENCES
Sherman Stein, How The Other Half Thinks, 2001, page 149.
LINKS
Table of n, a(n) for n=1..32.
EXAMPLE
a(1) = 1 because a,b,c and d are similar.
a(2) = 1 because aa is not squarefree; so ab is the only valid case.
a(3) = 2 counting aba and abc.
a(4) = 4 counting abac, abca, abcb and abcd.
a(5) = 11 counting abaca,abacb,abcab,abcac,abcba,abacd,abcad,abcbd,abcda,abcdb and abcdc.
CROSSREFS
Cf. A006156, A060688, A051041.
KEYWORD
nonn
AUTHOR
Alford Arnold, Apr 22 2006
EXTENSIONS
a(16)-a(25) from Max Alekseyev, Jul 03 2006
a(26)-a(30) from Giovanni Resta, Mar 20 2020
STATUS
approved
A343421
Number of Dean words of length n, i.e., squarefree reduced words over {0,1,2,3}.
+10
2
4, 8, 16, 24, 40, 64, 104, 144, 216, 328, 496, 720, 1072, 1584, 2344, 3384, 4952, 7264, 10632, 15504, 22656, 33136, 48488, 70592, 103032, 150352, 219400, 319816, 466664, 680872, 993440, 1447952, 2111448, 3079464, 4491216, 6548936, 9550728, 13927840, 20311168
(list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
A Dean word is a reduced word that does not contain occurrences of ww for any nonempty w.
a(n) is a multiple of 4 by symmetry. - Michael S. Branicky, Jun 20 2022
LINKS
Martin Ehrenstein, Table of n, a(n) for n = 1..64
Richard A. Dean, A sequence without repeats on x, x^{-1}, y, y^{-1}, Amer. Math. Monthly 72, 1965. pp. 383-385. MR 31 #350.
Tero Harju, Avoiding Square-Free Words on Free Groups, arXiv:2104.06837 [math.CO], 2021.
PROG
(C++)
#include <iostream>
#include <vector>
bool good (const std::string& s) {
long n = s.size();
for (long i = 1; i <= n/2; i++) {
bool match = true;
for (long j = 0; j < i; j++) {
if (s[n-i+j] != s[n-2*i+j]) {
match = false; break; } }
if (match) return false; }
return true; }
std::vector<std::string> s = {"01"}, t, d = {"02", "13"};
int main () {
std::cout << "1 4\n";
for (long i = 2; i < 40; i++) {
std::cout << i << " " << 8*s.size() << "\n";
for (char c : d[i%2]) {
for (const std::string& x : s) {
if (good(x+c)) t.push_back(x+c); } }
s.swap(t); t = std::vector<std::string>(); } } // James Rayman, Apr 15 2021
(Python)
def isf(s): # incrementally squarefree (check factors ending in last letter)
for l in range(1, len(s)//2 + 1):
if s[-2*l:-l] == s[-l:]: return False
return True
def aupton(nn, verbose=False):
alst, sfs = [], set("0")
for n in range(1, nn+1):
an, eo = 4*len(sfs), ["02", "13"]
sfsnew = set(s+i for s in sfs for i in eo[n%2] if isf(s+i))
alst, sfs = alst+[an], sfsnew
if verbose: print(n, an)
return alst
print(aupton(30)) # Michael S. Branicky, Jun 20 2022
CROSSREFS
Cf. A003324, A112658, A051041.
KEYWORD
nonn
AUTHOR
Michel Marcus, Apr 15 2021
EXTENSIONS
More terms from James Rayman, Apr 15 2021
STATUS
approved
page 1

Search completed in 0.010 seconds

Lookup Welcome Wiki Register Music Plot 2 Demos Index WebCam Contribute Format Style Sheet Transforms Superseeker Recents
The OEIS Community
Maintained by The OEIS Foundation Inc.
Last modified October 25 03:17 EDT 2024. Contains 377061 sequences.
License Agreements, Terms of Use, Privacy Policy