MÉTODOS DE CONTEO Y EL PRINCIPIO DEL PALOMAR

En muchos problemas discretos nos enfrentamos al problema de contar. Por ejemplo, en la sección 4.3 se vio que para estimar el tiempo de corrida de un algoritmo, era necesario contar el número de veces que se ejecutaban ciertos pasos o ciclos. Contar, también tiene un papel crucial en la teoría de probabilidad. En virtud de la importancia del conteo, se ha desarrollado una variedad de ayudas útiles, algunas bastante elaboradas. En este capítulo se desarrollan varias técnicas para contar. Dichas técnicas resultan útiles para derivar el teorema del binomio. El capítulo concluye con un análisis del principio del palomar, que con frecuencia permite probar la existencia de un objeto con ciertas propiedades

El menú de Comida Rápida de Kay se muestra en la figura 6.1.1. Como se observa, contiene dos entremeses, tres platos fuertes y cuatro bebidas. ¿Cuántas comidas diferentes están formadas por un plato fuerte y una bebida? Si se listan todas las comidas posibles que consisten en un plato fuerte y una bebida,

HT,  HM,  HC,  HR,  CT,  CM,  CC,  CR,  FT,  FM,  FC,  FR,

se ve que existen 12 comidas diferentes. (La comida que consiste en un plato fuerte cuya primera letra es X y una bebida cuya primera letra es Y se denota por XY. Por ejemplo, CR se refiere a una comida que consiste en carne asada y raspado de sabor). Observe que se tienen tres platos fuertes y cuatro bebidas, lo que da 12 =3 · 4.

ENTREMÉS

PLATO FUERTE

Nachos 2.15 Salami especial 1.90

Hamburguesa 3.25 Carne asada 3.65

Filete de pescado 3.15

BEBIDAS Té .70 Malteada .85

Cola .75 Refresco de sabor .75

Figura 6.1.1 Comida Rápida de Kay.

NHT, NHM, NHC, NHR, NCT, NCM, NC

Existen 24 comidas posibles de un entremés, un plato fuerte y una bebida.

(La comida que consiste en un entremés cuya primera letra es X, un plato fuerte cuya primera letra es Y y una bebida cuya primera letra es Z se denota por XYZ). Observe que se ofrecen dos entremeses, tres platos fuertes y cuatro bebidas, y que 24 =2 ·3 · 4. En cada uno de estos ejemplos se encuentra que el número total de comidas es igual al producto de los números de cada categoría. Estos ejemplos ilustran el principio de la multiplicación