Cómo contar el número de posibilidades de separar una cadena de n caracteres i veces

Answer 1

Según su ejemplo, está claro que no le importa si algunas de las cadenas resultantes son cadenas vacías. Asumiré que no te importará si la cadena vacía aparece varias veces.

Como ya ha notado, hay n + 1 lugares donde puede pegar una partición. Si realiza particiones i y no distingue entre particiones, tendrá [math] \ binom {n + i} {i} [/ math] combinaciones de posiciones. Intuitivamente, tienes posiciones [matemáticas] n + i [/ matemáticas], contando tanto los caracteres como los divisores, y eliges [matemáticas] i [/ matemáticas] para que sean divisores. Por supuesto, algunas de estas particiones se verán muy similares, por ejemplo, cinco de ellas serán “abcd” más cuatro cadenas vacías. Parece que está bien con esto ya que contó abcd más la cadena vacía dos veces en su ejemplo. Pero supongamos que desea contar todo esto como la misma solución. Las cosas se vuelven mucho más complicadas si haces esto.

Una forma de hacerlo es insistir en que las cadenas vacías tienen que venir al principio. Entonces, tienes (n-1 elige i) + (n-1 elige i-1) +… + 1 particiones posibles. El primer término en la suma corresponde a no permitir cadenas vacías, la segunda a exactamente 1 cadena vacía, la tercera a dos cadenas vacías y así sucesivamente hasta la solución única con la cadena completa en una partición y el resto de las cadenas vacías.