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

290 questions
Filter by
Sorted by
Tagged with
1answer
94 views
+100

### 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 ...
3answers
92 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 ...
2answers
92 views

1answer
72 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$ ...
0answers
12 views

1answer
53 views

### how many words are there of 5 letters that have at least one I and at least two T's, but no K or Y?

So it is more of a riddle than research-level mathematics, but your help would be hugely appreciated. Here is the full problem: With the Latin alphabet, how many words are there (counting all of them, ...
0answers
32 views

2answers
122 views

### A bag contains 5 red, 6 blue, and 4 yellow marbles

A. How many ways can marbles be drawn if at least 1 must be drawn? What I’ve done to attempt to solve this question A. Just imagine that the marbles aren’t actually marbles, but rather switches. The ...
2answers
415 views

### how do I calculate the Thue-Morse-Sequence over the alphabet {0,1} for $\left(w_{2021}\right)_{2} \bmod 19$?

We define the Thue-Morse-Sequence over the alphabet $\Sigma:=\{0,1\}$ as follows: we set $w_{0}:=0$, and for $n \in \mathbb{N}$ we define $w_{n+1}:=w_{n} \overline{w_{n}}$, where $\bar{w}$ is the unit ...
4answers
117 views

### An easy example of a non-quasiconvex subgroup

Let $G$ be a finitely generated group, and consider the surjection $\mu:F(A)\to G$ induced by the set of generators $A$, where $F(A)$ is the free group on $A$. A word $w$ is said to be ($\mu$-)...
3answers
81 views

### How many $5$ letter arrangements can be made from the word “numeracy” if it MUST include the letter “$y$”?

What I’ve done so far- I know that $y$ will occupy one spot of $5$ letters. I also know that I have to multiply by $5$ to get the final answer. However, I don’t know how to proceed to find the value ...
0answers
84 views

### Is there a name for these subgroups?

Let $F$ be a free group. Let $F_1$ be a subgroup with basis $B$. Assume that $F_1$ has the property that for every $\alpha\in F-F_1$, the set $\{\alpha\}\cup B$ is still free. Is there a name for ...
4answers
204 views

### Combinatorics - How many ways are there to arrange the string of letters AAAAAABBBBBB such that each A is next to at least one other A?

I found a problem in my counting textbook, which is stated above. It gives the string AAAAAABBBBBB, and asks for how many arrangements (using all of the letters) there are such that every A is next to ...
0answers
35 views

### Derive the recurrence relation

Either this question is the easiest one on StackExchange or I just don't get it. The question is : "Let F(n) be the number of strings of length n over an alphabet of size k. Derive a recurrence ...
3answers
86 views

### How many different 4-digit numbers can be made with the digits from 12333210?

How many different 4-digit numbers can be made with the digits from $12333210$? Attempt. So I've tried splitting into cases: Case 1: Only single letters. 1 2 3 0, except for when 0 is at the first ...
2answers
33 views

### Pick r from n with arrangement

I'm self-learning combination theory and encountered this problem. How many distinct $4$ digit number can be formed from picking numbers in $1,3,3,7,7,8$? I'm thinking to permute all numbers then ...
1answer
55 views

### Combinatorics proof counting

The question is counting the number $b_{p,q}$ of binary strings with no consecutive $1$’s, with a $0$ at each end. With q 1’s and p 0’s. How do I prove $b_n = b_{n-1} + b_{n-2}$ is equivalent to ...
2answers
256 views

...
5answers
81 views

### How many sequences of length 10 with elements $\{a, b, c, d\}$ have exactly $3$ out of $4$ elements?

My logic is since $3$ out of $4$ elements are chosen, each element would appear once. So a sequence would look like: $a\,b\,c\,x\,x\,x\,x\,x\,x\,x$ We have $7$ spots $x$ that can be whatever elements ...
2answers
51 views

1answer
51 views

### Counting the number of 'good' tuples of a given length [closed]

Fix a length $L$ and consider an $L$-tuple of $a$ and $b$ that obey the following rules: $Rule$ $1:$ $\textbf{IF}$ there is a consecutive string of $b$'s in the $L$-tuple such that the string does not ...
2answers
105 views

### Probability of a specific binary string sub-sequence occurring

I've been wracking my brains for a while to try to come up with a non-brute-force solution for this problem. If you have have a random binary sequence of length $N$, what is the probability that some ...
2answers
43 views

### Help with reasoning on how to set up a recurrence relation

I'm working with the following problem: An alphabet $\Sigma$ consist of the four numeric characters 1, 2, 3, 4, and the seven alphabetic characters a,b, c, d, e, f, g. Find and solve a recurrence ...
1answer
49 views

### How many words/strings of length 5 can we make using the first 10 letters of the alphabet with at least one repeated letter?

How would you approach a problem like this? If I were to make words of length 5 from the first 10 letters it would be 10^5 or 10x10x10x10x10, right? But how do I account for the repetition part? ...
2answers
53 views

1answer
26 views

### How many subsets of length 10 of the Latin alphabet don't contain the set $\{a, b, c, d\}$?

Let $A$ denote the set of the Latin alphabet. Let $B$ be a subset of $A$ such as $|B|=10$. How to claculate how many such subsets $B$ don't have for a subset the set $\{a, b, c, d\}$. In other words ...