jump to navigation

Contar subconjuntos Julio 15, 2008

Posted by Álvaro in combinatoria, teoremas, trucos, varios.
Tags: , ,
trackback

Una de las técnicas básicas para resolver problemas es contar de varias formas, ésta vez veremos las formas de contar subconjuntos de un conjunto que para propósitos prácticos es [n] = {1, 2,….,n}.

De hecho la notación {n \choose k} se inventó para expresar la cantidad de subconjuntos con k elementos en [n]. Pero primero hay que pensar en cosas mas fáciles…
¿cuántas opciones tenemos para escoger un elemento en [n]?
¿de qué formas distintas podemos escoger los n elementos?
¿de cuántas formas podemos hacer una lista de k elementos de [n]?

Bueno, una vez que entendemos esas preguntas y las repasamos en la mente mucho tiempo hasta el cansancio podemos pasar a ver ejemplos de contar formas de escoger subconjuntos.

1
Demostrar que la cantidad total de subconjuntos de [n] (incluyendo el vacío y el total) es 2^n

2
Calcular el promedio de tamaño de los subconjuntos de [n]

3
¿cuántas listas crecientes hay de tamaño k con elementos de [n]?

4
en un conjunto de n casillas, ¿cuántas formas hay de acomodar fichas de modo que cada casilla tenga a lo más una ficha y exactamente una tenga 2?

Ahora podemos pasar a ver problemas un poco mas difíciles…
Imaginemos una mesa redonda y n sillas, cada una con su número, en este conjunto los subconjuntos no pueden distinguirse si se ven desde cada posición, entonces hay varios que se ven igual (por cada giro de 1/n). Así hay preguntas naturales como:
¿cuántas formas distintas (salvo giros) hay de acomodar las sillas?
¿de cuántas formas podemos acomodar k personas en la mesa con las n sillas?
¿importa si n es primo?

He aquí algunos problemas:
5
¿de cuántas formas distintas (salvo el giro) podemos repartir las todas las sillas en 3 grupos?

6
si tenemos a las personas numeradas del 1 al n ¿de cuántas formas se pueden acomodar en las sillas numeradas si estas no estan necesariamente en orden?

7
si n es primo y a, b son ambos menores que n ¿de cuántas formas distintas podemos colorear a sillas de b colores?

Bueno, al final llegamos al siguiente resultado bonito usando solo conteo:

Si p es primo tenemos que: a^p-a es divisible entre p

La demostración es muy fácil, aunque sugiero intentarla antes de leerla.
En una mesa con p sillas hay que colorearlas de a colores y contar las formas distintas de colorear con al menos 2 colores, como son p sillas y cada una tiene a opciones para colorearse, tenemos que la cantidad total de coloraciones es a^p, pero de ellas hay a que consisten en todas las sillas coloreadas del mismo color (una por cada color). Y por cada coloración hay p giros que no se pueden distinguir, entonces en total tenemos \frac{a^p-a}{p} coloraciones con al menos 2 colores. Como éste número es entero, el numerador es divisible entre el denominador. QED

Un buen problema de tarea (dificil) es:
Demostrar que \displaystyle \sum_{k = 1}^{n-1} {n \choose k}^{-1} \leq 1

Comentarios»

1. Álvaro - Julio 29, 2008

Esta es la solución para el último problema:
Es fácil ver que el problema es equivalente a demostrar que:
\displaystyle \sum_{k=1}^{n-1} k!(n-k)! \leq n!

veamos cómo es cada término de la suma:
k! (n-k)!
que se puede interpretar como la cantidad de permutaciones de una lista de n elementos tales que los primeros k elementos quedan permutados en los primeros k lugares y los demás en los últmos (n-k) lugares.

Como no todas las permutaciones son de ésta forma, cuando contamos todas las permutaciones (n! ) son mas que todas las que dejan a los primeros k elementos en los primeros k lugares (para cada k)

Responder