Questions tagged [combinatorics-on-words]

combinatorial properties of strings of symbols from a finite alphabet. Also includes sequences such as the Thue-Morse and Rudin-Shapiro sequence.

Filter by
Sorted by
Tagged with
1
vote
3answers
45 views

How many length-$k$ ternary strings have evenly many of a given symbol?

I write down a string of $k$ letters, where each letter is $X, Y, \text{or } Z.$ The letter $X$ appears an even number of times. How many different sequences of letters could I have written down? I ...
0
votes
0answers
46 views

Combinatorial set theory: finding the cardinality of a set

For an integer $0 \leq k \leq 2^{N-m}$, and an alphabet $\Sigma = \{0, 1\}$, define a set of sets $B_{k}$ as $$B_{k} = \{ B \subseteq \{0, 1\}^{n} : |\{x \in \Sigma^{N-m} : x \Sigma^{m} 0^{n-N} \...
1
vote
0answers
16 views

What is the minimal possible length of an $n$-universal word? [duplicate]

Suppose $A$ is a finite alphabet. Let's call a word $w \in A^*$ $n$ -universal iff it contains every word from $A^n$ as a subword. What is the minimal possible length of an $n$-universal word over $A$?...
7
votes
1answer
104 views

Word problem and quotient group

Let $G$ be given by the group presentation $G = \langle a,b \mid S \rangle$, where $S = \{aa,bbb\}$. The formal definition of $G$ is: Let $F$ be the free group on $\{a,b\}$. Let $H$ be the ...
-1
votes
1answer
36 views

How many “words” of any length can be made from the letters in word: MAMMA? [closed]

Iam not sure how to solve this question because the word MAMMA has 3 M and 2 A. Thanks in advance
3
votes
2answers
59 views

Cardinality of $\{𝑓:\{1, \ldots , 𝑛\} → \{0,1,2\}\mid ∀𝑖 ∈ \{1, \ldots , 𝑛 − 1\}: 𝑓(𝑖) + 𝑓(𝑖 + 1) ≠ 4\}$

What is the cardinality of this set? $$\{𝑓:\{1, … , 𝑛\} → \{0,1,2\}\mid ∀𝑖 ∈ \{1, … , 𝑛 − 1\}: 𝑓(𝑖) + 𝑓(𝑖 + 1) ≠ 4\}$$ On a logical level, I understand that it must be the set of all ...
2
votes
1answer
46 views

Find the number of $n$-length Lyndon words on alphabet $\{0,1\}$ with $k$ blocks of 0's.

Let $L(n,k)$ denote the number of Lyndon words of lenth $n$ on a binary alphabet $\{0,1\}$ where $k$ is the number of blocks of 0's in the word. For example, if we consider $n=5$, then 5-length Lyndon ...
12
votes
2answers
198 views

Does the fraction of distinct substrings in prefixes of the Thue–Morse sequence of length $2^n$ tend to $73/96$?

Recall that the Thue–Morse sequence$^{[1]}$$\!^{[2]}$$\!^{[3]}$ is an infinite binary sequence that begins with $\,t_0 = 0,$ and whose each prefix $p_n$ of length $2^n$ is immediately followed by its ...
1
vote
1answer
274 views

Combinatorics or Permutations for 2 letters into a five letter strings

On Binary Island, the locals have only two letters in their alphabet: A and B. Sequences of these letters are called strings. The number of letters in a string is called its length. If a string has ...
1
vote
0answers
52 views

Blocks of consecutive letters in a random word

Let $X$ be an alphabet with $d$ letters, and we consider words over $X$. A block in a word is a subword of the form $xx...x$ for some letter $x\in X$. Every word $w$ is uniquely partitioned on blocks $...
2
votes
0answers
45 views

Words with an overlap prefix

Let $\mathcal{A}$ be some alphabet of distinct symbols, say $\mathcal{A} = \{a, f, l\}$. Let $\mathcal{A}^*$ be the set of all finite words over $\mathcal{A}$. An overlap is any word of the form $...
0
votes
0answers
37 views

Complexity of determining the Hamming distance from a given word to a given regular language

Suppose $L \subset A^*$ is a given regular language (defined by the corresponding DFA). What is the best possible computational complexity of an algorithm, that for a given word $w \in A^*$ returns ...
2
votes
0answers
161 views

A group word having no trivial proper subword

The question is: what is the object in the title called, if it has been defined elsewhere? Let $G$ be a group generated by a finite set $S\subset G$. A word of length $k$ in $S$ is a string $w=s_1\...
0
votes
1answer
51 views

Find a recurrence relation and give initial conditions for the number of words of length $n$ that do not contain two consecutive vowels.

I'm trying to find a recurrence relation for the number of words of length $n$ that do NOT contain two consecutive vowels. I'm trying to relate the problem to a similar one, of bit strings (Say, a ...
0
votes
0answers
21 views

First sums of the Thue-Morse sequence

Let $t_n$ denote the $n^{\rm th}$ element of the Thue-Morse sequence, i.e., $t_n$ begins $$ 0,1,1,0,1,0,0,1,\ldots $$ The first differences of this series are present in the OEIS as entry A029883. ...
1
vote
0answers
27 views

How many number string with absolute difference of every neighboring digits greater than 1 [duplicate]

You are given a string with length 10. Its characters are 0,1,2,...,9 (every number are in the string). How many permutations of the string such that the absolute difference of every two neighboring ...
0
votes
1answer
21 views

General formula for number of strings created from $n$ letters, where $m$ are identical and the rest are distinct.

The problem: Given $n$ letters, of which $m$ are identical and the rest are distinct, find a formula for the number of strings which can be made. Tests: Ex 1. n = 3, m = 0: DOG: { , D, O, G, DO, DG,...
1
vote
1answer
28 views

Are all elementary equational languages regular?

Suppose $A$ is a finite alphabet. $x \notin A$. Let's call a word equation over $A$ a pair of words $(w, u) \in (A \cup {x})^* \times (A \cup {x})^*$. Let's call a word $\alpha \in A^*$ a solution of ...
0
votes
0answers
56 views

Expected Levenshtein distance between two random binary strings

Suppose $X$ and $Y$ are randomly chosen from binary strings of length $n$ with uniform distribution. What is the expected Levenshtein distance between them? All I currently know is, that it does not ...
1
vote
1answer
145 views

Mathematical induction to prove number of 1's in a string composed of 1's and 0's is a multiple of 3

To start this off, please excuse the title as I couldn't think of a better way to word it. The following is a homework question I'm working on, for some background, I haven't done induction in a ...
1
vote
2answers
64 views

Words of length $n$ out of an alphabet of $n$ symbols such that no symbol appears exactly $k > 0$ times

I need to count the possible words of length $n$ out of an alphabet of $n$ symbols such that no symbol appears exactly $k$ times, with $k > 0$. I already tried considering the weak compositions of ...
1
vote
0answers
65 views

Maximal subset with given Hamming distances

Suppose $A$ is a finite alphabet, $|A| = n$. Suppose $m \in \mathbb{N}$. Let’s define the Hamming metric on $A^m$ as $d_m(a_1…a_m, b_1…b_m) = |\{i \leq m|a_i \neq b_i\}|$. Now, let’s define $s(n, m, ...
2
votes
0answers
46 views

Finite concatenation-free languages

Suppose, $A$ is a finite alphabet. $L \subset A^*$ is a language. Let's call $L$ concatenation-free iff $\forall u, v \in L$ we have $uv \notin L$. Does there exist some function $c: \mathbb{N} \...
1
vote
1answer
176 views

Existence of thin bases

Suppose $A$ is a finite alphabet. Let’s call a formal language $L$ over $A$ a base of order k iff $|A^* \setminus L^k| < \infty$. The following statement is true: If $|A| \geq 2$ and $L$ is a ...
4
votes
1answer
37 views

How many possible ways to arrange the letters of FOO_FIGHTERS such that the underscore isn't on either end?

My thought process: There are $\frac{12!}{2!2!}$ possible ways of arranging FOO_FIGHTERS total, then I should subtract the number of ways it can be arranged with the underscore on either end. I ...
0
votes
0answers
14 views

Probability of an at least n occurences of subsequences of length k in a RNA of length n

Suppose we have a RNA sequence of length N, then we have a subsequence of length K, $K \le N$ Is there a method to calculate the probability of the subsequence occuring an arbitrary number of times ...
1
vote
1answer
42 views

Closed form for the partial sums of the Thue-Morse sequence

Let $t_n$ denote the $n^{\rm th}$ element of the Thue-Morse sequence, i.e., $t_n$ begins $$ 0,1,1,0,1,0,0,1,\ldots $$ Now let $s_n$ denote the sequence defined by the partial sums of the $t_n$, so $...
0
votes
0answers
21 views

For what $n$ is $V_n$ finite? [duplicate]

Suppose, $A_n = \{a_1, ... , a_n\}$ is an $n$-letter alphabet. Suppose, $V_n$ is the set of all words formed by the alphabet $A_n$, that do not contain two same consecutive nonempty subwords (that ...
1
vote
1answer
20 views

Characterization of factorial balanced set of words.

In the following, all words are defined over the alphabet $\{0,1\}$. If $w$ is a word, then we let $h\left(w\right)$ denote the number of $1$s in $w$; we let $\left|w\right|$ denote the length of $w$;...
0
votes
0answers
11 views

Canonical lengths of braids

We know that every braid has a unique left weighted decomposition $B=\Delta^mA_1A_2...A_k$ where $A_iA_{i+1}$ is left weighted, each $A_i$ being a permutation braid. I wanted to show that len(BB') $\...
0
votes
1answer
484 views

Formula for consecutive $0$s in the Thue-Morse sequence

Let $n\geq0$ be a positive integer and let $t_n$ denote the $n^{\rm th}$ element of the Thue-Morse sequence. Thus, $t_0=0,t_1=1,t_2=1,t_3=0, \ldots$. Is there a formula for the integers $n$ such that ...
7
votes
1answer
50 views

Does every sufficiently long string contain many repetitions of a string of bounded length?

Let $S$ be a finite set and $d > 0$. Does there exist $\ell > 0$ such that the following holds? Every sufficiently long string with letters in $S$ contains at least $d$ consecutive copies of ...
1
vote
1answer
34 views

Prove that $w_{n+2}\geq w_{n+1}+w_{n}$, where $w_{n}$ is the number of $n$-length “allowed words” of $0$'s and $1$'s

For $n\in\mathbb{N}$ we call a finite sequence $x_{1}x_{2}\ldots x_{n}$ a word if $x_{i}\in\{0,1\}$ for all $1\leq i\leq n$. We say that a word is allowed if it satisfies the following two conditions: ...
6
votes
1answer
78 views

What is the max length string that can be formed using k distinct characters so that all of its substrings are unique.

Given k distinct characters , what is the max length string that can be formed using these characters one or more time so that all the sub-string whose size is greater than one are unique. Eg - For k ...
1
vote
1answer
56 views

Given a Surface $S$'s word, classify $S$ through word rule manipulation.

Consider the closed Surface $S$ represented by the word: $a_{1}\cdots a_{n} a_{n+1} \cdots a_{2n} a_{1} \cdots a_{n} a^{-1}_{n+1} \cdots a^{-1}_{2n}$ Use word rules to convert this sequence into a ...
2
votes
2answers
66 views

Finding a recurrence for the number of $n$-digit passwords having the same digit at least twice in a row [closed]

Passwords consist of digits. A password is valid if it contains the same digit at least twice in a row. For example 4558, 000637 and 33972240 are valid passwords but 8385878 is not a valid password. ...
4
votes
1answer
201 views

Formula for the sum of words in a 3 letter algebra

I have two alphabets with 3 letters, $\{V,U,U^\dagger\}$ and $\{X_1,X_2,X_3\}$ where $$ V = X_1 + X_2 + X_3, \, U = X_1 + \omega X_2 + \omega^2 X_3, \, U^\dagger = X_1 + \omega^2 X_2 + \omega X_3 $$ ...
2
votes
1answer
364 views

Find a recurrence for the number of binary strings with no three consecutive 1’s.

Question: Let $\mathcal{J}_{n}$ denote the set of binary strings with no three consecutive $1$s. Let $j_n$ = |$\mathcal{J}_{n}$|. Determine $\mathcal{J}_{1}$, $\mathcal{J}_{2}$, and $\mathcal{J}_{3}...
0
votes
0answers
14 views

Why divide by (size of alphabet) - 1 in Martin-Löf randomness tests?

In Information and Randomness: An Algorithmic Perspective, 2nd ed., Calude defines "Martin-Löf test" for uniform distributions over a finite alphabet of size $Q$, and includes this requirement for a ...
0
votes
1answer
52 views

Arranging the $26$ English letters in a row given two constraints

In how many ways can we arrange the $26$ English letters in a row so that no two vowels are adjacent to each other, and each block of consonant(s) (between $2$ vowels) is/are in alphabetical order?...
0
votes
1answer
38 views

How many anagrams are there for the word “MAGENTA” such that only one vowel appears in its original position?

How many anagrams are there for the word "MAGENTA" such that only one vowel appears in its original position? (a) $1512$ (b) $1152$ (c) $1008$ (d) $720$ (...
3
votes
1answer
144 views

Arranging the letters $I,I,I,I,M,P,P,S,S,S,S$, what is the rank of the word MISSISSIPPI?

All words that contain the letters $I,I,I,I,M,P,P,S,S,S,S$ are listed alphabetically so that the first two letters must be distinct, (i.e. the first word in the list is IMIIIPPSSSS, the second word ...
2
votes
2answers
115 views

Arranging the letters of the word ACCESSORIES given two constraints.

In how many different ways can we arrange the letters of the word ACCESSORIES so that no two similar letters are adjacent to each other, as well as no two vowels are adjacent to each other? ...
1
vote
3answers
103 views

Counting words whose letters have parity condition

How many words exist, such that the total number of each letter has a given parity? Let $N := \{1,\dots,n\}$. I regard the set $N^r$, that is, the set of all words of length $r$ with the "letters" $1$...
1
vote
1answer
30 views

Are any identities of the form $t(a+b)$ known, where $t(n)$ is the $n^{\rm th}$ element of the Thue-Morse sequence?

Let $t(n)$ denote the $n^{\rm th}$ element of the Thue Morse sequence, i.e., $t(n)=1$ if the number of $1$s in the binary expansion of $n$ is odd, $0$ otherwise. Let also $t(0)=0$. It is easy show ...
3
votes
3answers
96 views

Counting non-repetitive words

Let $S = \{a, b, c, \ldots \}$ be an alphabet, and let $S^N$ be the set of words with letters in $S$ of length $N$ that are not expressible as the repetition of any single word in $\bigcup_{M < N} ...
3
votes
2answers
195 views

Number of binary words that can be formed

How many binary words of length $n$ are there with exactly $m$ 01 blocks? I tried by finding number of ways to fill $n-2m$ gaps with $0$ and $1$ such that no $'01'$...
0
votes
1answer
20 views

complexity function of ultimately periodic words

Why do ultimately periodic words have a bounded complexity function? It's clear intuitively but I don't know how to formalize it
0
votes
1answer
52 views
1
vote
1answer
52 views

Number of ways to form 4 lettered word out of the letters of MATHEMATICS

There will be 3 cases to consider for the above problem, out of which the following will be one of them: 2 different and 2 alike letters are chosen. Now, we have 3 sets of alike letters, namely ${(M,...