9 votos

Arreglo de ceros y unos

Voy a estar agradecido por las ideas (o incluso soluciones!) para la siguiente tarea. Realmente quiero saber cómo resolverlo.

Deje $M$ ser cualquier entero positivo que representa la longitud de la línea construida de $0$ $1$ símbolos. Vamos a llamar a $M$-$N$-línea de una línea de $M$ símbolos, en los que hay exactamente $N$ ($1 \leq N \leq M$) (todos los demás elementos son ceros).

También el número de $L$ es dado tal que $1 \leq L \leq N$.

La tarea es calcular el número de todos los $M$-$N$-líneas en las que hay un grupo de exactamente $L$ consecutivas, y ningún grupo de más de $L$ consecutivas.

Por ejemplo, si $M = 6$, $N = 4$, $L = 2$ luego hay $6$ tal $M$-$N$-líneas:

$$1-1-0-0-1-1$$

$$1-1-0-1-0-1$$

$$1-1-0-1-1-0$$

$$0-1-1-0-1-1$$

$$1-0-1-0-1-1$$

$$1-0-1-1-0-1$$

Gracias de antemano!

1voto

Mark Stanfill Puntos 51

En primer lugar, la lista de los $M-N$ cero: $$\wedge_10\wedge_20\wedge_3\dots\wedge_{M-N}0\wedge_{M-N+1}$$ A continuación, vamos a cada una de las $\wedge_i$ ser la función de generación de $g_i(x)=(1+x+x^2+\dots+x^L)$, esto significa que para cada una de las $\wedge$ no sólo se les permite tener en la mayoría de las $L$ uno, ya que hay $(M-N+1)$ $\wedge$'s, con lo que la generación de la función $$G_1(x)=\prod_{i}^{M-N+1}g_i(x)=(1+x+x^2\dots+x^L)^{M-N+1}$$ and solve for $[x_1^N]$, this is the coefficient of $x^N$, and this is the number of arrangements that for each arrangement there exists groups of at most $L$ consecutive one's. But we are looking for the arrangements that exist groups of exactly $L$ consecutive one's, so we need to subtract the arrangements that for each $\wedge$ there have at most $(L-1)$ one's, then this will give you the arrangements that exist at least one exactly $L$ consecutivos.

Por el mismo método que el anterior, la generación de la función de las modalidades que para cada una de las $\wedge$ tiene más de $(L-1)$ consecutivas es $$G_2(x)=(1+x+x^2+\dots+x^{L-1})^{M-N+1}$$ y resolver para $[x_2^N]$.

Finalmente, $[x_1^N]-[x_2^N]$ es la respuesta.

Esto es sólo la idea de la solución, si desea que la forma general de la solución que le llevará un poco de tiempo para realmente resolver para$[x_1^N]$$[x_2^N]$.

0voto

Stefan Babos Puntos 371

$m$...número de elementos(cero o uno),
$n$...número de unos,
$l$...la longitud de la secuencia.

$d=\left\lfloor\frac{n}{l}\right\rfloor$...número de secuencias de longitud $l$ de los
$r=n \mod l$...número de los restantes($r \lt l$). Estos son, además, marcada por medio de la barra de $\bar{1}$.

$z$...número de ceros, $z=m-n$.
Por ejemplo. Si tenemos $z$ ceros queremos insertar $d=3$ secuencias. Entonces, para cualquier secuencia $11...1$, y 4 ceros $0000$, podemos insertar la secuencia a cualquier $a_i, i={1...5}$ lugares $a_10a_20a_30a_40a_5$. Para hacer esto $\binom{5}{3}$ maneras. Una de las manera es esta: $11...1011...1011...10$(aquí he sustituido los elementos $a_1,a_2,a_3$) y ahora permanecen $2$ ceros y $r$ $\bar{1}$ . Estos ceros y $\bar{1}$ se puede arreglar $\binom{r+2}{1}$.

Así que el total de arreglos podrían ser: $$a=\binom{z+1}{d}\binom{r+z-d}{z-d}$$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X