ap_combinatoria

8/6/2019 ap_combinatoria

1/25

COMBINATORIA

PREUNIVERSITARIA

Manuel Hernndez LuisVirginia Barcel


2/25

Combinatoria : Hernndez Barcel Pagina 1

INTRODUCCIONLa combinatoria es la rama de la matemtica que tiene por objeto el estudio de los diferentes agrupamientosy ordenaciones que pueden recibir los elementos de un conjunto, con independencia de la naturaleza de losmismos. A la hora de agrupar elementos de un conjunto, podemos tener presentes tres criterios:

- Considerar, o no, el orden de los elementos dentro de cada agrupacin.- Repetir, o no, los elementos dentro de cada agrupacin.- Decidir el nmero de elementos que tendrn las agrupaciones.

A cada manera de agrupar los elementos la llamaremos muestraEn definitiva, nuestro problema consistir en,

- dado un conjunto de m elementos- contar las maneras de agruparlos

- en grupos de n elementos- considerando un criterio para el orden

- y un criterio para la posibilidad de repeticin de los elementos.

Diagramas en rbolUna primera aproximacin al problema de contar las posibles muestras dados ciertos criterios, es empezarpor casos sencillos y representativos, y utilizar un diagrama de rbol para "dibujar" las posibles formas deir construyendo las agrupaciones.Una vez hecho el rbol (a veces basta con esbozarlo simplemente), se puede contar directamente en l elnmero de muestras posibles. O si no, se puede utilizar el rbol para deducir ese nmero. Al final, el rbolnos permitir deducir una frmula general para cada caso.

Luego, ya con las frmulas en la mano, slo hay que ver qu caso nos plantea un problema para aplicardirectamente la frmula adecuada, y... ya est!

Esta ltima frase es un poco optimista. No es que no sea cierta, pero, llegados a este punto, lo difcil verdaderamenteno es aplicar la frmula sino determinar en qu caso nos encontramos.

Para llegar hasta aqu, pues, es recomendable empezar por el principio y practicar cada caso hasta estar seguro de

haberlo comprendido .

Para que no tengamos ningn problema "de comunicacin" ms adelante, vamos a ponernos de acuerdo enla nomenclatura que utilizaremos. Las nuevas palabras son:* "rbol",* "raz",* "rama",* "nodo" o "nudo", y* "hoja".

* "nivel": La raz representa el nivel 0. Los nodos y las hojas estn en un nivel u otro segn las ramas que les separa de la raz.Cada rama aade un nivel. "camino" : cualquier recorrido por las ramas del rbol desde raz hasta alguna de las hojas.(es decir

mustra)

Enfocaremos el tema, pues, partiendo de un problema sencillo pero representativo del tipo de muestras que pueden

hacerse segn se apliquen los criterios ya mencionados


3/25


PERMUTACIONESP1.- Supongamos que organizo una carrera, en la que participan 5 corredores. De cuntas manerasposibles llegarn a la meta? (no se permite el abandono, ni cabe la posibilidad de un empate).Supongamosque mis corredores son: Alberto, Benito, Cirilo , Doroteo y Eustaquio. Los llamaremos A, B, C, D y E.

Veamos cmo puedo "montar" el rbol:Inicialmente, no hay nada. Empieza la carrera y va transcurriendo.

Entonces, llega el primer corredor a la meta.podra ser A, o B, o C, tambin D e incluso E.

Luego llegar el segundo corredor.Si primero lleg A, podra ser que ahora llegara B, o C, o D, o E.Pero si primero lleg B, ahora cabe que lleguen A, o C, o D, o E.etc...

Hasta aqu, nuestro rbol podra tener el siguiente aspecto

Si pasamos a ver quien llega en tercer lugar, quedarn siempre tres posibilidades, a saber:Si lleg primero A y luego B, puede ser que llegue a continuacin C, o D, o E.Pero si despus de A lleg C, llegar uno cualquiera de entre B, D o E.

La cuestin es la que se ve en el cuadro siguiente:- Si hay 5 corredores, tengo 5 posibles primeros puestos.

- Una vez determinado el primer puesto, me quedan 4 por llegar: por cada primero hay 4 posiblessegundos.

- Una vez s el primer y el segundo puesto, me quedan 3 por llegar: por cada primer y segundo puestohay 3 posibles terceros.

- Ahora an me quedan 2 por llegar: por cada primer, segundo y tercer puesto, hay 2 posibles cuartos.


4/25


- Y slo falta uno por alcanzar la meta: por cada 4 llegados a meta, hay 1 solo posible ltimo corredor.

y el rbol queda como sigue:

Observamos que:

Partiendo de la raz: 1r nivel de nodos

5 posibilidadescada posibilidad se multiplica por...2o nivel de nodos4 posibilidadesque a su vez se multiplican por...3o nivel de nodos3 posibilidadesque a su vez se multiplican por...4o nivel de nodos2 posibilidadesque finalmente se multiplican por...5o nivel de nodos1 posibilidad

Total: 5x4x3x2x1 posibles caminos desde la raz hasta las hojas

Eso es: 5! y se lee "5 factorial" o "factorial de 5". que en este caso da 120 caminos posibles.


5/25


Observar que lo que se ha hecho es contar el nmero de caminos diferentes que contiene el rbol.

Permutaciones, en generalAnalicemos la cuestin:

m elementos, (m=5, los 5 corredores) agrupados de m en m, (miro cmo llegan uno tras otro a la meta, sin dejarme ninguno) importa el orden, (quiero averiguar las diferentes llegadas a meta posibles. No es igual ABCDE que

EDCBA)

sin repetir elementos, (no va a llegar B dos veces en la misma carrera)

En estas condiciones, diremos que estamos ante una permutacin de m elementos

En el rbol, empezamos con m ramas y a cada nivel queda una rama menos. En total, hay m niveles.

La frmula es Pm=m!

Otros ejemplos:

P2.- Cuntos nmeros de 5 cifras distintas pueden hacerse con las cifras {1, 3, 5, 7, 9}?P3.- Con las letras de la palabra "SORTIJA" cuntas palabras distintas, con sentido o sin l, se puedenconstruir?P4.- Con las letras de la palabra "SORTIJA" cuntas palabras distintas, con sentido o sin l, se puedenconstruir que empiecen en vocal?P5.- De cuantas formas pueden quedar clasificados los 8 atletas finalistas olmpicos?P6.- Seis amigos, 3 chicos y 3 chicas , van al cine .De cuantas formas pueden sentarse si quieren estaralternados.


6/25


VARIACIONES

V1.- Supongamos que organizo una carrera, en la que participan 5 corredores. A los que ganan medalla(oro, plata y bronce) les hago una foto subidos al podium. Cuntas fotografas diferentes podra hacer?

(Se entiende por diferente que el medallista del oro en una foto fuese plata en otra, o incluso no ganaranada).

Supongamos otra vez que mis corredores son: Alberto, Benito, Cirilo, Doroteo y Eustaquio. Volvamos allamarlos A, B, C, D y E.

Veamos cmo puedo "montar" el rbol:

Inicialmente, no hay nada. Empieza la carrera y va transcurriendo.

Entonces, llega el primer corredor a la meta.podra ser A, o B, o C, tambin D e incluso E.

Luego llegar el segundo corredor.Si primero lleg A, podra ser que ahora llegara B, o C, o D, o E.Pero si primero lleg B, ahora cabe que lleguen A, o C, o D, o E.etc...

Hasta aqu, nuestro rbol podra tener el siguiente aspecto:

Si pasamos a ver quien llega en tercer lugar, quedarn siempre tres posibilidades, a saber:Si lleg primero A y luego B, puede ser que llegue a continuacin C, o D, o E.Pero si despus de A lleg C, llegar uno cualquiera de entre B, D o E.

La cuestin es la que se ve en el cuadro siguiente:- Si hay 5 corredores, tengo 5 posibles primeros puestos.


7/25


- Una vez determinado el primer puesto, me quedan 4 por llegar: por cada primero hay 4 posiblessegundos.- Una vez s el primer y el segundo puesto, me quedan 3 por llegar: por cada primer y segundo puesto

hay 3 posibles terceros.- Ahora an me quedan 2 por llegar. Pero estos ya no me importan.

Fijmonos en que, una vez s quin ocupar cada escaln del podium, ya tengo toda la informacin que

necesito para saber cuntas posibles fotografas puedo hacer.

y el rbol queda como sigue:

Observamos que:Partiendo de la raz: 1r nivel de nodos5 posibilidadescada posibilidad se multiplica por...2o nivel de nodos4 posibilidadesque a su vez se multiplican por...3o nivel de nodos3 posibilidades

Total: 5x4x3 posibles caminos desde la raz hasta las hojasEso es: 5!/2! que en este caso da 60 caminos posibles.


8/25


Observar que lo que se ha hecho es contar el nmero de caminos diferentes que contiene el rbol.

Variaciones, en general

Analicemos la cuestin: m elementos, (m=5, los 5 corredores) agrupados de n en n, (n=3, los tres primeros, que son los que me interesa ver en qu orden llegan) importa el orden, (quiero averiguar cuntas fotos del podium son posibles. No es igual ABC que

BCA)

sin repetir elementos, (no va a estar B en el escaln del oro y en el de la plata, a la vez)

En estas condiciones, diremos que estamos ante una variacin de m elementos, tomados en grupos de nelementos ("de n en n")

En el rbol, empezamos con m ramas y a cada nivel queda una rama menos..

La frmula es Vm,n=m!/(m-n)!

Otros ejemplos:V2.- Cuntos nmeros de 3 cifras distintas pueden hacerse con las cifras {1, 3, 5, 7, 9}?V3.- En una plantilla de 25 jugadores de ftbol, suponiendo que los jugadores son polivalentes, cuntasalineaciones del once titular se pueden hacer?V4.- Se sortean dos premios entre 14 personas, de forma que no pueden tocarle a la misma persona los dos.Cuntos resultados del sorteo son posibles?V5.- Cuntos partidos de Primera Divisin se juegan en una temporada de la liga espaola de ftbol?(Son20 equipos que juegan todos contra todos , una en casa y otra fuera)

V6.- Disponemos de 7 colores con los que hemos de pintar las tres franjas de una bandera sin repetirningn color. Cuntas banderas distintas salen?.


9/25


COMBINACIONESC1.- Supongamos que organizo una carrera, en la que participan 5 corredores. A los que ganan medalla(oro, plata y bronce) los invito a cenar. Cuntas cenas diferentes podra hacer?

Volvemos con los corredores Alberto, Benito, Cirilo, Doroteo y Eustaquio. Seguiremos llamndolos A, B,

C, D y E.

Veamos cmo puedo "montar" el rbol:

Inicialmente, no hay nada. Empieza la carrera y va transcurriendo.

Entonces, llega el primer corredor a la meta. Y, (cambiamos de estrategia!) esperamos a ver entrar lossiguientespodra ser A el primero, B el segundo y C, D o E el tercero. Consideremos ahora que el primero fue B.Bien pudiera llegar A el segundo y C el tercero, pero voy a contar con esta posibilidad? Qu ms me dainvitar a cenar a A y a B o a B y a A?! As que no considero el caso B-A porque el caso A-B ya locontempl en el primer camino del rbol. Y si B fue primero y C segundo, Tampoco voy a fijarme en el

caso que A entre tercero.Invitar a A, B y C a cenar es lo mismo que invitar a cenar a B, C y A!

Uf! Mejor ver cmo queda el rbol entero...

Notar que en un nivel, si del primer nodo salen cierto nmero de ramas, del siguiente nodo sale una ramamenos.El nmero de ramas va descendiendo a medida que avanzamos en niveles y en nodos.

Esto se debe a que no quiero repetir casos ya contemplados, porque el orden de llegada de los corredoresno me importa.

Contemos una vez ms el nmero de caminos del rbol, y obtendremos 10 cenas diferentes.


10/25


Combinaciones, en generalAnalicemos la cuestin:

m elementos, (m=5, los 5 corredores) agrupados de n en n, (n=3, los tres primeros, que son los que voy a invitar a cenar)

NO importa el orden, (una cena con A, B y C es como una cena con C, B y A) sin repetir elementos, (no voy a cenar con A y con A a la vez)

En estas condiciones, diremos que estamos ante una combinacin de m elementos, tomados en grupos den elementos ("de n en n")

En el rbol se aprecia la disminucin del nmero de ramas segn se avanza por los nodos y los niveles.

La frmula no es fcil de deducir del rbol, as que la deduciremos "pensando" un poco:

Podra contar las variaciones de m elementos en grupos de 3. Eso sera m!/(m-n)!. Pero entonces estaracontando los mismos casos ms de una vez. Debo dividir la cantidad encontrada por el nmero de veces que

voy a repetir casos. Cunto es esto?

Dado un grupo de n elementos (en nuestro ejemplo n=3, como el formado por A,B y C), cualquierpermutacin de esos n elementos me va a sobrar. El nmero de veces que puedo repetirlos es exactamentePn, o sea, n! (en nuestro ejemplo, repetir el tro A-B-C exactamente P3, o sea, 3!,=6 veces que serian :ABC,ACB,BAC,BCA,CAB,CBA). As que al total de grupos posibles he de eliminarle las veces que serepiten: dividiendo por n!

Y la frmula es Cm,n=m!/[(m-n)!n!]

Otros ejemplos:C2.- Entre un conjunto de 13 candidatos, cuntos equipos diferentes de 4 personas se pueden contratar?C3.- Entre un conjunto de 9 candidatos y 11 candidatas, cuntos equipos diferentes de 4 hombres y 5mujeres se pueden contratar?C4.- Dados 8 puntos no alineados tres a tres, Cuntas rectas diferentes determinan?C5.- Dados 8 puntos no alineados tres a tres, Cuntos tringulos diferentes determinan?C6.- Cuntos tringulos pueden formarse al unir tres vrtices de un polgono regular de 20 lados?


11/25


PERMUTACIONES CON REPETICIONPR1.- Tengo 3 caramelos de pia, dos de menta y uno de fresa. Los voy a repartir entre mis 6 amigos. Decuntas maneras puedo hacerlo?

Bien. Llamar a mis caramelos P, P, P, M, M, F.

Observar que, si a mi amiga Ana y a mi amigo Benito les doy un caramelo de pia, no importa qucaramelo de pia le d a cada uno. A ellos les parecer igual de bien.

Los 3 caramelos de pia son indistinguibles entre sLos 2 caramelos de menta son indistinguibles entre s

Adems,Para poder imaginarme el problema, supondr que tengo a mis amigos puestos en fila, por ejemplo, pororden alfabtico. Esto es para evitar contar los repartos siguientes como distintos:

Reparto 1: Reparto 2:Ana: P Benito: P

Benito: P Carlos: PCarlos: P Ana: PDelia: M Elena: MElena: M Delia: MFran: F Fran: F

Una vez tengo esto claro, es decir...fijados mis amigos en un orden dado,los posibles repartos los ir haciendo segn un rbol con un amigo en cada nivel:

Ana, Benito, Carlos, Delia, Elena, Fran.

Despus de la raz, empiezo a repartir por Ana:Tengo 6 posibilidades:

P, P, P, M, M o F.Una vez he dado el caramelo a Ana, sigo con Benito:Ahora tengo 5 posibilidades:

Si le di a Ana un caramelo de pia (P),me quedan para BenitoP, P, M, M o F.

Pero si le di a Ana otro de los caramelos de pia (otra vez P),me quedanP, P, M, M o F.

Tambin pude darle un caramelo de menta (M),entonces quedan para mi amigoP, P, P, M o F....

La cosa queda como en el rbol adjunto.


12/25


Pero en este rbol hay caminos repetidos!

Si cuento todos los caminos, el rbol es como el rbol de las permutaciones normales .Por tanto, la frmula sera

Pn=n!

Pero debo descartar,por cada 3 amigos a quienes haya dado los 3 caramelos de pia,las 3! maneras de dar 3 caramelos de pia a 3 amigos.

Eso lo hago dividiendo entre 3!(Si les doy pia a : A B y C ; tengo P3 = 3! = 6 formas de hacerlo y solo quiero una : ABC, ACB, BAC,BCA, CAB, CBA)

Tambin,por cada 2 amigos a quienes haya dado los 2 caramelos de menta,tengo que descartar las 2! maneras de repartir 2 caramelos de menta a 2 amigos.

Eso lo hago dividiendo entre 2!

Y finalmente,por cada posible amigo a quien se lo d,descartar las 1! maneras de repartir 1 caramelos de fresa a un amigo.

Eso lo hago dividiendo entre 1!

Me queda la siguiente cantidad de posibles repartos:

6! / (3! x 2! x 1!) = 60


13/25


Permutaciones con repeticin, en general

Si tenemos un conjunto de m elementos (en nuestro ejemplo m = 6 caramelos) reunidos en ggrupos (en nuestro caso g = 3 pues hay tres tipos de caramelos pia , menta , fresa-), dondea elementos son iguales entre s( por ejemplo a = 3 caramelos de pia) , b elementos son iguales

entre s(b = 2 caramelos de menta) , .............., y k elementos son iguales entre s(k = 1caramelos de fresa para el ltimo), el nmero de sus permutaciones es

Permutaciones con repeticin de m elementos, con a, b, ... k iguales entre sya+b+...+k = m

Fijemos las condiciones para tener permutaciones con repeticin:

m elementos, (m=6, los caramelos) agrupados de m en m, (los reparto todos entre todos mis amigos) importa el orden, (quiero averiguar las diferentes formas de dar los caramelos: no es igual -

una vez fijados mis amigos- dar M-M-F-P-P-P que P-P-P-F-M-M)

sin repetir elementos... (no voy a dar el MISMO caramelo a dos amigos)...excepto aquellos que son indistinguibles(como los 3 de pia, y los 2 de menta)

En estas condiciones, diremos que estamos ante una permutacin con repeticin de m elementoscon grupos de a, b, ...k elementos indistinguibles

Otros ejemplos:

PR2.- Cuntas palabras diferentes de 7 letras puedo hacer con las letras A, A, B, B, C, E, F?PR3.- De cuntas maneras diferentes puedo distribuir 10 bolas iguales en tres cajas? (en cada cajapuede haber de 0 a 10 bolas)PR4.- Adems de la locomotora, un tren lleva 3 vagones de segunda clase y 2 de primera clase,que pueden ordenarse de cualquier forma . Un da su posicin era as: 21122; otro as : 11222. Decuantas formas pueden ordenarse los vagones?PR5.- Hay que repartir 3 polos de fresa y 3 de vainilla entre 6 chicos. De cuantas formas sepuede hacer?PR6.- De cuantas formas se pueden ordenar 6 monedas iguales en hilera de forma que siemprese vean 3 caras y tres cruces?

!!...!.

!,...,,kba

mPR

kba

m==


14/25


VARIACIONES CON REPETICIONVR1.- Tengo un caramelo de pia, otro de menta y otro de fresa. Voy a sortearlos entre cinco de misamigos, de forma que a uno solo de ellos, con suerte, le podran tocar los tres. Cuntos repartosdiferentes podran suceder?

Recordando el problema nmero 2, Al tener que investigar las posibles llegadas diferentes a meta de cadacorredor, tenamos un caso de variaciones sin repeticin de 5 elementos tomados de 3 en 3.Al sortear tres caramelos diferentes entre 5 personas, tenemos un caso muy similar. La diferencia est en larepeticin: En el problema 2 una persona no poda ganar la medalla de oro y la de plata a la vez. Aqu si. Esdecir: una sola persona puede ganar por sorteo el caramelo de fresa y el de pia. Incluso puede ganartambin el de menta.

Lo plantearemos de la siguiente manera:

Pongo mis caramelos en un determinado orden. Por ejemplo: P - F - MDespus de la raz, empiezo por sortear el caramelo de pia.Tengo 5 posibilidades: para A, o B, o C, o D, o E.

Una vez he dado el caramelo de pia, sigo con el de fresa:Ahora vuelvo a tener 5 posibilidades:

para A, o B, o C, o D, o E.

Igual pasa en el nivel del caramelo de menta.Esto es: 5 posibilidades por cada posibilidad, por cada nivel.

La cosa queda como en el rbol adjuntoTotal, que al final el nmero total de posibles repartos es:


15/25


5x5x5 = 53

Variaciones con repeticin, en generalSi tenemos un conjunto de m elementos diferentes, para agruparlos en grupos de n elementos cada grupo,donde es posible que un elemento aparezca repetido

las variaciones con repeticin de m elementos, tomados de n en n son:

VRm,n= mn

Fijemos las condiciones para tener variaciones con repeticin:

m elementos, (m=5, los 5 amigos) agrupados de n en n, (formo grupos de 3 para asignar los 3 caramelos) importa el orden, (quiero averiguar las diferentes formas de dar los caramelos: no es igual -una vez

fijados los caramelos en pia, menta, fresa- drselos a Ana, Benito y Carlos que a Carlos, Ana yBenito)

repitiendo los elementos... (si sorteo los caramelos, puedo dar a la misma persona dos, o incluso lostres caramelos)

En estas condiciones, diremos que estamos ante una variacin con repeticin de m elementos en gruposde n elementos

Otros ejemplos:VR2.- Cuntos nmeros de 3 cifras pueden hacerse con las cifras {1, 3, 5, 7, 9}?VR3.- Con tres colores, cuntas banderas diferentes de 5 franjas podemos confeccionar?VR4.- Cuntas quinielas futbolsticas diferentes de 14 resultados pueden rellenarse? Y de 15?

VR5.- Cuntos nmeros de 5 cifras pueden hacerse con las cifras {1, 3, 5, 7, 9}?VR6.- Tengo que confeccionar un collar con perlas negras y perlas blancas. En total, el collar tendr 35perlas. De cuntas maneras distintas lo puedo hacer?


16/25


COMBINACIONES CON REPETICION

CR1.- Supongamos que tengo un montn de caramelos de menta, de fresa y de pia, y que quieroconfeccionar bolsitas de 5 caramelos cada una para repartirlas entre mis amigos el da de mi cumpleaos.

Cuntas bolsitas diferentes puedo hacer?

Para resolver este problema, empezaremos directamente por montar el rbol:

Observar que el rbol tiene la misma estructura que un rbol de combinaciones sin repeticin. Se ve si seconsulta el problema nmero 3..

Parece que sea el rbol de las combinaciones de 7 elementos tomados de 5 en 5.

Por lo tanto, para calcular las combinaciones con repeticin de 3 elementos tomados de 5 en 5, tengo quecalcular C7,5. Eso da 21.

Tengo 21 maneras diferentes de llenar una bolsa de 5 caramelos de entre un montn de caramelos de fresa,de menta y de pia.


17/25


Combinaciones con repeticin, en generalAnalicemos la cuestin:

m elementos, (m=3, los 3 tipos de caramelo) agrupados de n en n, (n=5, el nmero de caramelos que meter en cada bolsita) NO importa el orden, (una bolsa que contiene M, M, P, F, F, es como una bolsa con F, M, P, F, M)

repitiendo elementos, (en la misma bolsa puedo poner ms de un caramelo de un tipo dado)Observar que, slo con tres tipos de caramelo, para llenar una bolsa de 5 caramelos deber repetiralguno de los tipos.

En estas condiciones, diremos que estamos ante una combinacin con repeticin de m elementos,tomados en grupos de n elementos ("de n en n")

Cmo puedo yo saber, sin montar el rbol de una combinacin con repeticin, a qu rbol decombinacin sin repeticin se parece? A ver. Si uno dibuja un rbol de la combinacin sin repeticin dem elementos tomados de n en n, observar que...

En el primer nodo de la primera rama de cada nivel, hay tantas ramificaciones como m-n+1

Se ve que para una combinacin de 5 elementos tomados de 3 en 3, los primeros nodos contienen 5-3+1 = 3ramas.

(Elementos - niveles +1 = n de ramas de primeros nodos)

Se puede observar tambin que del primer nodo de una rama que proviene de un nodo con k ramas, siempresalen a su vez k ramas. Y de los siguientes nodos de su mismo nivel sale cada vez una rama menos.

Si resulta que construimos (como hemos hecho aqu) un rbol con 5 niveles y 3 nodos en cada primera ramade cada nivel, es que estamos construyendo el rbol de las combinaciones de m elementos tomados de 5 en5, donde m cumple que m-5+1 = 3

esto es m = 3+5-1 = 7En el caso general...

Si resulta que construimos un rbol con n niveles y m nodos en cada primera rama de cada nivel, es queestamos construyendo el rbol de las combinaciones de k elementos tomados de n en n, donde k cumpleque k-n+1 = m

esto es k = m+n-1

As que de ahora en adelante...Para saber cuntas combinaciones con repeticin hay de m elementos tomados de n en n,calcular las combinaciones sin repeticin de m+n-1 elementos tomados de n en n.

Y la frmula es CRm,n=Cm+n-1,n

Otros ejemplos:CR2.- Tengo un saco lleno de huevos de pascua rojos, verdes, amarillos y azules. Cuntas cajas diferentesde 5 huevos de pascua puedo llenar?CR3.- Tengo que llenar una caja con 10 bombones. Si puedo meter en la caja bombones grandes, medianosy pequeos, De cuntas maneras distintas lo puedo hacer?CR4.- Se dispone de tres tipos de polos y un chico desea guardarlos en cajas de 6. Cuantas cajas distintas

puede llenar?CR5.- Un ascensor recorre 5 pisos de un edificio. De cuantas formas pueden bajarse 7 personas ,atendiendo solo al n de personas que se bajan en cada piso.CR6.- Y si siempre debe bajarse al menos una persona en cada piso.


18/25


PROBLEMAS MEZCLADOS1.- Cuantos resultados distintos podemos obtener al:

a) lanzar un dado rojo y otro verdeb) lanzar un dado y extraer una carta de una barajac) lanzar tres dados

d) lanzar un dado , extraer una carta de una baraja y lanzar una moneda.2.- Cuntos nmeros de 6 cifras pueden hacerse con los dgitos {1, 2, 3, 4, 5, 6}?3.- Cuntos nmeros de 6 cifras pueden hacerse con los dgitos {1, 2, 3, 4, 5, 6}, sin repetir ninguna cifra?4.- Cuntos nmeros de 6 cifras pueden hacerse con los dgitos {1, 2, 3, 4, 5, 6}, mayores que 500.000?5.- Cuntos nmeros de 4 cifras pueden hacerse con los dgitos {0, 1, 2, 3, 4, 5, 6}?6.- Tenemos 5 libros iguales de matemticas y 3 iguales de lengua. de cuntas maneras se pueden ordenar?7.- En un polgono de 8 lados, cuntas diagonales hay?8.- Con cuatro nmeros positivos y seis negativos, cuntos productos de 4 factores distintos se puedenhacer? cuntos son positivos y cuntos son negativos?9.- En una carrera hay que superar los obstculos X, X, O, O, O, O, U, U, U. De cuntas maneras sepueden colocar los obstculos uno tras otro? En cuntas de esas maneras encontraremos un par U-Useguido?

10.- En una plantilla de ftbol hay 3 porteros, 7 defensas, 11 centrales, y 4 delanteros. Cuntasalineaciones posibles hay para una tctica 4-3-3?11.- Calcular el nmero de caminos de mnimo recorrido entre dos vrtices de una cuadrcula (siguiendo laslneas de la cuadrcula). Puede resolverse razonando con permutaciones y tambin utilizandocombinaciones. Cul ese nmero de caminos?.

12.- Se tienen 3 libros: uno de aritmtica (A), uno de biologa(B) y otro de clculo(C), y se quiere ver decuntas maneras se pueden ordenar en un estante.13.- Se tienen 7 libros y solo 3 espacios en una biblioteca, y se quiere calcular de cuntas maneras sepueden colocar 3 libros elegidos; entre los siete dados, suponiendo que no existan razones para preferiralguno.14.- Cuntas permutaciones pueden formarse con las letras de palabra BONDAD?15.- De cuntas maneras se pueden ordenar las letras de la palabra AMASAS?16.- Un hospital cuenta con 21 cirujanos con los cuales hay que formar ternas para realizar guardias.Cuntas ternas se podrn formar?

17.- De cuntas maneras pueden entrar cuatro alumnos en tres aulas, si no se hace distincin de personas?18.- Cuntos nmeros de tres cifras se pueden escribir con los dgitos 3,4,5, y 6?


19/25


19.- Cuntas columnas rellena un quinielista que juega cinco triples? Y uno que juega sietedobles?20.- Cuntos capicas de tres cifras se pueden escribir?21.- Cuntos nmeros naturales se pueden escribir con los dgitos 1, 2, 3, 4, y 5, sin que serepita ninguno? Cuntos terminan en 5? Cuntos comienzan por 3? (pueden ser nmeros con :desde 1 a 5 dgitos)

22.- De cuntos modos distintos pueden presentarse diez cartas de una baraja, sabiendo queson 4 ases, 3 reyes, 2 caballos y una sota?23.- Cuntos elementos hay que combinar de dos en dos para que el nmero decombinaciones sea 190?24.- Cuntas quinielas distintas se pueden hacer si creemos que el resultado de 4 partidos ser un 1, el de 5partidos puede ser un 1 o una x, y los 6 partidos restantes puede darse cualquiera de los tres signos?25.- Le damos una carta de una baraja espaola a cada uno de tres jugadores . Cuntos posibles repartosexisten.26.- Dos amigos juegan un torneo de ajedrez en el que ser vencedor el primero que logre ganar trespartidas (No se tienen en cuenta las partidas que terminan en tablas)De cuantas formas posibles puededesarrollarse el torneo?

27.- En un monte hay 7 puestos de vigilancia contra incendios y cada uno de ellos esta unido a los demspor un camino. cuantos caminos habr en total?28.- Un amigo le quiere regalar a otro 3 discos y los quiere elegir entre los 10 que mas le gustan. Decuantas formas puede hacerlo?29.- Vas a preparar un batido de frutas de tres sabores .Tienes 6 clases de fruta que vas a utilizar encantidades iguales. Cuntos batidos diferentes podrs hacer?30.- En un aula hay 6 ventanas que pueden estar abiertas (A) o cerradas (C) , indistintamente. Esta maanasu posicin era esta : ACAACA , es decir estaban abiertas la 1 , 3 , 4 y 6 y cerradas la 2 y 5. Cuntasposiciones distintas pueden tener las ventanas?31.- Cuntos resultados distintos podemos obtener si tiramos una moneda 10 veces?32.- En cada uno de los siguientes problemas debes responder a la siguiente pregunta: de cuantas formasse puede hacer?

a) Tres amigos van a comprar un polo para cada uno a una heladera en la que hay 6 clases de polos.b) Seis amigos van a comprar un polo para cada uno a una heladera en la que hay 3 clases de polos.c) Queremos repartir 3 polos distintos entre 6 chicos sin que pueda tocarle mas de un polo al mismo chico

.d) Queremos repartir 3 polos iguales entre 6 chicos sin que pueda tocarle mas de un polo al mismo chico.e) Un chico quiere elegir 3 polos entre 6 distintosf) Queremos introducir 6 polos en una caja , eligindolos de entre tres sabores diferentes.g) Queremos repartir 6 polos distintos entre 6 chicos.h) Hay que repartir 3 polos de fresa y 3 de vainilla entre 6 chicos.


20/25


SOLUCIONES

P1.- P5 = 5! = 120P2.- P5 = 5! = 120P3.- P7 = 7! = 5040

P4.- 3 . P6 = 3 . 6! = 3 . 720 = 2160P5.- P8 = 40320P6.- P3 .P3 = 36 si se empieza por un chico. Y P 3 .P3 = 36 si se empieza por una chica . Por tanto 72 formas

V1.- V5,3 = 5 . 4 . 3 = 5! / 2! = 60V2.- V5,3 = 60V3.- V25,11 = 177925144320000V4.- V14,2 = 182V5.- V20,2 =380V6.- V7,3 = 210

C1.- C5,3 = 5! / (2! . 3!) = 10C2.- C13,4 = 715C3.- C9,4 . C11,5 = 58212C4.- C8,2 = 28C5.- C8,3 = 56C6.- C20,3 = 1140

PR1.- PR63,2,1

= 6! / (3! . 2! . 1!) = 60PR2.- PR7

2,2,1,1,1= 1260

PR3.- 8 . P3 + 6 . PR32,1 = 48 + 18 = 66(Aclaracion : Estas son todas las formas que se deben tener en cuenta :0010,019,028,037,046,055118,127,136,145226,235,244334De ellas , las que tienen algn numero repetido se hallan por PR y las que no por Permutacionessimples.)

Tambin se puede hacer por CR3,10 = 66 , pues si tomamos tiras de 10 elementos tal que as :AABBBBBBBB, ABABBBBBBB, ABBABBBBBB.... Todas estas serian la misma , es decir , dosbolas en la bolsa A y 8 en la B (y 0 en la C).

PR4.- PR52,3 = 10 (Tambin se puede hacer por combinaciones: C5,3 C5,2 )PR5.- PR6

3,3= 20 (Tambin sale por C6,3 )

PR6.- PR63,3

= 20 (Idem al anterior por combinaciones)

VR1.- VR5,3 = 53= 125 (Las variaciones serian : 111, 112, ......211, 212, ...............555 .

Donde 111 quiere decir que al primer amigo le toco el de pia,el de menta y el de fresa ; 112 quiere decir que el primero tiene el de pia yel de menta y el segundo el de fresa y por supuesto todos los dems nadaetc. Es decir tres posiciones los tres sabores y en cada uno pueden estarcualquiera de los 5 amigos)

VR2.- VR5,3 = 53

= 125VR3.- VR

3,5= 3

5= 243

VR4.- VR3,14 = 314

= 4.782.969 ; VR3,15 = 315

= 14.348.907VR5.- VR5,5 = 5

5= 3125 ( A esto tambin se le podra llamar Permutaciones con

repeticin de 5 ; PR5 = 55

.Pero no se le llama as !!??)


21/25


VR6.- VR2,35 = 235

= 34359738368 = 3.436 1010

CR1.- CR3,5 = C5+3-1,5 = C7,5 = 21CR2.- CR4,5 = C8,5 = 56CR3.- CR3,10 = C12,10 = 66CR4.- CR3,6 = C8,6 = 28CR5.- Una posible combinacin seria : 1122345 , es decir 2 personas en el 1er piso etc.

Por tanto seria como tomar los 5 pisos y combinarlos de todas las maneras posibles engrupos de 7 , pero teniendo en cuenta que combinaciones como 1122345 y1212345 son la misma.Por tanto : CR5,7 = 330Donde la combinacin 1111111 significa que los 7 se bajaran en el 1er piso etc.

CR6.- De todas las combinaciones del ejercicio anterior , me quedo con los que tienen la formasiguiente 1-2-3-4-5-_-_ Donde los dos ltimos espacios pueden tener los valores 1 a 5Pero teniendo en cuenta que 1-2 seria igual a 2-1 y que los nmeros se pueden repetir ,es decir , por ejemplo me valdra 1-1Por tanto : CR5,2 = 15

0.- a) 6 . 6 =36 ; b) 6 . 40 = 240 ; c) 6 . 6 . 6 =216 ; d) 6 . 40 . 2 = 4801.- VR6,6 = 466562.- P6 = 7203.- VR6,5 + VR6,5 = 2 . 6

5= 15552

4.- VR7,4 = 24015.- PR8

5,3= 56 , o tambin C8,5 C3,5 = 56

6.- C8,2 - 8 = 20 diagonales7.- C10,4 = 210 ; C6,3 . 4 + 6 . C4,3 = 104 negativos. Por tanto 210 104 = 106 positivos.8.- PR9

2,4,3= 1260 ;

PR6, (2,4) . V7,2 + PR6, (2,4) . 7 = 735

(Aclaracion :suponemos la siguiente configuracin :

_ , X, _, X,_, O, _, O, _O,_O, _ . Sabemos que esos 6 objetos se puedenpermutar de PR6, (2,4) = 15 formas y ahora numeramos esos espacios del 1 al 7y tenemos en cuenta que :- Si queremos colocar U-U y U de forma separada seria de V7,2 = 42 formas

(Por tanto 15 . 42 = 630)- Si queremos colocar las tres seguidas seria 7 formas (Por tanto 15 . 7 = 105)

En total 735 formas.)(Si Supongo que U-U es una letra a la que llamo W . Y por tanto para las letrasX,X,O,O,O,O,W,U puedo colocarlas de PR8, (2,4,1,1) = 840 resultados posibles.

Esto estara mal pues estas tomando las permutaciones WU y UW diferentescuando son iguales UUU. A estas habra que quitarle las 7 formas de poner WU

y dejar las otras 7 UW . Pero por supuesto estas 7 las debo multiplicar por lasPR6,(2,4) .En total 7 . 15 = 105 , con lo que 840 105 = 735 , como el anterior)

9.- C3,1 . C7,4 . C11,3 . C4,3 = 3 . 35 . 165 . 4 = 6930011.- Sea h la diferencia horizontal y v la vertical entre ambos puntos. Deben darse h 'pasos' en horizontal yv en vertical, siempre en el mismo sentido los de cada tipo (sin retrocesos) para que el recorrido seamnimo.Se trata entonces de escoger las posiciones de los v pasos verticales (o de los h horizontales) entre los v+hque hay que dar: Comb(v+h, v)=Comb(v+h, h). ( Es decir tenemos 17 posiciones y debemos llenar 5 conlos pasos verticales de tal forma que la combinacin _ v _ v v _ _ v_ _ _ _ _ _ _ _ v significara que lospasos 2 ,4 ,5,8 y 17 serian verticales y ahora solo queda poner los 12 horizontales en los huecos. Y comoCm,n = Cm,m-n da lo mismo hacerlo por los pasos verticales que por los horizontales)

Por tanto C17,5 = C17,12 = 6188Alternativamente, se trata de formar las permutaciones con repeticin de 2 elementos, uno de los cuales serepite h (12) veces y otro v (5) en grupos de h +v (17) : PRv+h,(v,h) = (v+h)!/(v!h!), lo mismo que antes.PR17

12,5= 6188


22/25


12.- P3 = 3! = 6

13.- V7,3=7!/(7-3)!=7.6.5.4!/4!=7.6.5 = 210

14.- Hay 6!/2! . Si se escribe en lugar de BONDAD: BONDAD

Todas las letras son distintas, luego hay 6! permutaciones, pero cada par de permutaciones:

- - - D - D

- - - D- D

Coinciden, por lo tanto se tiene que dividir por 2 el nmero total de permutaciones.

Por tanto la solucin es PR62 = 6!/ 2! = 360

15.-:

16.- Se trata de formar todas las ternas posibles, sin repetir elementos en cada una, y sin importar el ordende los elementos.Si quisiramos formar todas las ternas posibles, sin repeticin de elementos en cada una, para elegir elprimer elemento hay 21 posibilidades, para el segundo quedan 20 posibilidades, y para el tercero 19posibilidades, por lo tanto el nmero de ternas posibles est dado por: 21* 20*19 = 7980Pero en este caso cada terna aparece repetida en distinto orden, por ejemplo tendremos: ABC, ACB, BAC,CAB y CBA. Son seis ternas con los mismos elementos, que est dado por el factorial de 3.Por lo tanto el total de ternas obtenido 7980, hay que dividirlo por 6

7980/6 = 1330Se pueden organizar las guardias de 1330 maneras diferentesEste es un problema de combinacin. C21,3 = 21!/ (3!. (21-3)!) = 1330

17.- CR3,4 = C3+4-1,4 = C6,4 = 6 . 5. 4. 3/(4. 3. 2. 1) = 15(Tambin se puede hacer por Permutaciones con Repeticin: sumas de 3 nmeros queden 4 solo hay cuatro : 4-0-0 , 2-2-0 , 2-1-1 , 3-1-0 y de esas a las 3 primeras lehallamos las PR3

2y a la restante P3 , por tanto 3 . 3 + 6 = 15 como antes)

18.- Se pueden escribir

nmeros

19.- Con cinco triples rellena

columnasCon siete dobles rellena :

columnas

20.- Suponiendo que aunque la primera cifra sea 0 se trata de un nmero de tres cifras y como la primera yla tercera cifra deben ser iguales (capicas) tenemos :

21.- Como pueden tener desde 1 hasta 5 cifras tenemos


23/25


22.-

23.-

24.- Los cuatro resultados 'fijos' los podemos elegir entre un signo, los 5 'dobles' entre dos y los 6 'triples'entre 3, por lo tanto la solucin sera: 1.1.1.1.2.2.2.2.2.3.3.3.3.3.3=23328O tambin :VR1,4 . VR2,5 . VR3,625.- V40,3 = 5928026.- C5, 3 + C5, 3= 20 (&Tambien PR5(3,2) + PR5(3,2) =20)27.- C7,2 = 2128.- C10, 3 = 12029.- C6, 3 = 2030.- VR2,6 = 2

6= 64

31.- VR2,10 = 102432.-

a) VR6,3 = 216b) VR3,6 = 729c) V6,3 = 120d) C6,3 = 40e) C6,3 = 40f) CR3,6 =28g) P6 =720h) PR6(3,3) = 20


24/25


25/25


RESUMEN

OTRAS FRMULAS TILES

Documents

ap_combinatoria