Análisis combinatorio

Generalidades definiciones

Con frecuencia se presentan problemas en los cuales, por ejemplo, una situación bancaria debe a los usuarios una tarjeta de crédito o de débito : una compañía de teléfonos debe asignar a cada suscriptor un número; yo gobierno estatal una plaza de circulación para cada vehículo.

La solución de este tipo de problemas implica calcular cuántos subconjuntos distintos se pueden formar con un conjunto de números. El sistema que se seleccione debe tener suficiente amplitud para cubrir el número de usuarios previstos.

A cada número, objeto o suceso se le llama elemento; a cada conexión con grupo de elementos se le identifica como una combinación y a cada ordenación única dentro de una combinación se le llama permutación.

Una combinación es un conjunto de elementos diferentes en cualquier orden. En cambio, la permutación se caracteriza por el orden de los elementos que lo forman.

Todos los elementos de un conjunto pueden ser empleados en cualquier combinación o permutación, pero es necesario utilizar a todos; generalmente estos elementos son de la misma especie, pero no es absolutamente necesario

2. Principios fundamentales del conteo

Al estudiar las operaciones con conjuntos en la parte relativa de este libro bien igual forma que lo hicimos en el de la aritmética y álgebra, no referimos al conjunto producto señalando que dados dos conjuntos.

A y B

A XB = { (a,b) } I a£ A. S £ B)

A este conjunto de parejas ordenadas se le llama producto cartesiano de A y B y es el principio fundamental para contar, y que citamos a continuación:

si un conjunto finito A contiene N elementos y un conjunto B también finito contiene R

elementos, entonces hay nr parejas ordenadas donde a £ A y b £ B; el resultado del producto A X B contiene nr elemento.

este principio puede extenderse a cualquier número de conjuntos de aplicarse a muchas situaciones de conteo.

Principio multiplica activo.

Si un primer suceso, algunos autores lo citan como evento, algo puede efectuarse entre p1 maneras diferentes, y si después de este suceso ha sido efectuado, un segundo suceso puede efectuarse entre p2 maneras diferentes, entonces los dos sucesos pueden verificarse siguiendo el orden indicado dep1p 2 maneras diferentes.

Problema 1

De cuantas maneras diferentes se puede seleccionar parejas de diferente sexo de un grupo de 4 hombres y 6 mujeres?.

Resolución.

Como cada hombre puede ser seleccionado de cuatro maneras diferentes y cada mujer puede ser seleccionada de seis maneras diferentes; entonces, cada pareja puede ser escogidas de:

4(6) = 24 maneras diferentes.

Si el suceso incluye más de dos sucesos diferentes podemos ampliar el principio multiplica activo, de manera que si después de haber ocurrido los dos principios sucesos, puede ocurrir un tercero de p3 en maneras diferentes, con un cuarto de p4 maneras diferentes, y por último un n-esimo de Pn maneras diferentes, con entonces los sucesos pueden ocurrir en el orden siguiente:

P1 P2 P3 P4 ….. Maneras diferentes

Problema 2.

Cuantos números naturales nones existen que tengan una expresión numérica de tres dígitos con los elementos:{0, 1, 2, 3, 4, 5, 6,7,}.

Resolución.

Para razonar sobre problemas de este tipo, ayuda traza un diagrama en la forma siguiente:

O poner rayas pequeñas _ _ _ _. Tantas como sean

Necesarias.

La cifra de las centenas es cualquiera de los siete elementos (1, 2, 3, 4, 5, 6,7) consideramos únicamente a siete ya que no podemos escoger el cero para las centenas, ahora escribimos un 7 en el primer espacio de.

La cifra de las decenas es cualquiera de los ocho elementos porque {0,1,2,3,4,5,6,7,8}

7 8

La cifra de las unidades deben ser cualquier número non de los elementos citados, que son un {1,3,5,7}

Por el principio multiplicativo las solución es :

784 = 224 son los números naturales nones que tiene tres hijas y que se pueden expresar con los elementos 1234567.

Problema tres.

Con los dígitos del cero al nueve se quieren formar números de cuatro cifras, sin repetir cifras en ninguno de los números formados.

a) cuando se pueden formar?.

b) cuantos números son impares?

c) cuantos números son divisibles entre 2?

d) que cuantos números son mayores o iguales que 3000?.

Resolución.

Tenemos 01239 son 10 elementos.

A)

aa)

7 48

9 9 8 7

9(9) (8) (7)= 4536

Se pueden formar 4536 numeros

B)

Para la ultima cifra para formas números impares en que pudimos el tenemos

(1,3,5,7,9) que son 5 elementos

9(8) (7)(5)= 2520

Se pueden fornar 2520 numeros impares

C)

Para la ultima cifra para formar números divisibles entre 2 en que pusimos el 5, tenemos

{0,2,4,6,8} que son 5 elementos

D)

.

Para un número mayor igual que en 3000 están el 3001. 3002, por lo tanto la primera cifra se puede escoger de {3,4,5,6,7,8,9} que son siete elementos.

9 9 7 5

9 9 77 5

7 9 78 7

7987 = 3528.

Y se puede obtener 3528 números mayores o iguales que 3000.

Problema 4.

Calcular cuántos números enteros de tres cifras se pueden obtener con los dígitos 2.3, 5.7 en los casos siguientes:.

A) no se permite la repetición de las islas en ninguno de los números

b) se permite la repetición de las cifras en los números.

Resolución.

A) no se permite la repetición.

Tenemos tres lugares para ser llenados.

El primer lugar puede llenarse de cuatro formas diferentes usando cualquiera de los números 2.3, 5.7; en este caso p2 = 3;p3=2 por lo tanto:4(3)(2)=24

los números enteros de tres cifras que pueden formarse sin repetir cifras, con los dígitos 2.3, 5.7 son 24.

B) se permite la repetición.

Tenemos tres lugares para ser llenados el primer lugar, el segundo y el tercero se pueden llenar cada uno con cuatro números por lo tanto: 444 = 64.

Los números enteros de tres cifras que pueden formarse con repetición, con los dígitos 2.3, 5.7 son 64.

Problemas 5

De una Ciudad A a otra B hay cuatro caminos; a su vez de, la ciudad B a la C de Estados Unidos, si todos los caminos son diferentes, de cuantas formas posibles:

A) viajar de a aceptar C pasando porB

B) hacer el viaje redondo desde A hasta C pasando por B

C) hacer el viaje redondo desde A hasta C pasando por B pero sin utilizar el mismo camino más de una vez que.

a) A -> B B->C

4 formas 6 formas

4(6)= 24 formas

b) A-> B B-> D C-> B B-> A

4 formas 6 formas 6 formas 4 formas

4(6) (6) 4) = 576 forma

A B C

Principio aditivo.

Un peso puede realizarse de dos maneras diferentes (una con la otra) y la primera de puede realizarse de p1 maneras diferentes de la siguiente de p2 maneras diferentes, puntos del suceso puede realizarse de p1+p2 maneras diferentes. Este principio, al igual que el principio multiplicativo, puede generalizarse por procesos que incluye tres o más operaciones excluyentes.

Analiza la situación siguiente: el problema se multiplican los sucesos cuando el primero le sigue otrp, y se suman los sucesos cuando éstos son aislados.

Problema 6.

Cinco ciudades de comunicarse con el diagrama que se cita.

De cuantas formas es posible:

a) viajar desde A hasta Eb) hacer el viaje redondo de este A hasta Ec) hacer el viaje redondo desde A hasta E incluso del mismo camino más de una vez

Resolución

a) Viajar desde A hasta E

Pasando por C

A-> B B-> C C->4 formas 3 formas 2 formas

Por el principio multiplicativo4(3) (2)= 24 formas

Pasando por D

A-> B B-> D D-> E4 formas 2 formas 4 formas

Por el principio multiplicativo

4(2) (4)= 32 formas

El viaje de A hasta E ya que sea pasando por C o por D por el principio aditivo se puede realizar en

24+32 = 56 formas

b) Viaje Redondo desde A hasta E

Por el principio multiplicativo obtenemos:

El viaje redondo desde A hasta E, por el principio aditico se puede realizar en

576+278+1024+768=3136

c) Viaje Redondo desde A hasta E sin usar el mismo camino mas de una vez

Por el principio Aditivo Obtenemos:

Elviaje redondo desde A hasta E sin usar el mismo camino mas de una vez, por el principio aditivo se puede realizar en:

144+576+56+288= 1584 formas

Problema 7.

Calcular cuántos números impares menores que 10000 pueden expresarse con los números 0,3,6,9.

Resolución.

como en el resultado se tendrá números de una,dos,tres o cuatro cifras podemos considerar cada caso por separado; y para que se impares, de los números 0.3, 6.9 únicamente podemos disponer del tres y el nueve; además, el cero no puede ser ciencia inicial de ninguna especie numérica de un número natural.

Para las unidades tenemos 2 impares, el 3 y el 9.

Por los números impares menores que 10000 que pueden expresarse usando de los números 0.3, 6.9 por el principio aditivo, tenemos: 6 + 24 + 96 = 126 números

Concluimos:

Muchos problemas de conteo se puede resolver aplicando únicamente los principios multiplica activo y aditivo, pero en algunos casos esto implica una considerable número de operaciones y razonamientos complicados; para evitarlo se han obtenido fórmulas para situaciones específicas que facilitan la solución.

3. Factorial.

el producto de cualquier número entero positivo n por todos los enteros menores que n se llama factoría de n y se expresa con el símbolo n! Por lo tanto:

El factoría de los primeros números enteros positivos se pueden obtener directamente utilizando la calculadora común, para números mayores obtienen con la fórmula aproximadamente lStirling y constando tablas elaboradas con resultados.

4. Permutaciones.

Cuando el problema de los conteos consisten ordenar elementos de un conjunto se le llama en mutación del conjunto. Se clasifican en:

Lineales: pertenecen a este tipo de los casos en los cuales los elementos ordenan en una pila.

Circulares: son todos aquellos casos en que los elementos deben ser colocados alrededor de un círculo en una secuencia psíquica o cerrada.

A. Permutaciones lineales.

a) Permutaciones de n elementos diferentes en grupos de r elementosb) permutaciones de n elementos, no todo diferentes entre síc) permutaciones de n elementos diferentes en grupos de n elementos

El caso el número de lugares es menor que el número de elementos; pero también puede presentarse el caso contrario que se disponga mayor número de lugares que tiene, cuando esto ocurre se permutan los lugares con los elementos.

Una permutaciones general se expresa así; nPr y también puede emplearse en notaciones P(n,r) y Pnr Donde:

n a ese total de elementos por acomodar y R la cantidad de elementos que se toman de n

El número de permutaciones de n elementos diferentes tomados en grupos de r en r

se obtiene con la fórmula:

Demostración de la fórmula.

El resultado de nPr es igual al número total de formas que pueden llenarse r lugares con n elementos diferentes: en primer lugar puede llenarse de n formas diferentes ya que en este punto todos los elementos están disponibles. En segundo lugar puede llenarse de n-1 elemento restantes.

Análoga mente el tercer lugar puede llenarse de n-2 formas diferentes y así sucesivamente.

Continuando con este proceso, observamos que en lugar de r puede llenarse como :

Problema 8.

Cuatro diferentes quintas de baloncesto pueden formarse con siete jugadores disponibles para jugar cualquier posición?.

Resolución.

El problema se puede resolver aplicando el principio fundamental de conteo con la fórmula

nPr=n (n-1)(n-2)… (n-r+1), sustituimos

7P5= 7 (6) (5) (4) (3)= 2520

Se pueden formar 2520 quintas diferentes con 7 jugadores disponibles

Observa cómo obtuvimos el último factor:

Problema 9.

en una empresa cinco ejecutivos asisten a una junta con 27 sillas calcula de cuantas formas pueden ocupar las sillas.

Resolución como únicamente se ocupan cinco de las sillas, el número de diferentes modos de ocuparlas es igual al número de permutaciones de 7 octetos considerados en grupos de cinco, se expresa 7P5

Problema 10.

Obtener cuantos números pueden formarse con los incisos uno, 2.3, 4.5 sin repetir ningún dígito

Problema 11.

Open en el valor de a)

Problema 12 placas calcular el número de permutaciones diferentes que pueden formarse con la letra de la palabra matemáticas tomadas a la vez.

Resolución.

La solución de este problema que implica sostener el número de permutaciones 11 letras consideradas en un grupo de 11, donde la letra a aparece repetida tres veces; la letra , t dos veces y la letra M, dos veces

Problema 13.

Calcular el número de permutaciones diferentes que pueden formarse con la letra de la palabra acacia, tomadas todas a la vez.

Resolución.

B. Permutaciones circulares o cíclicas.

Pertenecen a este tipo todos aquellos casos en el que n elementos diferentes deben de ser colocados alrededor de un círculo en una secuencia psíquica o cerrada, también en este caso interviene la totalidad de los elementos disponibles.

El número de permutaciones circulares de n objetos donde la colocación del primer elemento puede considerarse como fija,y los n -1 vendo restantes pueden arreglarse de formas, que expresan:

PC = (n-1 )!Problema 14. Un grupo formado por tres muchachas y tres muchachos se van a sentar de modo que ya estén alternadas con ellos.

Calcula de cuantas formas pueden hacerlo si:

a) se sientan en línea recta.b) Se sientan en una mesa circular.

Resolución

a) se sientan en línea recta.

Podemos considerar que las muchachas sientan en los lugares con numero de cara a los muchachos en lugares con número par.

Esto puede hacerse de 3! y 3! Por más diferentes, el mismo resultado se obtiene si ya se sientan en lugar de espadas y ellos en la. Tenemos que:

2(3! 3!) = 2 (6) (6) = 72

Solucion

Si se sientan en línea recta lo pueden hacer en 72 formas.

Resolución.

b) si se sientan en una mesa circular.

Podemos inicialmente sentar las muchachas arrebatador de la mesa en 2! Entonces quedan tres lugares alternados para sentar a los muchachos, que puede sentarse en tres formas, de donde: por

2! 3! 2(6)=12Solución.

Si lo hace en una mesa circular no puede hacer en 12 formas

Problema 15.

Calcular de cuantas formas se puede sentar ocho personas alrededor de una mesa si:

a) puede sentarse cualquier forma

b) si los personas determinen no deben estar a un lado de la otra

Solución.

Las ocho personas pueden sentarse en 5040 formas.

En este problema funcional que una de las personas se puede sentar en cualquier lugar y las 7 restantes pueden sentarse en 7!

c) como dos personas no han de estar juntas lo consideramos como una sola, y las siete personas restantes puede sentarse en círculo de seis por más, y las dos personas B)consideradas con una sola pueden ordenarse entre sí de todas formas; por lo tanto el número de relaciones este:

Solución.

Como en nada tenemos el número total de formas en que siete personas se pueden sentar alrededor de una mesa y ahora donde ya no deben estar juntas, entonces:

5040-1440= 3600 es la solución

5. Combinaciones.

Cuando el problema del corte consiste en obtener en cualquier orden grupos de R elementos de un total disponible de elementos diferentes es una combinación.

El número de combinaciones de n elementos tomados de r en r se expresa nCr, algunos autores emplean también otros símbolos esta última expresión se lee N sobre R en las expresiones anteriores:

N es total de elementos disponibles

R el tamaño de los equipos elegidos

a la expresión se lee como conoce como coeficiente binominal

el número de combinaciones de en elementos diferentes tomados de R en R está dado por la fórmula:

Demostración de las fórmulas.

De cada combinación de R elementos diferentes podemos por más R! Permutaciones; por lo tanto, de todas las combinaciones se puede formar un total de nCr . r!

Si esta expresión la igualamos con el nPr que la representación una permutación de en elementos diferentes tomados de R en R, tenemos:

Problema 16.

A. Combinaciones que se forman con un conjunto

Problema 18.

Un alumno de enseñanza media superior tiene siete libros de texto y cinco de matemáticas. Y seguido calcular de cuantas maneras envuelven ante el libro del principio de matemáticas en un librero.

Combinaciones que se forma con varios conjuntos.

Problema 17.

En una maquiladora se presentan los solicitantes bajo nueve hombres y cinco mujeres. De cuantas formas el jefe de personal puede hacer la selección sílica mente puede contratar a seis hombres y tres mujeres?

Resolución.Con la fórmula

6. Relaciones de las permutaciones y de las combinaciones.

Algunas de las relaciones de las permutaciones las combinaciones son las siguientes:

A. De la permutaciones

B.

Demostración.

Políticas del operador y denominador por R +1 y n, respectivamente en cada sumando.

Estas propiedades de las combinaciones son las que permiten opciones del triángulo de cada día que facilita el cálculo de los copresidentes de las potencias del binomio. Al final del siguiente capítulo veremos cómo se utiliza en el problema del binomio.

A. Principios fundamentales del conteo

B. Permutaciones.

Fórmulas

Relaciones de las permutaciones

D, orden.

En una permutación importa el orden y se relaciona sucesiones coordenadas: parejas ordenadas, triadas ordenadas, etcétera.

En las combinaciones de portal órdenes se relaciona con la selección de uso conjunto de un conjunto dado.

8. Problemas resueltos.

Las cada uno de los problemas siguientes decidir si se trata de una permutación con una combinación de obtener el resultado.

Problema 19 calcular el número de palabras de cinco letras no necesariamente con significado que se pueda formar con 12 letras diferentes.

Resolución.

Permutación.

Problema 20.

Calcular el número de palabras, no necesariamente con significado, que pueda formarse seleccionando seis consonantes y los vocales entre consonantes y cuatro vocales, todas diferentes.

Observa que en el problema anterior a éste, el número de palabras a formar era exactamente de cinco letras, por eso lo identificamos como permutación, ahora las consonantes y las vocales se van a seleccionar de diferentes grupos.

Resolución.

Combinación y permutación.

con base en el principio multiplique activo tenemos que formar cada una de las 210 formas para seleccionar las consonantes al seis formas de la selección de los vocales, por lo tanto:

210 (6) = 1260 formas.

El efecto de cada una de estas elecciones, las ocho letras pueden permutarse en 8! Por más diferentes, por ello, el número total de palabras, por el principio multiplique activo es de:

1260 (8!) = 1260 (8) (7) (6) (5) (4) (3) (2) (1)=50 803 200 formas

Solución.

50803200 palabras

Problema 21 calcular de cuantas maneras diferentes pueden colocarse siete libros en un librero.

Resolución

Problema 22.

¿De cuantas maneras diferentes pueden colocarse siete libros tomando sólo tres de ellos a la vez?

Resolución

Problema 23.

¿De cuantas maneras diferentes de colocar un comité con un presidente, un secretario tercero, en un club que consta de 15 socios? Por.

Resolución.

En cada uno de los 425 grupos, los comités (dependiendo de que sea presidente, secretario y tesorero. Para cada grupo hay 3! Ordenaciones distintas, el interés por el principio explicativo tenemos:

405 (31) = 455 (tres) (dos) (uno) = 2730 comités

Problema 24.

Se va a organizar un evento del de investigación de cinco personas entre ciento representantes de un partido mayoritario y seis del minoritario. Calcular el número de comités que se puede informar si deben constar:

a) exactamente de tres representantes del partido mayoritario, y por lo menos 3 representantes del minoritario

c) por lo menos 3 representantes del partido minoritario en este caso tenemos tres tipos de comités:1) tres representantes del partido minoritario y dos del mayoritario2) cuatro personas del partido minoritario y uno del mayoritario3) cinco del partido minoritario ninguno del mayoritario

Problema 25.

El gobierno del estado de la Federación desde el tipo de placa circulación de los automóviles particulares por otro que incluya dos letras del alfabeto y tres distritos del cero al nueve inclusive. Pero ¿cuántas placas fabricarán con estas características?.

Resolución.

Permutaciones.

Como no hay ninguna limitación se posa cualquiera de las 28 letras del alfabeto y cualquiera de los dígitos del 09 inclusive; por ejemplo, la placa 111 es un número permitido.

Además acepta que el dígito continuación de la segunda letra pueda ser de cero.

Inicialmente elegimos la letra que ocupó el primer lugar la placa, y 28 letras para escoger, tenemos para el primer número perenne, = 28 así 28 de igual manera por el segundo lugar en 3 = 28, como cualquiera de los números del 09 se pueden usar en cualquiera de los otros tres lugares

28(28)(10)(10)(10)=784000

Problema 26

un funcionario de un banco decide que los números de las tarjetas de débito se cambian de manera que no se repitan las letras con los números de cada una de ellas, incluirán dos letras del alfabeto y cuando número de los dígitos del 09 inclusive. Calcular el número de tarjetas que se van a fabricar

Problema 27.

Una bolsa con quienes volaron números del 1 al 6 bolas azules nombradas del uno al ocho ¿de cuantas modo se puede seleccionar 6 bolas de manera que 2 sean rojas y 4 azules?

Problema 28.

La carta de una fonda indican que cuando son pasos, siete carnes, pollo salado y cinco pósters. ¿De cuántos modos se podrán a una comida con quiste en una sopa, una carne, ensaladas y un postre?

Problema 29

Cuantos grupos de 5 o mas personas puedes formarse con 10 personas?

Problema 30

En una escuela enseñanza media superior los alumnos de matemáticas. En un examen incluye distintos problemas por resolver ocho de ellos. ¿Cuantos exámenes diferentes de ocho problemas para escoger esos 16?

Ejercicio 3