Aparentemente fácil combinatoria cerebro teaser

Question

Así que tengo un cerebro teaser que va como esto:

Hay una escuela en la que los premios a los estudiantes que, durante un período determinado, se nunca es tarde más de una vez y que no ocurra nunca a va a estar ausente por tres o más días consecutivos. Cuántos posibles permutaciones con repeticiones de la presencia (o ausencia) podemos construir para un determinado período de tiempo que otorgar al estudiante un premio? Se supone que cada día es sólo un estado En el tiempo, Tarde o Ausente durante todo el día, no te preocupes acerca de clases. Ejemplo: durante tres días de los plazos de tiempo, podemos crear los 19 permutaciones con repeticiones que conceder un premio.

Así que lo pensé como que: en primer lugar, nos permite reducir nuestro espacio posible de soluciones. Sabemos que hay $2^n$ posibles permutaciones con repeticiones sin llegar tarde a todo (causa, a continuación, cada una de las $n$ días es sólo En el tiempo o Ausente) y $n\cdot2^{n-1}$ permutaciones con repeticiones con exactamente uno de los Fines del estado.

Y aquí viene la parte difícil - ahora tenemos que restar todas las permutaciones con repeticiones que sostienen los tres (3) días de Ausencia, 4 consecutivos, los días de Ausencia y así sucesivamente. Al principio, pensé algo así como: hay $n - (k-1)$ formas para adaptarse a las $k$días consecutivos absency en un $n$días de plazo sin Fines de los estados. Entonces, yo jugueteó con la búsqueda de una fórmula para $k$días consecutivos absency plazos para con exactamente uno de los Fines del estado y que incluso empecé a encontrar algún tipo de trabajo-ish fórmulas como $2\cdot 3^{(n-k-1)}$ durante 3 días consecutivos absencies en plazos con exactamente uno de los Fines del estado, pero poco después de que (a) mi razonamiento era erróneo, (b) yo no podía llegar con algo generalizado para $k$-día absencies y (c) Me di cuenta de que tanto para este y para mi $n - (k-1)$, tengo que tener en cuenta también todas las combinaciones posibles de los días restantes pueden tomar (por ejemplo, todo puede ser En el tiempo, pero también cada segundo puede estar Ausente, no puede ser más que uno de 3 días absency y así sucesivamente) y todas estas cosas tenemos que restar.

Supongo que fue demasiado profunda con él y no hay duda de que tiene que haber algo menos retorcido solución. ¿Cómo debo hacerlo?

Answer 1

Tratar de construir una relación de recurrencia. Hay seis estados distintos que queremos de la pista: el estudiante puede ser "usado" de su fecha tardía o no, y no puede ser 0, 1, o 2 consecutivos, los días de ausencia al final del intervalo que estamos viendo. Así que vamos a usar las etiquetas por ejemplo,$f_{p0}(n)$ ($p$ para $p$erfect) para el número de cadenas de días de duración $n$ que no lleguen tarde y termina con un no-día de ausencia, $f_{p1}(n)$ el número de cadenas de días, que no tienen ninguna de las llegadas tarde y terminar con exactamente una ausencia, $f_{t0}(n)$ el número de cadenas de días que han utilizado la tardanza fecha y final con ninguna de las ausencias, etc. Entonces (por ejemplo) $f_{p2}(n)=f_{p1}(n-1)$ debido a que únicamente conocen el final de la cadena (es una ausencia), y sabemos exclusiva de la cadena antes de que (es una cadena de $n-1$ días sin tardanzas que termina en una ausencia). Del mismo modo, $f_{p0}(n)=f_{p0}(n-1)+f_{p1}(n-1)+f_{p2}(n-1)$ porque sabemos que el último día es un no-ausencia (y no hay retrasos), pero la cadena antes de que punto podría terminar en cualquier cosa (siempre y cuando no existen atrasos en que subcadena).

A partir de aquí, se puede llegar a construir una generación de función y encontrar una fórmula exacta para el resultado; me sorprendería si hay un muy limpia fórmula explícita (aunque hay probabilidades de un binomio suma similar a la de los números de Fibonacci), pero la generación de la función debe darle una fórmula explícita, al menos.

Answer 2

En esencia, usted quiere saber el número ternario de cadenas de caracteres (strings que consta de $0$s, $1$s y $2$s) de longitud $n$ que tienen más de un $0$ y no tienen tres o más consecutivos $1$s. (En otras palabras, un $0$ es una tarde, y un $1$ es un ausente.) Deje $A_n$ el conjunto de cadenas de este tipo, y deje $a_n=|A_n|$. Deje $B_n$ el conjunto de cadenas en $A_n$ que no contengan $0$, y deje $b_n=|B_n|$.

Si $\sigma\in A_n\setminus B_n$, $\sigma$ contiene exactamente un $0$. Si hay $k$ dígitos antes de la $0$, entonces no se $n-1-k$ dígitos después de la $0$, por lo que hay $b_k$ posibilidades para los dígitos antes de la $0$ $b_{n-1-k}$ para los de después de la $0$. Estas se pueden combinar de forma arbitraria, por lo que

$$|A_n\setminus B_n|=\sum_{k=0}^{n-1}b_kb_{n-1-k}\;,$$

y

$$a_n=|A_n|=|B_n|+\sum_{k=0}^{n-1}b_kb_{n-1-k}=b_n+\sum_{k=0}^{n-1}b_kb_{n-1-k}\;.$$

Ahora $b_n$ es el número de cadenas binarias de longitud $n$ que no contengan $00$, y es bien sabido que esto satisface la recurrencia

$$b_n=b_{n-1}+b_{n-2}+b_{n-3}$$

con las condiciones iniciales $b_0=1$, $b_1=2$, y $b_2=4$. (Estos son los tribonacci números con un desplazamiento de subíndice.) Por lo tanto, la recurrencia

$$b_n=b_{n-1}+b_{n-2}+b_{n-3}+[n=0]+[n=1]+[n-2]$$

es válida para todas las $n$ si establecemos $a_n=0$$n<0$, donde los tres últimos términos son Iverson soportes. Multiplicando por $x^n$, sumando más de $n\ge 0$, y dejando $g_B(x)=\sum_{n\ge 0}b_nx^n$, tenemos

$$\begin{align*} g_B(x)&=\sum_{n\ge 0}b_{n-1}x^n+\sum_{n\ge 0}b_{n-2}x^n+\sum_{n\ge 0}b_{n-3}x^n+1+x+x^2\\\\ &=x\sum_{n\ge 0}b_{n-1}x^{n-1}+x^2\sum_{n\ge 0}b_{n-2}x^{n-2}+x^3\sum_{n\ge 0}b_{n-3}x^{n-3}+1+x+x^2\\\\ &=(x+x^2+x^3)g_B(x)+1+x+x^2\;, \end{align*}$$

y por lo tanto

$$g_B(x)=\frac{1+x+x^2}{1-x-x^2-x^3}\;.$$

Ahora $\sum_{k=0}^{n-1}b_kb_{n-1-k}$ es el coeficiente de $x^{n-1}$$\big(g_B(x)\big)^2$, por lo que si $g(x)=\sum_{n\ge 0}a_nx^n$, luego

$$\begin{align*} g(x)&=g_B(x)+x\big(g_B(x)\big)^2\\\\ &=g_B(x)\big(1+xg_B(x)\big)\\\\ &=\frac{1+x+x^2}{\left(1-x-x^2-x^3\right)^2}\;. \end{align*}$$

La generación de la función es razonablemente bueno, pero las raíces de la cúbico en el denominador no son, así que usted no consigue una muy buena forma cerrada para la $a_n$. Aquí hay una tabla de los primeros valores de$a_n$$b_n$.

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6&7&8\\ b_n:&1&2&4&7&13&24&44&81&149\\ a_n:&1&3&8&19&43&94&200&418&861 \end{array}$$

Lamentablemente, este no es el mismo que OEIS A008466 con un desplazamiento de subíndice, aunque este hecho no se manifiesta hasta que $a_6$; por lo tanto, no es $2^{n+2}-F_{n+4}$.

Answer 3

Siguiente Steven Stadnicki, $f_{p0}(n), f_{p1}(n+1), f_{p2}(n+2)$ son todos los Tribonacci números en el índice de $n+2$ $f_{t0}(n), f_{t1}(n+1), f_{t2}(n+2)$ son todo lo mismo. El número total de la serie es la suma de estos, que es la misma serie con un índice hacia abajo, pero no se encuentra en OEIS. Acabo de hacer una hoja de Excel y se veía la serie en OEIS.

Answer 4

ETA2: OK, me parece bien.

ETA3: Como Brian Scott descubrió, de la serie real está en el error. Creo que la generación de la función es ACEPTAR, aunque, como se produce correctamente $200$ durante seis días.

La fórmula explícita es $2^{n+2}-F_{n+4}$ (donde $F_n$ $n$ésimo número de Fibonacci, con $F_0 = 0, F_1 = 1$). Así, por ejemplo, por tres días, tenemos $2^5-13 = 32-13 = 19$.

Como otra demandado hizo, me engañó un poco por el uso de OEIS. Yo el primero creado una generación de función, teniendo en cuenta que hay cero, uno, o dos ausencias, seguido por cualquier número de secuencias de una hora seguida de cero, uno, o dos ausencias. Denota a veces por $y$ y las ausencias por $z$, podemos escribir

$$ F(y, z) = \frac{1+z+z^2}{1-y(1+z+z^2)} $$

A continuación nos cuenta la posibilidad de llegadas tarde. Si hay $k$ a veces, uno de esos (o ninguno de ellos) pueden ser reemplazadas por una sola hora de llegada. Por lo tanto, nos gustaría reemplazar a $y^k$$(k+1)y^k$. Esto se puede lograr mediante la definición de

$$ G(y, z) = \frac{\partial}{\partial y} yF(y, z) $$

y, a continuación, mediante la evaluación de la serie de Taylor para el necesario grado, y la recolección de todos los términos de igual grado, nos encontramos con una expresión como

$$ \begin{align} G(y, z) & = 1+(2y+z)+(3y^2+4yz+z^2) \\ & + (4y^3+9y^2z+6yz^2) \\ & + (5y^4+16y^3z+18y^2z^2+4yz^3) \\ & + (6y^5+25y^4z+40y^3z^2+21y^2z^3+2yz^4)+\cdots \end{align} $$

que los rendimientos de los términos de $1, 3, 8, 19, 43, 94, \ldots$. De dónde (un milagro se produce-es decir, OEIS rendimientos) $2^{n+2}-F_{n+4}$. Hay, probablemente, un buen recurrencia explicación para esto, pero es la hora de la cena.

Answer 5

Aquí es lo que yo haría es :

• Dibujar la gráfica de la máquina de estado que representa el proceso. Cuenta con 7 miembros, y 3 de las transiciones que salen de cada estado (Uno para S, uno para L, una por Una)
• Reducir el problema a la búsqueda de cómo muchos caminos me llevan desde el estado inicial al estado final (donde se me niega el premio)
• Aplicar la solución de la "Good Will Hunting" problema. (http://www.math.harvard.edu/archive/21b_fall_03/goodwill/)
• Reste el resultado de $3^n$.