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
0 answers
38 views

A question about combinatorics involving words, patterns and overlaps

After reading some chapters of "Analytic Combinatorics" by Flajolet and Sedgewick (2009), I have the following problem that I am thinking about regarding patterns and overlaps: First, to ...
Gustavo-Silva's user avatar
3 votes
1 answer
169 views

A phone number has seven digits and cannot begin with a 0. How many phone numbers contain the sequence 123?

I was going though a course on edx.org and there the instructor counted $5$ different instances like $1 2 3$ _ _ _ _$ = 10^4$ _ $1 2 3 $_ _ _ $= 9\times10^3$ _ _ $1 2 3 $_ _ $= 9\times10^3$ _ _ _ $1 ...
Sandil Adhikari's user avatar
2 votes
0 answers
72 views

There are $n! $ word made from a world of n different letter by reversing the "maximum" number between the initial letters

A word is initially written with n different letters. Then at each step you write a new word of n letters, reversing the longest initial subword that does not produces a word of $n$ letters already ...
StCS's user avatar
  • 300
0 votes
0 answers
36 views

Formula for the Wythoff array from the infinite Fibonacci word

I have a question pertaining to whether the following way of writing the Wythoff array obtained from the Fibonacci sequence / infinite Fibonacci word is known or obvious. Let $n$ be an integer. Let $F(...
Vincent Russo's user avatar
2 votes
0 answers
84 views

Defining permutations of multiset using bijections

In Stanley's Enumerative Combinatorics, he defines a permutation $w$ of the set $S=\{x_1,...x_n\}$ with cardinality $n$ to be linear ordering $w_1w_2...w_n$, so that the word $w=w_1w_2...w_n$ ...
David Raveh's user avatar
  • 1,736
1 vote
1 answer
59 views

Number of strings of length $n$ over {$x,y,z$} where $x$ and $y$ appear at least once

What I did so far, using generating function: $[x^n] (x+x^2+\dots)(x+x^2+\dots)(1+x+x^2+\dots) = \frac{x^2}{(1-x)^3}= x^2\sum_{k=0}^\infty {3+k-1 \choose 2} x^k = \sum_{k=0}^\infty {2+k \choose 2} x^{...
strugglingmathguy's user avatar
3 votes
2 answers
159 views

Understanding Smirnov words in analytic combinatorics

I am trying to understand a generating function in the explanation of Smirnov words in this book, in page $204-205$. It is said that " Smirnov words. Following the treatment of Goulden and ...
user avatar
1 vote
1 answer
100 views

"No two $0$'s together" versus "No two consecutive $0$'s"

I am solving a problem which asks: How many $13$-bit binary numbers that have no two $0$'s together are there? My first approach: A $13$-bit binary number can either start and end with $0$ like $...
Eren Jaeger's user avatar
1 vote
2 answers
119 views

Number of Distinct Words of arbitrary length $k$ in Euclidean N-Space (i.e; $\mathbb{Z}^N$)

Consider the $N$ dimensional Euclidean Space ($\mathbb{Z}^N$) with it's generating set $G=\{g_1,\cdots,g_N\}$ (and their inverses obviously!), how many distinct words of arbitrary length $k$ are there?...
shawn.shobeiri's user avatar
4 votes
0 answers
53 views

Recovering an element of a free group from its projections

Assume you have an unknown word on an alphabet with at least three letters, and you know all the words obtained by erasing each copy of some letter. Then, you can find the first letter of the original ...
Béranger Seguin's user avatar
2 votes
0 answers
82 views

Inequality regarding kostka numbers in representation theory

Before I post my question, let me set up some notation. Notation. For $k\geq 1$, let $\lambda \vdash k$ be a partition of $[k]$. Let $C(k,m)$ be the set of all partitions $\lambda \vdash k$ of size $m$...
Srinivasan's user avatar
0 votes
0 answers
51 views

number of n length binary strings not containing specific factor [SOLVED]. [duplicate]

EDIT: Thanks to RobPratt's insight, (https://oeis.org/A005251), I wrote a quick and dirty python program to generate the number of bin strings not containing a 3 length string; ...
noha's user avatar
  • 1
2 votes
1 answer
208 views

Combinatorics 1 by n tiling problem generating function

Let $h_n$ denote the number of ways that a 1×n rectangle can be tiled with red, blue, green, and yellow squares, where there must be an even number of red tiles, an even number of blue tiles, and at ...
Mathematical Lie's user avatar
2 votes
1 answer
116 views

Given $m$ objects of type A and $n$ objects of type B, arrange them such that there are not more than two consecutive objects of type B.

I came across this question on Quora and got interested in solving it. Being given a number $m$ of objects of type A and a number $n$ of objects of type B, in how many ways can we create a bigger ...
Nothing special's user avatar
5 votes
1 answer
161 views

Find number of legal codes containing even number of zeros

A decimal code is declared legal if it has an even number of zeros$.$ For example $1900200$ is a legal code, but $10002$ is not. Let $a_n$ be the number of legal decimal codes of length $'n'$. Then (A)...
Maverick's user avatar
  • 8,344
1 vote
0 answers
76 views

How many strings can be formed by reordering the letters ABCDEF so that each string contains the substring EA or the substring CE or both?

How many strings can be formed by reordering the letters ABCDEF so that each string contains the substring EA or the substring CE or both? So I thought considering EA as single character there are 5! ...
Soumi Chatterjee's user avatar
2 votes
3 answers
144 views

Given the set of all strings of length 5 over the alphabet {a, b, c, d, e, f, g, h}, how many strings begin or end with an "e"?

I've tried to treat a string as five consecutive choices with each choice being a selection of a character in the given alphabet. To avoid overcounting strings that both start and end with 'e', I have ...
alr0404's user avatar
  • 21
2 votes
0 answers
92 views

Aperiodic Tilings and Squarefree Words [closed]

Here is the definition of aperiodic tiling on Wikipedia. "A tiling is called aperiodic if its hull contains only non-periodic tilings. The hull of a tiling $T\subseteq\mathbb{R}^d$ contains all ...
Thomas Anton's user avatar
  • 2,246
2 votes
1 answer
46 views

Number of possibilities for creating words of length four

A random generator is generating words of length $4$ out of the alphabet $\{0,1,2,3,4,5,6,7,8,9\}$, for example $1234$. What is the probability to get all different numbers? exactly one pair of same ...
BridgeTYH's user avatar
  • 155
1 vote
3 answers
61 views

Number of strings that are made of $3$ 'a', $1$ 'b', $2$ 'c' and $2$ 'd' such that $aaa$ does not appear

Number of strings that are made of $3$ 'a', $1$ 'b', $2$ 'c' and $2$ 'd' such that $aaa$ does not appear I tried to first place the other letters such that $bccdd$ then we will have gaps ${\_b\_ c\_ ...
Adamrk's user avatar
  • 1,035
2 votes
1 answer
194 views

Complete Codes and Kraft Inequality

Li and Vitanyi define a complete code as a uniquely decodable code to which no codeword can be added while keeping it uniquely decodable. They claim that this is easily seen to be equivalent to ...
Thomas Anton's user avatar
  • 2,246
4 votes
1 answer
51 views

The word problem for groups preceded PH Theorem as a practical undecidability result

The Paris-Harrington theorem is often cited as the first practical instance of an undecidable problem since it doesn't depend on self-reference or diagonalization and is an interesting mathematical ...
Hank Igoe's user avatar
  • 1,420
-3 votes
1 answer
73 views

Does perfect knowledge help you prevent a subword in a word? [closed]

Let there be three words $S_1, S_2,$ and $S_3$ using letters $A$ and $B$ such that neither $S_1$ nor $S_2$ has $S_3$ as a substring. For given $S_3,$ if there is a function that takes $S_1$ and $S_2$ ...
mathlander's user avatar
  • 3,831
1 vote
0 answers
57 views

Find the number of $\{a,b,c,d\}$-strings of length $n$

I am asked to find the the number of $\{a,b,c,d\}$-strings of length $n\in\mathbb{N}$ such that each string contains an odd number of $a$'s, an even number of $b$'s and at least one $c$. I used ...
End points's user avatar
1 vote
1 answer
63 views

What is the number of series $(x_1,x_2,x_3,x_4,x_5,x_6,x_7) \in \{0,1,2\}^7$ that do not contain the sequence $010$ in any three consecutive places? [duplicate]

What is the number of series $(x_1,x_2,x_3,x_4,x_5,x_6,x_7) \in \{0,1,2\}^7$ that do not contain the sequence $010$ in any three consecutive places? Hello! I have the following question in my ...
DanaN's user avatar
  • 43
2 votes
1 answer
258 views

Counting words from 3 letter alphabet based on various conditions.

Please let me know if you can find any mistakes and explain corrections to my work. This exercise is verbatim a Discrete Math professor's assignment. Let $$W= \lbrace w \in \lbrace a, b, c \rbrace ^∗:...
nickalh's user avatar
  • 1,009
1 vote
2 answers
1k views

How many words of length $n$ can be formed which do not contain $k$ consecutive repeated characters?

I am struggling with a question regarding counting number of possible words of length n which do not contain k consecutive equal characters, given that $2 \leq k \leq n$. The words can be formed only ...
theleftwinger's user avatar
5 votes
1 answer
77 views

find the 2002th term of a binary sequence

Source: 2002 UofT Math Competition, problem 9. A sequence whose entries are 0 and 1 has the property that, if each 0 is replaced by 01 and each 1 by 001, the sequence remains unchanged. What is the ...
user3379's user avatar
  • 1,769
0 votes
1 answer
125 views

Find all strings containing {A, B, C} with length 3 and don't have AB, BC, or CA as a substring.

In this case, repetition is allowed, I know there are 12 possibilities because I calculated by hand. My problem is what formula or combination of formulas I can use to solve this question.
Juan Diego Alvarez's user avatar
4 votes
2 answers
59 views

Proving an equation for the number of "sentences" using $k$ letters

Suppose there is a language of three words $W_1=a$, $W_2=ba$, $W_3=bb$. Let $N(k)$ be the number of sentences using exactly $k$ letters. Then there is only one sentence with a single letter, $(a)\,$ ...
utobi's user avatar
  • 1,228
0 votes
1 answer
51 views

• How many ”special” words are in $S$

My attempt: the answer of first question is: $$A_{26}^5=\frac{26!}{21!}=26*25*24*23*22=7893600$$ But i got stuck in the second question but i think the answer is $A_{6}^2 A_{20}^3$ is it true ?
calipaw's user avatar
  • 29
4 votes
1 answer
79 views

How many subsequences do you need to look for to infer a word?

Suppose that a word of length $L \in \mathbf{N}$ is defined to be an element of $A^{L}$, where $A$ is a finite set of characters and that a subsequence of a word is an ordered list of characters which ...
Matthew Barber's user avatar
5 votes
2 answers
482 views

Find the number of words that can be made by all of the letters in the word 'GEOMETRY' so that no vowels are adjacent.

The given question is: Find the number of words that can be made by all of the letters in the word GEOMETRY so that no vowels are adjacent. My approach: 5! × (6𝑃 3/2!) = 7200, using the logic of ...
qwerty's user avatar
  • 394
3 votes
2 answers
116 views

Number of strings containing an adjacent pair of a specific character

Problem Space Given a set of strings $S$ of length $N$ where each character of $S$ is to be filled by choosing exhaustively from it's own alphabet subset $S_n$ where $n < N$. For example, if $N=2$ ...
Seanny123's user avatar
  • 169
5 votes
2 answers
160 views

Can we define addition of numbers which are **NOT** eventually all zero as we go to the left?

I am struggling to define addition of objects which are similar to decimal-expansions. In this post, we refer to the decimal-expansion-like things as "wumbers". Our goal is to write ...
Toothpick Anemone's user avatar
0 votes
0 answers
76 views

How many different ways can you write $u^5v^2$?

I have been working on a project trying to say that the Submonoid membership problem is decidable for different examples, one of those being the Klein Bottle. I am now left with a problem that I am ...
Max Pateman's user avatar
5 votes
1 answer
146 views

Word length function on subgroup

Let $G$ be a group finitely generated by a set $S$ with $S=S^{-1}$. The word length of an element $g \in G$ (with respect to $S$) is defined as \begin{eqnarray} |g|_S:= \min \{n \in \mathbb{N} \mid ...
worldreporter's user avatar
5 votes
1 answer
282 views

Normal subgroup generated by one element

Let $F$ be a free group of rank at least two and $\alpha,\beta$ be two elements in $F$. Let $N(\alpha)$ (resp. $N(\beta)$) be the normal subgroup generated by $\alpha$ (resp. $\beta$); i.e., $N(\alpha)...
Tommy W. Cai's user avatar
6 votes
2 answers
227 views

Sequence of $0$’s and $1$’s without six consecutive identical blocks

Let $S_n$ be the number of sequences of $n$ zeroes and ones such that the sequence does not contain six consecutive identical blocks of numbers. Show that $S_n$ tends to infinity as $n\to\infty$. ...
Fred Jefferson's user avatar
1 vote
1 answer
70 views

Is word substitution invertible?

Here is the problem. Let us say we have a word made up of two letters, for example, $ABBBA$. Say I enforce the substitution $A\to AB$ to get the word $ABBBBAB$. Is it always the case that if I know ...
2132123's user avatar
  • 1,555
-3 votes
1 answer
48 views

How many words can we make with the following letters $PTEXYPADFYOLNQYIG$? [closed]

How do you solve this? How many words can we make with the following letters PTEXYPADFYOLNQYIG keeping the vowels in the same position?
Dacxj0's user avatar
  • 3
0 votes
2 answers
80 views

Counting permutations with inclusion-exclusion

How many permutations are there of the letters XXXYYYZZZ if no more than two X’s can appear together and no more than two Y’s can appear together? I get a vague idea that I should use PIE to solve ...
grxxes75's user avatar
1 vote
1 answer
697 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 ...
yuyu's user avatar
  • 27
2 votes
0 answers
71 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^{\...
bryanjaeho's user avatar
1 vote
1 answer
157 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 ...
user3472's user avatar
  • 1,023
0 votes
0 answers
29 views

Bitstring counting with three elements

A bitstring (length $10$ $\{0,1\}$) has exactly $120$ string that contains three $0$s, but now I am trying to find out how many strings with three zeroes if the string looks like this: $\{0,1,\phi\}$. ...
victorialangoe's user avatar
1 vote
1 answer
369 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, ...
kolistivra's user avatar
2 votes
1 answer
130 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$). ...
Jean Charles's user avatar
1 vote
2 answers
92 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 ...
boaz's user avatar
  • 4,667
2 votes
3 answers
131 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 ...
Ayan Bhowmik's user avatar

1
2 3 4 5
8