¿Cómo responder la siguiente pregunta combinatoria?

Question

Consideremos el conjunto a $S = \{ 1,2, \cdots , 15 \}$. La pregunta general es: ¿cuántos subconjuntos de a $S$ existen tales que los subconjuntos contiene 4 diferentes elementos sin ningún tipo de números consecutivos? Como un sub-pregunta, tengo que demostrar que este problema es equivalente a encontrar el número de soluciones de $$(*) \qquad a_1 + a_2 + a_3 + a_4 + a_5 = 14 ; \qquad a_1,a_5 \geq 0 ; a_2, a_3, a_4 \geq 2 $$ Para probar esto, he intentado lo siguiente. Considerar los números del 1 al 15 establecidas uno al lado del otro en una fila, comenzando con el número 1 y terminando con 15. Para encontrar los subconjuntos que obbey las restricciones dadas, hemos de comenzar por recoger algunos de número de $a_1 \geq 1$. A continuación, $a_2$ no puede ser un número consecutivo, de manera que la distancia a $a_1$ debe ser mayor que o igual a dos. Similares para$a_3$$a_4$. Entonces yo no sé acerca de $a_{5}$.

Sin embargo: a uno se le pide demostrar que el problema original es equivalente a probar que $a_1 \geq 0$, no $a_1 \geq 1$. Además, no entiendo por qué la $a_{5}$ entra en la escena aquí: debemos encontrar subconjuntos que contienen $4$ elementos, derecho? Podría por favor explicar esto? Además, no entiendo por qué la $(*)$-marcado suma debe ser igual a 14. Por favor podría esto explicar esto así, o darme una pista?

Además, se me pide que demuestran que este número de subconjuntos es igual al coeficiente de $x^{14}$ de la generación de la función $$f(x) = \frac{x^6}{(1-x)^5} .$$ ¿Cómo hace uno para mostrar que? O podría por favor dar una sugerencia?

Answer 1

Imaginemos que hemos escogido $4$ números, no hay dos consecutivos. Lista en orden, como $p,q,r,s$.

Deje $a_1$ el número de enteros en el intervalo de $[1,15]$ que son menos de $p$, y deje $a_5$ el número de enteros en el intervalo que son mayores de $s$. Deje $a_2$ el número de enteros en el intervalo de $(p,q]$. (Por lo que no recuento $p$, pero podemos hacer un recuento $q$.) Deje $a_3$ el número de enteros en el intervalo de $(q,r]$, e $a_4$ el número de enteros en el intervalo de $(r,s]$.

Tenga en cuenta que $a_1\ge 0$, $a_5\ge 0$, y cada una de las $a_2,a_3,a_4$$\ge 2$. Tenga en cuenta también que $a_1+a_2+a_3+a_4+a_5=14$. Para dejar $g_1$ ser la "brecha" hasta el primero de los números enteros, $g_2$ la brecha entre los dos primeros elegido enteros, $g_3$ la brecha entre los dos siguientes, $g_4$ la brecha entre los dos siguientes, y $g_5$ la brecha final. A continuación,$g_1+g_2+g_3+g_4+g_5 +4=15$. Tenemos $g_1=a_1$, $g_5=a_5$, y para los restantes tres $i$ tenemos $g_i=a_i-1$.

Por lo tanto $a_1+(a_2-1)+(a_3-1)+(a_4-1)+a_5+4=15$, dando $a_1+a_2+a_3+a_4+a_5=14$. Es el hecho de que entre nuestros cuatro números de tres lagunas que representa el $14$.

Hemos demostrado que para cada elección de números de $p,q,r,s$, hay números de $a_1,\dots,a_5$ la satisfacción de los dadas las desigualdades, y con suma $14$.

No es difícil de revertir el argumento, y mostrar que cualquier secuencia $a_1,\dots,a_5$ que satisface el dado de las desigualdades y con suma $14$ determina una selección de $p\lt q\lt r\lt s$ no hay dos seguidos.

Answer 2

Deje $1\leq x<y<z<u\leq15$ tal que $y\ne x+1$, $z\ne y+1$ y $u\ne z+1$. A continuación, $\{x,y,z,u\}$ es un subconjunto de a $S$ que contiene exactamente $4$ no consecutivos elementos. Tomando $a_{1}=x-1$, $a_{2}=y-x$, $a_{3}=z-y$, $a_{4}=u-z$ y $a_{5}=15-u$, las condiciones se puede reescribir como $a_{1}\ge0$, $a_{i}\geq2$ para $i=2,3,4$, $a_{5}\geq0$ y $a_{1}+\cdots+a_{5}=14$.

Vamos $a_{1}=b_{1}$, $a_{5}=b_{5}$ y $a_{i}=b_{i}+2$$i=2,3,4$. Bajo la condición de $b_{i}\geq0$ el número de soluciones de $b_{1}+b_{2}+b_{3}+b_{4}+b_{5}=8$ es igual a $\binom{12}{4}$.

Answer 3

El uso de "Estrellas y Barras" para contar.

Podemos representar los cuatro números como una cadena de 4 'bares' y 11 'estrellas', donde la posición de cada uno el bar cuenta un número.

Así, la cadena: "$**|*|***|**|***$" representa: $\{3, 5, 9, 12\}$.

Ya tenemos al menos una de las 'estrellas' entre cada par de 'barras', esto es equivalente a encontrar las permutaciones de 4 barras y las 8 restantes estrellas.

Así que hay $\dbinom{12}{4} = \dfrac{12!}{4!\;8!} = 495$ maneras de hacer esto.

---

El siguiente paso es mostrar que el problema de las cinco variables también pueden ser representados por la misma cadena.