PDF de programación - Ejercicios resueltos de Matemática discreta: Combinatoria, funciones generatrices y sucesiones recurrentes.

Ejercicios resueltos de Matemática discreta: Combinatoria,

funciones generatrices y sucesiones recurrentes.

(4º Ingeniería informática. Universidad de La Coruña)



José Manuel Ramos González







Introducción

Estos ejercicios han sido propuestos por los profesores de Matemática discreta del
cuarto curso de Ingeniería Informática en la universidad de La Coruña. Fueron resueltos por
mí para ayudar a mi hijo, en ese momento estudiante de esa carrera.

En mi calidad de profesor de matemáticas de enseñanza secundaria, tuve previamente
que estudiar el tema de funciones generatrices y sucesiones recurrentes para proceder a su
resolución, ya que los tenía olvidados de mi época de estudiante.

Por ello quiero dejar de manifiesto en esta breve introducción que, si bien los
resultados han sido contrastados en su mayoría, algunos (espero que en una ínfima cantidad)
pueden contener algún error, tanto en su solución como en su transcripción al ser escritos,
no responsabilizándome de las consecuencia que dichos errores puedan inducir.



J.M. Ramos
Pontevedra 2008



Ejercicios de combinatoria resueltos. Matemática Discreta. 4º Ingeniería Informática



CAPÍTULO I



COMBINATORIA

José Manuel Ramos González

Ejercicios de combinatoria resueltos. Matemática Discreta. 4º Ingeniería Informática


1. Un número telefónico consta de siete cifras enteras. Supongamos que la
primera cifra debe ser un número entre 2 y 9, ambos inclusive. La segunda y
la tercera cifra deben ser números entre 1 y 9, ambos inclusive. Cada una de
las restantes cifras es un número entre 0 y 9, ambos inclusive. ¿Cuántos
números de teléfono distintos pueden formarse con estas condiciones?



SOLUCIÓN:

Para la primera cifra tenemos 8 casos. Para la segunda y tercera juntas son RV9,2
y las restantes serán RV10,4.

En consecuencia el número de teléfonos es 8.92.104 = 6.480.000
2. Una empresa produce cerraduras de combinación. Cada combinación consta
de tres números enteros del 0 al 99, ambos inclusive. Por el proceso de
construcción de las cerraduras cada número no puede aparecer más de una
sola vez en la combinación de la cerradura. ¿Cuántas cerraduras diferentes
pueden construirse?



SOLUCIÓN:
Una posible combinación sería 1, 23, 87 que sería distinta de 23, 1, 87, por lo que
importa el orden. Por otra parte nos dicen que cada número no puede aparecer más
de una sola vez, por lo que no hay repetición.

Se trata de V100, 3 = 100.99.98


3. El consejo directivo de una empresa informática tiene 10 miembros. Se ha
programado una próxima reunión de accionistas para aprobar una nueva lista
de ejecutivos (elegidos entre los 10 miembros del consejo). ¿Cuántas listas
diferentes, formadas por un presidente, un vicepresidente, un secretario y un
tesorero, pueden presentar el consejo a los accionistas para su aprobación?Si
tres miembros del consejo son ingenieros en informática ¿cuántas de las
anteriores listas tienen:

a) un ingeniero propuesto para la presidencia?
b) exactamente un ingeniero en la lista?
c) al menos un ingeniero en la lista?
SOLUCIÓN:
Llamemos a los miembros 1,2,3,..., 10

Una lista sería 1,2,3,4 otra sería 4,5,3,1 donde el orden importa ya que el primero
sería el presidente, el segundo el vicepresidente, el tercero el secretario y el cuarto el
tesorero, es decir que la lista 1,2,3,4 no sería la misma que la 4,3,2,1 ya que el primer
caso el presidente sería 1 y en el segundo sería 4. Obviamente no hay repetición.

Así pues el número de listas es V10,4= 10.000.
a) Si tres miembros del consejo son ingenieros. ¿En Cuántas listas hay un ingeniero

propuesto para la presidencia?



Fijamos el presidente (3 casos) y variamos a los restantes. Tendríamos entonces

3.V9,3 = 3.9.8.7

José Manuel Ramos González

Ejercicios de combinatoria resueltos. Matemática Discreta. 4º Ingeniería Informática



b) En cuantas listas hay exactamente un ingeniero.

Tenemos 3 ingenieros para 4 posiciones y los 7 miembros restantes los variamos

de 3 en 3
4.3.V7,3
c) En cuantas listas hay por lo menos un ingeniero.

Calculamos todas las que no tienen ningún ingeniero y las restamos del total, es

decir

V10,4 – V7,4



4. Con las cifras 1, 2, 3, 4, 5 y 7 se forman números de cinco cifras que no tengan
ninguna repetida.a) ¿Cuántos números se pueden formar? b) ¿Cuántos de ellos son
múltiplos de 4 y cuántos son múltiplos de 2?
SOLUCION:

a) Importa el orden y no hay repetición V6,5 = 6.5.4.3.2 = 720
b) Son múltiplos de 4 los que acaban en 12, 24, 32, 44, 52, 72. El caso 44 no nos

vale por haber repetición.



Acaban en 12 V4,3 = 4.3.2. = 24. Por tanto los múltiplos de 4 son 5.24=120.
Como hay 720 casos, acaban en una cifra concreta de las 6, 720/6 = 120 y como

para ser pares tienen que acabar en 2 o 4, el número de pares que hay es 240.



5. Un profesor del Departamento de Computación tiene siete libros de programación
diferentes en una estantería. Tres de los libros son de FORTRAN y los otros cuatro de
PASCAL. ¿De cuántas formas puede ordenar el profesor estos libros si:
a) no hay restricciones?
b) los lenguajes se deben alternar?
c) todos los libros de FORTRAN deben estar juntos?
d) todos los libros de FORTRAN deben estar juntos y los libros de PASCAL también?

SOLUCIÓN:

a) Si constituyen siete libros diferentes, el resultado es P7 = 7!
b) Los lenguajes deben alternar, es decir P1F1P3F2P2F3P4 y siempre deben estar
colocados así variando solamente los subíndices. Por cada cuaterna de los de
Pascal tengo P3 = 3! ternas de fortran. Por tanto la solución es P4.P3 = 4!.3!

c) Si los libros de Fortran deben estar juntos, puedo considerar un bloque a los tres

permutados entre sí, es decir, por ejemplo:



P1(FFF)P2P3P4

El número de casos que tendríamos en esa situación sería P5 = 5!, pero a su vez los

elementos de FFF permutan entre sí P3 veces, por lo que el resultado pedido será:
P5.P3 = 5!.3!

José Manuel Ramos González

Ejercicios de combinatoria resueltos. Matemática Discreta. 4º Ingeniería Informática

d) Si los de Fortran deben estar juntos y los de Pascal también tenemos los dos

casos FFFPPPP o PPPPFFF, es decir P2, pero a su vez el bloque FFF presenta
P3 casos y el bloque PPPP presenta P4 casos. El resultado final sería:

P2.P3.P4 = 2!.3!.4!
6. ¿De cuántas
la palabras
POLIINSATURADO de modo que se mantenga el orden en que aparecen las
vocales?
SOLUCIÓN:

se pueden colocar

formas

las

letras de

Método 1
Consideremos 14 cajas donde contener las 14 letras que componen esa palabra y las

numeramos para identificarlas del 1 al 14.

Como las vocales han de ir siempre en el orden O, I, I, A, U, A, O, para cada posición
de las vocales lo que permutan son las consonantes, es decir P7. Ahora solo nos falta ver
cuantas posiciones posibles tengo para las vocales. Ahí intervienen las cajas. Asigno
una caja a la vocal

Una posible solución sería 1234567, es decir que la O estaría en la caja 1, la I en la 2 y
en la 3, en la 4 habría una A en la 5 una U, en la 6 una A y en la 7 una O.

Otra posible solución sería 1(13)8(11)623. Los ordenaría de menor a mayor y la O
estaría en la caja 1, la caja 2 y 3 contendrían la I, la caja 6 contendría la A, la 8 sería
para la U, la 11 para la A y la 13 para la O.

¿Cuántas de estas disposiciones de las cajas podemos hacer? Como podemos observar
el orden de las cajas no importa, es decir que el caso 1234567 es el mismo que el
6543217 ya que las vocales tienen que conservar el orden inicial. Se trata entonces de
C14,7.
La solución del ejercicio es P7.C14,7
Método 2
Otra forma de plantearlo es así: Puesto que las vocales tienen siempre que estar en el
mismo lugar puedo denominarlas a todas por V, independientemente de cuales sean.
Tendría algunos casos como:

PVLVVNSVTVRVDV, PLVVVVRDTVVVNS, donde VVVVVVV siempre sería la
secuencia OIIAUAO. Se ve fácilmente que se trata de permutaciones con repetición ya
que importa el orden y existe repetición fija del elemento V, 7 veces y cada una de las
restantes letras 1 vez.

RP14; 7,1,1,1,1,1,1,1
Obviamente el resultado, utilizando ambos métodos, conduce a la misma solución:

14!/7!



7. Una mano de bridge consta de 13 cartas del conjunto de 52 de la baraja francesa.
a) ¿Cuántas manos de bridge son posibles?
b) ¿De cuántas formas se le puede dar a una persona 6 picas y 5 corazones?

SOLUCIÓN:

La baraja francesa consta de 13 cartas por cada “palo”, siendo los palos: picas,
corazones, tréboles y rombos. Y las 13 cartas de cada palo son el AS(1), 2, 3, 4, 5, 6, 7,

José Manuel Ramos González

Ejercicios de combinatoria resueltos. Matemática Discreta. 4º Ingeniería Informática

8, 9, 10, J, Q, K. Las tres últimas son el Jocker, Queen, King (el equivalente a la sota,
caballo y rey de la baraja española).
a) El número posibles de manos es obviamente C52,13 pues el orden en que estén
dadas las cartas no influye en la mano y no puede haber repetición por no haber
cartas repetidas.

b) En una mano hay C13,6 de dar 6 picas, pues tengo 13 picas para dar 6.

Analogamente para dar 5 corazones serían C13,5. Por último me quedan todavía dos
cartas por dar para completar la mano, de donde puedo elegir cualquiera que no sea
picas ni corazones, es decir 13 tréboles y 13 rombos, es decir C26,2
Por tanto el resultado final es C13,6. C13,5. C26,2


8. ¿Cuántos números enteros entre 1000 y 9999 satisfacen que la suma de sus dígitos
es exactamente 9?
¿Cuántos de los números anteriores tienen todas sus cifras diferentes de cero?


SOLUCIÓN:

a) Es equivalente a ¿cuántas soluciones enteras