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
1 vote
1 answer
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 ...
user avatar
  • 9
2 votes
0 answers
43 views

Kronecker powers and k-ary words

Let $A$ be any $k\times k$ matrix. Also, let $\otimes$ denote the Kronecker product and define $A^{\otimes n},$ the $n$th Kronecker power of $A$, by $A^{\otimes 1}:=A$ and $A^{\otimes n}:=A\otimes A^{\...
user avatar
0 votes
0 answers
21 views

How tail-repetitive can infinite non-repeating strings be?

Definitions A finite non-empty string $s$ is $n$-tail-repetitive iff there is some non-empty string $p$, so that $n+1$ copies of $p$ constitute a postfix of $s$. For example, the string ...
user avatar
  • 181
1 vote
1 answer
133 views

formula for the position of the ith one and the ith zero in an infinite binary sequence

Define an infinite binary sequence as follows: start with 0 and repeatedly replace each 0 by $001$ and each $1$ by $0$. Provide, with proof, a formula for the positions of the nth one and a formula ...
user avatar
  • 871
0 votes
0 answers
19 views

Bitstring counting with three elements

A bitstring (lenght 10 {0,1}) has exactly 120 string that contains three 0s, but now I am trying to find out how many strings with tree zeros if the string looks like this: {0,1,φ}. Can I still use ...
user avatar
1 vote
1 answer
71 views

How many words with non-consecutive letters?

Using the letters A,B,C,D,E,F,G only once, how many words can be generated such that alphabetically consecutive letters are not next to each other? For the version with only the letters A,B,C,D,E, ...
user avatar
2 votes
1 answer
119 views

Eventually-prime decimal expansions

Let $w$ be a right-infinite word over the alphabet $A = \{ 0, 1, \dots, 9\}$, with a distinguished decimal point after at most finitely many symbols from the left (i.e. $w$ is in $A^\ast . A^\omega$). ...
user avatar
1 vote
2 answers
58 views

Counting problem about Palindromes

Consider the set of four digit sequences $d_1d_2d_3d_4$, where $d_i\in\{0,1,\ldots,9\}$. (a) What is the number of all four digit sequences, which contain no palindromic subsequence. For example, the ...
user avatar
  • 4,316
2 votes
3 answers
112 views

Number of $n$ lettered words made out of $n$ A's and $n$ B's with specified conditions.

Number of $n$ lettered words made out of $n$ A's and $n$ B's such that the number of A's from the left is at all times greater than the number of B's from the left. String needs to contain both ...
user avatar
1 vote
0 answers
42 views

On the number of length-$4$ words over $\{a, b, c\}$

Given the alphabet $\Sigma := \{ a, b, c \}$, find the number of all possible length-$4$ words over $\Sigma$. In this case, the order does of course matter and it is also the case that same letter ...
user avatar
  • 23
1 vote
1 answer
51 views

Number of $5$-letter words out of $\{a,b,c,d\}$ with 2 letters occurring exactly twice.

How do I count the number of $5$-letter words out of $\{a,b,c,d\}$ with 2 letters occurring exactly twice? My current attempt to a solution looks like this. Select two different letters out of $\{a,b,...
user avatar
  • 67
1 vote
4 answers
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 ...
user avatar
4 votes
6 answers
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 ...
user avatar
  • 21.7k
1 vote
3 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 6,569
0 votes
0 answers
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 ...
user avatar
  • 5,329
3 votes
0 answers
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 ...
user avatar
  • 61
3 votes
1 answer
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 ...
user avatar
9 votes
1 answer
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-...
user avatar
4 votes
3 answers
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 ...
user avatar
  • 71
0 votes
0 answers
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 ...
user avatar
0 votes
3 answers
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 ...
user avatar
0 votes
1 answer
50 views

How many $4$ digits numbers can be obtained by using $1,1,2,3,4,5$?

My friend asked me this question. First I am wondering whether this problem is well defined. However, my attemp was: a. Counting all 4 digits numbers from $\{1,2,3,4,5\}$ which is $5 \cdot 4 \cdot 3 \...
user avatar
  • 183
0 votes
1 answer
67 views

What is the number of n-digit numbers that can be written with the numbers 2, 3 and 4 that add up to be odd? [closed]

What is the number of 4-digit numbers that can be written with the numbers 2, 3 and 4 that add up to be odd? for example: 3-23-32-43-34-223-243-232-234-322-324-342-344-... ... n-digit numbers.
user avatar
4 votes
2 answers
202 views

Generating series for ternary strings without 000 and not ending with 0

I would like to find a formula for $T_n$, the number of ternary strings of length $n$ so that they do not contain three consecutive zeroes, and they do not end with $0$ as well. I can find a ...
user avatar
  • 645
1 vote
2 answers
276 views

Binary strings with exactly $n$ ones but without 000 or 111

I am a newbie in binary strings and generating series. I have a problem of enumeration which can be transformed to the following: find the number of binary strings of exactly $n$ ones which do not ...
user avatar
  • 645
0 votes
0 answers
23 views

Can any binary Hamming space be embedded into the binary Levenshtein space?

Suppose $(M_0, d_0), (M_1, d_1)$ are two metric spaces. Let's call a function $f: M_0 \to M_1$ an embedding iff $\forall a, b \in M_0$ $d_0(a, b) = d_1(f(a), f(b))$. It is not hard to see, that ...
user avatar
  • 14.8k
5 votes
1 answer
99 views

Recursive formula for a combinatorial problem and define the generating function

Question: Let $\sigma=\{a,b,c\}$. How many words can we assemble without the substrings $'ab'$ and $'bc'$? define the recursive formula. define the generating function for this formula. $Solution.A....
user avatar
  • 862
7 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 14.8k
1 vote
2 answers
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,...
user avatar
  • 33
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 2,323
7 votes
2 answers
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$. ...
user avatar
  • 1,049
1 vote
0 answers
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.:...
user avatar
  • 862
3 votes
1 answer
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 ...
user avatar
  • 791
1 vote
1 answer
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
  • 153
0 votes
2 answers
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 ...
user avatar
  • 1,585
4 votes
1 answer
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 ...
user avatar
  • 7,327
2 votes
3 answers
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 ...
user avatar
  • 4,350
2 votes
2 answers
140 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^...
user avatar
  • 365
3 votes
3 answers
99 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 $\...
user avatar
1 vote
1 answer
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$ ...
user avatar
  • 341
1 vote
0 answers
13 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\...
user avatar
4 votes
4 answers
419 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 ...
user avatar
  • 43
1 vote
1 answer
82 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 ...
user avatar
  • 407
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
0 answers
53 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 ...
user avatar
  • 645

1
2 3 4 5
7