Circuitos hamiltonianos

Un circuito hamiltoniano es un recorrido cerrado de un grafo que pasa por todos sus vértices una única vez. Si nos limitamos a grafos en forma de grillas cuadradas, podemos encontrar fácilmente un circuito en las grillas con una cantidad par de vértices siguiendo este esquema:

Circuito hamiltoniano en una grilla de 8x8 vértices.

Circuito hamiltoniano en una grilla de 8x8 vértices.

Puede encontrarse un circuito de esta misma naturaleza en una grilla cuadrada con una cantidad impar de vértices? Cambia esto si se permiten grillas rectangulares?

La respuesta a este problema (y al anterior de sumas) en el próximo post…

Números de Stirling de segunda especie

Contar la cantidad de formas en que pueden distribuirse n elementos en k cajas es bastante simple, una vez que descubrimos el truco de pensarlo como asignarle un número de caja a cada elemento. Claramente esto nos da k^n posibles formas. Si ignoramos el “etiquetado” de las cajas, claramente esto nos deja k^n/k! formas.
[Nota 22/7/13: este análisis es incorrecto, como indica Jon abajo. El análisis correcto de este se encuentra en una nueva página.]

Este problema se hace más difícil si agregamos la restricción de que ninguna caja puede permanecer vacía y, de hecho, recuerdo haber esquivado resolver este problema en más de una ocasión (y no soy el único 😀 ). Pero en Wikipedia encontré una solución elegante y, tal vez, lo suficientemente memorable para que la recuerde en caso de encontrarme nuevamente con este problema…

Denominemos

\left\{\begin{matrix} n \\ k \end{matrix}\right\}

al número de distintas formas en las que podemos distribuir n elementos en k cajas sin dejar ninguna vacía y sin distinguir entre cajas (o sea el número de distintas particiones de \{1,2,...,n\} en k subconjuntos). Entonces podemos dividir las formas de efectuar esta distribución en dos clases: las que ponen al elemento n solo en una caja y las que no lo hacen.

Una vez situado el elemento n en una caja, las distribuciones serán equivalentes a n-1 elementos en k-1 cajas. Por lo tanto, habrá

\left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\}

formas de efectuar la distribución dejando solo al elemento n.

Por otro lado, si el elemento n no se encuentra solo, el problema es equivalente a distribuir n-1 elementos en k cajas sin dejar ninguna vacía y luego insertar el elemento n en alguna de ellas (distinguibles por tener distintos subconjuntos de los elementos). En consecuencia habrá

k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}

formas de efectuar la distribución sin dejar al elemento n solo en una caja.

En conjunto eso nos deja la relación de recurrencia

\left\{\begin{matrix} n \\ k \end{matrix}\right\} = \left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\} + k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}

para estas cantidades, denominadas números de Stirling de segunda especie.