Articles of combinatorics on words

Count the number of strings containing $ac$ or $ca$ for a fixed length over ternary alphabet $A = \{a,b,c\}$ using rational series

This question is a continuation the one asked here, and which already received good answers. Here I am asking for a solution using rational series of formal languages as suggested by the user J. E. Pin in the other thread. Denote by $A = \{a, b, c \}$ a ternary alphabet, also denote by $|u|_{ac}$ […]

Counting elements in cartesian power with plurality + pattern constraints

Problem: I have an alphabet with n=8 letters (say $X=\{A, B, C, D, E, F, G, H\}$). I’m looking for words with m=24 letters, with three constraints: letter $A$ is the relative majority (like in $ABCAAFFHABCAAFFHABCAAFFH$ where $A$ appears 9 times, i.e., more than all other letters) (we could use “plurality” for this concept). one […]

Maximal Hamming distance

Here is a combinatorial problem: let $\Sigma=\{\alpha_1,\ldots,\alpha_n\}$ be an alphabet and we consider any words over $\Sigma$ of length $n$. We also define over the set of such words the Hamming distance: $$d(\omega,\omega’)=\#\{i\in \{1,\ldots,n\} \vert a_i\neq b_i\}$$ where $\omega=a_1\ldots a_{n}$ and $\omega’=b_1\ldots b_n$ are two words. The questions are the following: Let $\omega_0$ be the […]

How many permutations of a multiset have a run of length k?

Background $\newcommand\ms[1]{\mathsf #1}\def\msP{\ms P}\def\msS{\ms S}\def\mfS{\mathfrak S}$Suppose I have $n$ marbles of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color $i$. Let $\msP=(1^{n_1} 2^{n_2} \dots c^{n_c})$ be the multiset $\small\{\underbrace{1, \dots, 1}_{n_1},\underbrace{2,\dots,2}_{n_2},\dots,\underbrace{c,\dots,c}_{n_c}\}$ in frequency representation. The number of distinct permutations of $\msP$ is given by the multinomial: $$\left|\mfS_{\msP}\right|=\binom{n}{n_1,n_2,\dots,n_c}=\frac{n!}{n_1!\,n_2!\cdots n_c!}=n! \prod_{i=1}^c \frac1{n_i!}.$$ […]