# Questions tagged [combinatorics-on-words]

A branch of combinatorics that focuses on the study of words and formal languages

**4**

votes

**1**answer

82 views

### Is the density of 1's in the Fibonacci word uniform?

The Fibonacci word is the limit of the sequence of words starting with $0$ and satisfying rules $0 \to 01, 1 \to 0$. Equivalently, it is obtained from the recursion $S_n= S_{n-1}S_{n-2}$ under ...

**8**

votes

**1**answer

148 views

### Minimum number of permutations of $\{1,\ldots, n\}$ that together contain every $k$-subpermutation

Define a $k$-permutation of $\{1,\ldots, n\}$ to be a word $\tau_1 \ldots \tau_k$ such that $\{\tau_1,\ldots,\tau_k\}$ is a $k$-subset of $\{1,\ldots, n\}$. Thus an $n$-permutation of $\{1,\ldots, n\}$...

**19**

votes

**3**answers

726 views

### What is the fairest order for stage-striking (and is it the Thue-Morse sequence)?

Here's a fair-sequencing problem that doesn't quite match the usual fair-division problems. I think that, like those, the answer should also be the Thue-Morse sequence ("balanced alternation"), ...

**3**

votes

**1**answer

96 views

### Partition theorems for located words

In this paper Bergelson, Blass, and Hindman prove the following
Theorem 1.2 Let $W(\Sigma; v)$ be colored with finitely may colors and let $\bar s$ be an infinite sequence from $W(\Sigma; v)$. ...

**2**

votes

**1**answer

156 views

### Unique(ish) infinite string avoiding a set of patterns

Let $\Sigma$ be a finite alphabet of size at least 2. A (possibly infinite) string $s$ over alphabet $\Sigma$ encounters a pattern $p \in \mathbb{N}^*$ iff there is a non-erasing morphism $f: \mathbb{...

**4**

votes

**1**answer

116 views

### Subshifts with a free semigroup

Let $X$ be a subshift on a finite alphabet. I'm interested in the following property: there exist words $s,t\in\mathcal L(X)$ (the language of $X$) such that $\{s,t\}^*\subset \mathcal L(X)$. That is, ...

**1**

vote

**0**answers

29 views

### Latent Dirichlet Allocation on Contrived Data

I am doing a project that seems like it might be susceptible to Latent Dirichlet Allocation. However, my data is highly contrived (both in test cases and use cases) and my "words" don't come close to ...

**11**

votes

**1**answer

250 views

### “Bisecting” a free subgroup with respect to word length

My broad question is regarding the lengths of (reduced) words in a subgroup of a free group.
As motivation, consider the free group $Gp(S)$ where $|S|=n$, that is, a free group of rank $n$. Let $S=\{...

**11**

votes

**1**answer

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

**2**

votes

**0**answers

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

**4**

votes

**1**answer

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

**0**

votes

**1**answer

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

**5**

votes

**0**answers

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

**17**

votes

**0**answers

457 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$...

**5**

votes

**1**answer

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

**3**

votes

**1**answer

192 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$...

**0**

votes

**0**answers

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

**1**

vote

**1**answer

99 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}...

**4**

votes

**2**answers

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

**1**

vote

**1**answer

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

**4**

votes

**1**answer

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

**3**

votes

**0**answers

191 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**

votes

**0**answers

110 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 $$
...

**4**

votes

**1**answer

136 views

### Existence of an infinite word with a predetermined asymptotic for the word complexity

Let $w$ be an infinite binary word, for example: $$1010100001 0010011000 0001001110 0101011011 \dots$$
Let $N_w(k)$ be the set of distinct subwords of $w$ of length $k$, and $n_w(k)$ the cardinal of ...

**3**

votes

**1**answer

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

**2**

votes

**0**answers

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

**3**

votes

**1**answer

217 views

### Counting triple-free sequences

The Thue-Morse sequence is a triple-free element $(a_i)\in\{0,1\}^\mathbb{N}$ which can be constructed by iterating the transformations $0\to 01$ and $1\to 10$ starting from $0$.
The beginning of the ...

**1**

vote

**1**answer

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

**4**

votes

**1**answer

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

**19**

votes

**5**answers

963 views

### Three-halves-free words (analogous to square-free)

A square-free word
is a string of symbols (a "word") that avoids the pattern $XX$, where $X$ is any
consecutive sequence of symbols in the string.
For alphabets of two symbols, the longest square-free ...

**14**

votes

**1**answer

462 views

### Combinatorics of palindromic decompositions

This is sort of a companion to my question Number of trivializations of a trivial word in the free group (which in turn is motivated by my earlier question here). It turns out that that question may ...

**12**

votes

**1**answer

437 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$ ...

**15**

votes

**0**answers

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

**3**

votes

**1**answer

342 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 (...

**0**

votes

**1**answer

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

**30**

votes

**3**answers

1k views

### “Nyldon words”: understanding a class of words factorizing the free monoid increasingly

BACKGROUND.
Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor Reiner'...

**2**

votes

**0**answers

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

**13**

votes

**0**answers

192 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 $...

**4**

votes

**2**answers

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

**39**

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

**8**

votes

**1**answer

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

**8**

votes

**1**answer

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

**4**

votes

**0**answers

99 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$.
...

**30**

votes

**1**answer

852 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&...

**3**

votes

**1**answer

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

**4**

votes

**1**answer

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

**2**

votes

**1**answer

134 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[...

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

**5**

votes

**1**answer

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

**5**

votes

**2**answers

334 views

### Concatenation of strings [closed]

We have two strings (i. e., finite tuples) $A$ and $B$.
We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...