Questions tagged [combinatorics-on-words]
A branch of combinatorics that focuses on the study of words and formal languages
102
questions
11
votes
1
answer
326
views
Unique words in dihedral groups
Suppose $x$ is a word over the alphabet $\{0,1\}$.
Let $a$, $b$ be elements of the group Dih$_k$ for some $k$.
Let $\varphi=\varphi_{a,b,k}$ be the map from words over $\{0,1\}$ to elements of the ...
- 24.6k
3
votes
0
answers
279
views
Cayley Graphs and Cyclically reduced words [closed]
Let $G$ be a finite group and $S$ be a symmetric generating set for $G$. (EDIT: Assume $S$ does not contain involutions!) Cyclically reduced words can be thought of as minimal length representatives ...
- 939
4
votes
1
answer
162
views
Covering sequences of words
(If anyone has a better title please change it!)
Given two finite words $v,w$ in the alphabet $\{a,b\}$, define the $v$-proportion of $w$ to be the largest number of letters in $w$ which can be ...
- 399
21
votes
0
answers
667
views
Avoidable words
Let $u(x_1,...,x_n)$ be a word, $k\in \mathbb{N}$. We say that $u$ is $k$-avoidable if there exists an infinite word in $k$ letters $\{a_1,...,a_k\}$ which does not contain values of $u$ (i.e. words ...
CommunityBot
- 1
0
votes
1
answer
159
views
How many words are there such that some word $X$ is subsequence of them?
Let's define subsequence of the word as part of the word created by deleting some of its letters, for example aetics is a subsequence of mathematics.
QUESTION.
Given a $3$-letter word (let's call it ...
- 37.4k
5
votes
0
answers
1k
views
The functional equation $f(x) = qx + qxf(x) - f(x^2)$
A word (i.e., ordered string of letters) is bifix-free provided it has no proper initial string and terminal string that are identical. For example, the word $ingratiating$ has bifix $ing$, but the ...
- 399
17
votes
0
answers
530
views
Question about combinatorics on words
Let $\{a_1,a_2,...,a_n\}$ be an alphabet and let $\{u_1,...,u_n\}$ be words in this alphabet, and $a_i\mapsto u_i$ be a substitution $\phi$.
Question: Is there an algorithm to check if for some $m,k$...
- 116
5
votes
1
answer
389
views
Number of Lyndon words of given weight
Consider the alphabet consisting of two letters $a$ and $b$, and put the lexicographic order in which $a<b$.
We say that a non-empty word $w$ in this alphabet is a Lyndon word if, for any non-...
- 30.7k
3
votes
1
answer
276
views
Longest runs and concentration of measure
Consider the longest runs $\ell_\sigma(x)$ of the pattern $\sigma$ for $\sigma\in \{0, 1, 01, 10, 001,\dots\}$ etc. in a binary sequence $x=x_1\dots x_n$.
For example, $\ell_{001}(0001110010011001)=2$...
- 22.5k
0
votes
0
answers
182
views
Sum of unit vectors always has a binary span after constrained permutations
Conjecture:
Let $e_1 = (1,0,\ldots,0), \ldots , e_{m_1+m_2} = (0,\ldots,0,1)$ be the unit vectors of the standard basis $E$ of $\mathbb{R}^{m_1+m_2}$.
An enumeration $ E \cup -E = \{f_1, \ldots, ...
- 121
1
vote
1
answer
105
views
Weighted counting of circular codes
Given a circular code $X$ (for example: $X=\{ w,b \}$) with generating function $u(z)=\sum\limits_{k=0}^{\infty}{u_k z^k}$ (in this example : $u(z)=2z$), the generating function $p(z)=\sum\limits_{k=0}...
- 26.1k
4
votes
2
answers
134
views
Sturmian subword whose reverse is not a subword
Let ${\cal L}_n$ be the set of all subwords of length $n$ of a biinfinite Sturmian sequence, induced by a rotation coding with irrational angle $\theta$.
Take a word $w \in {\cal L}_{2^n}$ and write ...
- 2,085
1
vote
1
answer
214
views
Building the string on $\{0,1\}$ alphabet with $\Omega(n^{2})$ different substrings [closed]
As we know the number of different substrings has the upper bound $O(n^{2})$.
Consider the strings on $\{0,1\}$ alphabet. Can I build a string with $\Omega(n^{2})$ different substrings?
Actually I ...
5
votes
1
answer
433
views
Periodic strings
I wish to ask a problem in periodic strings, it might be well-known but I am a beginner in this subject, so I am very glad if someones can show me. My problem is that can we add some string to the end ...
- 27.8k
3
votes
0
answers
207
views
Repartition of 1's in the "Chacon word"
Consider the "Chacon words": $B_0=0$ and $B_{n+1} = B_nB_n1B_n$. The word $B_n$ has $\ell_n := \frac{3^{n+1}-1}{2}$ digits and the number of $1$'s in $B_n$ is $\ell_n - 3^n = \ell_{n-1} \sim \ell_n/3$...
- 2,433
2
votes
0
answers
114
views
Zero-one links: how many, and how to produce?
For $m \geq 1$, define a link to be a zero-one word $w=d_0d_1 \ldots d_k$, where $d_0=0$ and $k=2^m-1$ , such that the words
$$ w_0=0^{m-1}d_0, w_1=w_0d_1, w_2=w_1d_2, \ldots, w_k = w_{k-1}d_k $$
...
- 13.2k
3
votes
1
answer
145
views
Number and asymptotic for cyclic sequences
Cyclic sequence is equivalence class of cyclic shift action.
If $a = (a_1, ... , a_i)_c$ is cyclic sequence then $(a_1, a_2, \ldots a_{i-1}, a_i)_c = (a_2, a_3, \ldots, a_i, a_1)_c = \ldots = (a_i, ...
- 378
30
votes
1
answer
936
views
partition of infinite word onto permitted words
Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, $0<c&...
- 59.8k
2
votes
0
answers
183
views
Words with Local plus Global Constraints
While doing estimates on the complexity of an algorithm I have run into a word-combinatorial problem with both a local and a global constraint.
This seems to be a rather general situation and I'm ...
- 121
17
votes
3
answers
708
views
Probability that a word in the free group becomes (much) shorter?
Let $w$ be a word of length $2\ell$ chosen at random on the alphabet $\{x_1,x_1^{-1},x_2,x_2^{-1},\dotsc,x_k,x_k^{-1}\}$. By the reduction $\rho(w)$ I mean what you obtain by deleting substrings of ...
- 95.6k
1
vote
1
answer
161
views
Terminology for set of infinite strings with a certain prefix
Let $\mathcal{A}$ be a finite alphabet, and let $C$ be the Cantor space $\mathcal{A}^\omega$ under the product topology.
Given a finite string $s \in \mathcal{A}^*$, let $C(s)$ be the set of all ...
- 2,085
13
votes
1
answer
532
views
Number of trivializations of a trivial word in the free group
Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ ...
CommunityBot
- 1
4
votes
1
answer
299
views
Strings with no long runs from proper subalphabets
Let $R_{n,k,b}$ be the number of $b$-ary strings of length $n$ that contain some run of length at least $k$ from some $(b-1)$-ary subalphabet. Let $N_{n,k,b}=b^n-R_{n,k,b}$ be the size of the ...
- 24.6k
3
votes
1
answer
577
views
Combinatorics problem involving counting the number of certain substrings
I'm not sure if this question is suited for MO, but it does seem quite challenging to me, and is required for a research problem in chemistry I'm working on. I did try getting help from elsewhere (...
CommunityBot
- 1
15
votes
0
answers
481
views
Word complexity of primes mod 4
For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
- 16.3k
0
votes
1
answer
526
views
Is it possible to create an infinite sequence in which no subsequence is repeated 3 times in a row?
In Chess, there is the Threefold Repetition rule where if a sequence of moves is repeated 3 times in a row, either player can claim a draw.
Say two players wanted to play a legal, infinite game of ...
CommunityBot
- 1
13
votes
0
answers
289
views
Computing exact or asymptotics for number of strings over an alphabet of size $n$ that have no non-trivial substrings that appear more than once
I ran across a seemingly relatively simple combinatorics problem that appears open. For an alphabet of size $n$, let $A(n)$ be the number of strings over the alphabet that have no substring of length $...
- 30.7k
20
votes
4
answers
3k
views
Cube-free infinite binary words
A word $y$ is a subword of $w$ if there exist words $x$ and $z$ (possibly empty) such that $w=xyz$. Thus, $01$ is a subword of $0110$, but $00$ is not a subword of $0110$. I'm interested in right-...
- 1,329
15
votes
7
answers
1k
views
Two questions from combinatorics on words
Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...
14
votes
3
answers
2k
views
String of integers puzzle
I apologize for not have the math background to put this question in a more formal way.
I'm looking to create a string of 796 letters (or integers) with certain properties.
Basically, the string is ...
- 13.2k
2
votes
0
answers
213
views
Counting strings with alternating letters with generating functions
It is a classical problem that of finding the generating function (GF) of the number of strings with length $n$ having $m$ different letters (basically, the problem reduces to that of writing the ...
- 121
6
votes
2
answers
164
views
Which criteria guarantee an orthogonal circuit in $\mathbb R^3$ to be rigid?
For $n\ge4$, define an orthogonal circuit or O-circuit as a closed circuit of $n$ unit segments in $\mathbb R^3$ such that any two neighboring segments form a right angle. (Physically this could be ...
- 149k
40
votes
1
answer
1k
views
Do runs of every length occur in this sequence?
This is a repost from user r.e.s's unsolved Math Stack Exchange question: Do runs of every length occur in this string? That question was derived from my original question on the subject: Does this ...
CommunityBot
- 1
2
votes
1
answer
200
views
Equivalent subshifts
Let $X$ be a finite set, $(X^{\mathbb Z}, T)$ is the shift, i.e. the Tikhonov topological space of all bi-infinite words in $X$, $T$ shifts the words one letter to the right. A subshift is a closed ...
- 25.9k
8
votes
1
answer
318
views
Über theorem on unavoidable patterns?
Let $A$ be an alphabet of $k$ symbols,
and $p$ a pattern.
An example of a pattern is $p=XX$, where $X$ is any finite
string of symbols from $A^+$.
Avoiding $p$ is avoiding any subword repeated twice ...
- 24.6k
8
votes
1
answer
436
views
Is there a name for infinite words containing every finite words?
Apparently, the closest thing I've found would be normal number http://mathworld.wolfram.com/NormalNumber.html
But requiring that every finite words occurs is weaker than this property. So I'm ...
CommunityBot
- 1
4
votes
0
answers
121
views
Covariance matrix for number of powers in a word
A word over the alphabet $\{0,1\}$ of length $n$ may contain squares, cubes, and generally $k$th powers, where $2\le k\le n$. Let $O_k(w)$ denote the number of $k$th power occurrences in the word $w$.
...
CommunityBot
- 1
3
votes
1
answer
239
views
Calculating the probability that all possible length $r$ subwords exists in a string, with or without overlaps allowed
Let $S$ be a length $L$ string, where each character in the string is chosen with uniform random probability over an alphabet with $q$ characters. For example, a binary string would imply $q = 2$, a ...
- 24.6k
5
votes
1
answer
218
views
Which automated theorem provers can address the combinatorics of periods in strings?
Five years ago, I made a conjecture on the number of correlation classes that are exhibited by pairs of words in an alphabet of a given size. I later speculated that the conjecture could be tackled ...
- 55k
2
votes
1
answer
519
views
Notation for ends of a string
I work now a lot with strings of characters and other finite sequences and found that I need many times a good notation for "cutting the end" a string. If $a$ is a finite sequence and $a'$ is its ...
CommunityBot
- 1
2
votes
1
answer
141
views
Representability of sets of infinite sequences sharing common prefixes and factors (i.e. infixes)
Here we are concerned with the space $X^{\omega}$ of infinite sequences. Denote by $F_n(\xi)$
the set of factors (consecutive finite subsequences) of length $n$ and consider the set
$$
K_n(\xi) = \xi[...
- 798
5
votes
1
answer
336
views
What prefix and factors determine a ultimately periodic word uniquely
Let $\xi$ be an ultimately periodic sequence, i.e. there exists finite sequences $p, q \in X^*$ such that $\xi = pq^{\omega}$. Does there exists a $n > 0$ such that the prefix of length $n$ and all ...
- 37.4k
3
votes
2
answers
305
views
Maximal words (reloaded)
I have 3 more questions about maximal words (which are just another way of talking of necklaces).
Let W be a finite word on a two symbol alphabet {0,1}; let us say that W is maximal if it is the last ...
CommunityBot
- 1
20
votes
2
answers
723
views
congruence on words: having the same (scattered) subwords of length at most n
For a fixed finite alphabet $A=\{a,b,...\}$, write $x \sim_n y$ if the two words $x$ and $y$ have the same (scattered) subwords of length at most $n$. The relation $\sim_n$ is a congruence of finite ...
- 371
3
votes
5
answers
433
views
Strings and "co-subsequences"
Let $S$ be a string over some alphabet $\Sigma$. It is well known that a substring of $S$ is commonly defined as a sequence of contiguous elements from $S$, while a subsequence of $S$ is a sequence ...
- 1,329
3
votes
1
answer
280
views
A property of periodic words
Question is edited Perhaps this formulation is clearer.
It is well known that if a power of a primitive (i.e. not a proper power) word $u$ contains two different occurrences of a word $v$, $|v|>|u|...
- 37.4k
10
votes
1
answer
675
views
Analogues of the Knuth and Forgotten equivalences on permutations: have they been studied?
Consider a totally ordered alphabet $A$ of $n$ letters. Let $W$ be the set of all words over $A$ which have no two letters equal. Then, for example, we can define the Knuth equivalence on $W$ as the ...
- 427
10
votes
2
answers
1k
views
Ubiquitous Zimin words
Let $w$ be a word in letters $x_1,...,x_n$. A value of $w$ is any word of the form $w(u_1,...,u_n)$ where $u_1,...,u_n$ are words. For example, $abaaba$ is a value of $x^2$. A word $u$ is called ...
4
votes
4
answers
710
views
Subwords of cube-free binary words
I'm currently working on subwords of cube-free binary words.
A binary word is one composed of letters from a two-letter alphabet such as $\{0,1\}$. A word $y$ is a subword of $w$ if there exist ...
- 27.8k
3
votes
0
answers
184
views
Generalised de Bruijn Graph
I have encountered sets of the following type, consisting of words over a finite aphabet $A$.
If $S$ is such a set, then
$S$ is finite,
No word in $S$ is part of another element of $S$, and
every ...
CommunityBot
- 1