Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorics-on-words]

combinatorial properties of strings of symbols from a finite alphabet

2
votes
2answers
17 views

Question on word combinations with exclusivity

"How many 4 letter words on the alphabet {a,b,c} in which 'a' occurs exactly twice are there?" My answer is incorrect as I answered 3*3*2*2 4 letter words. However, this doesn't necessarily remove '...
0
votes
0answers
23 views

Balanced Word to Balanced (Sturmian?) Sequence

Let $E \in \{0,1\}^{n}, n\in \mathbb{N}$, be a balanced finite word: for every two subwords $U,V$ of the same length, the number of $1$'s in $U$ differs from the number of $1$'s in $V$ by at most one. ...
1
vote
1answer
43 views

Generating function for strings in $\{a,b,c\}^*$ in terms of block decompositions

Here is what my teacher did : Denote $A = \{a, aa, aaa, \ldots \} = a^*a$, $B=b^*b$, $C=c^*c$. Now let $D$ be the union of these sets. Define $f(A,B,C)$ to be the generating function on the set $D$ ...
1
vote
0answers
31 views

How to parse mathematical notation for this combinatorial problem?

So in the paper found here: https://link.springer.com/article/10.1007/BF01819761 We find this theorem here . I was having difficulty parsing the actual notation they're using and want to program ...
6
votes
0answers
106 views

Does there exist infinite words using the alphabet $\{A,B,C,D\}$ that avoids patterns $XX,\ XAX,\ XBX,\ XCX,\ XDX$?

Another form of this question is: Does there exist a gap-1 square-free infinite word using the alphabet {A,B,C,D}? Normally square-free in this context means that there are no sub-words twice in a ...
0
votes
1answer
27 views

Inequivalent Canonical words

I have a problem in understanding one line of "Combinatorial Group Theory" by Magnus, Karrass and Solitar (Page 27-28). (Please find it in the image below) In equation (4), it considers a group $G=\...
0
votes
1answer
29 views

Number of permutations of four letter word using letters anything between 0-2 times each

The first part of the problem involves calculating the number of four letter words possible to form from five letters A, B, C, D and E. Each letter can be used 0, 1 or 2 times. The second part of the ...
-1
votes
2answers
33 views

How to recursively define $w^i$ for $i≥0$

Given a string $w$, we denote with $w^i$ the string obtained by concatenating $i$ times $w$. How can I recursively define $w^i$ for $i≥0$? First of all, what does "concatenate" mean in this context?
1
vote
1answer
48 views

Properties of the closure in $\{0,1\}^\mathbb N$ of all shifts of a word

Let $w \in \{0,1\}^\mathbb N$ be some word. Let $\Sigma \subset \{0,1\}^\mathbb N$ be the set of all words obtained from $w$ by deleting an initial segment of $w$. So for every $n$ we have in $\Sigma ...
1
vote
2answers
20 views

Limit of set of finite words stable with prefix

Let $S$ be a set of finite words over a finite alphabet which contains at least two letters. Suppose that $S$ contains at least one word of length $n$ for all $n$ and that $a=a_0...a_k\in S \...
1
vote
0answers
33 views

Sum over binary words of length $k$.

Let $w$ be a word of length $k$ on binary alphabet$\{0,1\}$ with $p(0)=p$, $p(1)=q$, and $p>q$. How would you calculate this sum? (exact or up to the first order) $$\sum_{w,w^{'}}(p(w)+p(w^{'})-p(...
6
votes
2answers
182 views

Insertion and deletion of cubed words $w^3$

Evan Chen's seminal text presents the following as (spicy) problem 11C: Consider the set of finite binary words. Show that you can't get from $01$ to $10$ using only the operation "insert or delete ...
0
votes
2answers
41 views

What problem in combinatorics-on-words could this be a formula for: $\frac{2^i i}{2}$?

This came from a problem that I have solved, but it got me thinking. Below is the original question I had to answer (as was translated to English by me just now): G is a simple graph on 32 ...
2
votes
1answer
18 views

If I have a certain word, how can I find the lowest number of characters that must remain in their original spots if I permute it?

Let's say I have a word AAAB, and I'm trying to permute it so that the lowest number of characters remain in their original places. For this word, the minimum ...
1
vote
1answer
138 views

Formula to calculate possible combination of words in a 3x3 crossword grid

I created a program to solve crossword puzzle given 6 words with 7-letter each and the program will calculate how many total solutions it may have. In this 3x3 grid, the constraints I set is for ...
0
votes
2answers
29 views

Find the number of distinct line ups such that A,B,C are not adjacent?

question: 10 peoples including A,B,C are waiting in a line.How many distinct line ups are there such that A,B,C are not adjacent?(assumption: A,B,C may be in any order as long as all three are ...
3
votes
1answer
174 views

Counting particular odd-length strings over a two letter alphabet.

OEIS sequence A297789 describes The number of [equivalence classes of] length $2n - 1$ strings over the alphabet $\{0, 1\}$ such that the first half of any initial odd-length substring is a ...
2
votes
1answer
43 views

Decomposition into Lyndon Words

In this paper, the authors state a theorem that uses the fact that any word can be decomposed into Lyndon words (words on an ordered alphabet that are minimum among all of their rotations), but I don'...
2
votes
2answers
57 views

Confusion on “Lyndon Words, Free Algebras, and Shuffles”

There's a passage from the paper "Lyndon Words, Free Algebras, and Shuffles" by Guy Melancon and Christophe Reutenauer (which can be found here) that's causing me some confusion. Here, $A$ is some ...
2
votes
1answer
64 views

periodic tail of a periodic word

This problem was motivated by my work on this question $\qquad$ Periodicity of words Problem: Given a finite alphabet, let $w = u^n,\;$where $n > 1,\;$and $u\;$is a non-periodic word. Prove or ...
-1
votes
1answer
47 views

Periodicity of words

If we have a non-periodic word $u$. Is it possible to have another word $\beta = \gamma u^{i-1}$ with $i>1$ and $\gamma \neq u^*$ so that $\beta$ is periodic. it's intuitive to say that it is not ...
0
votes
0answers
25 views

Length of shortest word that contains all triples

Given a finite set $M := \{1...n\}$, what is the shortest word $w \in M^*$ so that the set of all subwords of $w$ is a superset of $M^3$? A subword is a prefix of a suffix. For $1 \leq n \leq 2$ it ...
12
votes
1answer
279 views

Asymptotic length of reduced word on free group with replacements

This seems to be an elementary question, but it's proving hard for me to just Google. Suppose you have a sequence which picks elements out of $\{a, a^{-1}, b, b^{-1}, c, c^{-1}\}$ with equal ...
3
votes
0answers
52 views

Binary words with prescribed numbers of adjacent subpairs

Suppose $w:= a_1 a_2 \cdots a_n$ is a binary word, i.e. $a_i \in \{0,1\}$ for all $1\le i \le n$. Let $$\sigma(w) = (\text{# subwords } 00, \text{# subwords } 01, \text{# subwords } 10,\text{# ...
-2
votes
1answer
48 views

How many strings of length L and n distinct lowercase letters?

Given a set of the lower case alphabet letters {a, b, c, .., z} and two integers n, l. How many strings of length l are there containing only n distinct letters? Example: At n = 2, l=6, some valid ...
3
votes
0answers
63 views

Is there a string of all words without repetition?

This might be trivial, or difficult, I do not know. I could not find anything on the internet and feel stupid for not seeing anything more straightforward. The question is whether for any alphabet $...
1
vote
1answer
34 views

Counting 4-words with a restriction by using EGF

$Problem:$ Let $q_n$ be the number of $n$-words containing letters from the set $\{a, b, c, d\}$ in which there is odd number of letters $b$. Find recursive relations for $q_n$, generating function ...
3
votes
1answer
219 views

Word Presentation of Fundamental Group of Trefoil Knot Complement

I'm trying to understand Slide 35 of Joan Birman's presentation on Lorenz knots, available here: https://www.math.columbia.edu/~jb/Lorenz-general-audience.pdf I'm struggling with this particular bit. ...
3
votes
2answers
79 views

Counting words with letter counts of specific parity

Question: How many words of length $ n $ are there consisting of letters $ A $, $ B $, $ C $ such that: At least one letter occurs an even (possibly zero) number of times At least one letter occurs ...
0
votes
1answer
77 views

Expected distance between two permutations? [closed]

Consider the integer vector ${\bf w}=[1,2,3,\dots,n]$ and permutations of such vector. If we define the function $$d({\bf u},{\bf v})=\sum_{i=1}^n |u_i - v_i|, $$ where $\bf u$ and $\bf v$ are any ...
1
vote
1answer
86 views

Counting words formed by adjacent transpositions

I would like to find an expression for the number of words that can be formed from a given word by a certain number of adjacent transpositions (without reversing any transpositions). In particular I ...
0
votes
0answers
64 views

General approach to solve some counting problems

I have heard that there is a general approach using generating functions to solve the following type of problems: find the number of words of length $8$ made from letters $A, B, C, D, E$ such that ...
3
votes
0answers
65 views

Minimizing the word norm for the lamplighter group

Consider the lamplighter group, which has the following group operation: $$ (s_1, T_1) (s_2, T_2) = (s_1 + s_2, T_1 \triangle \{s_1 + t \mid t \in T_2\}) $$ where $s \in \mathbb{Z}$ and $T \subset \...
1
vote
1answer
57 views

Subset division

I am trying to remove the first symbol "a" from this set $L=(a,b,c)^* \cdot (ab,bc) \cdot (a,b,c)^* $ where these sets represent strings and $(a,b,c)^*$ means all combinations of letters a,b,c with ...
4
votes
0answers
47 views

Construct large set of words with a property

Let $[m]$ denote $\{1,\ldots,m\}$ and $(v)_i$ denote the $i$-ith coordinate of a vector $v$. Let $m$ and $k$ be positive integers. Then $[m]^k$ denotes the set of all words with letters from $[m]$ of ...
0
votes
3answers
97 views

How many possible passwords of a four digit length contain at least one uppercase character and at least one number?

How many possible passwords of a four digit length contain at least one uppercase character and at least one number? 95 total ACII Symbols 26 uppercase letters 26 lowercase letters 10 numbers 33 ...
1
vote
1answer
63 views

Is there standard terminology/notation for the “prefix” of a word?

Given a word like $abbbaaaba$, we can take (say) the first three letters. We might write $$\mathrm{foo}_3(abbbaaaba) = abb,$$ or something like that. Is there any standard terminology or notation here?...
0
votes
2answers
48 views

Is there any way to simplify $\sum_{i=0}^n \binom{x}{i} \binom{y}{i + 1}$? [closed]

All these numbers are naturals and $$n \leq x\,,\quad\left(n + 1\right) \leq y$$
1
vote
1answer
61 views

What is the number of size 3 subsets of vertices of an n-dimensional hypercube such that the 3 vertices are pairwise a distance d apart?

Equivalently, what is the number of size 3 subsets S of binary words of length n such that the Hamming distance between each pair of words in S is exactly k. I think that if k is odd then there are ...
0
votes
2answers
175 views

What is the permutation of words a-z created with the pattern: cvcvcv where c = a consonant and v = vowel?

What is the permutation of words a-z created with the pattern: cvcvcv where c = a consonant and v = vowel? I want to know because I have a software that creates rooms with that name pattern and I ...
2
votes
0answers
40 views

Is it possible to define a metric in a “formula space”?

Consider a finite set $A$, called the set of constants, and a set $S$ of binary or unary operations over $A$, $S=\{\theta_1,\theta_2,\dots\theta_n\}$, such that $\theta_i:A\rightarrow A$ or $\theta_i:...
3
votes
1answer
227 views

Classification of Christoffel words

Using the Cayley graph description, I proved a nice little characterization Christoffel words that I will be using in an upcoming paper. I have been looking in the literature to see if I can just ...
1
vote
2answers
108 views

Password combinatorics on identical notes

I have the following two questions: A password consists only small letters a,…,z How many possibilities are there to put in a hat two identical folded notes such that on one of them is a ...
0
votes
2answers
601 views

How many ways are there to pick a sequence of two different letters of the alphabet from the word MATHEMATICS?

*Restriction: Once the first letter is picked, the second letter must be to the right of the first letter in the word "MATHEMATICS". For example, if we were to pick "S" as the first letter, there is ...
1
vote
1answer
61 views

Is it true that the set of all 0-1 sequence with no two consecutive 1 is uncountable

My answer is yes. It is true that the set of all 0-1 sequence with no two consecutive 1 is uncountable. Because think about it in the situation of coin tossing that either head or tail appearing with ...
1
vote
1answer
34 views

Applications of words?

What are some real-life applications of (Sturmian) words? I'm doing an undergraduate thesis on the Fibonacci infinite word $f$, and although what I'm doing is purely theoretical (by counting maximal ...
4
votes
1answer
87 views

Is there any algebraic structure on Dyck words of length $2n$ or full binary trees of $n+1$ leaves?

Just out of curiosity, I wonder if there are researches about algebraic structures on Dyck words of length $2n$ or (equivalently) full binary trees of $n+1$ leaves (with fixed $n \in \mathbb{Z}^+$). ...
3
votes
2answers
453 views

What is the probability of finding a certain gene of length $m$ inside our random DNA chain?

DNA code is composed of a sequence of four nucleotides: adenine (A), cytosine (C), guanine (G) and thymine (T). Consider we have a random DNA chain (not closed) of length $M$. What is the ...
0
votes
1answer
61 views

∀n ∈ N, ∃w1, w2, . . . , wn ∈ A+ such that w = w1w2 . . . wn and C(w) = C(wi) ∀i ∈ {1, . . . , n}

A is a finite set of letters and A+ denotes the set of all finite length strings formed by letters in A, i.e. ∀w ∈ A+, w is a string, each letter in w belongs to A and len(w) ≥ 1. E.g.- If A = {a, b} ...
2
votes
1answer
57 views

Can cyclic shifts of ABAB and ABBA be equal?

Do there exist binary strings $A$ and $B$ so that: the word $ABAB$ is a cyclic shift of $ABBA$ and the word $AB$ does not equal $BA$? Here $AB$ represents the concatenation of $A$ and $B$.