Upload
joaquin-zucchet
View
217
Download
0
Embed Size (px)
DESCRIPTION
Apuntes para Álgebra.
Citation preview
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 1/10
1
COMBINATORIA
La Combinatoria es la parte de las Matemática que estudia las diversas formas deagrupar los elementos de un conjunto, cuantificando dichas agrupaciones.
NOCIONES PREVIAS:
FACTORIALSe define por inducción:
0 N nSi : 1!0
1!1
2)!1.(! n sinnn
Ejemplo
5! = 5.4! = 5.4.3! = 5.4.3.2! = 5.4.3.2.1! = 5.4.3.2.1
Propiedad: n! = n.(n-1).(n-2)……….1 para n1
Se prueba por inducción:
Para n = 1 : 1! = 1 por definición.
Para n = h : h! = h.(h-1).(h-2)…..1 ( Hipótesis inductiva)
Para n = h+1: (h+1)! = (h+1).h! (por definición) =
= (h+1).h.(h-1).(h-2)……1 (por hipótesis inductiva)
Por lo tanto: n! = n.(n-1).(n-2)……….1
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 2/10
2
PRINCIPIO DE MULTIPLICACIÓN
Si una actividad A1 puede ser realizada mediante k 1 procedimientos, luego para cada
una de estas formas de A1 otra actividad A2 puede ser realizada por k 2 métodos, después
cada una de estas , tanto de A1 como de A2, una tercera actividad A3 puede ser efectuada
por k 3 procedimientos, etc...y así sucesivamente hasta una m-ésima actividad Am, la cual puede ser realizada mediante k m métodos, entonces "A1 y A2 y A3 y ... y Am" se
pueden efectuar de k 1·k 2·k 3·...·k m formas posibles.
Ejemplo :
Tres carreteras principales unen la población A con la población B; y dos
carreteras principales unen la población B con la población C.
Determinar el número de formas de realizar un viaje de la población A a la
población C; pasando por la población B.
Para ir de A a B existen 3 posibilidades y para ir de B a C hay 2 posibilidades.De este modo, conforme al Principio de Multiplicación existen 3.2 = 6 formas de
realizar el viaje.
COMBINATORIA
Existen distintas formas de agrupar los elementos de un conjunto, según se repitan
elementos o no, según se puedan tomar todos los elementos de que disponemos o no y si
influye o no el orden de colocación de los elementos:
COMBINATORIA SIMPLE
VARIACIONES SIN REPETICIÓN
Las variaciones sin repetición de m elementos tomados de n en n se definen como
las distintas agrupaciones formadas con n elementos distintos, eligiéndolos de entre los
m elementos de que disponemos, considerando un grupo distinto de otro tanto si
difieren en algún elemento como si están situados en distinto orden.
Fórmula:
)!(
!)1().........2).(1.(
nm
mnmmmmV nm
Ejemplo :
¿Cuantos números de tres cifras distintas se pueden formar con las nueve cifras
significativas del sistema decimal?
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 3/10
3
Al tratarse de números el orden importa y además nos dice "cifras distintas" luego no
pueden repetirse.
Por tanto, se pueden formar 504 números :
PERMUTACIONES SIN REPETICIÓN
Las permutaciones sin repetición de n elementos se definen como las distintas formas
de ordenar todos esos elementos distintos, por lo que la única diferencia entre ellas es el
orden de colocación de sus elementos.
Fórmula:
!
1
!
!0
!
)!(
!n
nn
nn
nV P n
nn
Ejemplo :
Con las letras de la palabra DISCO ¿cuantas palabras distintas se pueden formar?
Evidentemente, al tratarse de palabras el orden importa. Y además n = m, es decir
tenemos que formar palabras de cinco letras con cinco elementos D, I, S, C, O que no
están repetidos.
Por tanto, se pueden formar 120 palabras :
COMBINACIONES SIN REPETICIÓN:
Las combinaciones sin repetición de m elementos tomados de n en n se definencomo las distintas agrupaciones formadas con n elementos distintos, eligiéndolos de
entre los m elementos de que disponemos, considerando un grupo distinto de otro sólo
si difieren en algún elemento, (No influye el orden de colocación de sus elementos).
Fórmula:
)!!.(!nmn
mC nm
Ejemplo :
Cuantos grupos de 5 alumnos pueden formarse con los treinta alumnos de una clase.
(Un grupo es distinto de otro si se diferencia de otro por lo menos en un alumno)
No importa el orden (son grupos de alumnos). No puede haber dos alumnos iguales en
un grupo evidentemente, luego sin repetición.
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 4/10
4
Por tanto, se pueden formar 142506 grupos distintos :
COMBINATORIA CON REPETICIÓN
VARIACIONES CON REPETICIÓN
Las variaciones con repetición de m elementos tomados de n en n se definen como
las distintas agrupaciones formadas con n elementos que pueden repetirse, eligiéndolosde entre los m elementos de que disponemos, considerando un grupo distinto de otro
tanto si difieren en algún elemento como si están situados en distinto orden.
Fórmula:
nn
m mVR
Ejemplo :
¿Cuantos números de tres cifras se pueden formar con las nueve cifras significativas
del sistema decimal?
Al tratarse de números el orden importa y además no dice nada sobre "cifras distintas"
luego si pueden repetirse.
Por tanto, se pueden formar 729 números :
PERMUTACIONES CON REPETICIÓN:
Llamamos permutaciones con repetición de n elementos cuando en los n elementosexisten elementos repetidos (un elemento aparece a veces, otro b veces, otro c veces,
etc) verificándose que a+b+c+...=n.
Fórmula:
!!!
!,,
cba
n PR
cba
n
Ejemplo :
¿De cuántas maneras distintas pueden colocarse en línea nueve bolas de las que 4 son
blancas, 3 amarillas y 2 azules?
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 5/10
5
El orden importa por ser de distinto color, pero hay bolas del mismo color (están
repetidas) y además n = m, es decir colocamos 9 bolas en linea y tenemos 9 bolas para
colocar.
Por tanto, tenemos 1260 modos de colocarlas :
COMBINACIONES CON REPETICIÓN:
Las combinaciones con repetición de m elementos tomados de n en n se definencomo las distintas agrupaciones formadas con n elementos que pueden repetirse,
eligiéndolos de entre los m elementos de que disponemos, considerando un grupodistinto de otro sólo si difieren en algún elemento, (No influye el orden de colocación
de sus elementos).
Fórmula:n
nm
n
m C CR 1
Ejemplo :
En una confitería hay cinco tipos diferentes de pasteles. ¿De cuántas formas se pueden
elegir cuatro pasteles?
No importa el orden (son pasteles). Puede haber dos o más pasteles del mismo tipo en
un grupo, se trata entonces de combinaciones con repetición.
Por lo tanto tenemos 70 formas de elegirlos:
70)!15(!4
!84
145
4
5
C CR
Pautas para la resolución de problemas
Si en cada agrupación figuran sólo algunos de los elementos disponibles,
importando el orden de colocación de éstos, entonces es un problema de
variaciones. Si en cada agrupación figuran todos los elementos disponibles, importando su
orden de colocación, entonces se trata de un problema de permutaciones. Si en cada agrupación figuran sólo algunos de los elementos disponibles, sin
importar el orden de colocación de éstos, entonces estamos ante un problema de
combinaciones.
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 6/10
6
NÚMEROS COMBINATORIOS
Se define número combinatorio o coeficiente binómico como el valor numérico de las
combinaciones ordinarias (sin repetición) de un conjunto de m elementos tomados engrupos de n, siendo m y n dos números enteros y positivos tales que m ≥ n.
Matemáticamente, un número combinatorio se expresa como:
)!!.(
!,
nmn
mC
n
mnm
Los números combinatorios se leen «m sobre n».
Propiedades de los números combinatorios
Los números combinatorios presentan algunas propiedades muy interesantes que
justifican el amplio uso que se hace de ellos en algunas ramas científicas:
Los números combinatorios complementarios son iguales
nm
m
n
m
porque :
)!(!
!
nmn
m
n
m
y
n
m
nnm
m
nmmnm
m
nm
m
!)!(
!
))!(()!(
!
Cualquier número sobre 0 es igual a 1.
10
m
Porque1
!.1
!
)!0(!0
!
0
m
m
m
mm
Todo número sobre sí mismo es igual a 1.
1
m
m
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 7/10
7
Porque por la primera propiedad
10
m
m
m
Un número sobre 1 es siempre igual al número.
mm
1
Porquem
m
mm
m
mm
)!1(1
)!1.(
)!1(!1
!
1
Triángulo de Tartaglia
En el siglo XVI, el italiano Tartaglia propuso un triángulo regular de números tales
que:
Todas las filas del triángulo comienzan y terminan en 1, y son simétricas con
respecto al valor central.
Cada número del triángulo es igual a la suma de los dos situados encima de él
(salvo los extremos).
La suma de todos los elementos de cada fila coincide con el valor 2n, siendo n el
orden de la fila.
Esta disposición es de tipo combinatorio y se conoce como triángulo de Tartaglia o de
Pascal.
Este triángulo adquiere particular significación si se expresa en forma de números
combinatorios, y ayuda a comprender las propiedades de los mismos.
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 8/10
8
BINOMIO DE NEWTON
Vamos a deducir la fórmula que nos permitirá elevar un binomio a cualquier potencia de
exponente natural n. Esto es la forma de obtener
Para ello veamos como se van desarrollando las potencias de (a + b) :
Observando los coeficientes de cada polinomio resultante vemos que siguen esta
secuencia
O sea que cada uno de esos números corresponde al valor de un número combinatorio
así:
nba
baba 1
222
2 bababa 32232223
332 babbaababababababa
43223434464 babbabaabababa
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 9/10
9
Por otra parte, observando las potencias de (a+b) de nuevo vemos que las potencias de
a empiezan elevadas a n, va disminuyendo uno a uno hasta llegar a cero. A los
exponentes de b les ocurre lo contrario.
Y ya podemos escribir la fórmula general del llamado binomio de Newton
que también se puede escribir de forma abreviada así:
En general el término de lugar h en el desarrollo de es
1)1(
1
hhn
h bah
nT
Ejemplos:1) 5)32( y x
54322345 )3(5
5)3)(2(
4
5)3()2(
3
5)3()2(
2
5)3()2(
1
5)2(
0
5 y y x y x y x y x x
La fila 5 del triángulo de Tartaglia es: 1, 5, 10, 5, 10, 5, 1 ; que serán los valores de los
coeficientes.
2) Calcular sin desarrollar el término que ocupa el lugar 50 en el desarrollo de:
(a2+3/b)100
=
nnnnnnb
n
nab
n
nba
nba
na
nba
1221
1...
210
nh
h
hhnnba
h
nba
0
n
ba
49
512
50
3
49
100
baT
49
4910228 3
..10.89,9 ba
7/17/2019 APUNTES COMBINATORIA
http://slidepdf.com/reader/full/apuntes-combinatoria 10/10
10