Contando la cantidad de colorantes deseables

Question

Inspirado por Este tema:

Vamos a no ser $N$ bolas en una línea recta. Hemos de color con $m$ $(c_1, c_2,\ldots , c_m)$ diferentes colores.

Determinar la probabilidad existe al menos una racha de monocromática de bolas de, al menos, la longitud de la $1\leq k\leq N$.

La verdadera pregunta aquí es, ¿cómo hacemos un recuento de cómo muchos de los colorantes son deseables para nosotros y cuántos hay en total.

Por ejemplo, recoger $N=5, m=2$ (igual probabilidad), $k=3$. Con dos colores, no debería ser $2^5 = 32$ diferentes coloraciones.

EDIT: Gracias Arturo
$5$ formas para tres consecutivos a ocurrir, $2$ formas para cuatro seguidos y $1$ forma de cinco seguidos. Por simetría, no debería ser $16$ deseable opciones.

Con algunas modificaciones también podemos trabajar la solución si los colorantes había diferentes probabilidades.

Pregunta: ¿Cómo podemos contar deseable opciones a la hora de $N=100, m=2$ (igual probabilidad) y $k = 5$? No es muy sensible a contar cada caso. Es allí una manera de resolver este problema con lápiz y papel?

Answer 1

Hay $m^N= 2^{100}$ de los casos en total.
Hay $1231762993555129375668495000350$ deseable de los casos.

Para el conteo de cada una de las deseables casos exactamente una vez que usted puede hacer esto para todas las $i\in[k,N]$:

1. Elija un color común para las bolas con la posición$i-k+1$$i$. Cuenta con un factor de $m$
2. Elija cualquier color para las bolas con la posición$i+1$$N$. Cuenta con un factor de $m^{N-i}$
3. Partición (con el pedido) las bolas con la posición $1$ $i-k$en grupos de tamaño $1$$k-1$. E. g. para $i=9,k=5$ la valide tamaños de los grupos son $\quad\{\{4\},\{3,1\},\{1,3\},\{2,2\},\{2,1,1\},\{1,2,1\},\{1,1,2\},\{1,1,1,1\}\}$
   Para cada partición, el último grupo debe tener un color diferente de la del paso 1. El último segundo de grupo debe tener un color diferente al del último grupo etc. Por lo tanto, una determinada partición de los rendimientos de $(m-1)^q$ de los casos, donde $q$ es un grupo de recuento. En total obtenemos un factor de $S=\sum_q(m-1)^q$. Para el ejemplo de ($i=9,k=5$) tenemos a $q=1,2,2,2,3,3,3,4$

La suma depende de las variables $k$, $i$ y constante $m$. Tenemos

$S(1, i) = \max(2-i, 0) \\S(k, i)=\begin{cases} S(k-1,i-1)& k\leq i\leq 2 k-2 \\ (m-1)\sum_{j=1}^{k-1}S(k,i-j)& \text{else} \end{casos}$

Para obtener el resultado de multiplicar los factores y suma más de $i$: $$\sum_{i=k}^N S(k,i)m^{N-i+1}$$