Matemáticas | PnC y Coeficientes Binomiales

Requisito previo: conceptos básicos de combinatoria

Varios problemas de conteo requieren encontrar la cantidad de formas de organizar una cierta cantidad de elementos distintos, donde el orden relativo de estos elementos importa, otros problemas se enfocan en encontrar la cantidad de formas de seleccionar una cantidad particular de elementos de un conjunto, donde el orden de los elementos no importa. Ambos tipos de problemas son similares excepto por una diferencia crucial, esa diferencia es el orden .

permutacion –

Una permutación de un conjunto de objetos distintos es un arreglo ordenado de estos objetos. Una permutación a menudo también se conoce como un arreglo. El orden relativo de los elementos importa en un arreglo.
Una disposición ordenada de los $r$ elementos de un conjunto se denomina permutación r . Se representa como $P(n,r)$ .
para $1\leq r\leq n$ ,

$\begin{flalign*} P(n,r) &= n * (n-1) * ... * (n-r+1)\\ &= \frac{n * (n-1) * ... * (n-r+1) * (n-r) *...* 2 * 1}{(n-r) * (n-r-1) * .... * 2 * 1}\\ &= \frac{n!}{(n-r)!} \end{flalign*}$

La fórmula anterior para $P(n,r)$ es una aplicación simple de la regla del producto .

Ejemplo 1: ¿Cuántas permutaciones de la string «ABCDEFGH» tienen la string «ABC» como substring?
Solución: para que «ABC» sea una substring, las letras A, B y C deben aparecer como un bloque. Si consideramos ese bloque y las 5 letras restantes como objetos, tenemos un total de 6 objetos para ordenar.
Por lo tanto, el número de strings que tienen «ABC» como su substring = 6. = 720.
Ejemplo 2: encuentre el número de permutaciones de la palabra «CIVILIZACIÓN».
Solución: la palabra civilización tiene la siguiente frecuencia de caracteres
: ‘C’ – 1
‘I’ – 4
‘V’ – 1
‘L’ – 1
‘Z’ – 1
‘A’ – 1
‘T’ – 1
‘O’ – 1
‘N’ – 1
Si todos los caracteres fueran distintos, el número de permutaciones sería $P(n,n) = n!$ donde $n$ = 12. Pero como la letra ‘I’ se repite 4 veces, el número de permutaciones es menor. Esto se debe a que la permutación como un todo no cambia si los ‘yoes’ están dispuestos entre sí. Entonces, para corregir el número de permutaciones, dividimos el total de permutaciones por $P(r,r)$ donde $r$ es el número de veces que se repite una letra u objeto.
Número total de arreglos = $\frac{P(12,12)}{P(4,4)} = \frac{12!}{4!} = 19958400$

Combinación –

Una combinación de un conjunto de objetos distintos es solo un recuento de la cantidad de formas en que se puede seleccionar una cantidad específica de elementos de un conjunto de cierto tamaño. El orden de los elementos no importa en una combinación.
Una selección desordenada de $r$ elementos de un conjunto se llama combinación r . Se representa como $C(n,r)$ y $\binom{n}{r}$ .
Dado que una combinación es solo una permutación sin orden, el número de $r$ combinaciones se puede expresar en términos de $r$ permutación.
La $r$ permutación se puede obtener obteniendo primero la $r$ combinación y luego ordenando los elementos en cada $r$ combinación, lo que se puede hacer de varias $P(r, r)$ maneras.
$\therefore P(n,r) = C(n,r) * P(r,r)\\$
que nos da-

$\begin{flalign*} C(n,r) &= \frac{P(n,r)}{P(r,r)}\\ &= \frac{n!}{(n-r)!} * \frac{1}{r!}\\ &= \frac{n!}{r!(n-r)!}& \end{flalign*}$

Ejemplo 1: determine la cantidad de formas en que se pueden elegir 5 cartas de una baraja de 52 cartas, de modo que haya exactamente un as.
Solución: de los 4 ases, uno puede elegirse de $\binom{4}{1} = 4$ maneras.
Las 4 cartas restantes deben elegirse de las 48 cartas restantes. El número de formas de elegir estas 4 cartas es $\binom{48}{4} = 194580$ .
Número total de formas de elegir 5 cartas por regla de producto = $\binom{4}{1} * \binom{48}{4}$ = 4 * 194580 = 778320.
Ejemplo 2: un polígono tiene 44 diagonales. Halla el número de sus lados.
Solución: una diagonal es una línea que conecta dos vértices no adyacentes. Si $n$ es el número de vértices, entonces el número de pares de vértices no adyacentes = $\binom{n}{2} - n$ . $n$ se resta ya que hay $n$ lados.
Por lo tanto número de diagonales = número de vértices no adyacentes
$\frac{n(n-1)}{2} - n = 44$
Al resolver obtenemos $n$ = 11.

Coeficientes Binomiales –

Las $r$ combinaciones de un conjunto de $n$ elementos si se denotan por $\binom{n}{r}$ . Este número también se llama coeficiente binomial ya que aparece como un coeficiente en la expansión de potencias de expresiones binomiales.
El teorema del binomio da una potencia de una expresión binomial como una suma de términos que involucran coeficientes binomiales.

Formalmente,
sean $x$ y $y$ sean variables y $n$ sean un entero no negativo. Después

$\begin{flalign*} (x+y)^n &= \sum_{j=0}^{n} \binom{n}{j} x^{n-j}y^j\\ &= \binom{n}{0}x^{n} + \binom{n}{1}x^{n-1}y +...+ \binom{n}{n-1}xy^{n-1} + \binom{n}{n}y^{n} \end{flalign*}$

Ejemplo 1 – ¿Cuál es el coeficiente de $x^{12}y^{13}$ en la expansión de $(2x-3y)^{25}$ ?
Solución – $(2x-3y)^{25} = (2x+(-3y))^{25}$ .
Por el teorema del binomio-
$(2x+(-3y))^{25} = \sum_{j=0}^{25}\binom{25}{j}(2x)^{25-j}(-3y)^j$
Como la potencia de $y$ es 13, $j = 13$ .
Por lo tanto el coeficiente de $x^{12}y^{13}$ es-
$\binom{25}{13}2^{12}(-3)^{13} = - \frac{25!}{13!12!}2^{12}3^{13}$
Ejemplo 2: Demuestre que $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ .
Solución – Si ponemos $x = 1$ y $y = 1$ en la expresión del teorema binomial, obtenemos-
$\\ (1 + 1)^n = \sum_{k=0}^{n}\binom{n}{k} 1^{n-k} 1^{k} = \sum_{k=0}^{n}\binom{n}{k}\\$
$2^n = (1 + 1)^n = \sum_{k=0}^{n}\binom{n}{k}$
Ejemplo 3: Demuestre que $\sum_{k=0}^{n} (-1)^{k}\binom{n}{k} = 0$ .
Solución – Si ponemos $x = -1$ y $y = 1$ en la expresión del teorema binomial, obtenemos-
$\\ ((-1) + 1)^n = \sum_{k=0}^{n}\binom{n}{k} (-1)^{n-k} 1^{k} = \sum_{k=0}^{n} (-1)^{k} \binom{n}{k}\\$
$0 = 0^n = ((-1) + 1)^n = \sum_{k=0}^{n} (-1)^{k} \binom{n}{k}$
Ejemplo 4: Demuestre que $\sum_{k=0}^{n} (2)^{k}\binom{n}{k} = 3^n$ .
Solución – Si ponemos $x = 1$ y $y = 2$ en la expresión del teorema binomial, obtenemos-
$\\ (1 + 2)^n = \sum_{k=0}^{n}\binom{n}{k} (1)^{n-k} 2^{k} = \sum_{k=0}^{n} 2^{k} \binom{n}{k}\\$
$3^n = (1 + 2)^n = \sum_{k=0}^{n} 2^{k} \binom{n}{k}$

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.

Las preguntas 1 y 2 están relacionadas.
1. GATE CS 2007, Pregunta 84
2. GATE CS 2007, Pregunta 85
3. GATE CS 2003, Pregunta 4
4. GATE CS 2003, Pregunta 5

Referencias-

Matemáticas discretas y sus aplicaciones, por Kenneth H Rosen

Este artículo es una contribución de Chirag Manwani . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

permutacion –

Combinación –

Coeficientes Binomiales –

Deja una respuesta Cancelar la respuesta