Stack Exchange Network

Stack Exchange network consists of 175 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

1
vote
1answer
30 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,...
0
votes
1answer
29 views

Combinatorics: Choice of Passwords

Question: A sequence of exactly 8 symbols, which contains exactly one lower-case letter from ${a, . . . , z}$, exactly one upper-case letter from ${A, . . . , Z}$ and at least one from ${0, 1, . . . , ...
9
votes
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 ...
2
votes
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 ...
0
votes
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$ ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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) ?
4
votes
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, ...
-1
votes
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 ...
6
votes
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 ...
1
vote
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 '...
0
votes
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. ...
1
vote
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$ ...
1
vote
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 ...
7
votes
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 ...
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
31 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
37 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
31 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
36 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
191 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
43 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
211 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
30 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
187 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
47 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
61 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
73 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
53 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
293 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
60 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
71 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
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 ...
3
votes
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. ...
3
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
3
votes
0answers
72 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
73 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
150 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
65 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?...