Subconjuntos de $[n]$ del tamaño de la $k$ con exactamente un par de enteros consecutivos.

Question

Espero que no voy a hacer una pregunta que ya ha sido pedido (y contestar).

Tengo que determinar cuántos subconjuntos de $[n]:=\{1,\dots,n\}$ del tamaño de la $k$ contienen exactamente un par de $(i,i+1)$ de los posteriores enteros. He utilizado el siguiente enfoque: vamos a $T=(t_1,\dots,t_n)\subset\{0,1\}^n$ ser una cadena binaria de longitud $n$, la identificación de un subgrupo de tamaño $k$ extraídas de $[n]$, es decir,$\sum_i t_i=k$. Para $T$ para cumplir con las condiciones establecidas anteriormente, debe ser el caso que $T$ contiene $k-2$ no consecutivas y un par de consecutivas.

Para construir dicha secuencia, he utilizado el método de estrellas y barras: en primer lugar, encontrar una secuencia de longitud $k-1$ sin números consecutivos y, a continuación, obtener una secuencia de longitud $k$ con una consecutivos pareja.

1. Lugar $n-k$ ceros consecutivos en una cadena.
2. Hay $n-k+1$ lugares donde: $k-1$ pueden ser colocados de forma que no son consecutivos, por lo tanto, hay $\binom{n-k+1}{k-1}$ secuencias de longitud $n-1$ con $k-1$ que no son consecutivos.
3. Añadir un extra de uno cerca de la anterior. Para cualquier secuencia en la $(2.)$ hay $(k-1)$ posibilidades.

Total, que daría $(k-1)\times\binom{n-k+1}{k-1}$ posibilidades.

¿Esto tiene sentido? Gracias!

Answer 1

Por medio de enriquecimiento aquí es una solución mediante la generación de funciones. Se debe comenzar por seleccionar el primer valor:

$$\frac{z}{1-z}.$$

A continuación, añadimos en $k-1$ lagunas, marcando las lagunas de tamaño de uno (consecutivos los valores):

$$\left(uz+\frac{z^2}{1-z}\right)^{k-1}.$$

Por último tenemos la suma de todas las contribuciones (subconjuntos) que terminan en la mayoría de los $n$:

$$[z^n] \frac{1}{1-z} \times \cdot.$$ Obtenemos la respuesta

$$[z^n] [u^1] \frac{z}{1-z} \left(uz+\frac{z^2}{1-z}\right)^{k-1} \frac{1}{1-z}.$$

El coeficiente de extractor en $u$ asegura que tenemos exactamente un par de elementos consecutivos. Tenemos

$$[z^n] \frac{z}{1-z} \times z {k-1\elegir 1} \left(\frac{z^2}{1-z}\right)^{k-2} \times \frac{1}{1-z}.$$

Este es

$$(k-1) [z^n] \frac{z^{1+1+2k-4}}{(1-z)^k} = (k-1) [z^n] \frac{z^{2k-2}}{(1-z)^k} = (k-1) [z^{n-2k+2}] \frac{1}{(1-z)^k} \\ = (k-1) {n-2k+2+k-1\elegir k-1} = (k-1) {n-k+1\elegir k-1}.$$

Answer 2

Puede ser de interés considerar un método adicional para resolver este tipo de problemas.

Como se muestra en el dibujo, considere la posibilidad de un subconjunto $\left\{ {a_{\,1} ,\,a_{\,2} ,\,\; \cdots \,,a_{\,k} = h} \right\}$ con los requisitos, y cuyo último elemento es igual a $h$.
Vamos a echar hacia atrás delta $\left[ {a_{\,1} - 0,\,a_{\,2} - a_{\,1} ,\,\; \cdots \,,a_{\,k} - a_{\,k - 1} } \right]$ el cual tendrá todos los elementos positivos, de los cuales (excepto, eventualmente, el 1er elemento) sólo uno tendrá valor $=1$ y los otros, deberá ser mayor que el que, de manera consecutiva sumando a $h$.
Vamos a eliminar el elemento con Delta $=1$, nos quedamos con $k-1$ elemento, la 1ª con min. valor $1$ y el restante con min. valor $2$.
Vamos a deducir dichos de un umbral mínimo, y llegamos a obtener una débil composición de $h-2k$ a $k-1$ partes, con $4 \leqslant 2k \leqslant h$. Su número total es conocido por ser $$ \left( \begin{gathered} \left( {h - 2k} \right) + \left( {k - 1} \right) - 1 \\ \left( {k - 1} \right) - 1 \\ \end{reunieron} \right) = \left( \begin{gathered} h - k - 2 \\ k - 2 \\ \end{reunieron} \right)\quad \left| \begin{gathered} \,2 \leqslant k \hfill \\ \;2k \leqslant h \hfill \\ \end{reunieron} \right. $$ Multiplicando por el número de posiciones posibles del elemento eliminado, y sumando más de $h$ tenemos $$ \begin{gathered} \left( {k - 1} \right)\sum\limits_{2k\, \leqslant \,h\, \leqslant \,n} {\left( \begin{gathered} h - k - 2 \\ k - 2 \\ \end{reunieron} \right)} = \left( {k - 1} \right)\left( {\left( \begin{gathered} n + 1 - k - 2 \\ k - 1 \\ \end{reunieron} \right) - \left( \begin{gathered} 2k - k - 2 \\ k - 1 \\ \end{reunieron} \right)} \right) = \hfill \\ = \left( {k - 1} \right)\left( {\left( \begin{gathered} n - k - 1 \\ k - 1 \\ \end{reunieron} \right) - \left( \begin{gathered} k - 2 \\ k - 1 \\ \end{reunieron} \right)} \right)\quad \left| \begin{gathered} \,2 \leqslant k \hfill \\ \;2k \leqslant n \hfill \\ \end{reunieron} \right. = \left( {k - 1} \right)\left( \begin{gathered} n - k - 1 \\ k - 1 \\ \end{reunieron} \right) \hfill \\ \end{se reunieron} $$