RECURSOS DE CONTEO: LISTAS Y ÁRBOLES

Definición:Para cualquier conjunto finito, se escribe || para denotar la cantidad de elementos de dicho conjunto, de esta manera || = || precisamente cuando s y t son del mismo tamaño. Observemosque:
||=0 y |{1,2,3...n} | = n n+
Regla de la Suma (Regla de la Unión)Si  y son dos conjuntos finitos:
a) Si  y son disjuntos, es decir,  = , entonces || = || + ||
b) En general || = || + ||  ||La razón intuitiva por la que se cumple b) es que cundo calculamos || + || se estan contando dos veces los elementos de , por lo que debemos restar || de la suma de || + || para obtener ||
Regla delProducto (Principio de Elección)Para conjuntos finitos S y T se tiene que | S  T | = | S | · | T | ya que S  T = { ( s, t ) | s  S y t  T } y para cada una de las | S | selecciones en s en S hay | T |elecciones para t en T.Ejemplo:Sean S = {1, 2} y T = { a, b, c }, entonces | S | = 2 y | T | = 3, por lo que:
| S  T | = | S | · | T | = 2 · 3 = 6, dichos elementos son:
S  T = {( 1, a ), (1, b),(1, c), (2, a), (2, b), (2, c)}
4.2 RECURSOS DE CONTEO: LISTAS Y ÁRBOLES
Para ver estos recursos será más fácil si empezamos con un
Ejemplo:En el menú de un restaurante se tienen dos entradas, tresplatos principales y cuatro bebidas ¿Cuántas posibles combinaciones de comidas diferentes constan de un plato principal y una bebida?
Primeramente veamos el menú:
Entrada Plato Principal BebidasNachos (N) Hamburguesa (H) Te (T)
Ensalada (E) Hamburguesa con queso (Q) Leche (L)
  Filete de Pescado (F) Café (C)
    Cerveza de Raíz (R)
Si listamos todas las posibles comidas que constan de unplato principal y una bebida
HT, HL, HC, HR, QT, QL, QC, QR, FT, FL, FC, FR
se ve que hay 12 comidas diferentes. Ya que hay 3 platos principales y 4 bebidas, por la regla del producto 3 · 4 = 12comidas diferentes.
Además existen 24 comidas diferentes que constan de una entrada, un plato principal y una bebida, las cuales son:
NHT, NHL, NHC, NHR, NQT, NQL, NQC, NQR, NFT, NFL, NFC, NFREHT, EHL,...