Matemáticas/Combinatoria/Texto completo

• Sumatoria
• Factorial
• Binomio de Newton
• Permutación
• Combinación
• Triángulo de Pascal

Sección 1: Sumatoria

Letra sigma mayúscula, notación del sumatorio.

El sumatorioo sumatoria (también conocido como operación de suma, notación sigma o símbolo suma), es una notación matemática que permite representar sumas de muchos sumandos, n o incluso infinitos sumandos, evitando el empleo de los puntos suspensivos o de una explícita notación de paso al límite. Se expresa con la letra griega sigma mayúscula ($\Sigma$ , Σ).

Notación

La notación se expresa con la letra griega sigma mayúscula Σ de la siguiente manera:

Definición. $\sum _{i=m}^{n}a_{i}=a_{m}+a_{m+1}+a_{m+2}+\cdots +a_{n}$

Esto se lee: «sumatorio sobre i, desde m hasta n, de a sub-i». La variable i es el índice de suma al que se le asigna un valor inicial llamado límite inferior, m. La variable i recorrerá los valores enteros hasta alcanzar el límite superior, n. Necesariamente debe cumplirse que:

$m\leq n$

Pudiendo ver además que si m = n entonces:

$m=n\;,\quad \sum _{i=m}^{n}a_{i}=\sum _{i=m}^{m}a_{i}=a_{m}$

Si m es mayor que n, el resultado es el elemento neutro de la suma, es cero:

$m>n\;,\quad \sum _{i=m}^{n}a_{i}=0$

Como el conjunto de índices es un intervalo de enteros, es corriente indicar el primer índice debajo del símbolo de sumatoria, y el último por encima del mismo. Las siguientes notaciones son equivalentes

$\sum _{i\in [[m,n]]}{a_{i}}=\sum _{i=m}^{i=n}{a_{i}}=\sum _{i=m}^{n}{a_{i}}.$

El número de términos a sumar es entonces $n-m+1$, ya que el primer sumando es $a_{m}$ y el último sumando es $a_{n}$.

La suma de los cuadrados de los seis primeros enteros estrictamente positivos se escribe por ejemplo

$\sum _{i=1}^{6}{i^{2}}=1^{2}+2^{2}+3^{2}+4^{2}+5^{2}+6^{2}=91.$

La conmutatividad y la asociatividad de la adición, hacen que el resultado de una serie (finita) de adiciones, no dependa del orden en el cual los términos son considerados. La suma de una familia finita de elementos $(a_{i})$ indexada por un conjunto $I$ (no necesariamente ordenado) se indica entonces $\sum _{i\in I}{a_{i}}$.

Cuando la familia considerada es un conjunto finito $A$, la correspondiente suma también puede escribirse

$\sum _{x\in A}{x}=\sum A,$

La suma vacía convencionalmente es considerada igual a cero, entre otras cosas a fin de satisfacer la igualdad

$\sum {A\cup B}=\sum A+\sum B-\sum {A\cap B}.$

La notación de Einstein simplemente omite la escritura del símbolo de suma, ya que si un índice aparece sin definición, se sobreentiende que lo que se representa es la suma de los elementos al variar el índice.

Se debe notar que aunque el término sumatorio se refiere a un operador matemático útil para expresar cierto tipo de suma, no sustituye este término a la palabra suma. Se dice: «la suma de dos y tres es cinco», y no «el sumatorio de dos y tres es cinco». Por la misma razón, decir que se realizará, por ejemplo, el sumatorio de unos votos, es notoriamente un disparate.

Los operadores de suma son útiles para expresar sumas de forma analítica; esto es, representar todos y cada uno de los sumandos en forma general mediante el «i-ésimo» sumando. Así, para representar la fórmula para hallar la media aritmética de n números, se tiene la siguiente expresión:

${\overline {x}}={\frac {\displaystyle \sum _{i=1}^{n}x_{i}}{n}}$

Suma de una serie

Si $(a_{n})$ es un elemento de una serie, la suma total de los elementos de esta, es el límite de las sumas parciales (si es que este límite existe) $\sum _{n=0}^{\infty }a_{n}=\lim _{N\rightarrow +\infty }\sum _{n=0}^{N}a_{n}$.

Identidades

Hay fórmulas para calcular los sumatorios más rápido. Por ejemplo, para sumar los primeros mil números naturales no tiene mucho sentido sumar número por número, y se puede usar una fórmula como esta:

$\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$

$\sum _{i=1}^{1000}i={\frac {1000\;(1000+1)}{2}}=500\;500$

Algunas propiedades de la operación de suma

$\sum _{n=s}^{t}C\cdot f(n)=C\cdot \sum _{n=s}^{t}f(n)$, donde C es una constante

$\sum _{n=s}^{t}f(n)+\sum _{n=s}^{t}g(n)=\sum _{n=s}^{t}\left[f(n)+g(n)\right]$

$\sum _{n=s}^{t}f(n)-\sum _{n=s}^{t}g(n)=\sum _{n=s}^{t}\left[f(n)-g(n)\right]$

$\sum _{n=s}^{t}f(n)=\sum _{n=s+p}^{t+p}f(n-p)$

$\sum _{n=s}^{j}f(n)+\sum _{n=j+1}^{t}f(n)=\sum _{n=s}^{t}f(n)$

$\sum _{n\in A}f(n)=\sum _{n\in \sigma (A)}f(n)$, para un conjunto finito A (Donde σ es una permutación de A).

$\sum _{i=k_{0}}^{k_{1}}\sum _{j=l_{0}}^{l_{1}}a_{i,j}=\sum _{j=l_{0}}^{l_{1}}\sum _{i=k_{0}}^{k_{1}}a_{i,j}$

$\sum _{n=0}^{t}f(2n)+\sum _{n=0}^{t}f(2n+1)=\sum _{n=0}^{2t+1}f(n)$

$\sum _{n=0}^{t}\sum _{i=0}^{z-1}f(z\cdot n+i)=\sum _{n=0}^{z\cdot t+z-1}f(n)$

$\sum _{n=s}^{t}\ln f(n)=\ln \prod _{n=s}^{t}f(n)$

$c^{\left[\sum _{n=s}^{t}f(n)\right]}=\prod _{n=s}^{t}c^{f(n)}$

Algunas sumas de expresiones polinómicas

$\sum _{i=m}^{n}C=C\cdot (n-m+1)$ donde $C$ representa una constante

$\sum _{i=1}^{n}{\frac {1}{i}}=H_{n}$ (ver número armónico)

$\sum _{i=1}^{n}{\frac {1}{i^{k}}}=H_{n}^{k}$ (ver número armónico generalizado)

$\sum _{i=m}^{n}i={\frac {n(n+1)}{2}}-{\frac {m(m-1)}{2}}={\frac {(n+1-m)(n+m)}{2}}$ (ver progresión aritmética)

$\sum _{i=0}^{n}i=\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$ (caso especial de progresión aritmética)

$\sum _{i=0}^{n}i^{2}={\frac {n(n+1)(2n+1)}{6}}={\frac {n^{3}}{3}}+{\frac {n^{2}}{2}}+{\frac {n}{6}}$ (ver número piramidal cuadrado)

$\sum _{i=0}^{n}i^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}={\frac {n^{4}}{4}}+{\frac {n^{3}}{2}}+{\frac {n^{2}}{4}}=\left[\sum _{i=1}^{n}i\right]^{2}$

$\sum _{i=0}^{n}i^{4}={\frac {n(n+1)(2n+1)(3n^{2}+3n-1)}{30}}={\frac {n^{5}}{5}}+{\frac {n^{4}}{2}}+{\frac {n^{3}}{3}}-{\frac {n}{30}}$

$\sum _{i=0}^{n}i^{p}={\frac {(n+1)^{p+1}}{p+1}}+\sum _{k=1}^{p}{\frac {B_{k}}{p-k+1}}{p \choose k}(n+1)^{p-k+1},$ donde $B_{k}$ denota un número de Bernoulli (ver fórmula de Faulhaber).

Las siguientes fórmulas son manipulaciones de

$\sum _{i=0}^{n}i^{3}=\left(\sum _{i=0}^{n}i\right)^{2}$

generalizadas para que la serie comience en cualquier número natural (i.e., $m\in \mathbb {N}$ ):

$\left(\sum _{i=m}^{n}i\right)^{2}=\sum _{i=m}^{n}(i^{3}-im(m-1))$

$\sum _{i=m}^{n}i^{3}=\left(\sum _{i=m}^{n}i\right)^{2}+m(m-1)\sum _{i=m}^{n}i$

Algunas sumas que contienen términos exponenciales

En los sumatorios siguientes a es una constante no igual a 1

$\sum _{i=m}^{n-1}a^{i}={\frac {a^{m}-a^{n}}{1-a}}$ (m < n; ver serie geométrica)

$\sum _{i=0}^{n-1}a^{i}={\frac {1-a^{n}}{1-a}}$

$\sum _{i=0}^{n-1}ia^{i}={\frac {a-na^{n}+(n-1)a^{n+1}}{(1-a)^{2}}}$

$\sum _{i=0}^{n-1}i2^{i}=2+(n-2)2^{n}$ (caso especial cuando a = 2)

$\sum _{i=0}^{n-1}{\frac {i}{2^{i}}}=2-{\frac {n+1}{2^{n-1}}}$ (caso especial cuando a = 1/2)

Algunas sumas que contienen coeficientes binomiales y factoriales

$\sum _{i=0}^{n}{n \choose i}=2^{n}$

$\sum _{i=1}^{n}i{n \choose i}=n2^{n-1}$

$\sum _{i=0}^{n}i!\cdot {n \choose i}=\sum _{i=0}^{n}{}_{n}P_{i}=\lfloor n!\cdot e\rfloor$

$\sum _{i=0}^{n-1}{i \choose k}={n \choose k+1}$

$\sum _{i=0}^{n}{n \choose i}a^{(n-i)}b^{i}=(a+b)^{n}$, el Teorema del binomio

$\sum _{i=0}^{n}i\cdot i!=(n+1)!-1$

$\sum _{i=1}^{n}{}_{i+k}P_{k+1}=\sum _{i=1}^{n}\prod _{j=0}^{k}(i+j)={\frac {(n+k+1)!}{(n-1)!(k+2)}}$

$\sum _{i=0}^{n}{m+i-1 \choose i}={m+n \choose n}$

Errores comunes

En español suele llamarse erróneamente «sumatoria»; sin embargo según el diccionario de la Real Academia Española dicha palabra no existe en la lengua española. Por lo que lo más aconsejable es llamarle «sumatorio» u «operación de suma».

Enlaces externos

Commons

• Wikimedia Commons alberga contenido multimedia sobre Matemáticas/Combinatoria/Texto completo.

El Wikcionario contiene una entrada relacionada con este libro en: «Matemáticas/Combinatoria/Texto completo».

• Susana Castro, Funciones y Procesos Infinitos: Sumatorias
• Sumatorias - Ejercicios Resueltos - Razonamiento Matemático
• Este libro fue creado a partir de la traducción parcial del libro Symbole somme de Wikilibros en francés, bajo licencia GFDL y CC BY-SA 3.0 Unported.

Sección 2:Factorial

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40 320
9	362 880
10	3 628 800
15	1 307 674 368 000
20	2 432 902 008 176 640 000
25	15 511 210 043 330 985 984 000 000
50	30 414 093 201 713 378 043 × 1045
70	1,19785717... × 10100
450	1,73336873... × 101000
3.249	6,41233768... × 1010 000
25.206	1,205703438... × 10100 000
100.000	2,8242294079... × 10456 573

El factorial de un entero positivo n, el factorial de n o n factorial se define en principio como el producto de todos los números enteros positivos desde 1 (es decir, los números naturales) hasta n. Por ejemplo,

$5!=1\times 2\times 3\times 4\times 5=120.\$

La operación de factorial aparece en muchas áreas de las matemáticas, particularmente en combinatoria y análisis matemático. De manera fundamental el factorial de n representa el número de formas distintas de ordenar n objetos distintos (elementos sin repetición). Este hecho ha sido conocido desde hace varios siglos, en el siglo XII por los estudiosos hindúes.

La definición de la función factorial también se puede extender a números no naturales manteniendo sus propiedades fundamentales, pero se requieren matemáticas avanzadas, particularmente del análisis matemático.

La notación matemática actual n! fue usada por primera vez en 1808 por Christian Kramp (1760–1826), un matemático francés que trabajó en especial sobre los factoriales toda su vida.

Definición

La función factorial es formalmente definida mediante el producto

$n!=1\times 2\times 3\times 4\times ...\times (n-1)\times n$.

La multiplicación anterior se puede simbolizar también utilizando el operador productorio:

$n!=\prod _{k=1}^{n}k$.

También es posible definirlo mediante la relación de recurrencia

$n!={\begin{cases}1&{\text{si, }}n=0\\(n-1)!\times n&{\text{si, }}n>0\end{cases}}$

En esta segunda definición el dominio de la función es el conjunto de los enteros no negativos ℤ_≥0 y el codominio es el conjunto de los enteros positivos ℤ₊. En este caso hay una sucesión recurrente, el cálculo sucesivo de sus elementos se llama proceso recurrente y la igualdad n! = (n - 1)!n se nombra ecuación recurrente.

La segunda definición incorpora la premisa de que

$0!=1$

Cero factorial

La definición indicada de factorial es válida para números positivos. Es posible extender la definición a otros contextos introduciendo conceptos más sofisticados, en especial es posible definirla para cualquier número real excepto para los números enteros negativos y para cualquier número complejo exceptuando de nuevo los números enteros negativos.

Una extensión común, sin embargo, es la definición de factorial de cero. De acuerdo con la convención matemática de producto vacío, el valor de 0! debe definirse como:

$0!=1$

Es posible, sin embargo, dar un argumento intuitivo para justificar la elección, como sigue:

• Para cada número entero positivo n mayor o igual que 1, es posible determinar el valor del factorial anterior mediante el uso de la siguiente identidad:

$(n-1)!={\frac {n!}{n}}$

válida para todo número mayor o igual que 1.

Así, si se conoce que 5! es 120, entonces 4! es 24 porque

${\frac {5!}{5}}={\frac {120}{5}}=24$

y por tanto 3! debe ser necesariamente 6 puesto que

${\frac {4!}{4}}={\frac {24}{4}}=6$

El mismo proceso justifica el valor de 2! = 2 y 1!=1 ya que:

$2!={\frac {3!}{3}}={\frac {6}{3}}=2,\qquad 1!={\frac {2!}{2}}={\frac {2}{2}}=1$

Si aplicamos la misma regla para el caso extremo en que n!=1 tendríamos que 0! corresponde a:

$0!={\frac {1!}{1}}={\frac {1}{1}}=1$

Aunque el argumento puede resultar algo convincente, es importante tener en cuenta que no es más que un argumento informal y que la razón real por la cual se toma la convención de 0! = 1 es por ser un caso especial de la convención de producto vacío usada en muchas otras ramas de las matemáticas.

Aplicaciones

Los factoriales se usan mucho en la rama de la matemáticas llamada combinatoria, a través del binomio de Newton, que da los coeficientes de la forma desarrollada de (a + b)ⁿ:

$(a+b)^{n}={n \choose 0}a^{n}+{n \choose 1}a^{n-1}b+{n \choose 2}a^{n-2}b^{2}+\cdots +{n \choose n-1}ab^{n-1}+{n \choose n}b^{n}=\sum _{k=0}^{n}{n \choose k}a^{n-k}b^{k}$

donde ${n \choose k}$ representa un coeficiente binomial:

${n \choose k}={\frac {n!}{(n-k)!\cdot k!}}$

De igual forma se puede encontrar en la derivación por la regla del producto para derivadas de orden superior de manera similar que el binomio de newton:

${\frac {d^{n}x}{dx^{n}}}(f(x)g(x))=(fg)^{(n)}={n \choose 0}fg^{(n)}+{n \choose 1}f^{'}g^{(n-1)}+{n \choose 2}f^{''}g^{(n-2)}+\cdots +{n \choose n-1}f^{(n-1)}g^{'}+{n \choose n}f^{(n)}g=\sum _{k=0}^{n}{n \choose k}f^{(k)}g^{(n-k)}$

Donde f⁽ⁿ⁾ es la derivada enésima de la función f.

Por medio de la combinatoria, los factoriales intervienen en el cálculo de las probabilidades. Intervienen también en el ámbito del análisis, en particular a través del desarrollo polinomial de las funciones (fórmula de Taylor). Se generalizan a los reales con la función gamma, de gran importancia en la teoría de números.

Para valores grandes de n, existe una expresión aproximada para el factorial de n, dado por la fórmula de Stirling:

$n!\approx {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+{\frac {1}{288n^{2}}}+\cdots \right)$

La ventaja de esta fórmula es que no precisa inducción y, por lo tanto, permite evaluar n! más rápidamente cuando mayor sea n.

El factorial de n es generalizado para cualquier número real n por la función gamma de manera que

$\Gamma (n)=(n-1)!=\int _{0}^{\infty }\;t^{n-1}e^{-t}\;dt\,$

sólo para n > 0. Se puede generalizar aún más, para todo número complejo z que no sea igual a un entero no positivo, mediante la siguiente definición:

$\Gamma (z)=(z-1)!=\lim _{n\to \infty }{\frac {n!\;n^{z}}{z\;(z+1)\cdots (z+n)}}\,$

Productos similares

Primorial

El primorial Plantilla:OEIS se define de forma similar al factorial, pero sólo se toma el producto de los números primos menores o iguales que n.

Doble factorial

Se define el doble factorial de n mediante la relación de recurrencia:

$n!!=\left\{{\begin{array}{lcl}1&{\mbox{si}}&n\leq 0\\(n-2)!!\cdot n&{\mbox{si}}&n>0\\\end{array}}\right.$

Por ejemplo:

$8!!=2\cdot 4\cdot 6\cdot 8=384$

$9!!=1\cdot 3\cdot 5\cdot 7\cdot 9=945$

La sucesión de dobles factoriales Plantilla:OEIS para:

$n=0,1,2,\dots$

empieza así:

$1,1,2,3,8,15,48,105,384,945,3840,\dots$

La definición anterior puede extenderse para definir el doble factorial de números negativos:

$(n-2)!!={\frac {n!!}{n}}$

Y esta es la sucesión de dobles factoriales para:

$n=-1,-3,-5,-7,\dots$

$1,-1,{\frac {1}{3}},-{\frac {1}{15}},\dots$

El doble factorial de un número negativo par no está definido.

Algunas identidades de los dobles factoriales:

1. $n!=n!!(n-1)!!\,$
2. $(2n)!!=2^{n}n!\,$
3. $(2n+1)!!={(2n+1)! \over (2n)!!}={(2n+1)! \over 2^{n}n!}$
4. $(2n-1)!!={(2n-1)! \over (2n-2)!!}={(2n)! \over 2^{n}n!}$
5. $\Gamma \left(n+{1 \over 2}\right)={\sqrt {\pi }}\,\,{(2n-1)!! \over 2^{n}}$
6. $\Gamma \left({n \over 2}+1\right)={\sqrt {\pi }}\,\,{n!! \over 2^{(n+1)/2}}$

Véase también

• Productorio
• Subfactorial
• Función gamma

Enlaces externos

Wikilibros tiene otro libro relacionado con éste llamado: «Matemáticas/Combinatoria/Texto completo».

• Algoritmos interesantes(en inglés)
• http://factorielle.free.fr
• Calculadora de factoriales - Hasta 200.000

Sección 3: Binomio de Newton

Formulación del teorema

Este teorema establece: Usando la fórmula para calcular el valor de ${\tbinom {n}{k}}$ (que también es representado ocasionalmente como $C(n,k)\,$ o $C_{k}^{n}$) se obtiene la siguiente representación: $(x+y)^{n}=\sum _{k=0}^{n}{\frac {n!}{k!(n-k)!}}x^{n-k}y^{k}$ El coeficiente de $x^{n-k}y^{k}\,$ en el desarrollo de $(x+y)^{n}\,$ es ${n \choose k}$ donde ${\tbinom {n}{k}}$ recibe el nombre de coeficiente binomial y representa el número de formas de escoger k elementos a partir de un conjunto con n elementos. Usualmente el teorema del binomio se expresa en la siguiente variante: $(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}={n \choose 0}x^{n}+{n \choose 1}x^{n-1}y+{n \choose 2}x^{n-2}y^{2}+\cdots +{n \choose n-1}xy^{n-1}+{n \choose n}y^{n}$

Ejemplo

Como ejemplo, para n=2, n=3, n=4, utilizando los coeficientes del triángulo de Pascal:

(2) ${\begin{cases}(x+y)^{2}=x^{2}+2xy+y^{2}\\(x+y)^{3}=x^{3}+3x^{2}y+3xy^{2}+y^{3}\\(x+y)^{4}=x^{4}+4x^{3}y+6x^{2}y^{2}+4xy^{3}+y^{4}\end{cases}}$

Para obtener la expansión de las potencias de una resta, basta con tomar -y en lugar de y en los términos con potencias impares de y. La expresión (2) queda de la siguiente forma:

$(x-y)^{2}=x^{2}-2xy+y^{2}\,$

Teorema generalizado del binomio (Newton)

Isaac Newton generalizó la fórmula para tomar otros exponentes, considerando una serie infinita (que converge cuando |x/y|<1):

(3) ${(x+y)^{r}=\sum _{k=0}^{\infty }{r \choose k}x^{r-k}y^{k}}$

Donde r puede ser cualquier número real (en particular, r puede ser cualquier número real, no necesariamente positivo ni entero), y los coeficientes están dados por:

${r \choose k}={1 \over k!}\prod _{n=0}^{k-1}(r-n)={\frac {r(r-1)(r-2)\cdots (r-k+1)}{k!}}$

(el k = 0 es un producto vacío y por lo tanto, igual a 1; en el caso de k = 1 es igual a r, ya que los otros factores (r − 1), etc., no aparecen en ese caso).

Una forma útil pero no obvia para la potencia recíproca:

${\frac {1}{(1-x)^{r}}}=\sum _{k=0}^{\infty }{r+k-1 \choose k}x^{k}$

La suma en (3)

converge y la igualdad es verdadera siempre que los números reales o complejos x e y sean suficientemente cercanos, en el sentido de que el valor absoluto | x/y | sea menor que uno.

Sección 4: Permutación

Una permutación es la variación del orden o de la disposición de los elementos de un conjunto ordenado o una tupla sin elementos repetidos.

Definición formal

La definición intuitiva de permutación, como ordenamientos o arreglos de los elementos de un conjunto se formaliza con el uso del lenguaje de funciones matemáticas.

Definición. Una permutación de un conjunto X es una función biyectiva de dicho conjunto en sí mismo.

Ejemplo de permutación considerada como función biyectiva.

Para ilustrar la definición, retomemos el ejemplo descrito en la introducción. En el ejemplo, X={1, 2, 3}.

Entonces, cada correspondencia uno a uno entre el conjunto {1, 2, 3} a sí mismo equivale a una forma de ordenar los elementos.

Por ejemplo, la asignación biyectiva dada por

• 1 → 1
• 2 → 2
• 3 → 3

puede hacerse corresponder al ordenamiento "1, 2, 3".

Por otro lado, la asignación biyectiva dada por

• 1 → 3
• 2 → 2
• 3 → 1

puede hacerse corresponder al ordenamiento "3, 2, 1".

En la definición de permutación, no se establece condición alguna sobre X, el cual puede incluso ser infinito. Sin embargo, es común considerar únicamente el caso en que X es un conjunto finito al estudiar permutaciones.

La combinatoria trata del número de diferentes maneras que existen de considerar conjuntos formados a partir de elementos de un conjunto dado, respetando ciertas reglas, como el tamaño, el orden, la repetición, la partición. Así un problema combinatorio consiste usualmente en establecer una regla sobre cómo deben ser las agrupaciones y determinar cuántas existen que cumplan dicha regla. Básicamente, tres asuntos: permutaciones, combinaciones y variaciones (aunque se puede considerar a las permutaciones como un tipo especial de variaciones), todas sin repetición o con ella.

Un tipo importante de esas agrupaciones son las llamadas permutaciones. Dada una n-tupla ordenada de elementos de un conjunto, el número de permutaciones es el número de n-tuplas ordenadas .

Fórmula del número de permutaciones

Dado un conjunto finito $A\,\!$ de $n\,\!$ elementos, el número de todas sus permutaciones es igual a factorial de n:
$n!=n(n-1)(n-2)\cdots 1\,\!$.

Demostración: Dado que hay $n\,\!$ formas de escoger el primer elemento y, una vez escogido éste, sólo tenemos $(n-1)\,\!$ formas de escoger el segundo elemento, y así sucesivamente, vemos que cuando llegamos al elemento k-ésimo sólo tenemos $[n-(k-1)]\,\!$ posibles elementos para escoger, lo que nos lleva a que tenemos $n(n-1)(n-2)\cdots 2\cdot 1\,\!$ formas de ordenar el conjunto, justamente lo que enunciamos anteriormente.

Ejemplo: sea el conjunto A={1,2,3} en este caso hay 6 permutaciones, en forma compacta: 123, 132, 213, 231, 312, 321. En álgebra, para estudiar los grupos simétricos se presentan entre paréntesis y en dos filas, en la primera siempre aparece 1 2 3.

Una variante de lo mismo, si se va a formar un comité que involucra presidente, tesorero y secretario, habiendo tres candidatos a, b, c ; cuando se elige por sorteo los cargos sucesivamente, hay seis posibilidades u ordenaciones: abc, acb, bca, bac, cab, cba.

Sección 5: Combinación

La combinatoria estudia las diferentes formas en que se pueden agrupar u ordenar los elementos de un conjunto. El punto de partida será el principio de la multiplicación o estrategia del producto.

Principio de la multiplicación o estrategia del producto

Ejemplo 1: Un equipo de baloncesto tiene que elegir un nuevo uniforme. Para ello debe escoger entre 4 camisetas y 5 pantalones con diferentes colores. ¿Cuántos uniformes distintos se pueden componer con las camisetas y pantalones disponibles?

Para resolver este problema hemos de tener en cuenta que cada una de las camisetas se podrá combinar con cada uno de los pantalones disponibles. Si tuviéramos una única camiseta, podríamos componer 5 uniformes diferentes, resultado de combinar dicha camiseta con cada uno de los 5 pantalones. Si tuviéramos 2 camisetas, podríamos componer 5 uniformes distintos para cada camiseta, resultado de combinar cada camiseta con cada uno de los 5 pantalones. Tendríamos por tanto 2 · 5 = 10 combinaciones posibles. Siguiendo el mismo razonamiento, llegaríamos a la conclusión de que con 4 camisetas y 5 pantalones, podríamos componer 4 · 5 = 20 uniformes diferentes.

Lo que hemos utilizado es lo que se conoce con el nombre de principio de la multiplicación, que puede enunciarse de la siguiente forma:

Principio de la multiplicación. Si tenemos a opciones para escoger un objeto, b opciones para elegir un segundo objeto, c opciones para escoger un tercero, etc., el número total de formas de combinar los distintos objetos es el producto a · b · c · .....

Ejemplo 2: ¿Cuántos números de tres cifras se pueden formar con los dígitos 0, 1, 2, 3 y 4, sin que se repita ninguna cifra?

Las opciones para escoger la primera cifra son cuatro, pues ésta no puede tomar el valor 0, ya que ningún número de tres cifras comienza por 0. Para la segunda cifra tendremos también cuatro opciones, pues aunque en este caso si puede tomar el valor 0, tendremos que descartar el valor que haya tomado la primera cifra, por no poderse repetir ninguna. Por último, para la tercera cifra tendremos tres opciones, resultado de descartar los valores empleados en las dos primeras cifras, para evitar repeticiones.

Por tanto, aplicando el principio de la multiplicación, se obtiene que hay 4 · 4 · 3 = 48 números de tres cifras distintos con los dígitos indicados en el enunciado.

Sección 6: Triángulo de Pascal

En Matemáticas, el teorema del binomio es una fórmula que proporciona el desarrollo de la potencia n-ésima (siendo n, entero positivo) de un binomio. De acuerdo con el teorema, es posible expandir la potencia (x + y)ⁿ en una suma que implica términos de la forma ax^by^c, donde los exponentes b y c son números naturales con b + c = n, y el coeficiente a de cada término es un número entero positivo que depende de n y b. Cuando un exponente es cero, la correspondiente potencia es usualmente omitida del término. Por ejemplo,

$(x+y)^{4}\;=\;x^{4}\,+\,4x^{3}y\,+\,6x^{2}y^{2}\,+\,4xy^{3}\,+\,y^{4}.$

El coeficiente a en los términos de x^by^c - x^cy^b es conocido como el coeficiente binomial ${\tbinom {n}{b}}$ o ${\tbinom {n}{c}}$ (los dos tienen el mismo valor).

Formulación del teorema

Este teorema establece:

Usando la fórmula para calcular el valor de ${\tbinom {n}{k}}$ (que también es representado ocasionalmente como $C(n,k)\,$ o $C_{k}^{n}$) se obtiene la siguiente representación:

$(x+y)^{n}=\sum _{k=0}^{n}{\frac {n!}{k!(n-k)!}}x^{n-k}y^{k}$

El coeficiente de $x^{n-k}y^{k}\,$ en el desarrollo de $(x+y)^{n}\,$ es ${n \choose k}$

donde ${\tbinom {n}{k}}$ recibe el nombre de coeficiente binomial y representa el número de formas de escoger k elementos a partir de un conjunto con n elementos. Usualmente el teorema del binomio se expresa en la siguiente variante:

$(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}={n \choose 0}x^{n}+{n \choose 1}x^{n-1}y+{n \choose 2}x^{n-2}y^{2}+\cdots +{n \choose n-1}xy^{n-1}+{n \choose n}y^{n}$

Ejemplo

Como ejemplo, para n=2, n=3, n=4, utilizando los coeficientes del triángulo de Pascal:

${\begin{cases}(x+y)^{2}=x^{2}+2xy+y^{2}\\(x+y)^{3}=x^{3}+3x^{2}y+3xy^{2}+y^{3}\\(x+y)^{4}=x^{4}+4x^{3}y+6x^{2}y^{2}+4xy^{3}+y^{4}\end{cases}}$

Para obtener la expansión de las potencias de una resta, basta con tomar -y en lugar de y en los términos con potencias impares de y. La expresión (2) queda de la siguiente forma:

$(x-y)^{2}=x^{2}-2xy+y^{2}\,$

Teorema generalizado del binomio (Newton)

Isaac Newton generalizó la fórmula para tomar otros exponentes, considerando una serie infinita:

(3) ${(x+y)^{r}=\sum _{k=0}^{\infty }{r \choose k}x^{r-k}y^{k}}$

Donde r puede ser cualquier número real (en particular, r puede ser cualquier número real, no necesariamente positivo ni entero), y los coeficientes están dados por:

${r \choose k}={1 \over k!}\prod _{n=0}^{k-1}(r-n)={\frac {r(r-1)(r-2)\cdots (r-k+1)}{k!}}$

(el k = 0 es un producto vacío y por lo tanto, igual a 1; en el caso de k = 1 es igual a r, ya que los otros factores (r − 1), etc., no aparecen en ese caso).

Una forma útil pero no obvia para la potencia recíproca:

${\frac {1}{(1-x)^{r}}}=\sum _{k=0}^{\infty }{r+k-1 \choose k}x^{k}$

La suma en (3)

converge y la igualdad es verdadera siempre que los números reales o complejos x e y sean suficientemente cercanos, en el sentido de que el valor absoluto | x/y | sea menor que uno.

Coeficiente binomial

Para aplicar el Teorema del binomio, el coeficiente binomial se presenta como ${\tbinom {\alpha }{k}}$ de forma sencilla:

${\alpha \choose k}:={\frac {\alpha (\alpha -1)(\alpha -2)\cdots (\alpha -k+1)}{k!}}.$

Generalizaciones

Ejemplo combinacional de coeficiente trinomial.

En vez de considerar las potencias de a + b, se puede considerar las del trinomio a + b + c. De esta manera, (a + b + c)ⁿ es una suma de monomios de la forma λ_{p, q, r} ·a^p·b^q·c^r, con p, q y r positivos, p + q + r = n, y λ_{p, q, r} un número natural que se llama coeficiente trinomial. Los cálculos son similares a los del coeficiente binomial, y se dan mediante la siguiente expresión:

$\lambda _{p,q,r}={n \choose p,q,r}={\frac {n!}{p!q!r!}}$,

en subconjuntos de p, q y r elementos.

Pirámide de Pascal. Se han dibujado las primeras secciones a partir de la cumbre.

Estos coeficientes se pueden considerar como la analogía tridimensional del triángulo de Pascal. De hecho, a la distribución de estos coeficientes al estilo piramidal se le conoce como pirámide de Pascal; es también infinita, con secciones triangulares, y el valor en cada casilla es la suma de los valores de las tres casillas encima de ella.

En esta pirámide se observa una invariante por rotación de 120 grados alrededor de un eje vertical que pasa por el vértice. El triángulo de Pascal aparece en las tres caras de la pirámide.

De igual manera, todo esto se puede generalizar a dimensiones finitas cualesquiera, pero sin la posibilidad de hacer dibujos explicativos sencillos.