Análisis Combinatorio

Análisis Combinatorio 1
Álgebra y Geometría Analítica
Conceptos preliminares. Principio fundamental del análisis combinatorio. La función

factorial. Fórmula de Stirling.
Combinatoria simple: Variaciones o Permutaciones simples de n elementos tomados

de a r, Permutaciones simples de n elementos. Combinaciones simples de n elementos
tomados de a r.
CONCEPTOS PRELIMINARES:
El interés del hombre por los juegos de azar viene indudablemente

desde los tiempos históricos, pero no fue hasta principios de 1650 que se hizo un fundamento
matemático para la solución de diversos problemas sugeridos por esos juegos. El Chevalier
de Meré, llamado el “filósofo jugador del siglo XVII”, interesado en obtener información sobre
los riesgos que corría en los juegos de dados consultó a uno de los matemáticos más
famosos de todos los tiempos: Blaise Pascal, quien a su vez escribió a un matemático aún
más célebre, el consejero parlamentario de la ciudad de Toulouse, Pierre de Fermat y en la
correspondencia que intercambiaron se planteó por primera vez la Teoría de la Probabilidad.
Con el correr de los años, la Teoría de la Probabilidad encontró su

cauce durante el siglo XIX de la mano de Laplace en muchas aplicaciones, no sólo en
Ingeniería y Matemática, sino también en campos como la Agricultura, la Administración de
Empresas, la Medicina y la Sociología.
La Teoría de la Probabilidad representa el intento de la mente humana

de afrontar cuantitativamente la complejidad de fenómenos en los que intervienen un gran
número de causas, cada una de las cuales resulta imposible de controlar. Tales fenómenos
decimos, están regidos por el azar.
El azar es un nombre que damos a nuestra ignorancia: que un dado al

caer muestre en su cara superior el 1 o bien el 2, el 3, el 4, el 5 o el 6 está determinado por
su posición inicial, por el impulso con el cual es arrojado, por el material con el que está
construido, como así también por la naturaleza de la superficie
sobre la cual rebota, por la eventual velocidad del viento, etc.... Como hay tantas causas que
intervienen en el fenómeno, no sabemos ponderar ni calcular su efecto y entonces, decimos
que es el azar el que determina el resultado. Pero a pesar del azar, seguramente diremos
que un dado está “cargado” si al arrojarlo 1000 veces, solo obtenemos veinte veces el
número uno, porque las innumerables complejidades que
gobiernan un fenómeno tal como el lanzamiento de un dado, se equilibran cuando lo
repetimos un gran número de veces.
Resulta entonces, que la complejidad del resultado de un fenómeno

simple que nos lo hace impredecible o azaroso se convierte en ley matemática simple e
inexorable cuando en lugar de considerar un solo fenómeno tomamos en cuenta los
resultados de cientos o miles de fenómenos semejantes.
1
Una disciplina estrechamente vinculada con la Teoría de la
Probabilidad es la Estadística: nacida con anterioridad a dicha Teoría, trata principalmente
el problema de la recolección, organización y presentación de datos en tablas y gráficos.
La palabra Estadística nos trae frecuentemente imágenes de números
organizados en grandes arreglos, tablas de cifras relativas a nacimientos, muertes,
impuestos, ingresos, deudas, créditos, etc... Ello es debido a que el uso de la
palabra Estadística por parte del ciudadano común se hace como sinónimo de recolección y
agrupamiento de datos; por. ejemplo, cuando se habla de las estadísticas en el campeonato
de fútbol, o las estadísticas de los accidentes de automovilismo.
Con el advenimiento de la Teoría de la Probabilidad se puso de

manifiesto que la Estadística puede emplearse en la extracción de conclusiones válidas y en
la toma de decisiones razonables.
El lanzamiento de un dado o de una moneda, la extracción de un naipe

de una baraja o de los números de la lotería son experiencias denominadas aleatorias1 pues
sus resultados dependen del azar.
También son aleatorios el instante en que llegará un ómnibus a su

parada, el número de hijos que tendrá un matrimonio, la estatura que tendrá uno cualquiera
de ellos o el número de años que vivirá.
Los primeros ejemplos son sencillos de seguir ya que con comodidad y

rapidez los eventos correspondientes pueden repetirse muchas veces. Es por esta razón que
el estudio de las probabilidades comienza con los juegos de azar. A partir de ellos, se
obtienen leyes que rigen los fenómenos aleatorios y que se aplican, con éxito similar a los
problemas de la vida real, que son en realidad muchísimo más interesantes.
En muchos casos el número de posibilidades que pueden darse en un
determinado suceso no es muy grande y en consecuencia la enumeración de las mismas no
resulta difícil. Sin embargo, aparecen dificultades si la cuenta directa (por corresponder a
grandes números) se convierte en una imposibilidad desde el punto de vista práctico.
Para estos casos se utiliza el Análisis Combinatorio que, en una
primera aproximación podría definirse como una manera sofisticada de contar.
Principio fundamental del Análisis Combinatorio: (también llamado principio

fundamental del conteo o de contar)
Si un determinado suceso, operación o acción puede ocurrir de n1

maneras distintas y si, siguiendo a ese suceso otro puede ocurrir de n2 maneras diferentes
y siguiendo a este suceso un tercer suceso puede ocurrir de n3 maneras y así
sucesivamente..., el número total de formas diferentes en que pueden realizase estos
sucesos será igual a: n1•n2•n3•....
Ejemplo1: Si un hombre tiene tres sacos y dos corbatas, podrá elegir (principio fundamental
de contar) de n1•n2=3•2 = 6 maneras distintas primero un saco y después una corbata.
Para dar una solución gráfica al problema anterior se emplea una
estructura llamada diagrama arborescente o simplemente diagrama de árbol.
1
La palabra aleatorio proviene del latín alea que significa suerte y también dados. La palabra azar viene del
árabe, idioma en el cual el azar significa también dados.
2
c1 S1C1
c2 S1C2
S1
c1 S2C1
S2
c2 S2C2
S3
c1 S3C1
c2 S3C2
La estructura de diagrama de árbol permite no sólo obtener el número

de sucesos posibles, sino también individualizar cada uno de los mismos.
Ejemplo 2: Supongamos que deseamos viajar de la ciudad A hasta la ciudad C, pasando

por la ciudad B, contando para ello con cuatro rutas que unen las ciudades A y B y tres rutas
entre B y C. Nos interesa saber cuántas rutas diferentes pueden transitarse desde A hasta
C.
2 1
A 3 B 2 C
4 3
Por cada ruta entre A y B hay tres elecciones posibles antes de

emprender la ruta entre B y C. Puesto que hay cuatro maneras distintas de llegar desde A
hasta B, habrá en total 4•3=12 formas de llegar desde A hasta C.
Este problema, como todos aquellos que corresponden al Análisis

Combinatorio pueden formularse en el lenguaje de la Teoría de Conjuntos- En efecto, las
rutas entre A y C pueden expresarse mediante un conjunto de pares ordenados en
los cuales la primera componente es una de las posibles rutas entre A y B y la segunda
componente corresponde a una de las rutas entre B y C:
{(1,1); (1,2); (1,3); (2,1); (2,2);(2,.3);(3,1);(3,2);(3,3);(4,1);(4,2);(4,3)}
Ejemplo 3: Suponemos que el director de una película debe conformar una familia
compuesta por un marido, una esposa y un hijo, eligiendo entre 4 actores, 5 actrices y tres
niños. El marido puede elegirse de cuatro maneras distintas y por cada elección existirá la
posibilidad de elegir 5 esposas, resultando un total de 4•5=20 matrimonios posibles. Por
cada elección de los padres, es decir, por cada matrimonio elegido, se podrán efectuar tres
3
elecciones para el hijo. En consecuencia, el número de familias posibles resultará 4•5•3=
60.
Actividad: ¿De cuántas maneras diferentes podrá vestirse una persona que tiene dos
camisas, tres pantalones y cuatro pares de zapatos?
El Análisis Combinatorio trata de las distintas maneras en que se

pueden organizar subconjuntos de un conjunto dado, siguiendo determinadas restricciones
particulares para cada problema. Si en los subconjuntos a estructurar los elementos que
intervienen no pueden repetirse se tratará de la llamada Combinatoria Simple mientras que,
cuando pueden hacerlo, nos estaremos ocupando de la Combinatoria con Repetición.
Notación de Factorial: Dado un número natural n, recibe el nombre de factorial de n (n!), el

producto decreciente de la sucesión de los números naturales entre n y 1:
n!=n(n-1)(n-2)••••3•2•1
Ejemplo:
6! = 6•5•4•3•2•1
6! = 6•5!
6! = 6•5•4!
Cuando el número n es muy grande no resulta sencillo el cálculo de

n!. Las máquinas de calcular electrónicas de uso corriente permiten calcular hasta 69!, lo
que significa que la expresión en la que interviene factorial, si no puede simplificarse, será
dificultosa de calcular. Para tales casos suele utilizarse la fórmula aproximada debida a
Stirling:
n -n
n ! @ 2p n • n e
en la cual e = 2,718291828459045... es la base de los logaritmos naturales.
Ejemplo:
a) con la máquina de calcular: 69! = 1,71 •1098
b) con la fórmula de Stirling: 69 ! = 2 • 3,14 • 69 • 6969 • (2,7128...)-69
Aplicando logaritmos decimales:
log 69! = ½(log 2 + log 3,14 + log 69) + 69 •log 69 - 69•log 2,718...= 98,23779...
69! = 1,72 • 1098
COMBINATORIA SIMPLE:
Pueden distinguirse tres problemas distintos estudiados en el

conjunto A = { a1 ; a2 ;............; a(n-1) ; an}:
1) Variaciones o Permutaciones de n elementos tomados de a r. (r<n)

Definición: Llamamos variaciones, permutaciones o arreglos de n elementos tomados
de a r a los distintos ordenamientos que pueden realizarse de acuerdo con las siguientes
condiciones:
a) En cada uno de los subconjuntos intervienen r de los n elementos constitutivos del
conjunto A que se estudia.
b) Dos subconjuntos se considerarán distintos si difieren en algún elemento o bien, si
contando con los mismos elementos es distinto el ordenamiento.
4
Se trata en consecuencia, de la estructuración de subconjuntos

ordenados de A (debe considerarse como elemento distintivo de dos subconjuntos el hecho
de que, a pesar de contar con los mismos elementos, sea distinto el ordenamiento).
Por tal razón y a los efectos de diferenciarlos de los conjuntos no
ordenados se los encerrará entre paréntesis (siguiendo la notación de los pares ordenados
de números reales, de las ternas ordenadas, etc.)
Teniendo en cuenta que en los problemas del Análisis Combinatorio

interesa conocer el número de arreglos que se pueden realizar, sin que sea necesario
describir cada uno de los subconjuntos posibles, utilizaremos para obtener una fórmula de
recurrencia la estructura de diagrama de árbol que permite, escribiendo parcialmente el
mismo, obtener fórmulas de aplicación para el problema general.
Para ejemplificar el proceso, consideremos el problema de obtener el
número de las V4,3 (variaciones de cuatro elementos tomados de a tres), a partir del conjunto
A = {a1 ; a2 ; a3 ; a4}.
Se debe entonces, construir subconjuntos del conjunto A en cada uno

de los cuales intervengan tres elementos, recordando que dos subconjuntos se considerarán
distintos si difieren en algún elemento o si, estando conformados por los mismos elementos,
es distinto el ordenamiento.
Para comenzar, construimos las Variaciones de cuatro elementos

tomados de a un elemento. A partir de una raíz, abrimos cuatro ramas:
(a1)
(a2)
(a3)
(a4)
Hemos obtenido las V4,1 = 4. Con análogo razonamiento podemos inferir que las Vn,1
(variaciones de n elementos tomados de a uno) resultarán en un número igual a n. (Vn,1 =
n)
A partir de cada una de las V4,1 trataremos de construir las V4,2 .

Teniendo en cuenta que las Variaciones que estamos construyendo son simples, es decir
sin repetición, cada una de las V4,1 dará origen a conjuntos binarios (pares ordenados) que
se obtendrán yuxtaponiendo a las mismas uno de los tres elementos de A que no haya sido
utilizado, resultando:
(a1,a2)
(a1) (a1,a3)
(a2)
(a1,a4)
(a3)
(a4)
Como puede observarse fácilmente, no resulta necesario escribir la

totalidad de las ramificaciones del árbol, ya que puede inferirse que el número de las V4,2
resultará de multiplicar el número de las V4,1 por tres (3).
5
V4,2 = V4,1•3 = 4•3
A partir de las V4,2 siguiendo un razonamiento similar, construimos las

V4,3 teniendo en cuenta que cada una de las V4,2 constituidas por dos elementos, dará lugar
a dos V4,3; cada una de ellas por yuxtaposición de un elemento tomado del conjunto A que
no figure en la correspondiente V4,2. Así se obtiene (abrimos el árbol únicamente para el
subconjunto (a1,a3):
(a1,a2) (a1,a3,a2)
(a1) (a1,a3)
(a2) (a1,a4) (a1,a3,a4)
(a3)
(a4)
resultando por cada una de las V4,2 dos V4,3 ; lo que significa:
V4,3 = 2 V4,2 = 4•3•2
Con análogo razonamiento, la estructuración del diagrama de árbol nos permite inferir:
V5,3 = 3V5,2 = 5•4•3
V6,3 = 4V6,2 = 6•5•4
Vn,3 = (n-2)Vn,2 = n(n-1)(n-2)
Vn,4 = (n-3)Vn,3 = n(n-1)(n-2)(n-3)
Puede observarse para cada caso que el resultado es el producto de una sucesión
decreciente de números naturales que comienza con el primero de los subíndices y tiene
tantos términos como indica el segundo subíndice; así, si queremos calcular V1000,4 , el
resultado será 1000•999•998•997 ; y si queremos calcular Vn,r obtendremos:
Vn,r = n(n-1)(n-2)(n-3)............[n-(r-1)] ; que equivale a:
Vn,r = n(n-1)(n-2)(n-3)............(n – r + 1)
Utilizando la notación de factorial, si multiplicamos y dividimos el segundo miembro de la

expresión anterior por (n - r)!, resulta:
n(n - 1)(n - 2)(n - 3) • • • •(n - r - 1)(n - r ) !
Vn, r =
(n - r ) !
el numerador del segundo miembro equivale al desarrollo de n! por ser:
(n-r)! = (n-r)(n-r-1)(n-r-2)•••3•2•1
resultando entonces:
6
n!
Vn, r =
(n - r )!
Ejemplo: Utilizaremos la última expresión deducida para calcular V1000,4
1000 ! 1000 ! 1000 • 999 • 998 • 997 • 996 !

V1000,4 = = = = 1000 • 999 • 998 • 997
(1000 - 4) ! 996 ! 996 !
2) Permutaciones de n elementos:
Se trata ahora de estructurar subconjuntos de un conjunto dado

en los cuales intervienen todos los elementos del conjunto que se estudia, diferenciándose
unos de otros solamente por el ordenamiento.
Si tomamos como punto de partida para la estructuración de una

fórmula de recurrencia el conjunto de las V4,3 que construimos como modelo para obtener el
número de las Vn,r
(a1,a2)
(a1) (a1,a3) (a1,a4,a2)
(a2) (a1,a4) (a1,a4,a3)
(a3)
(a4)
vemos que cada una de las V4,3 originadas por la dupla (a1,a4) que están representadas en
la última columna, sólo puede dar origen a una V4,4 obtenida mediante la yuxtaposición del
único elemento faltante tomado del conjunto A que se
estudia; es decir que la terna (a1,a4,a2), por ejemplo, dará origen únicamente a la cuaterna
(a1,a4,a2,a3)
(a1,a2)
(a1) (a1,a3) (a1,a4,a2) (a1,a4,a2,a3)
(a2) (a1,a4)
(a1,a4,a3)
(a3)
(a4)
lo que significa que el número de las V4,4 = P4 = 4•3•2•1= 4! ; podemos entonces escribir:
Pn= n!
3) Combinaciones de n elementos tomados de a r.
Se trata en este caso de conformar subconjuntos de un conjunto dado,

tales que en cada uno de ellos intervengan r de los n elementos del conjunto A que se
7
estudia, (siendo r £ n) con la condición de que dos subconjuntos deben considerarse distintos
sólo en el caso en que difieran al menos en un elemento.
A los efectos de obtener la correspondiente expresión de recurrencia,

tomemos como ejemplo la construcción de las Combinaciones de cuatro elementos tomados
de a 3, es decir la construcción de las C4,3 tomadas del conjunto
A={a1,a2,a3,a4}. Con la condición impuesta, los subconjuntos a construir serán no ordenados,
razón por la cual encerramos sus elementos entre llaves. Se obtienen mediante simple
análisis las siguientes ternas:
{a1,a2,a3} ; {a1,a2,a4} ; {a1,a3,a4} ; {a2,a3,a4}
Si a partir de estos subconjuntos, escribimos las permutaciones de los

elementos de cada uno de ellos, obtendremos:
(a1,a2,a3) (a1,a3,a2) (a2,a1,a3) (a2,a3,a1) (a3,a1,a2) (a3,a2,a1)

Como las ternas ordenadas de la tabla anterior han sido obtenidas

siguiendo el mecanismo de estructurar todos los subconjuntos posibles de tres elementos de
A: primero aquellos que se diferencian en algún elemento, (los que corresponden a cualquier
columna) y luego todos aquellos que, manteniendo los elementos, se obtienen permutando
el orden de los mismos (ver una cualquiera de las filas), en dicha tabla habremos escrito
(recordar la definición) la totalidad de las variaciones de cuatro elementos tomados de tres.
Resulta entonces que si cualquier columna representa la descripción
de las C4,3 y cada fila la descripción de las P3, podremos asegurar que:
V4,3 = C4,3 •P3

V
o bien: C4,3 = 4,3
P3
V
que puede generalizarse: Cn, r = n, r
Pr
n!
utilizando la expresión: Vn, r =
(n - r) !
n!
llegamos a Cn,r =
r ! (n - r) !
Potencia de un binomio. Introducción. Estructura de los términos. Estructura

de los coeficientes. Tabla de cálculo directo de los coeficientes para una potencia
8
cualquiera. El coeficiente binomial o número combinatorio: propiedades
Aplicación de las propiedades al cálculo de los coeficientes del desarrollo de la
potencia n-ésima de un binomio. Triángulo de Tartaglia.
Potencia de un binomio.(El binomio de Newton).
Para encontrar una expresión de recurrencia que nos permita obtener el

desarrollo de (a+b)n cualquiera sea n perteneciente al conjunto No (naturales incluido el cero)
sin tener que multiplicar sucesivamente la base (a+b) por sí misma, nos basaremos en
algunos desarrollos realizados para potencias pequeñas, que conocemos desde la escuela
media.
(a+b)o = 1
(a+b)1= 1a1b0 +1a0b1
(a+b)2= 1a2b0+2a1b1+1a0b2
(a+b)3= 1a3b0+3a2b1+3a1b2+1a0b3
(a+b)4= 1a4b0+4a3b1+6a2b2+4a1b3+1a0b4
En los desarrollos precedentes pueden realizarse las siguientes

observaciones;
a) respecto de la estructura de los desarrollos:
a1) el número de términos es igual a la potencia mas uno (n+1).

a2) en todos los casos se efectúan en potencias crecientes de b (desde 0 hasta n)
y en potencias decrecientes de a (desde n hasta 0).
a3) todos los términos son homogéneos, es decir, del mismo grado n, lo que significa
que si en un término cualquiera el grado de b es i, el grado de a deberá ser n-i,
resultando que el término genérico o término general del desarrollo será de la
forma an-ibi,.precedido de un coeficiente cuya forma de generación describimos:.
b) respecto de la formación de los coeficientes:
(a+b)o = 1
(a+b)1= 1 1
(a+b)2= 1 2 1
(a+b)3= 1 3 3 1
(a+b)4= 1 4 6 4 1
con los coeficientes de los segundos miembros de las igualdades se ha formado un

“triángulo numérico” en el cual:
b1) para cualquier potencia el primero y el último coeficientes son iguales a la unidad;
el segundo y el anteúltimo son iguales al valor de la potencia.
b2) existe simetría en el valor de los coeficientes, con uno central si n es par y dos
centrales iguales si n es impar. Por esta razón solo es necesario encontrar el
valor de un número de coeficientes equivalente a la parte entera del cociente
9
n
, teniendo en cuenta que, para todo n, el valor del primer coeficiente es la
2
unidad.
b3) en el “triángulo numérico” cada uno de los coeficientes, exceptuando el
primero de cada desarrollo, es igual a la suma del que tiene encima más el
de la izquierda de este último o bien, puede obtenerse como la diferencia entre
el que tiene debajo y el que tiene a su izquierda.
b4) Para cualquier potencia, todos los coeficientes, a partir del segundo
pueden calcularse multiplicando el coeficiente del término anterior por la
potencia de a en su término y dividiéndolo por la potencia de b en el
término cuyo coeficiente se quiere calcular.
Como veremos y justificaremos posteriormente, esta última

observación resulta de suma utilidad, ya que posibilita calcular directamente los
coeficientes para cualquier potencia, por grande que ella sea, sin tener que apelar al previo
conocimiento de los coeficientes de potencias menores obtenidas del triángulo numérico.
Debe destacarse que, cuando n aumenta, el cálculo de los coeficientes utilizando el triángulo
numérico resulta engorroso y muchas veces inviable.
Para ejemplificarla observación efectuada en b4) volvamos al

desarrollo del binomio para la potencia n = 4
(a+b)4= 1a4b0+4a3b1+6a2b2+4a1b3+1a0b4
el cálculo de los coeficientes puede realizarse como sigue:
coef. 0 = 1 (como se dijo en b1), para cualquier potencia es igual a la unidad).
4
coef. 1 = 1 • = 4
1
3
coef. 2 = 4 • = 6
2
2
coef. 3 = 6 • = 4
3
1
coef. 4 = 4 • = 1
4
El cálculo puede generalizarse utilizando la expresión:
n - i +1ö
coef. i = coef.i-1 æç ÷ válida para todo i mayor o igual que uno.
è i ø
Ejemplificamos para n = 6
coef. 0 = 1
6 -1 +1ö
coef. 1 = 1 æç
6
÷ = 1• = 6
è 1 ø 1
6 - 2 +1ö
coef. 2 = 6 æç
5
÷ = 6 • = 15
è 2 ø 2
6 - 3 +1ö
coef. 3 = 15 æç
4
÷ = 15 • = 20
è 3 ø 3
10
6 - 4 +1ö
coef. 4 = 20 æç
3
÷ = 20 • = 15
è 4 ø 4
6 - 5 +1ö
coef. 5 = 15 æç
2
÷ = 15 • = 6
è 5 ø 5
6 - 6 +1ö
coef. 6 = 6 æç
1
÷ = 6• =1
è 6 ø 6
resultando los coeficientes de (a+b)6 iguales a 1 6 15 20 15 6 1

utilizando la observación b3), podemos escribir los valores de los coeficientes para n = 5 y n
=7
(a+b)5 = 1 5 10 10 5 1
(a+b)6 = 1 6 15 20 15 6 1
(a+b)7 = 1 7 21 35 35 21 7 1
Ahora nuestro triángulo numérico puede ampliarse a:

(a+b)o = 1
(a+b)1 = 1 1
(a+b)2 = 1 2 1
(a+b)3 = 1 3 3 1
(a+b)4 = 1 4 6 4 1
(a+b)5 = 1 5 10 10 5 1
(a+b)6 = 1 6 15 20 15 6 1
(a+b)7 = 1 7 21 35 35 21 7 1
El cálculo que hemos realizado puede tabularse, permitiendo una gran

simplificación y aumento de la rapidez en la obtención de los coeficientes.
Supongamos que queremos obtener los coeficientes para la potencia

n = 7; teniendo en cuenta la simetría a que hemos hecho referencia en b2), sólo será
necesario calcular un número de coeficientes equivalente a la parte entera de 7/2, es decir,
tres coeficientes:
n - i +1 7 6 5
i 0 1 2 3
coef. i 1 7 21 35
y para la potencia n = 15 (calculamos siete coeficientes)
11
n - i +1 15 14 13 12 11 10 9
I 0 1 2 3 4 5 6 7
Coef.i 1 15 105 455 1365 3003 5005 6435
resultando los coeficientes:
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
Supongamos ahora que queremos calcular el sexto coeficiente

(i = 5) del desarrollo del binomio para la potencia 15 (ver la zona sombreada de la tabla
anterior). El valor requerido se obtiene mediante la operación:
15 • 14 • 13 • 12 • 11 V15,5
= = C15,5 = 3003
1• 2 • 3 • 4 • 5 P5
en la cual el número resultante equivale a las combinaciones de quince elementos tomados
de a cinco, pero no se trata de un arreglo sino de un número que, por la estructura de su
obtención llamamos Número Combinatorio. Vamos a demostrar que esta estructura de
cálculo es válida cualquiera sea el valor de la potencia n.
Generalizando;
n - i +1 n n-1 n-2 n-3 … … n-i+1 … …

i 0 1 2 3 4 … … i … …
coef. i 1 coef. i ... ...
n(n - 1)(n - 2)(n - 3).......(n - i + 1)

coef. i = ;
1 • 2 • 3 • 4.... • i
multiplicando y dividiendo el segundo miembro por (n-I)!
n(n - 1)(n - 2)(n - 3).......(n - i + 1)(n - i )! n!

coef. i = =
1 • 2 • 3 • 4.... • i • (n - i )! i!(n - i )!
que escribimos:
ænö n! ænö
coef.i = çç ÷÷ = ; al símbolo çç ÷÷ lo denominamos indistintamente
è i ø i!(n - i )! èi ø
número combinatorio o coeficiente binomial. Al número n lo llamamos numerador y al
número i, denominador, sin que ello signifique que se trata de un cociente entre estos
números.
Podemos entonces escribir los desarrollos para distintas
potencias, expresando los coeficientes como números combinatorios; por ejemplo, para la
potencia n = 4 resultará:
(a + b )4 = æçç
4ö 4 0 æ 4ö 3 1 æ 4ö 2 2 æ 4ö 1 3 æ 4ö 0 4
÷÷a b + çç ÷÷a b + çç ÷÷a b + çç ÷÷a b + çç ÷÷a b
è0ø è1 ø è 2ø è3ø è 4ø
y para la potencia n:
(a + b )n = æçç
n ö n 0 æ n ö n -1 1 æ n ö n - 2 2 ænö æ n ö n -( n -1) n -1 æ´n ö 0 n
÷÷a b + çç ÷÷a b + çç ÷÷a b + .... + çç ÷÷a n -ibi + .... + çç ÷÷a b + çç ÷÷a b
è0ø è1 ø è2ø èi ø è n - 1ø èn ø
12
ænö
expresión en la cual cada uno de los coeficientes puede obtenerse a partir del primero çç ÷÷
æ nö æ n ö æ n - i +1ö è0ø
çç ÷÷ = çç ÷÷ × ç ÷
=1. mediante la fórmula è i ø è i - 1ø è i ø;
por ejemplo, para el desarrollo de (a+b)7:
æ7ö æ7ö æ 7 -1 +1ö æ7ö

çç ÷÷ = çç ÷÷ × ç ÷, lo que es igual a çç ÷÷ = 1 × 7 = 7
è1 ø è 0 ø è 1 ø è1 ø
æ7ö æ7ö æ 7 - 2 +1ö æ7ö
çç ÷÷ = çç ÷÷ × ç ÷; " " " " " çç ÷÷ = 7 × 3 = 21
è 2 ø è1 ø è 2 ø è 2ø
æ7ö æ7ö æ 7 - 3 +1ö æ7ö 5
çç ÷÷ = çç ÷÷ × ç ÷; " " " " " çç ÷÷ = 21 × = 35
è3 ø è 2ø è 3 ø è3ø 3
y así siguiendo...
o de manera más rápida como se explicará y desarrollará en la tabla
n - i +1 7 6 5
i 0 1 2 3
coef. i 1 7 21 35
La potencia n-ésima de un binomio puede escribirse en forma

condensada:
n
(a + b )n = å æçç
n ö n -i i
÷÷a b
i =0 ø
è i
expresión que recibe el nombre de “El binomio de Newton” y en la cual los coeficientes
pueden obtenerse mediante los métodos desarrollados.
Para aceptar la validez de esta última expresión condensada cualquiera

sea n, falta generalizar las observaciones b2) y b3; para ello realizaremos el análisis de las
propiedades de los que hemos llamado Números Combinatorios.
Propiedades de los Números Combinatorios
Generalización de la observación b2)
ænö æ n ö
La igualdad çç ÷÷ = çç ÷÷ que corresponde a la simetría de los
èi ø èn - iø
coeficientes se traduce en palabras de la siguiente manera:
Dos números combinatorios de iguales numeradores y denominadores

tales que su suma es igual al numerador, se dicen de órdenes complementarios y son
iguales.
13
Demostración.
El desarrollo de los números combinatorios para ambos miembros
puede expresarse como: factorial de numerador dividido el factorial del denominador que
multiplica al factorial de la diferencia entre numerador y denominador. Para
n! n!
nuestra igualdad: = ; eliminando el paréntesis del segundo factor
i!(n - i )! (n - i )![n - (n - i )] !
n! n!
del denominador del segundo miembro, resulta: = ; lo que significa que,
i !×(n - i )! (n - i )!i!
cualquiera sea n, los coeficientes simétricos del desarrollo son iguales. La observación b2),
se ha transformado en una propiedad).
Ejemplo: en el desarrollo de (a+b)4 se verifican las siguientes igualdades:

æ 4ö æ 4ö æ 4ö æ 4ö
çç ÷÷ = çç ÷÷ = 1 ; çç ÷÷ = çç ÷÷ = 4 :
è0ø è 4ø è1 ø è 3 ø
que se leen: el primero y el último coeficiente son iguales a la unidad; el segundo y el
anteúltimo son iguales a la potencia.
Generalización de la observación b3)
Que un coeficiente cualquiera puede obtenerse en el triángulo

numérico como la suma entre el que tiene encima y el de la izquierda de este último se
expresa, si los consideramos como números combinatorios, de la siguiente manera
“La suma de dos números combinatorios de iguales
numeradores y denominadores sucesivos es un nuevo número combinatorio cuyo
numerador es una unidad mayor que la de los numeradores de los sumandos
y cuyo denominador es igual al mayor de los denominadores de los sumandos”,
y se simboliza:
æ n - 1ö æ n - 1ö æ n ö
çç ÷÷ + çç ÷÷ = çç ÷÷ ;
èi -1 ø è i ø èi ø
Demostración: aplicando la definición, escribimos para cada número combinatorio de la

igualdad, factorial del numerador, dividido el factorial del denominador que multiplica al
factorial de la diferencia:
(n - 1) ! +
(n - 1) ! = n !
(i - 1) !×[(n - 1) - (i - 1)]! i !×(n - 1 - i ) ! i!×(n - i ) !
que puede simplificarse eliminando paréntesis en el segundo factor del denominador del
primer término del primer miembro y ordenando de manera conveniente el segundo factor
del denominador del segundo término del primer miembro:
(n - 1) ! + (n - 1) ! = n ! ;
(i - 1) !×[n - i ]! i !×(n - i - 1) ! i !(× n - i ) !
teniendo en cuenta que:
i != i × (i - 1) !
(n - i ) != (n - i ) × (n - i - 1) !
multiplicamos y dividimos el primer término del primer miembro por i y el segundo término
del primer miembro por (n - i ) , resultando:
14
i × (n - 1)! (n - i ) × (n - 1) ! = n!
+
i × (i - 1) !×[n - i ] ! i !×(n - i ) × (n - i - 1) ! i !×(n - i )!
i! (n - i )!
i × (n - 1) ! (n - i ) × (n - 1) ! n!
+ =
i !×(n - i ) ! i !×(n - i ) ! i !×(n - i ) !
por tener el primer miembro denominador común:
i × (n - 1) !+(n - i ) × (n - 1) ! n!
= ;
i !×(n - i ) ! i !×(n - i ) !
vemos ahora que el numerador del primer miembro tiene como factor común (n - 1)!;
operando convenientemente:
(n - 1) !×(i + n - i ) = n !
i !×(n - i ) ! i !×(n - i ) !
(n - 1) !×(n ) = n !
i !×(n - i ) ! i !×(n - i ) !
siendo el numerador del primer miembro igual a n!, la observación b3 transformada en
propiedad queda demostrada para cualquier valor de n, es decir, para cualquier potencia.
Aplicación de los números combinatorios al cálculo de los coeficientes del desarrollo

de la potencia de orden n de un binomio.
Según hemos visto, el desarrollo de la potencia n-ésima de un inomio

puede escribirse;
(a + b )n = æçç
n ö n 0 æ n ö n -1 1 æ n ö n - 2 2 ænö æ n ö n -( n -1) n -1 æ´n ö 0 n
÷÷a b + çç ÷÷a b + çç ÷÷a b + .... + çç ÷÷a n -ibi + .... + çç ÷÷a b + çç ÷÷a b
è0ø è1 ø è2ø èi ø è n - 1ø èn ø
que para las potencias comprendidas entre 0 y 4 toma el aspecto;

(a+b)o = 1
(a+b)1= 1a1b0 +1a0b1
(a+b)2= 1a2b0+2a1b1+1a0b2
(a+b)3= 1a3b0+3a2b1+3a1b2+1a0b3
(a+b)4= 1a4b0+4a3b1+6a2b2+4a1b3+1a0b4
o lo que es igual, expresados los coeficientes como números combinatorios:

æ0ö
(a+b)o = çç ÷÷
è0ø
æ1 ö æ 1ö
(a+b)1= çç ÷÷ a1b0 + çç ÷÷ a0b1
è0ø è 1ø
æ 2ö æ 2ö æ 2ö
(a+b)2= çç ÷÷ a2b0+ çç ÷÷ a1b1+ çç ÷÷ a0b2
è0ø è1 ø è 2ø
æ3ö æ 3ö æ3ö æ 3ö
(a+b)3= çç ÷÷ a3b0+ çç ÷÷ a2b1+ çç ÷÷ a1b2+ çç ÷÷a0b3
è0ø è1 ø è 2ø è 3ø
15
æ 4ö æ 4ö æ 4ö æ 4ö æ 4ö
(a+b)4= çç ÷÷ a4b0+ çç ÷÷ a3b1+ çç ÷÷ a2b2+ çç ÷÷ a1b3+ çç ÷÷ a0b4
è0ø è1 ø è 2ø è3ø è 4ø
estos desarrollos pueden escribirse en forma simplificada, cuando interesan solamente los
coeficientes:
æ0ö
(a+b)o çç ÷÷
è0ø
æ 1 ö æ 1ö
(a+b)1 çç ÷÷ çç ÷÷
è 0 ø è 1ø
æ 2ö æ 2ö æ 2ö
(a+b)2 çç ÷÷ çç ÷÷ çç ÷÷
è 0 ø è1 ø è 2 ø
æ 3 ö æ 3ö æ 3 ö æ 3ö
(a+b)3 çç ÷÷ çç ÷÷ çç ÷÷ çç ÷÷
è 0 ø è1 ø è 2 ø è 3 ø
æ 4ö æ 4ö æ 4ö æ 4ö æ 4ö
(a+b)4 çç ÷÷ çç ÷÷ çç ÷÷ çç ÷÷ çç ÷÷
è 0 ø è1 ø è 2 ø è 3 ø è 4 ø
observándose en todos los desarrollos que:
a) El primero y el último coeficiente son iguales a la unidad (verificar que para cualquier
ænö ænö
potencia çç ÷÷ y çç ÷÷ son iguales a la unidad.
è0ø ènø
b) El segundo y el anteúltimo coeficiente son iguales a la potencia.
c) Cualquier coeficiente puede obtenerse, de acuerdo con la segunda propiedad de los
números combinatorios, sumando los dos que en el triángulo tiene encima; por
ejemplo
æ 3 ö æ 3ö æ 4ö
çç ÷÷ + çç ÷÷ = çç ÷÷
è 2 ø è 3ø è3ø
(recordar que: “La suma de dos números combinatorios de iguales numeradores
y denominadores sucesivos es un nuevo número combinatorio cuyo numerador
es una unidad mayor que la de los numeradores de los sumandos y
cuyo denominador es igual al mayor de los denominadores de los sumandos”,
Estas observaciones permiten “traducir” el triángulo de los números combinatorios a un

triángulo aritmético, que recibe el nombre de Triángulo de Tartaglia o de Pascal y que se
desarrolla:
1 1
1 2 1
1 3 3 1
1 4 6 4 1
16
1 5 10 10 5 1
y así siguiendo...
Término general del desarrollo:
ænö
Tiene la forma; Ti = çç ÷÷a n -ibi
èi ø
Atención: el cuarto término de un desarrollo tiene i = 3 ya que i, recordamos, va desde 0

hasta n.
Ejemplo 1: Hallar los términos de (a+b)3
æ3ö æ 3ö
T0 = çç ÷÷a3b0 = a3 ; T1 = çç ÷÷a 2b1 = 3a 2b
è0ø è1 ø
æ3ö æ 3ö
T2 = çç ÷÷a1b3 = 3ab 2 ; T3 = çç ÷÷a 0b3 = b3
è 2ø è 3ø
Ejemplo 2: Calcular el término inicial del desarrollo de (3 x - 2 y )7
æ7ö
T0 = çç ÷÷(3 x )7 (- 2 y )0 = 1 × 37 × x 7 = 2187 x 7
è0ø
Ejemplo 3: Calcular el quinto término para el binomio del ejemplo anterior:
(para el 5to. término debemos considerar i = 4)
æ7ö
T4 = çç ÷÷(3 x )3 (- 2 y )4 = 35 × 27 × x3 × 16 y 4 = 15.120 x3 y 4
è 4ø
7
Ejemplo 4: Calcular el término de grado uno en el desarrollo de æç 3 x - ö÷
1
è xø
( )
i
æ7ö æ 1 ö æ7ö 1 æ7ö
Ti = çç ÷÷ × 37 -i × x 7 -i ç - ÷ = çç ÷÷ × 37 -i × x 7 -i × (- 1)i × i = çç ÷÷ × 37 -i × (- 1)i × x 7 - 2i
èi ø è x ø èi ø x èi ø
como el grado del término buscado debe ser uno; 7-2i = 1 que nos da i = 3
æ7ö
entonces, T3 = -çç ÷÷ × 37 -3 × x 7 - 2×3 = -35 × 81 × x = -2835 × x
è3ø
7
Ejemplo 5: calcular el cuatro término del desarrollo de æç 3 x - ö÷
1
è xø
17
Utilizamos la tabla
n - i +1 7 6 5
i 0 1 2 3
coef. i 1 7 21 35
1
T3 = 35 × 34 × (- 1)3 × x 4 × 3 = -35 × 81 × x = -2835 × x
x
Ejemplo 6: calcular los coeficientes del desarrollo de (a+b)43:
n - i +1 43 42 41 40 39 38 37 36 35 34
i 0 1 2 3 4 5 6 7 8 9 10
coef .i 1 43 903 12341 123410 962598 6,1x106 3,2x107 1,5x108 5.6x108 1,9x109
n - i +1 33 32 31 30 29 28 27 26 25 24 23
i 11 12 13 14 15 16 17 18 19 20 21
coef .i 5,8x10 1,5x101 3,7x101 7,8x101 1,6x101 2,7x101 4,2x101 6,1x101 8,0x101 9,6x101 1,1x101
9 0 0 0 1 1 1 1 1 1 2
18

Análisis Combinatorio

Cargado por

Copyright:

Formatos disponibles

Análisis Combinatorio

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Análisis Combinatorio

Cargado por

Copyright:

Formatos disponibles

Análisis Combinatorio 1

Álgebra y Geometría Analítica

Conceptos preliminares. Principio fundamental del análisis combinatorio. La función

Combinatoria simple: Variaciones o Permutaciones simples de n elementos tomados

El interés del hombre por los juegos de azar viene indudablemente

Con el correr de los años, la Teoría de la Probabilidad encontró su

La Teoría de la Probabilidad representa el intento de la mente humana

El azar es un nombre que damos a nuestra ignorancia: que un dado al

Resulta entonces, que la complejidad del resultado de un fenómeno

Con el advenimiento de la Teoría de la Probabilidad se puso de

El lanzamiento de un dado o de una moneda, la extracción de un naipe

También son aleatorios el instante en que llegará un ómnibus a su

Los primeros ejemplos son sencillos de seguir ya que con comodidad y

Principio fundamental del Análisis Combinatorio: (también llamado principio

Si un determinado suceso, operación o acción puede ocurrir de n1

La estructura de diagrama de árbol permite no sólo obtener el número

Ejemplo 2: Supongamos que deseamos viajar de la ciudad A hasta la ciudad C, pasando

Por cada ruta entre A y B hay tres elecciones posibles antes de

Este problema, como todos aquellos que corresponden al Análisis

El Análisis Combinatorio trata de las distintas maneras en que se

Notación de Factorial: Dado un número natural n, recibe el nombre de factorial de n (n!), el

Cuando el número n es muy grande no resulta sencillo el cálculo de

Pueden distinguirse tres problemas distintos estudiados en el

1) Variaciones o Permutaciones de n elementos tomados de a r. (r<n)

Se trata en consecuencia, de la estructuración de subconjuntos

Teniendo en cuenta que en los problemas del Análisis Combinatorio

Se debe entonces, construir subconjuntos del conjunto A en cada uno

Para comenzar, construimos las Variaciones de cuatro elementos

A partir de cada una de las V4,1 trataremos de construir las V4,2 .

Como puede observarse fácilmente, no resulta necesario escribir la

V4,2 = V4,1•3 = 4•3

A partir de las V4,2 siguiendo un razonamiento similar, construimos las

Vn,r = n(n-1)(n-2)(n-3)............[n-(r-1)] ; que equivale a:

Utilizando la notación de factorial, si multiplicamos y dividimos el segundo miembro de la

Ejemplo: Utilizaremos la última expresión deducida para calcular V1000,4

1000 ! 1000 ! 1000 • 999 • 998 • 997 • 996 !

Se trata ahora de estructurar subconjuntos de un conjunto dado

Si tomamos como punto de partida para la estructuración de una

(a2) (a1,a4) (a1,a4,a3)

3) Combinaciones de n elementos tomados de a r.

Se trata en este caso de conformar subconjuntos de un conjunto dado,

A los efectos de obtener la correspondiente expresión de recurrencia,

{a1,a2,a3} ; {a1,a2,a4} ; {a1,a3,a4} ; {a2,a3,a4}

Si a partir de estos subconjuntos, escribimos las permutaciones de los

(a1,a2,a3) (a1,a3,a2) (a2,a1,a3) (a2,a3,a1) (a3,a1,a2) (a3,a2,a1)

Como las ternas ordenadas de la tabla anterior han sido obtenidas

V4,3 = C4,3 •P3

Potencia de un binomio. Introducción. Estructura de los términos. Estructura

Potencia de un binomio.(El binomio de Newton).

Para encontrar una expresión de recurrencia que nos permita obtener el

En los desarrollos precedentes pueden realizarse las siguientes

a1) el número de términos es igual a la potencia mas uno (n+1).

b) respecto de la formación de los coeficientes:

con los coeficientes de los segundos miembros de las igualdades se ha formado un

Como veremos y justificaremos posteriormente, esta última

Para ejemplificarla observación efectuada en b4) volvamos al

El cálculo puede generalizarse utilizando la expresión:

resultando los coeficientes de (a+b)6 iguales a 1 6 15 20 15 6 1

Ahora nuestro triángulo numérico puede ampliarse a:

El cálculo que hemos realizado puede tabularse, permitiendo una gran