Subconjuntos con 3 términos consecutivos

Question

Considere el siguiente conjunto: $$\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$$

Quiero calcular cuántos subconjuntos de longitud $6$ no tienen tres mandatos consecutivos.

Mi idea era hacer:

longitud 6 no tienen términos consecutivos = longitud total $6$ - longitud $6$ tener tres (o más) mandatos consecutivos

que pensaba que era

$${10\choose 6} - 8 {7\choose 3}.$$

Sin embargo, se trata de una cifra negativa. ¿Alguna idea?

Answer 1

Alinee 4 palos en una fila, representando los números no elegidos, y represente los 6 números elegidos con puntos.

Los palos crean 5 huecos, por lo que si $x_i$ es el número de puntos en el hueco $i$ ,

$\hspace{.3 in}$ tenemos $x_1+\cdots+x_5=6$ con $x_i<3$ para cada $i$ .

Utilizando la inclusión-exclusión, si $S$ es el conjunto de todas las soluciones y $E_i$ es el conjunto de soluciones con $x_i\ge3$ ,

el número de soluciones viene dado por

$\displaystyle\big|\overline{E_1}\cap\cdots\cap\overline{E_5}\big|=\big|S\big|-\sum_{i}\big|E_i\big|+\sum_{i<j}\big|E_i\cap E_j\big|=\binom{10}{4}-\binom{5}{1}\binom{7}{4}+\binom{5}{2}\binom{4}{4}=\color{red}{45}$ .

Answer 2

Utilizando el método de las estrellas y las barras En este caso, las estrellas representan los números elegidos y las barras los no elegidos.

Un ejemplo de configuración sería así:

$|\star\star\star|\star||\star\star$

que correspondería a $(2,3,4,6,9,10)$ .

La regla es que sólo puede haber como máximo 2 estrellas entre cada dos barras.

Lo que significa que, en los 5 espacios producidos por las 4 barras, hay números del 0 al 2 que suman 6.

Utilizando la fuerza bruta:

• 0+0+2+2+2 = 6 (correspondiente a $\binom52$ = 10 casos)
• 0+1+1+2+2 = 6 (correspondiente a $\binom52\binom32$ = 30 casos)
• 1+1+1+1+2 = 6 (correspondiente a $\binom51$ = 5 casos)

Sumando 45 casos.

---

Edición: He probado la fuerza bruta en otros ejemplos, y he encontrado que corresponde a A027907 que se llama:

"Triángulo irregular de coeficientes trinómicos T(n,k) (n >= 0, 0<=k<=2n), leído por filas (la fila n se obtiene expandiendo (1+x+x^2)^n)".

Se convierte en filas:

  1
  1   1   1
  1   2   3   2   1
  1   3   6   7   6   3   1
  1   4  10  16  19  16  10   4   1
  1   5  15  30  45  51  45  30  15   5   1
  1   6  21  50  90  26 141 126  90  50  21   6   1
  1   7  28  77 161 266 357 393 357 266 161  77  28   7   1
  1   8  36 112 266

Utilizando el hecho de que se obtiene expandiendo $(1+x+x^2)^n$ podemos derivar $T(n+1,k)=T(n,k)+T(n,k-1)+T(n,k-2)$ .

Por lo tanto, fila completa $8$ (contando con que la primera fila sea la fila $0$ ):

   1
   1    1    1
   1    2    3    2    1
   1    3    6    7    6    3    1
   1    4   10   16   19   16   10    4    1
   1    5   15   30   45   51   45   30   15    5    1
   1    6   21   50   90  126  141  126   90   50   21    6    1
   1    7   28   77  161  266  357  393  357  266  161   77   28    7    1
   1    8   36  112  266  504  784 1016 1107 1016  784  504  266  112   36    8    1

Además, hay que tener en cuenta que nuestra respuesta $45$ está en la fila $5$ y $45=T(5,6)$ .

En general, en un conjunto de $n$ números consecutivos, para encontrar el número de subconjuntos de longitud $d$ que no contenga tres términos consecutivos, basta con encontrar $T(n-d+1,d)$ .