¿De cuántas maneras se puede dividir una cadena de longitud n de forma que cada subcadena tenga una longitud de al menos m?

Question

Suponga que tiene una cadena de longitud 7 (abcdefg) y desea dividirla en subcadenas de longitud mínima 2.

La enumeración completa de las posibilidades es la siguiente:

ab/cd/efg
ab/cde/fg
abc/de/fg
abc/defg
abcd/efg
abcde/fg
abcdefg

Y quizás algunos otros.

En general, si tenemos una cadena de longitud n y queremos dividirla en subcadenas de longitud al menos m, ¿de cuántas formas podemos conseguirlo?

Answer 1

Sea $f(n,m)$ denota este número. Claramente, $f(n,m)=0$ si $n<m$ con la excepción de que $f(0,m)=1$ para todos $m$ . Para $n>m$ tenemos $$ f(n,m)=\sum_{k=m}^nf(n-k,m)$$ Puede ser más sencillo si se cuenta por número de subcadenas: Para dividir en $r$ es lo mismo que dividir $n-rm$ en $r$ sumandos no negativos, lo que es posible en exactamente $n-rm+r\choose r-1$ formas ("estrellas y barras"). Así encontramos $$ f(n,m)=\sum_{r=1}^{\infty}{n-r(m-1)\choose r-1}\qquad\text{if }n\ge m>0.$$

Answer 2

Podemos modelizar la situación con funciones generadoras . Para ello consideramos cadenas binarias formadas por $0s$ y $1s$ . Sea $$0^\star=\{\varepsilon,0,00,000,\ldots\}$$ denotan todas las cadenas que contienen sólo $0$ s con longitud $\geq0$ . La cadena vacía se indica con $\varepsilon$ . La función generadora correspondiente es $$x^0+x^1+x^2+\ldots=\frac{1}{1-x},$$ con el exponente de $w^n$ marcando la longitud $n$ de una cadena de $0s$ y el coeficiente de $x^n$ que marca el número de cadenas de longitud $n$ .

Codificamos las subcadenas de longitud mínima $m(\geq 2)$ como cadenas que empiezan por $1$ seguido de al menos $m-1$ ceros. S \begin{align*} (1)(0^{m-1})(0^\star) \end{align*} w \begin{align*} \frac{x^m}{1-x} \end{align*}

$$ $$

Dado que cada cadena se compone de una o varias subcadenas, las cadenas \begin{align*} (10^{m-1}0^\star)(10^{m-1}0^\star)^\star \end{align*} w \begin{align*} \frac{\frac{x^m}{1-x}}{1-\frac{x^m}{1-x}}=\frac{x^m}{1-x-x^m}\qquad\qquad m\geq 2 \end{align*}

$$ $$ OPs ejemplo con $m=2$ da como resultado una función generadora de la _Números de Fibonacci_ \begin{align*} \frac{x^2}{1-x-x^2}=x^2+x^3+2x^4+3x^5+5x^6+8x^7+\mathcal{O}(x^8) \end{align*}

Por lo tanto, el coeficiente de $x^7$ es igual a $8$ correspondientes a ocho cadenas diferentes de longitud $7$ con subcadenas de longitud mínima $2$ . Estas cadenas son \begin{align*} &1010100\quad\quad(2,2,3)\\ &1010010\quad\quad(2,3,2)\\ &1001010\quad\quad(3,2,2)\\ &1010000\quad\quad(2,5)\\ &1001000\quad\quad(3,4)\\ &1000100\quad\quad(4,3)\\ &1000010\quad\quad(5,2)\\ &1000000\quad\quad(7) \end{align*}