# Questions tagged [combinatorics-on-words]

combinatorial properties of strings of symbols from a finite alphabet

124 questions
1answer
17 views

### Generating function for amount of words, only using letters A,B and C, without two or more successive A's. [on hold]

Question in the title; I kinda feel helpless about that one.
1answer
30 views

1answer
93 views

### How many letters suffice to construct words with no repetition?

Given a finite set $A=\{a_1,\ldots , a_k\}$, consider the sequences of any length that can be constructed using the elements of $A$ and which contain no repetition, a repetition being a pair of ...
1answer
30 views

### Counting binary Lyndon words with fixed degree in one letter

uGiven an alphabet ${x,y}$, a (binary) Lyndon word is a word $w$ in $\{x,y\}$ such that if $w=uv$ is a factorisation of $w$ into non-empty subwords, then $u<v$ in lexicographic order. This is ...
1answer
14 views

### Solving recurrence equation for lossy duplication

Suppose we have a word of length $L$ from a two-letter alphabet (say, $\mathcal{A} = \{A,B\}$), and we duplicate it. However, our duplication is fallible: each element of the result is incorrect ($A$ ...
2answers
47 views

### In a word containing $k$ A's, how many permutations place at least $n$ A's consecutively?

Suppose a word is $l$ letters long, and it contains $k$ A's. (The specific letter is irrelevant) Is there a general formula to count how many permutations contain at least $n$ consecutive A's? (Assume ...
2answers
46 views

### How many essentially different strings are there of length $\leq n$ and over an alphabet of size $|\Sigma| = m$?

For example, $aaaaaabb \simeq ccccccdd$ essentially, because a smallest grammar algorithm would perform the exact same steps to reduce one as the other. So how can I phrase this in terms of formal ...
0answers
28 views

### Does This Property of Words Have a Name?

Let us say an infinite word $w=w_1w_2\cdots$ over a finite alphabet $\{a_1,\ldots,a_r\}$ is good if there exists a positive integer $m$ such that none of the words $a_1^m,\ldots,a_r^m$ appear as ...
1answer
40 views

### How many word can we make with infinited times of $B$, $D$ $M$ and only one $O$?

In a case, we have infinite times of the letter B, D, M and only one O. How many different word containing those letter can we make (can be meaningless in this term) ?
1answer
81 views

### Are all Fibonacci words uniquely represented as concatenation of two palindromes?

Suppose Fibonacci word sequence is a word sequence defined by the following relations: $$\phi_1 = «0»$$ $$\phi_2 = «01»$$ $$\forall n > 2 \text{ } \phi_n = \phi_{n - 1}\phi_{n - 2}$$ Let’s prove, ...
1answer
67 views

### How many n-letter words are there, such that number of letters “a” is even? [closed]

How many n-letter words (made of letters from 25-letter english alphabet) are there, such that number of letters "a" is even? ("a" appears even number of times in a word). I'm trying to create ...
1answer
68 views

### For what $n$ is $W_n$ finite?

Suppose, $W_n$ is the set of all words formed by letters '$a$' and '$b$', that do not contain $n$ same consecutive nonempty subwords (that means that for any nonempty word $u$, the word $u^n$ is not a ...
2answers
34 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 '...
0answers
33 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. ...
1answer
46 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$ ...
0answers
32 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 ...
1answer
147 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 ...
1answer
27 views

2answers
31 views

1answer
38 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 ...
1answer
257 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. ...
2answers
90 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 ...
1answer
156 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 ...
1answer
87 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 ...
0answers
76 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 ...
0answers
72 views