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

1
vote
2answers
38 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
40 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
27 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
36 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
57 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
53 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
60 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 ...
2
votes
2answers
27 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
30 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
44 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 ...
6
votes
0answers
112 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
30 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
36 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
28 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
190 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
183 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
180 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
58 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
67 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
49 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
286 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
50 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
65 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
35 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
230 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
83 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
88 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
67 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
68 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
64 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
118 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
62 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
188 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
243 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 ...