Supongamos $n$ es el número de elementos y $k$ el tamaño del subconjunto.
La idea es construir una generación de función por la elección de la
primer elemento de cada subconjunto y, posteriormente, añadiendo una serie de lagunas
entre los valores adyacentes, el marcado de pistas de elementos consecutivos. Utilizamos
$w$ para estas carreras y $u$ a marca de carreras de al menos tres consecutivos
elementos y $z$ para el común de los huecos de tamaño, al menos, dos. También utilizamos
$v$ contar elementos. Tenemos entonces que a partir de primeros principios de la OGF
$$f(z,w,u,v) = \frac{vz}{1-z}\sum_{q\ge 0} \frac{v^q z^{t2}}{(1-z)^p}
\\ \times \left(\sum_{p\ge 0} (vw+uv^2a^2+uv^3^3+uv^4w^4+\cdots)^p
\left(\sum_{q\ge 1} \frac{v^q z^{t2}}{(1-z)^p}\right)^p\right)
\\ \times (1+vw+uv^2a^2+uv^3^3+uv^4w^4+\cdots) + 1.$$
Como una comprobación de validez debemos obtener todos los subconjuntos de
$$\frac{1}{1-z} f(z,z,1,1)$$
(el multiplicador por $1/(1-z)$ suma de las contribuciones de estos subconjuntos
son classifified según el último elemento). Obtenemos
$$\frac{z}{1-z} \sum_{q\ge 0} \frac{z^{t2}}{(1-z)^p}
\\ \times \left(\sum_{p\ge 0} (w+w^2+w^3+w^4+\cdots)^p
\left(\sum_{q\ge 1} \frac{z^{t2}}{(1-z)^p}\right)^p\right)
\\ \times (1+w+w^2+w^3+w^4+\cdots) + 1.$$
Esto se simplifica a
$$\frac{z}{1-z} \frac{1}{1-z^2/(1-z)}
\left(\sum_{p\ge 0} \frac{w^p}{(1-w)^p}
\left(\frac{z^2/(1-z)}{1-z^2/(1-z)}\right)^p\right)
\frac{1}{1-w} + 1
\\ = \frac{z}{1-z-z^2}
\frac{1}{1-wz^2/(1-z)/(1-w)/(1-z^2/(1-z))}
\frac{1}{1-w} + 1
\\ = \frac{z}{1-z-z^2}
\frac{1}{1-wz^2/(1-w)/(1-z-z^2)}
\frac{1}{1-w} + 1
\\ = z
\frac{1}{1-z-z^2-wz^2/(1-w)}
\frac{1}{1-w} + 1
= z \frac{1}{(1-z-z^2)(1-w)-wz^2} + 1.$$
Para concluir ponemos $w=z$ y obtener
$a$z \frac{1}{(1-z-z^2)(1-z)-z^3} + 1
= z \frac{1}{1-z-z^2-z+z^2+z^3-z^3} + 1
\\ = z \frac{1}{1-2z} + 1 = \frac{1-z}{1-2z}.$$
Vemos que en la multiplicación por $1/(1-z)$ obtenemos
$$\bbox[5px,border:2px solid #00A000]{\frac{1}{1-2z}.}$$
Hay $2^n$ subconjuntos y la comprobación de validez.
Ahora para eliminar los subconjuntos que contienen tres elementos que
calcular
$$\frac{1}{1-z} f(z,z,0,v)$$
que los rendimientos de
$$\frac{vz}{1-z}\sum_{q\ge 0} \frac{v^q z^{t2}}{(1-z)^p}
\\ \times \left(\sum_{p\ge 0} v^p w^p
\left(\sum_{q\ge 1} \frac{v^q z^{t2}}{(1-z)^p}\right)^p\right)
\\ \times (1+vw) + 1$$
que es
$$\frac{vz}{1-z} \frac{1}{1-vz^2/(1-z)}
\times \left(\sum_{p\ge 0} v^p w^p
\left(\frac{vz^2/(1-z)}{1-vz^2/(1-z)}\right)^p\right)
\times (1+vw) + 1
\\ = \frac{vz}{1-z} \frac{1}{1-vz^2/(1-z)}
\times \left(
\frac{1}{1-v^2wz^2/(1-z)/(1-vz^2/(1-z))}\right)
\\ \times (1+vw) + 1
\\ = \frac{vz(1+vw)}{(1-z)(1-vz^2/(1-z)) - v^2wz^2} + 1
\\ = \frac{vz(1+vw)}{1-z-vz^2 - v^2wz^2} + 1.$$
En la sustitución de $w$ $z$ y multiplicando por $1/(1-z)$así tenemos
$$\frac{1}{1-z}\frac{vz+v^2z^2}{1-z-vz^2 - v^2z^3} + \frac{1}{1-z}.$$
El segundo término sólo contribuye para$k=0$, mientras que el primero no
contribuir al $k=0.$ Esto significa que hay un subconjunto de elementos cero
no contienen tres elementos, a saber, el conjunto vacío, y
esto es obviamente cierto.
Simplificando podemos encontrar
$$\frac{1}{1-z}\frac{vz+v^2z^2-(1-z)/z}{1-z-vz^2 - v^2z^3}
+ \frac{1}{z} \frac{1}{1-z-vz^2 - v^2z^3}
+ \frac{1}{1-z}
\\ = \left(1-\frac{1}{z}\right)\frac{1}{1-z}
+ \frac{1}{z} \frac{1}{1-z-vz^2 - v^2z^3}
\\ = -\frac{1}{z} + \frac{1}{z}
\frac{1}{1-z-vz^2 - v^2z^3}
\\ = -\frac{1}{z} + \frac{1}{z} \frac{1}{1-z}
\frac{1}{1-vz^2/(1-z) - v^2z^3/(1-z)}.$$
Observar que
$$[v^k] \frac{1}{1-vz^2/(1-z) - v^2z^3/(1-z)}
= \sum_{q=0}^k [v^k] \frac{v^q z^{t2}}{(1-z)^p} (1+vz)^q
\\ = \sum_{q=0}^k \frac{z^{t2}}{(1-z)^p} [v^{k-q}] (1+vz)^q
= \sum_{q=0}^k {q\elegir k-q} \frac{z^{t2}}{(1-z)^p} z^{k-q}
\\ = \sum_{q=0}^k {q\elegir k-q} \frac{z^{k+p}}{(1-z)^p}.$$
El coeficiente de extracción en $z$ ahora procede de la siguiente manera:
$$[z^n] \frac{1}{z}\frac{1}{1-z}
\sum_{q=0}^k {q\elegir k-q} \frac{z^{k+p}}{(1-z)^p}
= [z^{n+1}] \sum_{q=0}^k {q\elegir k-q}
\frac{z^{k+p}}{(1-z)^{q+1}}
\\ = \sum_{q=0}^k {q\elegir k-q}
[z^{n+1-k-q}] \frac{1}{(1-z)^{q+1}}.$$
Tenemos la forma cerrada que es
$$\bbox[5px,border:2px solid #00A000]{
\sum_{q=0}^k {q\elegir k-q} {n+1-k\elegir q}.}$$
Listado de estos valores en forma triangular encontramos
$$1, 1, 1, 1, 2, 1, 1, 3, 3, 0, 1, 4, 6, 2, 0, 1, 5, 10, 7, 1,
\\ 0, 1, 6, 15, 16, 6, 0, 0, 1, 7, 21, 30, 19, 3, 0, 0, 1,
\\ 8, 28, 50, 45, 16, 1, 0, 0, \ldots$$
que nos señala OEIS A078802 donde el
análisis anterior es confirmado.
El cálculo anterior fue apoyado por los siguientes Arce código.
con(planta);
ENUM :=
proc(n, k)
opción de recordar;
lista local, pos, res;
si k < 3, a continuación, volver binomial(n,k) fi;
res := 0;
para la lista en elegir(n, k) ¿
pos k-2 do
si la lista[pos] + 1 = lista[pos + 1] y
lista[pos + 1] + 1 = lista[pos+2] luego
break;
fi;
od;
si pos = k-1, entonces
res := res + 1;
fi;
od;
res;
end;
X1 := (n, k) ->
coeftayl(coeftayl(-1/z+1/z*1/(1-z-v*z^2-v^2*z^3),
v=0, k), z=0, n);
X2 := (n, k) ->
agregar(binomial(p,k-q)*binomial(n+1-k,p), q=0..k);
En particular, para subconjuntos de veinte elementos de un conjunto que contiene el
entero rango de uno a treinta el número de subconjuntos sin tres
consecutivos elementos es
$$\bbox[5px,border:2px solid #00A000]{66.}$$
