Teoria combinatoria

TEORÍA COMBINATORIA

El origen de los problemas de conteo o “teoría combinatoria” se relaciona con los juegos de azar, más concretamente, con los juegos de cartas y dados. El tratamiento teórico de los problemas de conteo se inicia en el siglo XVII con los matemáticos Blaise Pascal (1623-1662) y Pierre de Fermat (1601-1665). El problema que dio origen a la teoría tiene que ver con la divisiónde las apuestas en un juego de lanzamiento de monedas que el Caballero de Meré –un jugador empedernido– le planteara a Blaise Pascal. El juego consistía en el lanzamiento de una moneda sucesivas veces. El ganador es el jugador que alcanza primero 6 éxitos (6 caras ó 6 números). Pero el juego se interrumpe si en el noveno lanzamiento se obtiene el resultado 5 a 4. El problema planteado por elCaballero de Meré tenía que ver con la forma en que se deben repartir las apuestas acumuladas al interrumpirse el juego, en tanto no hay un ganador. El Caballero de Meré creía que lo más justo era repartir las apuestas en la relación 5 a 4, pero no estaba convencido. Pascal demostró que las apuestas debían repartirse en la relación 3 a 1 si se toma en consideración que, de continuar el juego, quienlleva 5 éxitos tiene 3 veces más chance de ganar el juego que su contrincante. Supongamos que quien apuesta por “cara” lleva 5 éxitos.

C gana C
½

C gana C
½ N ½

½
N gana N

P(que gane quien apuesta por C) = ½ + ½ . ½ = 3/4
P(que gane quien apuesta por N) = ½ . ½ = ¼

Los problemas deconteo se presentan en muy diferentes ámbitos. Un jefe debe distribuir 3 tareas diferentes entre sus tres funcionarios, un entrenador debe elegir 11 jugadores para un partido de fútbol entre los 18 de su plantel, un jefe de producción debe decidir qué parte de la producción asignará a las máquinas A, B, C y D, un especialista en diseño gráfico debe elegir una combinación de 3 colores entre 5 posiblespara ilustrar una caja de cartón que sirve de envase, un investigador de mercado debe elegir entre diferentes criterios de clasificación (edad, sexo, nivel socio-económico, conocimiento previo del producto) para formar grupos de discusión (focus groups), 99 diputados deben seleccionar para votar entre 3 proyectos de ley alternativos. Una pregunta relevante es “¿Cuáles son los resultados posiblesen estos problemas?”. A veces, enumerar todos los casos posibles puede ser muy engorroso. Por ejemplo, supuesto que los 18 jugadores de fútbol son polifuncionales (cualquiera de ellos puede jugar en cualquiera de los 11 puestos) el entrenador tiene más de un billón de formas de seleccionar los jugadores para el partido. En cambio, las formas en que se pueden asignar las 3 tareas entre los 3funcionarios (supuesto que todos deben trabajar) es un número sensiblemente menor: es el número de formas en que se pueden reordenar las tres tareas, 6 en total:

| |FUNCIONARIOS |
| | |
| | |
| ||
|TAREAS | |
| |A |B |C |
| |1 |2 |3 |
| |1 |3 |2 |
| |2 |1 |3 |
||2 |3 |1 |
| |3 |1 |2 |
| |3 |2 |1 |

Un problema más sencillo que el de enumerar todos los casos posibles consiste en responder a la pregunta “¿Cuántos son los casos posibles?” Esta es la pregunta clave en los problemas de conteo. Por ejemplo,...