Número de vectores cuyo inicio es diferente de su final

Question

Considerar todos los $n$-dimensiones de los vectores $v$ con elementos de $\{0,1\}$. Podemos decir que si existe un $n > j \geq 1$ tal que $v_{1,\dots,j} = v_{n-j+1,\dots, n}$, entonces el vector es "malo". De lo contrario, el vector es "buena". Por ejemplo, $v^{T} = (0,1,0,0,1)$ es mala y $(0,1,1,1)$ es bueno.

Cuántos buenos son vectores de longitud $n$?

Answer 1

Este es un problema que utiliza el principio de inclusión exclusión (ver página 223 de Stanley CE1, disponible de forma gratuita en su sitio web). Deje $f_=(0)$ denotar el número de vectores de longitud $n$, y deje $f_\geq(j)$ denotar el número de vectores cuya primera $j$ elementos que coincida con su último $j$ elementos. Luego, por el Principio de Inclusión Exclusión: $$f_=(0) = \sum\limits_{j = 0}^{\lfloor n/2 \rfloor} (-1)^j f_\geq(j).$$

Por lo tanto, sólo necesitan encontrar el $f_{\geq}(j)$. Si la primera $j$ coincide con el último $j$ elementos, entonces tenemos $2^j$ opciones para los elementos coincidentes, y $2^{n - 2j}$ para la media de los elementos. Por lo tanto tenemos a $f_{\geq}(j) = 2^{n - j}$. Poner esto juntos, tenemos $$\begin{align*} f_=(0) &= \sum\limits_{j = 0}^{\lfloor n/2 \rfloor} (-1)^j f_\geq(j) \\ &= \sum\limits_{j = 0}^{\lfloor n/2 \rfloor} (-1)^j 2^{n - j} \\ &= 2^n \sum\limits_{j = 0}^{\lfloor n/2 \rfloor} \left(-\frac{1}{2} \right)^j \\ &= 2^n \frac{1 - \left(-\frac{1}{2}\right)^{\lfloor n/2 \rfloor + 1} }{1 - \left(-\frac{1}{2}\right)} \\ &= \frac{2}{3}\cdot 2^{n}\left(1 + \left(-\frac{1}{2}\right)^{\lfloor n/2 \rfloor} \right). \end{align*}$$

Como $n$ se hace grande, tenemos aproximadamente el $\frac{2}{3} 2^n$ buena vectores.