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

393 questions
Filter by
Sorted by
Tagged with
108 views

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 ...
• 85
1 vote
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,...
1 vote
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 ...
1 vote
67 views

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 ...
• 1,139
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 ...
1 vote
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 ...
• 40.7k
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 ...
• 51
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 ...
1 vote
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$ ...
• 15k
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 ...
1 vote
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 ...
200 views

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$ ...
• 1,835
1 vote
73 views

1 vote
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?...
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 ...
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$...
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; ...
• 1
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 ...
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 ...
• 2,219
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)...
• 9,599
1 vote
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! ...
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 ...
• 21
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 ...
• 2,346
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 ...
• 155
1 vote