# 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.

331 questions
Filter by
Sorted by
Tagged with
1 vote
276 views

### Recursive relation practice

My questions: Call a string of letters "legal" if it can be produced by concatenating (running together) copies of the following strings: 'v', 'ww', 'xx' 'yyy' and 'zzz'. For example, the ...
• 9
43 views

• 67
1 vote
239 views

### How many $3$-character strings can be formed using the letters of word MISSISSIPPI? [duplicate]

Only the letters that repeat in the original word can be repeated. I've tried $\frac{11!}{4!4!2!}$ and the for n = then result of the previous permutation I did $\binom{n}{3}$. Just feels like there ...
125 views

### Revisit : $20\choose 5$ subsets without 3,4 or 5 consecutive numbers

Addendum-2 just added to my question. Addendum just added to my question. $\underline{\textbf{Overview}}$ This is a self-answer question of this original question. I strongly suspect that the ...
• 21.7k
1 vote
69 views

### Subwords of the Thue-Morse Sequence

In addition to Complexity of Thue-Morse Sequence, I have the following question: Has anyone found a characterization for subwords of Thue–Morse sequence? I.e., for a given binary word, can I (easily ...
• 51
10 views

### substitutions and shifts query

how to prove: Let $L$ be a language on alphabet $\mathbb A$. Suppose that: every subword of a word in $L$ is a word in $L$, and Every word in $L$ is extendable on both left and the right to a word in ...
40 views

### Number of all ordered lists using characters of a word

How to count all the ordered lists (of any length) that can be made from the letters of a given word? Let's denote this by $f(w)$. Is there a better way than the following (grouping by how many of ...
• 6,569
37 views

### Does a string's "characters" refer to a position in the string, or a value in the alphabet?

This is just a terminology question about the term "character" in the formal theory of strings of symbols. Does the term "character" refer to a particular indexed position in the ...
• 5,329
73 views

### Four digit-number that cannot contain sequence $45$

I keep coming up with the result $8720$ for this, but it's not correct. I calculate like this: Total number of four-digit numbers: $9000$ Combinations beginning with $45$ ($45xx$): $100$ Combinations ...
• 61
107 views

### (Solved)Find the number of $9$ letter words using the letters P, Q, and R containing at least one P and at least two Qs.

Please help me with the last question on my discrete maths assignment because I can't get what I am doing wrong. Find the number of 9 letter words using the letters P, Q, and R containing at least ...
247 views

### Prefixes of a word multiplying to the identity in a free group

Let $A$ be a finite alphabet, and let $w \in (A \cup A^{-1})^\ast$ be a freely reduced word over the alphabet $A$ and formal inverse symbols $A^{-1}$. Suppose $w$ is non-empty. Can there ever be non-...
422 views

### What is the number of non-increasing 4 digit numbers?

This problem, though quite simple, has stumped my teenage mind. How many 4-digit numbers are there whose digits are non-increasing? This seemed quite simple at first, meaning I have the digits [9 8 7 ...
• 71
33 views

### What is this total order over finite sequences over positive integers?

I've stumbled into a group theoretic problem regarding a certain total orders over words. This is very much outside the scope of my current research interests and so want to ask what this order is and ...
59 views

### number of 10 bit binary numbers that repeat a 1

So I have the following problem: given a set of 10 0s or 1s, find the total number of combinations that have at least one instance of 11 so for instance: 1100000000, 1111111111, and 1101001101 all ...
50 views

• 862
175 views

### Chance letter a next to b in circle with whole alphabet such that no vowels next to each other

Here's a question from a book on probability I'm working through: If the $26$ letters of the alphabet are written down in a ring so that no two vowels come together, what is the chance that a is next ...
• 1,345
31 views

### Can we check in polynomial time whether a Dyck word can be assembled from given fragments?

Suppose, $\alpha_1, … , \alpha_n \in \{(, )\}^*$ are arbitrary bracket sequences with total length $\sum_{i=1}^n |\alpha_i| = N$. Can we check in polynomial (in respect to $N$) time whether a Dyck ...
• 14.8k
1 vote
291 views

### Discrete mathematics - ternary strings.

Let n be a natural number, n≥3. A ternary string is a sequence of n symbols that has some of the digits 0, 1, 2. In other words, a ternary string is a n-permutation with a repetion of the set {∞⋅0,∞⋅1,...
• 33
1 vote
76 views

### Counting the number of passwords with at least one digit, one consonant and one vowel

How many $7$-key long passwords are there with at least one consonant and at least one vowel and at least one digit? Note that there are $5$ vowels and $21$ consonant and $10$ digits. I tried to count ...
• 466
196 views

### Batmanacci: a Fibonacci sequence, but with letters

I stumbled upon the Batmanacci problem (via kattis.com), where we have a Fibonacci sequence that starts with $a_1 = \text{'N'}$ and $a_2 = \text{'A'}$, and uses concatenation instead of addition. We ...
• 2,323
220 views

### How many words of length $k$ are there such that no symbol in the alphabet $\Sigma$ occur exactly once?

Introduction Given an alphabet $\Sigma$ of size $s$, I want to find a way of counting words $w$ of length $k$ which obey the rule: No symbol occurs exactly once in $w$. We'll call this number $Q^s_k$. ...
• 1,049
1 vote
59 views

### Recursive formula for a combinatorial problem

Question: Let $\Sigma =\{1,2,3,4\}$. For $n\ge 1,$ let $S_n$ be the set of all words above $\Sigma$ in which each adjacent chars are different and the last char isn't the same as the first char. E.g.:...
• 862
184 views

### Counting words of length $n$ from $k$-sized alphabet with no substring of $k$ consecutive distinct letters

How many words of length $n$ are there, if we have an alphabet of $k$ distinct letters, but the words cannot contain any substring that is made of $k$ consecutive distinct letters, i.e, no $k$-length ...
• 791
1 vote
269 views

### Arrangements of 3 red beads, 3 green beads, and 3 blue beads if rotations/reflections are the same and no 2 consecutive beads are the same color

I've found a problem which gives 3 red beads, 3 green beads, and 3 blue beads. It asks how many arrangements there are of the 3 sets of beads on a necklace, given that the conditions that all 9 beads ...
• 401
60 views

### Number of ways to transform binary sequences into another one using given operations

You're allowed to perform one of four operations each time on a binary sequence: Delete the rightmost 0 in the sequence (if it exists) Turn the rightmost ...
• 153
67 views

### How many strings are there of length $n$ over $\{ 1,2,3,4,5,6 \}$ s.t. the sum of all characters in the string divide by $3$.

Problem: How many strings are there of length $n$ over $\{ 1,2,3,4,5,6 \}$ s.t. the sum of all characters in the string divide by $3$. Attempt: Initially I thought about solving this using ...
• 1,585
127 views

### Recursive factorization of words

Let $\Sigma$ be an alphabet of cardinal $n$. Let $T$ be the set of ordered binary tree whose nodes are labeled by words over $\Sigma$, such that each leaf is labeled by a letter $a\in \Sigma$ and the ...
• 7,327
182 views

### Find a recurrence relation for the number of bit strings of length $n$ by Goulden-Jackson

I am working over Goulden -Jackson Method, I tried to undergo every possible question type. I obtained the following questions from Rosen's Discrete Mathematics and Its Applications. I solved them by ...
• 4,350
140 views

• 745
1 vote
77 views

### Probability that $010$ is present in an $n$-length binary sequence

Imagine a memoryless source that outputs 0's and 1's with probabilities $P_X(0)$ and $P_X(1)$. For example, $P_{X^2}(00)=P_X(0)P_X(0)$. How would you calculate the probability that the sequence $010$ ...
• 341
1 vote