MATEMTICA I

MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
Considerando los elementos de un conjunto, se trata de saber, cuales y cuntos son los distintos ordenamientos o agrupaciones que se pueden obtener con los elementos de un conjunto, de manera tal que todos y cada uno de ellos (ordenamiento o agrupaciones) tenga el mismo nmero de componentes. Interesa adems, saber calcular su nmero sin necesidad de formarlos y contarlos. Para resolver el problema fundamental del anlisis combinatorio se prescinde de la naturaleza de los elementos, pero no de su ordenamiento, pues en algunos casos resulta imprescindible. En combinatoria se utilizan y definen tres formas o mtodos de obtener los distintos ordenamientos o agrupaciones; cada uno de los cuales posee caractersticas propias, que surgen de las condiciones impuestas en la definicin. Estos tres mtodos o formas de agrupaciones son: variaciones, permutaciones y combinaciones, las cuales a su vez cada una de ellas pueden ser: simples o con repeticin. ANLISIS COMBINATORIO SIMPLE 1. VARIACIONES, ARREGLOS O DISPOSICIONES Dados m objetos a, b, c,., h, k, l, llmese variaciones, arreglos o disposiciones de los m objetos tomndolos de a n, o tomados de n en n o n-arios (siendo nm), a los grupos de objetos que se pueden formar de modo que: 1) En cada grupo entran n de los m objetos. 2) Dos grupos se consideran distintos cuando difieren, o bien en alguno de los objetos, o bien en el orden que van colocados. Si son m los elementos y n el nmero de orden (nmero de elementos de cada grupo) las
n n variaciones las simbolizaremos: Vm,n o Vm . (Otras notaciones utilizadas son Am,n o Am o bien

Dm,n o Dn ) m
Por ejemplo, dados los elementos a, b, c, d, donde m = 4, se tienen: Variaciones Monarias: grupos tomados de a 1 elemento, es decir V4,1 . Ellas son: (1) a b c d 4 grupos distintos

Variaciones Binarias: grupos tomados de a 2 elementos, es decir V4,2 . Ellas son: ab (2) ba ca da ac bc cb db ad bd cd dc 12 grupos distintos

Variaciones Ternarias: Si se toman los grupos de 3 en 3, es decir V4,3 . Ellas son: abc (3) bac cab dab abd bad cad dac acb bca cba dba acd bcd cbd dbc adb bda cda dca adc bdc cdb dcb 24 grupos distintos

Finalmente, si se toman grupos de 4 en 4, tendremos

Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich) 1

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
Variaciones Cuaternarias: es decir V4,4 . Ellas son: (4) abcd abdc acbd 24 grupos distintos

............................................... ............................................... ...............................................

En cada uno de los cuatro cuadros, se observa que cada arreglo es distinto de los dems porque vara el orden o porque posee algn elemento diferente. Formacin de los arreglos o variaciones Dados m objetos: a, b, c, d,., k, l En primer lugar, los arreglos de a uno, son los elementos mismos: (1) a, b, c, d,., k, l

Para formar los arreglos binarios de los m objetos, tomemos cada arreglo de a uno y coloqumosle despus cada uno de los restantes objetos. Por el arreglo a que figura en (1) se obtiene: ab, ac, ad,ah, ak, al, y as tambin de los dems. En consecuencia todos los arreglos binarios se pueden escribir en un cuadro: ab, ac, ....ak, al ba, bc, ....bk, bl ... (2) ... ka, kb, ....kh, kl la, lb, .......lh, lk Para formar los arreglos de a tres, se usa el mismo procedimiento: a partir de cada uno de los arreglos de (2) se le agregan sucesivamente al la derecha todos los objetos que faltan, obtenindose as todos los arreglos ternarios: abc, abd, abk, abl acb, acd,.....ack, acl ... ... (3) alb, alc, alh, alk bac, bad, bak, bal ... ... lka, lkb, ., lkh Y as sucesivamente. Se observa que el proceso es general y se podrn formar los arreglos n-arios.

Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich)

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
Nmero de arreglos o variaciones En la generalidad de los casos, ms que saber cuales son los grupos posibles, interesa saber cuntos son. Para ello se sigue un procedimiento inductivo:
1 Segn (1), el nmero de arreglos monarios es: Vm = m

En el cuadro (2) se observa que cada arreglo de un elemento se ha combinado con los (m 1) elementos restantes en consecuencia:
2 1 Vm = Vm (m 1) 2 Vm = m (m 1)

En el cuadro (3) se observa que cada uno de los arreglos binarios se ha combinado con los (m 2) elementos restantes, o sea:
3 2 Vm = Vm (m 2) 3 Vm = m (m 1) (m 2)

Si se hubiesen formado los arreglos cuaternarios de igual forma, se vera que:

4 3 Vm = Vm (m 3) 4 Vm = m (m 1) (m 2) (m 3)

Y as sucesivamente, hasta llegar a:

n n Vm = Vm1 [m (n 1)] n n Vm = Vm1 (m n + 1)

o Se conviene que Vm = 1

Ordenando las variaciones de los sucesivos rdenes y multiplicando miembro a miembro se obtiene:
1 Vm = m 2 1 Vm = Vm (m 1)

3 2 Vm = Vm (m 2) 4 3 Vm = Vm (m 3)

.......................... ..........................
n n Vm1 = Vm2 (m n + 2) n n Vm = Vm1 (m n + 1)

n ( ) ) Vm = m 44444(m42444(44443) 1 m 1 4 2 ....... m n + 1 n factores

O sea que el nmero de arreglos de m elementos de orden n es igual al producto de n factores decrecientes a partir de m.
Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich) 3

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
2. PERMUTACIONES Formacin de las permutaciones Se llaman permutaciones de m objetos a las variaciones de orden m de esos mismos objetos. Como en cada permutacin intervienen los m objetos, dos permutaciones solo pueden diferir en el orden en que estn agrupados sus elementos. Por ejemplo: Las permutaciones de las letras A, B, C son: ABC; ACB; BAC; BCA; CAB; CBA Donde se observa que en todas figuran las tres letras dispuestas en distinto orden. Nmero de permutaciones Designando como Pm al nmero de permutaciones de m objetos; por definicin se tiene que:
m Pm = Vm

Basta hacer n = m en la frmula de los arreglos, en consecuencia el ltimo factor es:

mm+1=1
y como los factores van disminuyendo en una unidad, el penltimo ser 2, el antepenltimo 3, etc. En consecuencia:
m Pm = Vm = m (m 1) (m 2) ....... 3 2 1

Formas usuales para expresar el nmero de permutaciones El producto de los m primeros nmeros naturales distintos de cero se llama factorial de m y se lo representa por m!. En consecuencia, la frmula que da el nmero de permutaciones de m objetos se puede escribir as:

Pm = m (m 1) (m 2) ....... 3 2 1

3. COMBINACIONES Se llaman combinaciones n- arias (monarias, binarias, ternarias, etc.) de m objetos (con y n m), o combinaciones de m objetos tomados de a n por vez, a los distintos m, n grupos que se pueden formar de manera tal que: 1) En cada grupo entran n de los m objetos. 2) Dos grupos se consideran distintos cuando difieren en alguno de los elementos que lo forman. En las combinaciones solo se tienen en cuenta los objetos que intervienen en ellas y no en el orden en que estn agrupados en las mismas. Formacin de las combinaciones Consideremos, por ejemplo, cuatro elementos A, B, C, D, en el orden en que las escribimos. Cada una de esas letras constituye una combinacin de primer orden o monaria de los mismos. C1 4

( )

Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich)

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
Las combinaciones de segundo orden o binarias se pueden obtener agregando a la derecha de cada una de las de primer orden, cada uno de los objetos que le siguen: AB; AC; AD; BC; BD; CD

(C )
2 4

Las combinaciones de tercer orden se obtienen agregando a la derecha de cada una de las de segundo orden cada uno de los objetos dados que siguen al ltimo de los que figuran en ella, entonces: ABC; ABD; ACD; BCD C3 4 Y finalmente las de cuarto orden: ABCD C4 4 Nmero de combinaciones Si consideramos, por ejemplo, las combinaciones de tercer orden de las letras A, B, C, D y debajo de cada una de ellas expresamos todas las permutaciones que pueden hacerse con sus elementos, obtenemos todos los arreglos de tercer orden de dichas letras:
C3

( )

( )

64444 744444 44 8 ABC ABD ACD BCD ACB ADB ADC BDC BAC BAD CAD CBD P3 BCA BDA CDA CDB CAB DAB DAC DBC CBA DBA DCA DCB
3 Observando el cuadro anterior, se deduce que: V4 = C3 P3 = 4 6 = 24 4

Razonando en forma anloga para el caso de Cn , o sea que formamos todas las Cn y con cada m m una de ellas formamos todas las permutaciones posibles, o sea Pn se obtiene en total:
n Cn Pn = Vm m

de donde resulta:
n Vm m (m 1) (m 2) ........ (m n + 1) = Pm n!

Cn = m

NMERO COMBINATORIO El nmero de combinaciones de m objetos tomados de a n en n se denomina tambin nmero combinatorio y se lo simboliza de la siguiente manera:

m Vn = Cn = m m n n!
Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich) 5

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
Por ejemplo:

8 V3 8 7 6 = C3 = 8 = = 56 8 3 3! 3 2 1
Otra forma de expresarlo es:
n m Vm m (m 1) (m 2) ........ (m n + 1) = = n n! n!

y multiplicando numerador y denominador por (m n) se tiene: !

m m (m 1) (m 2) ....... (m n + 1) (m n) (m n 1) ........ 3 2 1 = n n!(m n)! m m! = n n!(m n)!

Propiedades de los nmeros combinatorios

1)

m =1 0 m m! = 0 0!(m 0)! = 1 m m! = 0 m! = 1 0! m m! = 0 m! = 0!
m =1 m m m! = m m!(m m)! = 1 m m! = m m!0! = 1

0! = 1

2)

3) Nmeros combinatorios complementarios Definicin: Dos combinaciones del mismo nmero de objetos son complementarias cuando la suma de sus rdenes es igual al nmero de objetos:

m m y n m n son complementarios ya que n + m n = m

Propiedad: los nmeros combinatorios complementarios son iguales.
Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich) 6

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
m m = n m n m! m! = n!(m n)! (m n)![m (m n)] ! m! m! = n!(m n)! (m n)!n!
4) La suma de dos nmeros combinatorios de igual base (nmero de objetos), y de rdenes consecutivas (n 1 y n) da por resultado el nmero combinatorio de orden n y base inmediatamente superior.

m 1 m 1 m n 1 + n = n (m 1)! (m 1)! (m 1)! (m 1)!(m n) + = + = (n 1)![(m 1) (n 1)] n!(m 1 n)! (n 1)!(m n)! n (n 1)!(m n)! ! m m! (m 1)!(n + m n) = = n (n 1)!(m n)! n!(m n)! n
m! = m (m 1)! (m n)! = (m n 1)!(m n) (m n 1)! = (m n)! mn

Tringulo de Tartaglia
0 Considerando que C1 = m y Cm = 1 y que 0! = 1, para un valor dado de m, dicho tringulo m

permite calcular con facilidad todas las Cn . Procedemos as: m

0 0 En una primera fila se colocan: C1 = C1 = 1 , en una segunda fila C2 , C1 , C2 , en una 1 2 2 0 0 2 tercer fila C3 , C1 , C2 , C3 , hasta que en una ensima fila se colocan Cn , C1 , Cn ,.............Cn . Se 3 3 3 n n

obtiene un tringulo aritmtico llamado tringulo de Tartaglia, en el que cada trmino es la suma de los dos ms cercanos de la fila anterior:

1 1 1 1 1 1 1 1 8 7 28 6 21 56 5 15 35 4 10 3 6 2

1 1 3 4 10 20 35 70 56 15 21 28 5 6 7 8 1 1 1 1 1 1

Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich)

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
Generalizacin de los nmeros combinatorios La mxima generalizacin conveniente la constituye el smbolo , definido por: m

V V(V 1) (V 2) ........ (V n + 1) = n! n (I) V = 1 0

Por ejemplo:

(n = 1, 2, 3......)
siendo V

2 / 5 4 =

2 5

2 2 2 2 3 1 2 3 5 5 5 5 5 = 4!

8 5 24

13 5 = 624 1 = 26 625 24 625

( 1) ( 2) 3,14 2,14 1,14 = 1,276724 3 3! 6 (3,14) (4,14) (5,14) 11,136324 3 6

El smbolo se lee V sobre n como si fuera una fraccin, y el conjunto de los se llaman n n coeficientes binomiales. Para V = m entero y positivo, coincide con el nmero combinatorio n

Cn . m

De

las

propiedades

anteriormente

expresadas,

la

tercera

(nmeros

combinatorios

V complementarios), deja de tener sentido para , pero las otras valen con toda generalidad. m m

Obsrvese que tambin la (I) define , siendo m y n naturales tales que n > m, pero en tal n caso,

m = 0 pues en el numerador aparece el factor (m m) = 0 . n

Por ejemplo:

3 3 (3 1) (3 2) (3 3) (3 4) (3 5) = =0 6 6!

Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich)

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
ANLISIS COMBINATORIO CON REPETICIN Hasta ahora hemos supuesto que en cada variacin (arreglo), permutacin o combinacin, los objetos que intervienen son todos distintos entre si. Si se omite esa suposicin, se tendrn las variaciones, permutaciones o combinaciones con repeticin. 1. VARIACIONES CON REPETICIN Las variaciones o arreglos de m objetos, n-arios (monarios, binarios, etc.), concuerda con la definicin dada anteriormente para los arreglos simples sin ms que agregar a la condicin la clusula: no necesariamente distintos (los objetos). Formacin y nmero de variaciones o arreglos con repeticin Por ejemplo: los arreglos binarios con repeticin de cinco objetos a, b, c, d, e son: aa ba ca da ea ab bb cb db eb ac bc cc dc ec ad bd cd dd ed ae be ce de ee

V'5,2

En este ejemplo se aprecia como se forman los arreglos binarios a partir de los monarios (que no son sino los objetos mismos a, b, c, d, e), agregando a continuacin de cada uno de estos, sucesivamente todos los objetos. O sea que si llamamos:

V'm,n
V'm,1 = m V'm,2 = V'm,1 m
De igual manera, a partir de los arreglos binarios se forman los ternarios agregando sucesivamente todos los objetos a continuacin de cada uno de los binarios. En consecuencia, el nmero de arreglos binarios se ve multiplicado por m. Este es un procedimiento general que nos permite concluir diciendo que los arreglos n-arios de m objetos con repeticin, es igual al de orden (n 1) multiplicado por m. O sea:

V'm,n = V'm,n1 m
y si se conviene que Podemos deducir que

V'm,0 = 1 V'm,1 = m

V'm,2 = V'm,1 m = m m = m2

V'm,3 = V'm,2 m = m2 m = m3

V'm,n = m 44 2444 = mn m 1 m4....... 3

nveces

Como se observa, no hay inconveniente en que n>m.

Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich) 9

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
2. PERMUTACIONES CON REPETICIN Son las variaciones o arreglos m-arios de los m objetos. En consecuencia:

P'm = V'm,m
Por ejemplo: Si permutamos los objetos 1, 2, 3: 111 211 311 112 212 312 113 213 313 121 221 321 122 222 322 123 223 323 131 231 331 132 232 332 133 233 333

Permutaciones con grupos de elementos iguales Estos grupos presentan similitud con las permutaciones con repeticin, pero no deben confundirse. Sean dados un grupo p de elementos iguales; otro grupo q de elementos iguales entre s, pero distinto de los anteriores; otro grupo r de elementos iguales entre s y distinto de los anteriores; etc. Y, finalmente, otro grupo de t de elementos iguales entre s y distinto de todos los dems grupos. El nmero total de elementos u objetos es n = p + q + r + ..+ t. Se llaman permutaciones de los n elementos, de clase (p, q, r, .t) a las agrupaciones de los n objetos que difieran en la colocacin u orden en que van dispuestos. Su nmero ser:

n! p,q,r,....t = Pn p!q!r!...... t! p + q + r + ..........t = n

3. COMBINACIONES CON REPETICIN Las combinaciones con repeticin de m objetos tomndolos de n en n, o sea, narias, se definen como las combinaciones simples, sin ms que agregar a la definicin la clusula de que los n objetos que forman cada combinacin no son necesariamente distintos. Dados m objetos, si deseamos formar combinaciones simples, stas solamente pueden ser de rdenes 1, 2, 3, .., m. En cambio, si formamos combinaciones con repeticin, stas podrn ser de cualquier orden, por grande que sea. Por ejemplo: Con los objetos a, b, c se pueden formar binarias: aa ab ac bb bc cc Ternarias: aaa aab aac abb abc acc bbb bbc bcc ccc
4 4 C'3,4 = C3 + 4 1 = C6

C'3,2 = C2 + 2 1 = C2 . 3 4

3 C'3,3 = C3 + 3 1 = C5 3

Cuaternarias: aaaa aabb aacc abbb abcc accc bbbb bbcc bccc cccc aaab aabc abbc bbbc aaac

En general:

m + n 1 C'm,n = n
10

Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich)

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO

PRODUCTO DE FACTORES BINOMIALES CON UN TRMINO COMN (x + a) (x + b) = x2 + (a+b) x + ab (x + a) (x + b) (x + c) = [x2 + (a+b) x + ab] (x + c) = x3 + (a+b+c) x2 + (ab+ac+bc) x + abc (x + a) (x + b) (x + c) (x + d) = [x3 + (a + b + c) x2 + (ab + ac + bc) x + abc] (x + d) =
= x4 + x3d + (a + b + c) x3 + x2(a + b + c) d + x2(ab + ac + bc) + x (ab + ac + bc) d + x abc + abcd =

x4 + x3 (a + b + c + d) + x2(ab + ac + ad + bc + bd + cd) + (abc + abd + acd + bcd) x + abcd ........................... En general:

n n-1

(x + a). (x + b). (x + c)(x + i). (x + j). (x + k) =

x + x (a + b + c + + i + j + k) + xn-2(ab + ac + + jk) + xn-3(abc + .. + ijk) + + x ([Link] + . + bc..jk) + [Link] BINOMIO DE NEWTON

(x + a)

6444444 74444444 4n 8 = (x + a) (x + a) ............ (x + a)

(x + a)n = xn

+ xn 1 (a + a + .... + a) + xn 2 (aa + aa + .... + aa) +

+ xn 3 (aaa + aaa + .... + aaa) + ..... + x aa....a + ..... + aa....a + aaa....a 123 123 1 24 4 3 n 1 n n 1
A continuacin se calcula cada uno de los coeficientes de las x:
n 1 es (a + a + .... + a) = n a El coeficiente de x

El coeficiente de xn2 es (aa + aa + .... + aa) = a2 + a2 + .... + a2 Cada trmino es a

2

y el nmero de esos trminos es el nmero de combinaciones de n elementos

2 a tomados de dos en dos, es decir trminos iguales a a , o sea: 2

(aa + aa + .... + aa) = (a24442.... + a2 ) = n a2 + a2 + 1 4443

n 2

El coeficiente de xn 3 es

(aaa + aaa + .... + aaa) = (a3

+ a3 + .... + a3 , cada trmino es a3 y el

nmero de esos trminos es el nmero de combinaciones de los n elementos a tomados de 3 en 3, es decir trminos iguales a a3 , o sea: 3

(aaa + aaa + .... + aaa) = (a34442.... + a3 ) = n a3 + a3 + 1 4443

n 3

Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich)

11

MATEMTICA I
MATERIAL DE APOYO

UNIVERSIDAD NACIONAL DE CUYO FACULTAD DE CIENCIAS APLICADAS A LA INDUSTRIA Ingenieras y Profesorado

ANLISIS COMBINATORIO
Anlogamente,

n 1 . El nmero de El coeficiente de x es aa....a + ...... + aa....a , donde cada trmino es igual a a 123 123

esos trminos es el nmero de combinaciones de n elementos a tomados de (n 1) en (n 1) ,

n 1 es decir n 1 trminos iguales a a , o sea:

n 1

n 1

aa....a + ...... + aa....a = an 1 + an1 + ..... + an 1 = n an 1 123 123 14444 24444 3 n 1 4 4 n 1 n1 n

n 1

n a El ltimo trmino es a 44 244 a = a 1 a 4 .....4 3 n

Luego, reemplazando los coeficientes por los valores calculados, se obtiene:

(x + a)n = xn + n xn1 a + n xn2 a2 2

n + xn3 a3 + ..... + 3

n n 1 + an n 1 x a

que es la expresin de la llamada regla de Newton, la cual tambin puede escribirse as:

(x + a)n =
n n = xn + xn 1 a + 1 0 n n2 2 x a + .... + 2
n

n n k k x a + .... + k

n n n 1 + an n n 1 x a

O tambin, en general:

(a + b)n = n ank k k =0

bk

Algunas observaciones 1) El desarrollo de la potencia n-sima de un binomio tiene n+1 trminos, segn lo indica la variacin de k, desde 0 hasta n. 2) Se puede demostrar que el trmino de lugar h en el desarrollo es:

n n (h1) h 1 Th = b h 1 a

Profesor Rubn Lanieri (Colaboracin: Sandra Dimarco y Estela Simonovich)

12