Skip to main content

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 votes
2 answers
108 views

How many $5$ or $6$-letter words can be created with $1$ a, $2$ b's, and $3$ c's? [closed]

How many $5$ or $6$-letter words can be created with $1$ a, $2$ b's, and $3$ c's? I have calculated the number of permutations of all $6$ letters (all $6$-letter words) using $$\frac{n!}{n_1!n_2!n_3!} ...
Brayden Atwell's user avatar
4 votes
0 answers
203 views

Counting words that agree at some place with each of their cyclic permutations

Let $a(m,n)$ be the number of words $W$ of length $m$ in an alphabet of $n$ letters, which have the property that each cyclic permutation of $W,$ has the same letter as $W$ in some place. For example, ...
Tom WIlde's user avatar
  • 271
2 votes
2 answers
80 views

The number of strings of length $n$ consisting of symbols $A,B,C$ not containing substring $CC$

So I'm wondering what is wrong with my reasoning. Let $a_n$ be the number of strings of length $n$ in letters $A,B,C$ not containing substring $CC$. I want to solve it like this. Let $b_n$ be the ...
per persson's user avatar
2 votes
2 answers
126 views

Counting binary strings with $9$ ones and containing $11011$

I am currently trying to solve this problem: How many strings of 20 bits are there with exactly nine $1$s and containing at least one occurrence of $11011$ as a substring? I don't have problems with ...
Shicchan Zero's user avatar
0 votes
2 answers
54 views

At least two consecutive 'A's

How many permutations of A,A,A,B,B,C,C,D,D,D contain at least two consecutive 'A's? My attempt: The number of permutations with exactly two consecutive 'A's: $$ W(P_{AA})=\frac{9!}{1!2!2!3!}-2\cdot \...
Proper Illumination's user avatar
2 votes
3 answers
116 views

The number of ways $abcabcabc$ can be arranged so that no word contains the sequence $abc$

My approach is as follows: Total no. of permutations - abc appears once - twice - thrice $For \ 1 \ abc \ : \ $ We can arrange $ \ a,b,c,a,b,c \ $ (in $\frac{6!}{2!2!2!}$ ways),then subtract the ...
User's user avatar
  • 85
1 vote
1 answer
60 views

Correcting Overcounting in Formula for Strings with 3 Consecutive Characters

I have a string of length n that can consist of 3 different characters: a, b, and c. I need a formula to calculate the number of strings which contains at least 3 consecutive c's (e.g., ccccb). So far,...
Zugzwangerz's user avatar
1 vote
1 answer
69 views

How many strings made of $a$ "A"s and $b$ "B"s are there such that at any point in writing it there are never $k$ more "A"s than "B"s?

I was dealing with a problem stating: "What is the probability that, picking one ball at a time from a jar containing 1,016 red balls and 1,008 green balls, there is never a moment where the ...
Francisco Sierra's user avatar
1 vote
2 answers
67 views

How many isomorphism classes are there of strings of length $n$ over alphabet $\Sigma$ of size $k$?

Isomorphisms of Strings. $$ s = aa \simeq bb\\ s = ab \simeq ba $$ So the set of strings over a 2-letter alphabet of length 2 have merely 2 isomorphism classes. $$ s = aaa \simeq bbb \\ s = aab \simeq ...
SeekingAMathGeekGirlfriend's user avatar
4 votes
1 answer
47 views

Combinatorial proof that $\sum_{k=1}^{n} k {2n \choose n+k}=\frac{1}{2}n{2n \choose n}$ [duplicate]

I'd like to find a combinatorial/algebraic proof of the identity: $$\sum_{k=1}^{n}k{2n \choose n+k}=\frac{1}{2}n{2n \choose n}$$ The only proof of this that I've been able to find on the Internet, ...
N. S.'s user avatar
  • 81
1 vote
1 answer
35 views

Recursion for n-strings made using ${a,b,c}$ in which abc and other 5 perms don't appear

The title should be self explanatory. Let $B_n$ be the set of all $n$ length words made using the letters $a,b,c$ such that no three consecutive distinct letters appear. That is, we want to avoid $abc$...
Snowflake's user avatar
  • 326
0 votes
1 answer
28 views

Extremal Combinatorics Problem on words

Find the maximum length $m$ of the sequence $a_1 a_2 \dots a_m$ such that (1) Each $1\le a_i\le n(\in\mathbb{N})$ (2) No $1\le i \le m-1$ such that $a_{i}=a_{i+1}$ (3) Call $(x,y)$ good if $a_i=x, a_j=...
C TI's user avatar
  • 41
4 votes
1 answer
48 views

Average length of longest duplicated substring in a random binary string of length N

What is the average length of longest substring occurring at more than one position in a uniformly random binary string S of length N ? For example, ...
VainMan's user avatar
  • 1,735
1 vote
0 answers
41 views

Confusion with problem regarding 3-letter strings created from a 5-letter alphabet

I'm taking a discrete math course in university right now and we're studying permutations and combinations as one of the chapters. The question I'm confused about states that given a 5-letter alphabet,...
JBatswani's user avatar
3 votes
1 answer
67 views

What is the total number of words of length $500$ on $\{a,b\}$ such that the letter $"a"$ appears more than $"b"$ ( without Brute force)?

The question : What is the total number of words of length $500$ on $\{a,b\}$ such that the letter "$a$" appears more than "$b$"? $(*)$ We know that the total number of words is $ ...
User33975329257439645's user avatar
3 votes
1 answer
92 views

Prove a string can be rearranged such that no character repeats

I'm solving a coding problem, and I wanted to mathematically prove that the answer exists. Essentially, we are given a string of lowercase letters, and we want to know if it can be rearranged such ...
sodiumnitrate's user avatar
5 votes
0 answers
103 views

Combinatorial problem about finding equidistant words

Assume I have an alphabet $\{A,B,C...\}$ with a total of $K$ symbols. For words of same length, I define the distance $d$ between them as the number of positions in which they have differing symbols (...
mavzolej's user avatar
  • 1,472
1 vote
0 answers
40 views

Is $2$-avoidability determinable?

Is it decidable if a given word is $2$-avoidable? That is, does there exist an algorithm which can determine for a given pattern whether every infinite binary word contains that pattern? It seems that ...
volcanrb's user avatar
  • 3,054
0 votes
0 answers
25 views

Why does this example not break avoidability?

Suppose we have an alphabet $E = \{x_1,x_2,...x_k\}$. Then according to (https://arxiv.org/pdf/1902.05540.pdf, page 2), Zimin words are unavoidable. How does word $w = (x_1)(x_1)(x_1)\ldots$ not ...
Koen de Jong's user avatar
1 vote
1 answer
93 views

Expanding series to obtain desired words using generating functions

I am working on analytic combinatorics by myself. According to theorem, $$W\bigg(z,\frac{az}{1+az},\frac{bz}{1+bz},\frac{cz}{1+cz}\bigg)=\bigg(1-\frac{az}{1+az}-\frac{bz}{1+bz}-\frac{cz}{1+cz}\bigg)^{-...
user avatar
0 votes
0 answers
18 views

Seeking Formalization or Verification of an Inequality Involving Sums and Products

Body: Hello everyone, I've been working on an inequality involving sums and products over certain functions and indices, and I've come up with a proof sketch. However, I'm not entirely sure about its ...
Martin Geller's user avatar
0 votes
2 answers
107 views

Discrete Math Strings

Question: 7. A string that is obtained by rearranging the letters of the word BOOGER is called awesome, if the string does not contain the substring OO. Thus, GEOROB is awesome, whereas GREOOB is not ...
Ali Sobh's user avatar
1 vote
0 answers
15 views

Separating a primitive word of $A^*$ from its proper prefixes by a monoid morphism from $A^*$ to $\mathbb Z$.

This question came up as a side issue during the course of a research project and I am wondering whether the answer is yes or no. A word is primitive if it is not a proper power of a shorter word. A ...
J.-E. Pin's user avatar
  • 40.7k
3 votes
3 answers
274 views

How many binary strings of length 10 are there that don't contain either of the substrings 101 or 010?

How many binary strings of length 10 are there that don't contain either of the substrings 101 or 010? I've tried doing some casework, thinking that there wouldn't be too many cases, but it didn't ...
vic100's user avatar
  • 51
3 votes
3 answers
414 views

Number of words with 8 letters using an alphabet of 3 consonants and 2 vowels with constraints

A new language is developed such that it has $5$ letters $A ,B, C ,D, E$ where A, E are called vowels while B, C, D are called consonants . The language has the following rules :a letter cannot be ...
roinuj navog's user avatar
1 vote
0 answers
117 views

Which hyperoperations produce a "prefix-complete" sequence?

Definition ("prefix-complete"): A sequence of positive integers $(a_n)_{n=1,2,3,\dots}$ will be called prefix-complete in base $b$ iff, for any positive integer $p$, there is some $a_n$ ...
r.e.s.'s user avatar
  • 15k
2 votes
1 answer
119 views

What's the minimum guaranteed substring match between a binary string and a chosen rotation?

Given $n$: An adversary chooses a binary string $X$ of length $n$. I choose two distinct rotations of $X$, called $Y$ and $Z$, with the goal of maximizing $m$, the length of the longest prefix shared ...
kevincrawfordknight's user avatar
1 vote
0 answers
51 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
200 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
76 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
  • 349
0 votes
0 answers
59 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
95 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,835
1 vote
1 answer
73 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
269 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
113 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
129 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
62 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
3 votes
0 answers
221 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
435 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
129 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
267 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
  • 9,599
1 vote
0 answers
112 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
402 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
103 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,346
2 votes
1 answer
58 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
65 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
  • 913
2 votes
1 answer
473 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,346
4 votes
1 answer
54 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,416
-3 votes
1 answer
77 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
  • 4,057

1
2 3 4 5
8