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

367 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
169 views

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$ ...
1 vote
59 views

1 vote
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?...
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 ...
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$...
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; ...
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 ...
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 ...
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)...
1 vote
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! ...
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 ...
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 ...
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 ...
1 vote
61 views

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$. ...
1 vote
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 ...
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?
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 ...
1 vote