En esencia, cómo de muchas maneras se puede elegir un subconjunto de N personas que hay 3 personas en el subconjunto que son adyacentes en el conjunto original.
por ejemplo, N = 4 Permite etiquetar a la gente {1,2,3,4} Puedo elegir {1,2,3} , {2,3,4} , { 1,2,3,4} lo que hace un total de 3 maneras.
Aquí supongo que {1,2,3} = {3,2,1} etc. son los mismos
¿Hay alguna fórmula general que pueda derivar para el cálculo de este?
Vamos a llamar al número de formas de seleccionar un subconjunto de N personas que hay 3 personas en el subconjunto que son adyacentes en la serie original como $a_n$. Llame a tales subconjuntos buena.
Vamos a intentar encontrar una periodicidad de $a_n$.
Ahora, tomemos cualquier subconjunto de a $N-1$ de la gente, y considerar la posibilidad de que el conjunto de con $N$ en él y no en ti. Claramente, ambos son distintos buena subconjuntos. Así que, esto equivale a $2 a_{n-1}$ maneras.
Así, los elementos que aún no han considerado $N$ en el tresillo, y de hecho el triplete $N-2, N-1,N$ debe ser el único dentro del subconjunto, de lo contrario, se ha calculado antes. Así que, esto equivale a $2^{n-4} - a_{n-4}$ formas, como necesitamos el número de subconjuntos de a $N-4$ personas que no tienen cualquier triplete (tenga en cuenta que el elemento $N-3$ no puede estar en el conjunto).
Así, obtenemos la recurrencia como $$a_{n} = 2a_{n-1} + 2^{n-4} - a_{n-4}$$ with initial conditions as $a_1=a_2=0, a_3=1, a_4=3$.
En lo que respecta a una fórmula general, el uso de OEIS lleva a esto que nos dice que la función es la generación de $$G(x) = \frac{x^3}{(1-2x)(1-x-x^2-x^3)}$$ and also gives a nicer looking recurrence: $$a_n = 3a_{n-1} - a_{n-2} - a_{n-3} - 2a_{n-4}$$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
