1

1

Universidad �acional de La Plata

Facultad de Ciencias �aturales y Museo

Cátedra de Matemática y Elementos de Matemática

Asignatura: Matemática

Contenidos de la Unidad Temática nº 10 A�ÁLISIS COMBI�ATORIO

Conceptos preliminares. Principio fundamental del

Análisis Combinatorio. La función factorial. Fórmula

de Stirling.

Combinatoria simple: Variaciones, Permutaciones y

combinaciones.

a) Potencia de un binomio: Introducción. Estructura

de los términos y de los coeficientes. Tabla de cálculo

directo de los coeficientes. 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.

b) Combinatoria con repetición: Variaciones.

Permutaciones de n elementos y Permutaciones con

elementos indistinguibles. Permutaciones con

repetición

Ing. Carlos Alfredo López Profesor Titular

2

2

Facultad de Ciencias �aturales y Museo Cátedra de Matemática y Elementos de Matemática Asignatura: Matemática

Análisis Combinatorio

Ing. Carlos Alfredo López

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.

3

3

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••••....

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.

4

4

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.

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. 1

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)}

5

5

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 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:

nnenn 2 ! n −−−−••••ππππ≅≅≅≅ 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: 6969 ...)7128,2(69693,142 ! 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}:

6

6

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.

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

7

7

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).

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:

8

8

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:

!

)(

!))(1()3)(2)(1(,

rn

rnrnnnnnV rn

−

−−−••••−−−=

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:

)!(

!,

rn

nV rn

−=

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

9979989991000!996

!9969979989991000

!996

!1000

!)41000(

!10004,1000 •••=

••••==

−=

V

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)

9

9

(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 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) (a1,a2,a4) (a1,a4,a2) (a2,a1,a4) (a2,a4,a1) (a4,a1,a2) (a4,a2,a1) (a1,a3,a4) (a1,a4,a3) (a3,a1,a4) (a3,a4,a1) (a4,a1,a3) (a4,a3,a1) (a2,a3,a4) (a2,a4,a3) (a3,a2,a4) (a3,a4,a2) (a4,a2,a3) (a4,a3,a2)

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

10

10

o bien: 3

3,43,4

P

VC =

que puede generalizarse: r

rnrn

P

VC

,, =

utilizando la expresión: ! r)-(n

! nV rn =,

llegamos a ! r)-(n! r! n

C r,n ====

11

11

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 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

12

12

encontrar el valor de un número de coeficientes equivalente a la parte

entera del cociente 2

n, teniendo en cuenta que, para todo n, el valor del

primer coeficiente es la 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).

coef. 1 = 41

41 =•

coef. 2 = 62

34 =•

coef. 3 = 43

26 =•

coef. 4 = 14

14 =•

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

coef. i = coef.i-1

+−

i

in 1 válida para todo i mayor o igual que uno.

Ejemplificamos para n = 6 coef. 0 = 1

coef. 1 = 1 61

61

1

116=•=

+−

coef. 2 = 6 152

56

2

126=•=

+−

coef. 3 = 15 203

415

3

136=•=

+−

13

13

coef. 4 = 20 154

320

4

146=•=

+−

coef. 5 = 15 65

215

5

156=•=

+−

coef. 6 = 6 16

16

6

166=•=

+−

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:

1+− in

7

6

5

i 0 1 2 3 coef. i 1 7 21 35

y para la potencia n = 15 (calculamos siete coeficientes)

1+− in

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

14

14

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:

300354321

11121314155,15

5

5,15===

••••

••••C

P

V

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;

1+− in

n

n-1

n-2

n-3

…

…

n-i+1

…

…

i 0 1 2 3 4 … … i … … coef. i 1 coef. i ... ...

coef. i = i

innnnn

••••

+−−−−

....4321

)1).......(3)(2)(1(;

multiplicando y dividiendo el segundo miembro por (n-I)!

coef. i =)!(!

!

)!(....4321

)!)(1).......(3)(2)(1(

ini

n

ini

ininnnnn

−=

−•••••

−+−−−−

que escribimos:

coef.i = )!(!

!

ini

n

i

n

−=

; al símbolo

i

n lo denominamos indistintamente

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á:

( ) 40312213044

4

4

3

4

2

4

1

4

0

4babababababa

+

+

+

+

=+

y para la potencia n:

( ) nnnniinnnnnba

n

nba

n

nba

i

nba

nba

nba

nba

01)1(22110 ´

1........

210

+

−++

++

+

+

=+

−−−−−−

expresión en la cual cada uno de los coeficientes puede obtenerse a partir del primero

0

n=1. mediante la fórmula

+−⋅

−=

i

in

i

n

i

n 1

1;

15

15

por ejemplo, para el desarrollo de (a+b)7:

...

353

521;

3

137

2

7

3

7

2137;2

127

1

7

2

7

771,1

117

0

7

1

7

siguiendoasíy

=⋅=

+−⋅

=

=⋅=

+−⋅

=

=⋅=

+−⋅

=

3

7 " " " " "

2

7 " " " " "

1

7 a igual es que lo

o de manera más rápida como se explicara y desarrollara en la tabla

1+− in

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

i

iinnba

i

nba

0

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) .

La igualdad

i

n=

− in

n que corresponde a la simetría de los

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. 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

16

16

nuestra igualdad:( )[ ]!)!(

!

)!(!

!

innin

n

ini

n

−−−=

−; eliminando el paréntesis del

segundo factor del denominador del segundo miembro, resulta: !)!(

!

)!(!

!

iin

n

ini

n

−=

−⋅; lo

que significa que, 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:

43

4

1

4;1

4

4

0

4=

=

=

=

:

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:

=

−+

−

−

i

n

i

n

i

n 1

1

1;

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:

( )( ) ( ) ( )[ ]

( )( ) ( )!!

!

!1!

!1

!11!1

!1

ini

n

ini

n

ini

n

−⋅=

−−⋅

−+

−−−⋅−

−

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:

( )( ) [ ]

( )( ) ( )!!

!

!1!

!1

!!1

!1

ini

n

ini

n

ini

n

−⋅=

−−⋅

−+

−⋅−

−;

teniendo en cuenta que: ( )

( ) ( ) ( )!1!

!1!

−−⋅−=−

−⋅=

ininin

iii

multiplicamos y dividimos el primer término del primer miembro por i y el segundo término del primer miembro por ( )in − , resultando:

( )( ) [ ]

( ) ( )( ) ( ) ( )!!

!

!1!

!1

!!1

!1

ini

n

inini

nin

inii

ni

−⋅=

−−⋅−⋅

−⋅−+

−⋅−⋅

−⋅

17

17

!i ( )!in −

( )( )

( ) ( )( ) ( )!!

!

!!

!1

!!

!1

ini

n

ini

nin

ini

ni

−⋅=

−⋅

−⋅−+

−⋅

−⋅

por tener el primer miembro denominador común: ( ) ( ) ( )

( ) ( )!!

!

!!

!1!1

ini

n

ini

ninni

−⋅=

−⋅

−⋅−+−⋅;

vemos ahora que el numerador del primer miembro tiene como factor común )!1( −n ; operando convenientemente:

( ) ( )( ) ( )!!

!

!!

!1

ini

n

ini

inin

−⋅=

−⋅

−+⋅−

( ) ( )( ) ( )!!

!

!!

!1

ini

n

ini

nn

−⋅=

−⋅

⋅−

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;

( ) nnnniinnnnn ban

nba

n

nba

i

nba

nba

nba

nba 01)1(22110 ´

1........

210

+

−++

++

+

+

=+

−−−−−−

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:

(a+b)o =

0

0

(a+b)1=

0

1a1b0 +

1

1a0b1

(a+b)2=

0

2a2b0+

1

2a1b1+

2

2a0b2

(a+b)3=

0

3a3b0+

1

3a2b1+

2

3a1b2+

3

3a0b3

(a+b)4=

0

4a4b0+

1

4a3b1+

2

4a2b2+

3

4a1b3+

4

4a0b4

18

18

estos desarrollos pueden escribirse en forma simplificada, cuando interesan solamente los coeficientes:

(a+b)o

0

0

(a+b)1

0

1

1

1

(a+b)2

0

2

1

2

2

2

(a+b)3

0

3

1

3

2

3

3

3

(a+b)4

0

4

1

4

2

4

3

4

4

4

observándose en todos los desarrollos que:

a) El primero y el último coeficiente son iguales a la unidad (verificar que para

cualquier potencia

0

n y

n

n son iguales a la unidad.

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

2

3 +

3

3 =

3

4

(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

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

y así siguiendo...

19

19

Término general del desarrollo:

Tiene la forma; iini ba

i

nT

−

=

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

330

3231

2

2121

3030

3

3;3

2

3

31

3;

0

3

bbaTabbaT

babaTabaT

=

==

=

=

==

=

Ejemplo 2: Calcular el término inicial del desarrollo de ( )723 yx −

( ) ( ) 777070 21873123

0

7xxyxT =⋅⋅=−

=

Ejemplo 3: Calcular el quinto término para el binomio del ejemplo anterior:

(para el 5to. término debemos considerar i = 4)

( ) ( ) 4343434 120.1516273523

4

7yxyxyxT =⋅⋅⋅=−

=

Ejemplo 4: Calcular el término de grado uno en el desarrollo de 7

13

−x

x

( ) ( ) ( )iiii

iiii

iii x

ixx

ixx

iT 2777777 13

7113

713

7 −−−−−−⋅−⋅⋅

=⋅−⋅⋅⋅

=

−⋅⋅

=

como el grado del término buscado debe ser uno; 7-2i = 1 que nos da i = 3

entonces, xxxT ⋅−=⋅⋅−=⋅⋅

−=

⋅−−283581353

3

7 327373

20

20

Ejemplo 5: calcular el cuatro término del desarrollo de 7

13

−x

x

Utilizamos la tabla

1+− in

7

6

5

i 0 1 2 3 coef. i 1 7 21 35

( ) xxx

xT ⋅−=⋅⋅−=⋅⋅−⋅⋅= 283581351

13353

4343

Ejemplo 6: calcular los coeficientes del desarrollo de (a+b)43:

1+− in 43 42 41 40 39 38 37 36 35 34

i 0 1 2 3 4 5 6 7 8 9 10

icoef . 1 43 903 12341 123410 962598 6,1x106 3,2x107 1,5x108 5.6x108 1,9x109

1+− in 33 32 31 30 29 28 27 26 25 24 23

i 11 12 13 14 15 16 17 18 19 20 21

icoef . 5,8x109 1,5x1010 3,7x1010 7,8x1010 1,6x1011 2,7x1011 4,2x1011 6,1x1011 8,0x1011 9,6x1011 1,1x1012

21

21

Combinatoria con repetición: Variaciones con repetición de n elementos tomados de a r. Permutaciones con repetición de n elementos. Permutaciones con elementos indistinguibles. Combinaciones con repetición.

Variaciones con repetición:

Llamamos Variaciones con repetición de n elementos

tomados de a r (V*n,r) a los distintos ordenamientos que pueden efectuarse con los n

elementos del conjunto que se estudia, teniendo en cuenta que en cada ordenamiento

puede repetirse cualquier elemento hasta r veces. Por tal razón para este tipo de

combinatoria r puede ser menor, mayor o igual que n.

Para encontrar una fórmula de recurrencia que nos permita

calcular el número de las V*n,r comenzamos a partir del conjunto A = {a1 , a2 , a3 , a4} a

construir las V*4,1 que no pueden ser distintas a las V4,1 resultando:

(a1)

(a2)

(a3)

(a4)

Por tratarse de Variaciones con repetición, cada uno de los

subconjuntos que componen las V*4,1 podrá originar 4 conjuntos binarios, ya que, al

permitirse la repetición, todos los elementos de A, pueden ser utilizados. En efecto:

(a1,a1)

(a1,a2)

(a1) (a1,a3)

(a2) (a1,a4)

(a3)

(a4)

resultando en la última columna: V*4,2 = 4••••4 = 42

Como cada vez que hagamos una nueva ramificación podremos estructurar 4 nuevos

subconjuntos inferimos, sin más trámite, que: V*n,r = n r

Las variaciones con repetición pueden utilizarse para resolver un problema que en Estadística recibe el nombre de “muestreo con repetición” Si tenemos

22

22

un bolillero con m bolillas numeradas de 1 a m y se van extrayendo una a una r bolillas con el cuidado de anotar el número de cada una de las que salen y previamente a sacar la siguiente reponerlas en el bolillero, se obtiene un conjunto de r números que pueden o no ser repetidos. Se obtiene así un conjunto ordenado (a1, a2, a3.... ar) donde los ai pueden repetirse hasta r veces que recibe el nombre de “muestra de tamaño r” tomada de un conjunto de m elementos, permitiéndose la repetición. El número total de muestras posibles de tamaño r corresponde a las V*n,r = n r NOTA IMPORTANTE: Cuando el número r alcanza el valor de n, debería escribirse V*n,n = n n. Es preferibie, cuando esto sucede y en cada uno de los subconjuntos interviene un número de elementos igual a n, cambiar el nombre de Variaciones por el de Permutaciones con repetición de n elemendos, simbolizándose P*n = nn

Permutaciones con elementos indistinguibles

Sea ahora un conjunto formado por n elementos, entre los cuales hay algunos que son distintos pero indistinguibles entre sí; por ejemplo consideremos un conjunto formado por tres tizas blancas, dos verdes y una azul. Se trata de un conjunto de 6 tizas con las cuales resulta posible efectuar 6! = 720 permutaciones.

Sin embargo, como es fácil entender, cuando a partir de un ordenamiento cualquiera se permuten entre sí, por ejemplo, la posición de dos tizas blancas, la permutación resultará distinta pero indistinguible de la que le dio origen.

Cuando se nos presenta este problema, la solución al mismo

consiste en hallar el número de permutaciones distinguibles (las que se obtienen sólo al intercambiar la posición de elementos que resulten distinguibles: dos tizas de distinto color)

Sea entonces el conjunto T = {B;B;B;V;V;A}. El número total de permutaciones que pueden realizarse con los elementos del conjunto T es, como ya hemos visto de 6! = 720 permutaciones simples.

El diagrama arborescente nos permitirá encontrar el número de

permutaciones distinguibles: para ello comencemos por identificar las tizas de igual color mediante un subíndice:

T= {B1;B2;B3;V1;V2;A}

23

23

En una primera ramificación colocaremos las permutaciones distinguibles, cuyo número nos es desconocido:

X ?

(B1;B2;B3;V1;V2;A)

(B1;B2;V1;B3;V2;A)

(B1;B2;V1;B3;A;V2)

(V1;V2;A;B1;B2;B3)

(las líneas punteadas indican que no se conoce el número de las permutaciones distinguibles: no se conoce el número de ramas en la primera ramificación). Llamamos X (incógnita) al número de elementos de dicha columna.

A partir del conjunto de las permutaciones distinguibles cuyo

número X desconocemos, comenzamos a desarrollar las siguientes ramas de la estructura de árbol. Cada una de las permutaciones distinguibles dará origen a 3! permutaciones como consecuencia del intercambio en la posición de las Bi

X ?

(B1;B2;B3;V1;V2;A)

(B1;B2;V1;B3;V2;A)

(B1;B2;V1;B3;A;V2) X••••3!

(V1;V2;A;B1;B2;B3)

(V1;V2;A;B1;B3;B2)

(V1;V2;A;B1;B2;B3) (V1;V2;A;B2;B1;B3)

(V1;V2;A;B2;B3;B1)

(V1;V2;A;B3;B1;B2)

(V1;V2;A;B3;B2;B1)

resultando que el número total de permutaciones de la segunda columna es X••••3!.

Con similar razonamiento, pueden obtenerse permutaciones distintas pero indistinguibles en una tercera columna, cambiando el ordenamiento de las V (tizas verdes), como se desarrolla en el esquema de la página siguiente:

24

24

(B1;B2;B3;V1;V2;A)

(B1;B2;V1;B3;V2;A)

(B1;B2;V1;B3;A;V2)

X••••3!

(V1;V2;A;B1;B2;B3)

(V1;V2;A;B1;B3;B2)

(V1;V2;A;B2;B1;B3)

(V1;V2;A;B1;B2;B3) X••••3!••••2!

(V1;V2;A;B2;B3;B1) (V1;V2;A;B3;B1;B2)

(V1;V2;A;B3;B1;B2)

(V1;V2;A;B3;B2;B1) (V1;V2;A;B3;B2;B1)

Como en la última columna habrá por cada uno de los subconjuntos de la anteúltima columna 2! permutaciones, el número total de las permutaciones, distinguibles e indistinguibles, cuyo número es igual a 720, resultará:

X••••3!••••2! =6! =720

de donde: ! 2 ! 3

! 6X

••••====

Si en un conjunto de n elementos existen n1 distintos entre sí pero indistinguibles; otros n2 elementos distintos entre sí pero también indistinguibles entre ellos, y así siguiendo..., el número de las permutaciones distinguibles que podrán obtenerse será:

••••••••••••••••

==== ! n ! n

! n P

21

;...n ; nn

21

Ejemplo: Calcular el número de permutaciones distinguibles que pueden obtenerse con las letras de la palabra NEUQUEN. Solución:

630! 2! 2 ! 2

!234567! 2 ! 2 ! 2

! 7P 2;2;2

7 ====••••••••

••••••••••••••••••••====

••••••••====

25

25

NOTA IMPORTANTE: La diferencia conceptual entre las Permutaciones con repetición y las Permutaciones con elementos indistinguibles es que mientras en las primeras los elementos del conjunto que se estudia son todos distintos y en los subconjuntos que se conforman pueden repetirse estos elementos hasta r veces, en las permutaciones con elementos indistinguibles el conjunto que se estudia tiene elementos que son distintos pero indistinguibles entre sí (caso de tres tizas blancas, dos verdes y una azul y, en cada uno de los subconjuntos que se estructuran intervienen todos los elementos con las repeticiones que marca el conjunto estudiado). Combinaciones con repetición:

Sea un conjunto { }4321 ,,, aaaaA = con los elementos del cual nos proponemos construir subconjuntos de tres elementos sin que interese el orden en que están ubicados los mismos,, permitiéndose la repetición de cualquiera de ellos hasta tres veces. Algunos de los subconjuntos resultantes pueden ser:

{ } { } { }321221111 ,,;,,;,, aaaaaaaaa ; decimos que cada grupo es una combinación con repetición de los cinco elementos del conjunto que se estudia tomados de a tres elementos. El número de los subconjuntos posibles se simboliza C*4,3. .

Como no interesa el ordenamiento interno en cada subconjunto,

los grupos { } { },,,, 2,12221 qaayaaa son la misma combinación con repetición..

El número de las C*4,3 puede obtenerse recurriendo a un artificio que efectúa una comparación con las combinaciones simples, es decir, con aquellas en las que no se permite la repetición.

El artificio puede ejemplificarse estableciendo una

correspondencia biunívoca entre las combinaciones con repetición de cuatro elementos tomados de a tres y las combinaciones simples de seis elementos tomados también de a tres La correspondencia que se establece tiene en cuenta las distintas posiciones de un elemento repetido en la combinación con repetición.

Trabajemos con los conjuntos

{ } { }65432143,21 ,,,,,,, ssssssSyrrrrR == ; con los elementos del

conjunto R escribiremos las combinaciones con repetición y con los del conjunto S las combinaciones simples, incrementando en las combinaciones simples el subíndice de cada elemento en tantas unidades como elementos le preceden en el respectivo subconjunto, es decir que el subíndice del 1º, 2º y 3º elementos correspondientes a la combinación con repetición de elementos r se incrementan en 0,1 y 2 unidades para conformar la combinación simple de elementos s). Valga como ejemplo; { } { }431221 ,,,, sssrrr →

26

26

CORRESPONDENCIA CORRESPONDENCIA { } { }321111 ,,,, sssrrr →

{ } { }421211 ,,,, sssrrr → { } { }521311 ,,,, sssrrr →

{ } { }621411 ,,,, sssrrr →

{ } { }431221 ,,,, sssrrr →

{ } { }531321 ,,,, sssrrr →

{ } { }631421 ,,,, sssrrr →

{ } { }541331 ,,,, sssrrr →

{ } { }641431 ,,,, sssrrr →

{ } { }651441 ,,,, sssrrr →

{ } { }432222 ,,,, sssrrr →

{ } { }532322 ,,,, sssrrr →

{ } { }632422 ,,,, sssrrr →

{ } { }542332 ,,,, sssrrr →

{ } { }642432 ,,,, sssrrr →

{ } { }652442 ,,,, sssrrr →

{ } { }543333 ,,,, sssrrr →

{ } { }643433 ,,,, sssrrr →

{ } { }653443 ,,,, sssrrr →

{ } { }654444 ,,,, sssrrr →

Habiéndose desarrollado el cuadro anterior que expresa la

correspondencia biunívoca entre las combinaciones con repetición de cuatro elementos tomados de a tres y las combinaciones simples de seis elementos tomados también de a tres, puede obtenerse el número de las primeras , calculando el número de las segundas. Simbólicamente:

C*4,3 = C6,3

Generalizando esta expresión para conjuntos de n elementos y subconjuntos de r elementos, puede escribirse:

C*n,r = Cn+r-1,r

27

27

Cuestionario de Repaso.

1) Defina factorial de un número n. 2) Enuncie el principio fundamental del análisis combinatorio. 3) Explique en que casos debe usarse la fórmula de Stirling. 4) Diferencie los conceptos de combinatoria simple y con repetición. 5) Enuncie los problemas que puede resolver la combinatoria simple. 6) Explique como es la estructura de los términos en el desarrollo de la potencia

n.ésima de un binomio. 7) Explique como es la estructura de los coeficientes de cada término en el

desarrollo de la potencia n-ésima de un binomio. 8) Escriba el término i-ésimo del desarrollo. 9) Defina los coeficientes binomiales o números combinatorios. 10) Demuestre las propiedades de los números combinatorios. 11) Escriba la forma condensada del Binomio de Newton. 12) Describa los problemas del análisis combinatorio con repetición.

28

28

PROBLEMAS DE COMBINATORIA

Nota: siendo una de las dificultades fundamentales en la resolución de problemas de Combinatoria la identificación del tipo del mismo (combinatoria simple o con repetición y dentro de ellas el tipo de específico del cual se trata), el siguiente conjunto de problemas ha sido confeccionado ex-profeso sin ordenamiento temático Ejercicio nº 1: Las matrículas de los vehículos automotores de la República Argentina constan de tres letras seguidas de tres dígitos. ¿cuál es el número de patentes distintas que pueden construirse si para cada conjunto de letras existe el número 000? Rta: 19.683.000 Ejercicio nº 2: Una organización consta de veintiseis miembros. ¿De cuántas maneras distintas se pueden elegir un presidente, un secretario y un tesorero, si una misma persona no puede ocupar más de un cargo? Rta: 15.600 Ejercicio nº 3: Se va a conformar un comité de tres miembros para entrevistar al Director de una Escuela compuesto por un alumno de 5º año, uno de 4º y uno de 3º. Si hay tres candidatos de 5º año, 2 de 4º y 4 de 3º, determinar cuántos comités distintos pueden formarse empleando el principio fundamental de contar por un lado y el diagrama arborescente por otro. Rta: 24 Ejercicio nº 4: De cuántas maneras diferentes pueden ordenarse 5 bolas en una fila? Rta: 120 Ejercicio nº 5: De cuántas maneras pueden sentarse diez personas en una banca, si sólo hay cuatro lugares disponibles? Rta: 5040 Ejercicio nº 6: Se quieren sentar 5 hombres y 4 mujeres en una fila de manera tal que las mujeres ocupen los sitios pares. ¿De cuántas maneras distintas pueden sentarse? Rta: 2880 Ejercicio nº 7: ¿Cuántos números de cuatro cifras pueden formarse con los diez dígitos (0,1,2,3...9) si: el cero no puede ocupar la unidad de mil a) Los números pueden repetirse. b) Los números no pueden repetirse. c) Si el último dígito ha de ser cero y los números no pueden repetirse. Rta: a) 9000; b) 4536; c) 504 Ejercicio nº 8:

29

29

Cuatro libros distintos de matemática, seis diferentes de física y dos diferentes de química se colocan en un estante. ¿ De cuántas formas distintas es posible ordenarlos si: a) los libros de cada asignatura deben estar todos juntos? b) Solamente los libros de matemática deben estar juntos. Rta: a) 207.360; b) 8.709.120 Ejercicio nº 9: De cuántas formas puede elegirse una comisión de cinco personas entre nueve? Rta: 126 Ejercicio nº 10: Cuántos tipos distintos de ensalada pueden prepararse con lechuga, zanahoria, berro y remolacha? Rta: 15 Ejercicio nº 11: Con siete consonantes y cinco vocales diferentes, ¿cuántas palabras distintas pueden formarse, que consten de cuatro consonantes y tres vocales? (no es necesario que las palabras tengan significado lingüístico) Rta: 1.764.000 Ejercicio nº 12:

Demostrar que

−−−−====

rn

n

r

n

Ejercicio nº 13:

Demostrar que

====

−−−−++++

−−−−

−−−−

r

n

r

1n

1r

1n

Ejercicio nº 14:

Hallar el término constante en el desarrollo de 12

2

x1

x

++++

Rta: 495 Ejercicio nº 15:

Escribir el desarrollo de n)ba( ++++ si el término general tiene el aspecto i)in( b a i

n −−−−

Ejercicio nº 16: Utilizando la notación de ∑∑∑∑ generar una expresión de recurrencia que permita

obtener el desarrollo de la potencia n-sima de un binomio cualquiera. Ejercicio nº 17: Se deben colocar en una única fila un conjunto de quintillizos, uno de cuatrillizas y uno

de trillizos, todos vestidos con un uniforme. De cuántas maneras posibles distinguibles

podrán alinearse? Rta: 27.720

Ejercicio nº 18:

De cuantas maneras puede elegirse un concejo municipal entre seis hombres y cinco

mujeres, si el concejo debe estar compuesto por tres hombres y dos mujeres?

30

30

Rta: 200

Ejercicio nº 19

Escribir sin efectuar el desarrollo el décimo término del desarrollo de 10

2

+y

x

Ejercicio nº 20: Tenemos 6 personas A, B, C, D, E. F, que participan de una competencia. Tres de estas personas serán finalistas ocupando el primero, segundo y tercer puesto. No se admiten empates y cada uno obtiene medallas diferentes. Nos interesa estudiar todas las formas posibles en que estos lugares pueden ocuparse.

a) Calcular la cantidad de formas diferentes en que pueden ocuparse los

tres puestos. Rta: 120 b) Es necesario enumerar todos los casos posibles para responder la

pregunta anterior? Proponer una estrategia para responder la pregunta a) sin recurrir a la descripción de todos los casos.

c) Puede ser A, B,A uno de los resultados posibles ? d) Si sabemos que B ocupará el primer lugar, de cuantas formas distintas

pueden ocuparse los puestos ? Rta: 20

Ejercicio nº 21 En un club hay 100 socios en condiciones de aspirar a los cargos de presidente, vicepresidente, secretario y tesorero. Cuantas listas distintas pueden formarse si una persona fija debe ocupar el cargo de tesorero? Rta: 941.094 Ejercicio nº 22 : En una cajita hay fichas del mismo tamaño numeradas del 1 al 9. Presentamos el siguiente juego : Sacar tres fichas, una después de la otra, sin reponerlas en la caja, colgando cada ficha de un cartel preparado para tal fin. Pagamos lo mismo que la apuesta que se realice si el número resulta par. En caso contrario nos quedamos con la apuesta. Quien tiene ventaja y porqué? Ejercicio nº 23: : Una persona necesita hablar por teléfono pero no recuerda bien el número que consta de siete cifras.. Sabe que demora un minuto en marcar y preguntar si es el lugar donde desea comunicarse. Cuanto demorará como máximo para hablar con quien desea en cada uno de los siguientes casos ? : a) Si recuerda que la característica tiene tres números y comienza con 4 y además

todos los números que componen el teléfono son distintos. Rta: 42 días b) Si recuerda que la característica tiene tres números y puede comenzar conl

cualquier dígito, que todos los dígitos que componen el teléfono son distintos y que además, aparece el 1 seguido del 2 en algún lugar.

Rta: 28 días Ejercicio nº 24: : Queremos poner en fila a 7 personas entre las que se encuentran Ariel y Marta. a) De cuantas formas diferentes podemos hacerlo si Marta debe estar

siempre primera ? Rta: 720

31

31

b) De cuantas formas diferentes podemos hacerlo si Ariel y Marta nunca pueden estar juntos ? Rta: 3600

c) De cuantas formas podemos alinearlas si entre Marta y Ariel siempre debe haber exactamente tres personas ? Rta: 720

Ejercicio nº 25: En una población d 20.000 habitantes, una persona le rumorea algo a otra persona, quien lo repite a una tercera, etc... En cada paso, se escoge aleatoriamente el receptor del rumor. De cuántas formas distintas puede pasar un rumor 10 veces sin volver a la persona que lo originó ? Rta: 1,02 x 1043 Ejercicio nº 26: Discutamos ahora el siguiente problema: En un curso de 25 alumnos queremos elegir 3 de ellos para formar un equipo de fútbol. Si suponemos que todos ellos pueden ser jugadores ; cuántos equipos diferentes ;podrían formarse ? Antes de comenzar a resolver este problema, haremos algunas preguntas : a) Existe alguna diferencia entre este problema y el Problema 20? b) Si existe tal diferencia, explicar su incidencia en el cálculo. Encontrar una estrategia para responder el cuestionario anterior, para lo cual se propone simplificar las cantidades trabajando con un curso de cuatro alumnos A = {a1, a2, a3, a4} formando equipos de 3 alumnos elegidos entre ellos. Nota: para resolver un problema en el que el orden no es importante, debemos recurrir a otros conocidos en los que el orden importa. No necesitamos confeccionar todo un cuadro que represente la totalidad de posibilidades cada vez que se presente un problema de este tipo, pero es importante que tengamos siempre presente su estructura. Rta: 2300 Ejercicio nº 27: Si en lugar de tener 25 alumnos el curso tiene 40 y queremos formar equipos de 3 personas cada uno : cuántos equipos diferentes pueden armarse si previamente se ha elegido uno de los cuarenta alumnos como arquero para todos los equipos? Rta: 741 Ejercicio nº 28: En un pueblo pequeño hay 5000 habitantes, 40% hombres y 60% mujeres. Se eligen grupos de 5 personas. a) cuantos grupos diferentes pueden formarse para asistir a un programa de televisión

en representación del pueblo ? Rta: 2,6 x 1016 b) Cuántos grupos, para asistir al programa podemos armar si debe haber tres mujeres

y dos hombres ? Rta: 8,99 x 1015 c) Si el grupo es para ocupar la presidencia, vicepresidencia y tres secretarías con

igual jerarquía de una empresa de la localidad : cuántos grupos distintos podrán armarse ? Rta: 5,2 x 1917

Ejercicio nº 29: Cuántas palabras distintas, sin importar que tengan o no sentido, pueden formarse con las letras de la palabra ÁRIDO y cuántas con las letras de la palabra ARADA ? Rta: 120 y 20

32

32

Ejercicio nº 30

Tenemos 7 bolitas blancas y 3 negras que deseamos ordenar en fila. De cuántas

maneras distintas puede hacerse la ordenación. Rta: 240:

Ejercicio nº 31: Calcular el factorial del número 50 utilizando la fórmula de Stirling. Verificarlo por medio de la función factorial. Ejercicio nº 32:

Verificar que el número de combinaciones con repetición de tres elementos tomados de a 2, puede calcularse transformándolo a un problema de la Combinatoria Simple. Ejercicio nº 33: Diez personas se saludan mediante un apretón de manos. Cuántos apretones de manos hubo? Rta: 45 Ejercicio nº 34: Cuántos abonados telefónicos pueden obtenerse si cada número tiene siete cifras y en todos los casos el primer número es un cuatro? Rta: un millón de abonados. Ejercicio nº 35: En una caja hay seis tizas, una blanca, una amarilla, una verde y tres rojas. Calcular el número de permutaciones indistinguibles o no identificables que pueden construirse con ellas. Rta: 600 Ejercicio nº 36: Hallar el número de diagonales de un octógono. Rta: 20 Ejercicio nº 37: Cuantas rectas se determinan uniendo 10 puntos del plano no alineados de a tres? Rta: 45 Ejercicio nº 38: Escribir una expresión de recurrencia que permita calcular el número de diagonales que tiene un polígono de n lados. Ejercicio nº 39: De cuántas maneras distintas se pueden colocar seis personas alrededor de una mesa circular? Rta: 120 Ejercicio nº 40: En un campeonato de fútbol de dos ruedas participan 18 equipos. Cuántos partidos deberán jugarse; Rta: 306

33

33

BIBLIOGRAFÍA:

DI CARO, Héctor: Algebra y Geometría Analítica.

ROJO, Armando: Algebra I y II.

FERNANDEZ Y SAGASTUME: Algebra.

KEMENY, SNELL, THOMPSON; Introducción a las Matemáticas

Finitas.