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.

Filter by
Sorted by
Tagged with
3
votes
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 ...
2
votes
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 ...
2
votes
2answers
92 views

Number of $n$ length word that can be formed using the alphabets $a$, $b$, $c$, $d$ such that $a$ and $b$ never come together.

My thought : Total $n$ letter words that can be formed by repeating $4$ letters is number of onto functions from set of $n$ elements to set of $4$ elements. This is equal to $4^n-4\times 3^n+6\times 2^...
3
votes
3answers
77 views

Generating function for runs in alphabets

Let $\mathcal{J}$ be a finite set of letters. Suppose that $|\mathcal{J}| = m$. Now designate a letter from the set $\mathcal{J}$. What is the ordinary generating function of words with letters from $\...
1
vote
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$ ...
1
vote
0answers
12 views

Eventual combinatorial rank of iterates of substitutions

Let $A$ be a finite alphabet, $A^+$ be the set of finite nonempty words in $A$ and $\sigma\colon A\to A^+$ a map. For words $w = a_1\cdots a_{|w|} \in A^+$, we define $\sigma(w) = \sigma(a_1)\cdots\...
5
votes
4answers
229 views

How many words can you create of length 6 with given properties?

How many words can you create of length 6, from the letters a, b, c and d if you must include each letter at least once you must include each letter at least once, and a must appear exactly once. My ...
-1
votes
2answers
41 views

Find string array of length n with digits 1 2 3 with no consecutive digits. Solve with combinatorics and recurrent relation. [closed]

Find a string array of length n with digits 1, 2 and 3, in which two digits do not occur consecutively? (ex. 1223..) How many different string arrays exist? a) write it using combinatorics b) find the ...
1
vote
1answer
76 views

A bus has to visit three cities, each of them four times.The number of ways it call be done if bus is not allowed to start and end in the same city is [closed]

A bus has to visit three cities, each of them four times. The number of ways it call be done if bus is not allowed to start. and end in the same city is? (A) 1260 (B) 1120 (C) 980 (D) None of the ...
0
votes
0answers
23 views

how many words can be created with $12$ characters which includes $4$ Cs and $5$ Ds and any other letter of the alphabet? (statistics and probability)

The problem is: How many words of $12$ letters can I get if the word includes $4$ letters of C and $5$ letters of D and on the other spots of the word can be any letter of the $26$ letters of ...
0
votes
0answers
49 views

How many $n$-words from the alphabet $A=${$a,b,c,d$} are there such that $a$ and $b$ are never neighbors. [duplicate]

How many $n$-words from the alphabet $A=${$a,b,c,d$} are there such that $a$ and $b$ are never neighbors. $\\$ Source : Problem Solving Strategies by Arthur Engel$\\$ The solution given in the book ...
0
votes
0answers
29 views

Finding the number of $n$-words which can be formed under the given conditions.

Consider all $n$-words from the alphabet {$0,1,2,3$}. How many of them have an even number of :-$\\$ $(a).$ zeroes $\\$ $(b). $ zeroes and ones $\\$ Source : Problem Solving Strategies by Arthur Engel$...
1
vote
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, ...
1
vote
0answers
32 views

Counting strings with only a few unique elements such that no consecutive elements are the same

The problem concerns strings of length $\ell$, containing only a few unique elements of a larger alphabet, such that no two neighboring elements are the same. The problem: I have an alphabet $\{a,b,c,...
0
votes
1answer
115 views

Combinatorial problem on counting binary sequences

Let $\mathcal{S}_n$ be the set of all binary sequences formed by $n$ values in $\{-1,1\}$ and let $k<n$ a given non-negative integer with the same parity of $n$. For every sequence $\mathcal{S}\ni ...
0
votes
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 ...
0
votes
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 ...
4
votes
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$-)...
2
votes
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 ...
2
votes
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 ...
5
votes
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 ...
0
votes
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 ...
5
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
2answers
51 views

How many words of length $n$ is it possible to create from $\{a,b,c\}$ without any “$c$”s after a “$b$”?

This post is a duplicate of this post. The question is, How many words of length $n$ is it possible to create from $\{a,b,c\}$ without any “$c$”s after a “$b$”? For example, the string $\color{blue}{\...
1
vote
1answer
32 views

Combinatorics Question with vowels

How many 8-letter words contain exactly 5 vowels (a,e,i,o,u)? What if repeated letters were not allowed? This question has two parts to be answered. The first part is,"How many 8-letter words ...
0
votes
1answer
35 views

Counting the number of passwords of length 6 with the given conditions

A password of length 6 with upper case letters, lower case letters and digits. Password must contain at least 1 upper case, 1 lower case and 1 digit. How many possible passwords are there ? What I did....
0
votes
0answers
25 views

Bijection between binary strings with an even-length palindromic prefix and binary strings with a bifix

As Danny Rorabaugh's OEIS sequence A262312 suggests, the number of binary words of length $n$ that begin with a even-length palindromic prefix is the same as the number of binary words of length $n$ ...
1
vote
1answer
30 views

Composing words from a limited letter supply

A typesetter working with an $n$-letter alphabet has $k$ copies of each letter in his type case; how many $n$-letter words can he compose? What is the number of $n$-letter words composed from an $n$-...
2
votes
1answer
43 views

How many length 10 words can we make that start with “TRY” or end with “TRY”?

With replacement and repetition is allowed, if we can choose from the 26 letters of the alphabets, how many length 10 strings/ words can we make that either start with the substring "try" or ...
2
votes
4answers
127 views

Words of length $10$ in alphabet $\{a,b,c\}$ such that the letter $a$ is always doubled

Compute the number of words of length $10$ in alphabet $\{a,b,c\}$ such that letter $a$ is always doubled (for example "$aabcbcbcaa$" is allowed but "$abcbcaabcc$" is forbidden). ...
0
votes
1answer
16 views

Let $t_n$ be the number of strings of length $n$ that do not contain $11$ as a substring over the alphabet $\{ 1,2,3 \}$, prove $t_n =$ (cont.)

If $t_n$ denotes the number of strings of length $n$ that do not contain $11$ as a substring over the alphabet $\{ 1,2,3 \}$, then prove $t_n = \sum_{i=0}^{\lfloor{\frac{n+1}{2}} \rfloor}2^{n-i} C(n-i+...
-1
votes
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 ...
3
votes
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 ...
0
votes
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 ...
0
votes
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? ...
4
votes
2answers
53 views

Recurrence relations for strings of $0$'s and $1$'s of length $n$ where no $k$ consecutive $1$'s appear.

This question is related to this one, but the answers there do not explain my confusion. This is exercise 20 in page 28 in the book generatingfunctionology: Let $f(n,m,k)$ be the number of strings of $...
1
vote
1answer
65 views

How many ways can we write a word of 4 letters from the group of {1,2,3,4} without the sequence 12 and 23?

How many ways can we write a word of 4 letters from the group of {1,2,3,4} without sequence 12 and 23? the options are: 16 2.256 3.172 4.24 I think we can repeat on the same letter so I tried to ...
0
votes
3answers
34 views

In how many ways can 4-digit numbers be formed using 2,2,8,8 if each digit is used once only?

In how many ways can 4-digit numbers be formed using 2,2,8,8 if each digit is used once only? I'm confused as to how to solve this problem. If the question was "How many ways can 4-digit numbers ...
2
votes
1answer
48 views

How many different codes can be formed such that the code consists of two letters followed by four digits?

I have a question as follows: A small design company gives each of its products a code that consists of two letters followed by four digits. How many different codes can be formed such that the ...
1
vote
1answer
38 views

Explicit formula for number of n-digit ternary sequences with no consecutive 2's

I'm looking for an explicit formula for $a_n$ which denotes the number of ternary sequences with no consecutive 2's. I've managed to find the recursive formula $$a_n = 2a_{n-1} + 2a_{n-2}$$ I've ...
5
votes
2answers
77 views

Combinatorics - letters forbidden sequence.

I am trying to solve a question. I have 15 pens, where 5 are colored in Red, 5 in Green, and 5 in Blue. How many combinations can I order these pens so that there is no sequence of 5 pens with the ...
17
votes
4answers
333 views

The Soup Problem: how to asymptotically fairly split a geometric series and a constant one using a single pattern?

Literally every time I'm serving some soup I'm thinking of this little mathematical problem I devised. Imagine you have a very large (= infinite, for the purposes of the actual problem) bowl of soup ...
0
votes
0answers
33 views

Number of strings which have given prefix function

Prefix function of string is by definition $\pi: \mathbb A^n \to \mathbb N^n$, where $\mathbb A$ is set of all characters of string (alphabet) and $\mathbb N$ is set of natural numbers. If $s$ is ...
0
votes
1answer
41 views

Elementary combinatorics [duplicate]

You are given a string of $10$ characters, that can either be 'A' or 'B'. How many of them do not contain the string 'ABA'? What I thought was to adopt a recursive approach. Supposing we know the ...
4
votes
0answers
38 views

Cardinality of equivalence classes in the positive braid semigroup?

A presentation for the braid group is: $$B_n = \{ s_1,...,s_{n-1} | s_is_{i+1}s_i=s_{i+1}s_is_{i+1},\ \text{ } s_is_j = s_js_i \text{ for } |i-j| \geq 2\}$$ As a set, the positive braid semigroup $B_n^...
0
votes
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 $$...

1
2 3 4 5 6