Sentados en los asientos con espacio vacío

Question

Hay n sillas en fila. De cuántas maneras puede un maestro sentarse k a los estudiantes en estas sillas para que no 2 los alumnos se sientan uno al lado del otro (y, obviamente, no 2 los estudiantes se sientan en 1 silla)?

Yo estaba pensando acerca de la inclusión-exclusión, que a cada estudiante se sientan uno al lado del otro, sin embargo no es lo suficientemente bueno como no podría ser más sillas de los estudiantes. Básicamente, actualmente tengo ni idea de cómo resolverlo.

Answer 1

La línea de $n-k$ de las sillas en fila; estos serán los que se quedan vacíos.

Ahora elija $k$ de las brechas creadas por las sillas vacías en las que el asiento para los estudiantes;

desde allí se $n-k+1$ lagunas, esto da $\dbinom{n-k+1}{k}$ posibilidades.

Answer 2

Sugerencia: la Etiqueta de los escaños $1, 2, \ldots n$. Si el $k$ estudiantes ocupan los escaños $a_1, a_2, \ldots, a_k$ (en orden creciente), vamos a $b_1=a_1-1$, $b_2=a_2-2$, ... , $b_k=a_k-k$. Entonces $$0 \leqslant b_1 < b_2 < \dotsb < b_k \leqslant n-k,$$ por lo $B = \{b_1 \ldots, b_k\}$ $k$- elemento subconjunto de un $(n-k+1)$-set. Por el contrario, desde cualquier subconjunto puede obtener una configuración de asientos.

Ahora, la pregunta es: ¿cuántos de esos conjuntos de $B$ hay?

Answer 3

Si es solucionable, entonces $k\le \lfloor{\frac{n}{2}}\rfloor$ ($\lfloor x\rfloor$ es la función del suelo en caso de que usted no lo sabe). Tenemos que debido a que cada estudiante tiene que tener espacio alrededor de ellos si se inicia desde la parte frontal y vaya de estudiantes espacio de estudiantes espacio ... y continuar de esta manera es como la elección de un contenedor de dos para poner a cada estudiante. Hay en la mayoría de las $\frac{n}{2}$ de estos contenedores de dos. Por lo tanto, a través del principio del palomar, no puede haber más de $\frac{n}{2}$ de los estudiantes. Hay dos casos en los que, eventualmente, puede ser combinada del primer estudiante está en el frente o un asiento de atrás. Ahora, la representación de la multiplicación de todos los números positivos, junto a un número n! . También puede definir multifactorials como: $n\underbrace{!...!}_m=\prod_{d=0}^{\lfloor {\frac{n}{m}}\rfloor} n-dm$

Esto viene en uso, ya que, con m=2 tenemos n$\cdot(n-2)...$, lo que significa, que el primer estudiante tiene n escaños a elegir, la segunda tiene n-2 ... (no es la sede de la primera estudiante o el uno detrás de ella si se encuentran en la parte frontal). El maestro también podría haber comenzado el espacio, comenzando con el primer estudiante en la segunda mesa, en la fila que conduce a $(n-1)\cdot (n-3)...$ . De difusión de los alumnos como este, ha asumido $2\cdot k-1$ asientos de cualquiera de representación así, en el primer caso tenemos a $\frac{n!!}{(n-2\cdot k)!!}$ , y en el segundo caso $\frac{(n-1)!!}{(n-2\cdot k-1)!!}$ y dependiendo del orden de las cosas que importan se puede dividir por $k!\cdot (n-k)!$ para los arreglos de los estudiantes y las sillas vacías ( como si el pedido no importa que todos los estudiantes son iguales y todas las sillas vacías son las mismas cuando se ponga en los mismos lugares).

al menos esa es la mejor explicación que puedo dar.

Answer 4

Considerar las cadenas sobre el alfabeto $\{0,1\}$ donde $0$ denota una silla y $1$ denota un estudiante. Las cadenas que no contienen $11$ son capturados por la expresión regular $0^* (10^+)^* \{\varepsilon, 1\}$. Si le damos a $0$ un peso de $x$ $1$ un peso de $xy$ estamos buscando para el coeficiente de $[x^ny^k]$.

El uso de estos pesos, la generación de la función de $0^* (10^+)^* \{\varepsilon, 1\}$ es

$$ \frac{1}{1 - x} \cdot \frac{1}{1 - \frac{x^2y}{1 - x}} \cdot (1 + xy) = \frac{1 + xy}{1 - x - x^2y}. $$

Por lo tanto la respuesta es $$ [x^ny^k]\frac{1 + xy}{1 - x - x^2y} = [x^ny^k]\frac{1}{1 - x - x^2y} + [x^{n - 1}y^{k-1}]\frac{1}{1 - x - x^2y} $$ donde \begin{align} [x^ny^k]\frac{1}{1 - x - x^2y} &= [x^ny^k] \sum_m (x + x^2y)^m \\ &= [x^ny^k] \sum_m \sum_r \binom{m}{r} x^{m-r}x^{2r}y^r \\ &= [x^ny^k] \sum_m \sum_r \binom{m}{r} x^{m + r}y^r \\ &= \binom{n - k}{k}. \end{align} Por lo tanto $$ [x^ny^k]\frac{1 + xy}{1 - x - x^2y} = \binom{n - k}{k} + \binom{(n - 1) - (k - 1)}{k - 1} = \binom{n - k + 1}{k}. $$