Contar subconjuntos

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

Un comentario en “Contar subconjuntos

  1. 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)

incluye tu respuesta

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s