Para $x$ perros, elige cuántas jaulas para dos perros se necesitan. Esto oscilará entre $0$ a $\left\lfloor\frac{x}{2}\right\rfloor$ . Llamemos al número de jaulas de dos perros utilizadas $k$ .
Dado que estamos utilizando $k$ jaulas para dos perros, elija cuál $2k$ a los perros en jaulas para dos perros. A continuación, clasifique estos perros según un orden arbitrario ( por ejemplo, por número )
A continuación, entre todos los perros designados para ser colocados en jaulas de dos perros, elija al que se coloca en la jaula con el perro más pequeño. A continuación, elija al perro más pequeño que quede en la jaula. Repita este proceso hasta que todos los perros designados para ser colocados en jaulas de dos perros tengan sus parejas seleccionadas.
Sobre todos los valores de $k$ que tenemos como resultado:
$$1+\sum\limits_{k=1}^{\left\lfloor\frac{x}{2}\right\rfloor}\binom{x}{2k}(2k-1)!!$$
( notación factorial doble $n!!=n(n-2)(n-4)(n-6)\cdots(2~\text{or}~1~\text{depending on if $ n $ is even or odd})$ . Por ejemplo $6!!=6\cdot 4\cdot 2$ y $9!!=9\cdot 7\cdot 5\cdot 3\cdot 1$ )
( edit: cambiado el índice para empezar desde $k=1$ en lugar de tener que tratar de definir $(-1)!!$ como igual a $1$ o utilizando métodos más complicados para escribir el producto )
En cuanto a una solución alternativa, a partir de los comentarios anteriores podemos seguir los enlaces y llegar finalmente a la página de números de teléfono(matemáticas) que son exactamente los valores que desea calcular, lo que da lugar a otras formas bastante agradables de calcular el número.
Uno de estos métodos es el de las relaciones de recurrencia.
$T(0)=1,T(1)=1$ y $T(n)=T(n-1)+(n-1)T(n-2)$ para todos $n\geq 2$
La idea es que suponiendo que conozcamos el valor $T(k)$ para todos $k<n$ para encontrar $T(n)$ nuestra $n$ 'th perro puede estar en una jaula por sí mismo que se puede lograr en $T(n-1)$ maneras, o nuestro $n$ El perro puede estar en una jaula con otro perro. Elija qué perro que es, y luego el resto $n-2$ perros se pueden organizar en $T(n-2)$ maneras.
