Fórmulas Fundamentales de Combinatoria, Sucesiones y Relaciones de Recurrencia

Fundamentos de Combinatoria, Sucesiones y Recurrencias

Fórmulas Esenciales de Conteo (Combinatoria)

La combinatoria estudia las formas de contar colecciones de objetos. A continuación, se presentan las fórmulas fundamentales:

Permutaciones

• Permutación de orden n (sin repetición): El número de ordenamientos de n elementos distintos.

  Pn = n!

• Permutación con elementos indistinguibles (distintas): El número de ordenamientos que pueden formarse a partir de una colección de n objetos donde el objeto 1 aparece $k_1$ veces, el objeto 2 aparece $k_2$ veces, y así sucesivamente.

  n! / (k1! · k2! · ...)

• Permutación simple de r elementos tomados de n: Una secuencia (lista ordenada) formada por r elementos distintos seleccionados de un conjunto $A$ de tamaño $n$ ($1 \le r \le n$).

  nPr = n! / (n - r)!

• Permutación con repetición: Sea $A$ un conjunto tal que $|A|=n$ y $r \in \mathbb{Z}^+$, $r \ge 2$. El número de secuencias distintas de longitud $r$ que pueden formarse con los elementos de $A$ es:

  nr

Combinaciones

• Combinación de r elementos tomados de n: Dado un conjunto $A$ tal que $|A|=n$ y $r \in \mathbb{Z}^+$, $1 \le r \le n$. Es el número de subconjuntos de $r$ elementos de $A$.

  nCr = n! / (r! · (n - r)!)

Conceptos Clave de Sucesiones

Una sucesión es una lista ordenada de objetos dispuestos en un orden determinado (puede ser infinita o finita).

Formas de Definición de Sucesiones

• Forma Recursiva: Permite obtener cada término de la sucesión en función de uno o más elementos anteriores a él. Requiere especificar el primer término (o términos iniciales).
• Forma Explícita: Se expresa un término genérico de la sucesión únicamente en función de su posición en la lista.

Conceptos Relacionados

• Conjunto Correspondiente a una Sucesión: El conjunto de elementos distintos de la sucesión.
• Conjunto Numerable: Puede ser finito numerable, infinito numerable (ej. $\mathbb{N}$, $\mathbb{Z}$), o infinito no numerable (ej. $\mathbb{R}$).
• Cadena (String): Una sucesión de letras o símbolos. Si $A$ es el alfabeto (conjunto de símbolos o letras), $A^*$ es el lenguaje generado por $A$. Una palabra o cadena es un elemento de $A^*$. La cadena vacía se denota como $\Lambda \in A^*$.
• Concatenación de Cadenas: Sean $w_1$ y $w_2$ elementos de $A^*$. La concatenación $w_1 \circ w_2$ es la unión de ambas. Si $w \in A^*$, entonces $w \circ \Lambda = \Lambda \circ w = w$.
• Arreglo (Array): Una sucesión de posiciones que pueden contener cualquier elemento de un conjunto determinado $U$.

Función Característica de Conjuntos

Sea $A$ un subconjunto de un conjunto universal $U$. La función característica $f_A$ es una función que indica si un elemento $x \in U$ pertenece o no al subconjunto $A$.

fA: U → {1, 0}

Donde:

• fA(x) = 1 si $x \in A$.
• fA(x) = 0 si $x \notin A$.

Propiedades de la Función Característica

• Intersección: fA ∩ B(x) = fA(x) · fB(x)
• Unión: fA ∪ B(x) = fA(x) + fB(x) - fA(x) · fB(x)
• Diferencia Simétrica: fA Δ B(x) = fA(x) + fB(x) - 2 · fA(x) · fB(x)

Relaciones de Recurrencia

Para la sucesión $a_n$ donde $n \in \mathbb{Z}^+$, una relación de recurrencia es una ecuación que determina el término $a_n$ en función de otros términos anteriores. Esta es la forma recursiva. Resolver la relación implica encontrar la forma explícita de $a_n$.

Método de la Ecuación Característica (RRLH Grado 2)

Aplicable a Relaciones de Recurrencia Lineales Homogéneas (RRLH) de grado 2:

an = r1 · an-1 + r2 · an-2

La ecuación característica asociada es:

x2 - r1x - r2 = 0

Caso de Raíces Distintas ($s_1 \neq s_2$)

La solución explícita es de la forma:

an = u · s1n + v · s2n

Los coeficientes $u$ y $v$ se determinan resolviendo un sistema de ecuaciones basado en las condiciones iniciales.

Caso de Raíces Iguales ($s_1 = s_2 = s$)

La solución explícita es de la forma:

an = u · sn + v · n · sn

Método de Iteración (Hacia Atrás)

Este método se utiliza para encontrar la forma explícita mediante sustitución sucesiva.

Ejemplo: Resolver $a_n = 2 a_{n-1}$ para $n \ge 1$.

Al aplicar el método de sustitución hacia atrás, se observa la relación entre el exponente y el número de pasos:

1. $a_n = 2 a_{n-1}$
2. $a_n = 2 (2 a_{n-2}) = 2^2 a_{n-2}$
3. ...

Se infiere que, para llegar al término inicial $a_1$, se requieren $n-1$ pasos.

La forma explícita es:

an = 2n-1 · an-(n-1) = 2n-1 · a1, para $n \ge 1$.