Encuentre el número de arreglos posibles de N discos con una restricción dada

Question

De cuántas maneras se puede hacer una pila de N discos, tal que:

1. El disco inferior siempre tiene radio 1

2. Un disco puede colocarse en la pila si su radio es <= (el máximo de todos los radios de los discos por debajo de él + 1)

Se le da un suministro infinito de discos con todos los radios.

He pensado en un par de enfoques de recuento, pero eso tiene muchos solapamientos en la solución ya contada y no soy capaz de deshacerme de ella :(

Answer 1

Mi interpretación es que para $N=3$ las posibles torres son

1   2   1   2   3
1   1   2   2   2
1   1   1   1   1

Dejemos que $k$ sea el mayor radio de la torre, y así el siguiente disco puede ser más ancho en $k+1$ o puede ser uno de los radios existentes.

Dejemos que $S_2(N,k)$ sea el número de torres con $N$ discos y el mayor radio $k$ . Entonces $$S_2(N,k) = S_2(N-1,k-1) + k S_2(N-1,k)$$ que es la recurrencia para Números Stirling del segundo tipo .

Su suma sobre $k$ da la Números de campana $B_N$ que no tiene una fórmula cerrada simple, aunque la de Dobinski $$\frac{1}{e}\sum_{j=0}^{\infty} \frac{j^N}{j!}$$ es bastante bonito.

Esta imagen de OEIS A000110 puede dar una idea de por qué las preguntas son equivalentes: cada bola etiquetada es el siguiente nivel, mientras que cada nueva caja sin etiquetar es el siguiente radio.

Answer 2

Creo que estás viendo el Números de campana . Henry ya explicó sucintamente cómo obtener este resultado encontrando la recurrencia de los números de Stirling del segundo tipo (que cuentan las particiones de un $n$ -enviar a $k$ bloques sin etiquetar), pero añadiré un poco más de detalle. Al pasar de un $N-1$ pila a un $N$ se produce una de estas dos situaciones: o bien el nuevo disco es más grande que cualquiera de los anteriores, o bien al menos un disco anterior es igual de grande. Designar por $k$ el tamaño del disco más grande, entonces en la primera situación el $N-1$ La pila tiene $k-1$ como su mayor tamaño (y sólo hay una forma de extenderlo a una pila con $k$ como mayor tamaño), mientras que en la segunda situación el $N-1$ La pila tiene $k$ como su mayor tamaño, y se puede ampliar con cualquier disco de tamaño desde $1$ a $k$ . Denotando por $S(N,k)$ el número de pilas de altura $N$ con $k$ el tamaño del disco mayor, obtenemos la relación de recurrencia $$S(N,k) = S(N-1,k-1) + kS(N-1,k)$$ que dio Henry. Se puede reconocer esto (junto con $S(N,1)=1$ y $S(1,k)=0$ para $k>1$ ) como la relación que define los números de Stirling del segundo tipo, o en caso de que se te "olvide", puedes calcular una parte inicial de la matriz (triangular) de números, y reconocerlos, por ejemplo, buscando en el OEIS .

También permítanme aclarar cómo pueden relacionar sus pilas con tales pariciones, con $k$ variable (para obtener la suma de los números Stirling sobre todos los $k$ , dando el número de Bell).

Una pila divide el conjunto de los $N$ posiciones de los discos (digamos $1$ para el fondo, hasta $N$ para la parte superior) en bloques de posiciones que albergan discos del mismo tamaño $i$ con $i$ que varía de $1$ hasta un tamaño máximo $k$ . Para recuperar la pila de esta partición (de la cual las partes son sin etiquetar ), sólo hay que etiquetar con $1$ el bloque que contiene la posición inferior $1$ , entonces por $2$ el bloque con el menor resto de posición (es decir, que no esté ya en el primer bloque), si lo hay, entonces por $3$ el bloque con la posición restante más baja (es decir, que no esté ya en los dos primeros bloques), si lo hay, y así sucesivamente hasta etiquetar el último bloque $k$ . A continuación, ponga un disco de tamaño $i$ en cada posición del bloque etiquetado $i$ y que para $i=1,\ldots,k$ . Claramente esto satisface su restricción, y establece una biyección entre pilas y particiones en bloques.