Combinatoria | Construyendo un muro

Question

Deje $n$ ser un entero positivo. Un niño construye un muro a lo largo de una línea con $n$ idénticos a los cubos. Él pone el primer cubo en la línea y en cada paso posterior, se establece el siguiente cubo, ya sea en el suelo o en la parte superior de otro cubo, por lo que tiene una cara común con la anterior. Cuántas de estas distintas paredes existen?

Mi intento: En total hay n cubos así que supongamos que hay " m " el número de pilas de dichos cubos. Ahora necesitamos encontrar en cuántas formas de n se puede descomponer en m enteros. Estoy en lo cierto?

Answer 1

Para mayor brevedad, de la llamada "muralla" construido con $n$ cubos de un $n$-de la pared. Llamar a dos $n$-paredes diferente si, visto de izquierda a derecha, se mira diferente. Nos dan dos formas de contar la $n$-paredes, la segunda mucho más sencilla que la primera. Pero la primera forma tiene la ventaja de que surge de la experimentación con números pequeños. Que siempre se debe hacer, con el fin de tratar de tener una visión acerca de un nuevo problema combinatorio.

Es claro que el número de $1$-paredes es $1$.

El $2$-las paredes son de $11$ e $2$. Hay $2$ de ellos.

El $3$-las paredes son de $111$, $21$, $12$, y $3$. Hay $4$ de ellos.

Hacemos una lista de las $4$-paredes, cuidadosamente. Hay $8$ de ellos, $1111$, $211$, $121$, $31$, $112$, $22$, $13$, y $4$.

No es irrazonable suponer que el número de $n$-paredes es $2^{n-1}$, aunque hay que reconocer que la evidencia es escasa.

Ahora vamos a probar la conjetura de que, técnicamente por inducción. Supongamos que sabemos que para algunos $n$, que el número de $n$-paredes es $2^{n-1}$. Cuántas $(n+1)$-las paredes son de allí?

Hay dos tipos de $(n+1)$-de la pared. Tipo $A$ tiene un $1$ en el extremo derecho. Tipo $B$ tiene un número $>1$ en el extremo derecho.

Es evidente que el número de tipo de $A$ $(n+1)$-paredes es $2^{n-1}$. El tipo de $A$ $(n+1)$-las paredes se obtienen mediante la toma de cualquier $n$-de la pared, y añadiendo un $1$ en el extremo derecho. Dado cualquier tipo de $A$ $(n+1)$-de la pared, tenemos la oportunidad única de recuperar la $n$-muro que "viene de" por la eliminación de la terminal de $1$.

También hay $2^{n-1}$ tipo $B$ $(n+1)$-de las paredes. Se obtienen mediante la adición de un cubo en la parte superior de la derecha de la pila de un $n$-de la pared. Dado un tipo de $B$ $(n+1)$-de la pared, tenemos la oportunidad única de recuperar la $n$-muro que "viene de" por la eliminación de la parte superior del cubo de la derecha de la pila del tipo $B$ $(n+1)$-de la pared.

De ello se deduce que el número de $(n+1)$-paredes es $2^{n-1}+2^{n-1}$, es decir, $2^n$, dos veces tantas como el número de $n$-paredes.

Ya sabemos que el número de $1$-paredes es $2^{1-1}$, con esto se completa el proceso de inducción. De manera más informal, sabemos que hay $1$ $1$-de la pared. Por lo tanto, sin lista, sabemos que no debe ser $2$ $2$-de las paredes. Por lo tanto, sin lista, sabemos que debe haber $4$ $3$-de las paredes. Pero por lo tanto no debe ser $8$ $4$-de las paredes. Y por lo tanto no debe ser $16$ $5$-de las paredes. Y así para siempre.

De otra manera: Imagine que el hijo de la hermana mayor es un profesional de la pared diseñador. Ella establece el $n$ cubos en una larga fila, con un espacio de un par de centímetros entre consecutivos cubos. Hay $n$ cubos, y por lo tanto $n-1$ espacios.

Entonces, el diseñador elige un subconjunto del conjunto de $n-1$ espacios, y coloca una cinta en cada espacio. (Ella puede elegir el vacío subconjunto de la $n-1$ espacios, o simplemente $1$ de los espacios, o $2$, y así sucesivamente.)

Ahora su hermano pequeño se construye la pared. Los cubos desde el extremo izquierdo de la fila a la primera cinta que se amontonan unos sobre otros, para hacer la parte izquierda de la pared (si $0$ espacios fueron elegidos, todos los cubos de ir en la parte superior de uno al otro). Los cubos de la primera cinta de la segunda son apilados en la parte superior de uno al otro, inmediatamente a la derecha de la primera pila. Y así sucesivamente.

Es claro que no son exactamente el número de $n$-paredes, ya que hay maneras de elegir un subconjunto de la $n-1$ lagunas. Pero cualquier conjunto de $n-1$ elementos de ha $2^{n-1}$ subconjuntos, por lo que hay $2^{n-1}$ $n$-de las paredes.

Comentario: Vamos a agregar una regla a la pared del edificio: La pared debe ser exactamente $m$ cubos de largo. A continuación, en el segundo argumento, el diseñador debe elegir exactamente $m-1$ de la $n-1$ huecos para poner una cinta en. De ello se deduce que el número de diferentes paredes de longitud exactamente $m$ es $\binom{n-1}{m-1}$.

Answer 2

Su definición permite una considerable elección en el orden en el que los bloques de la pared terminada se establecen. Voy a suponer que usted considere dos paredes que parecen idénticas a ser "el mismo" de la pared, incluso si han sido construidos por los diferentes métodos.

Ahora, por cada pared terminada hay muchas maneras de construir. Pero podemos tomar la decisión de construir todas las paredes de izquierda a derecha, de tal manera que podamos generar primero la columna de la izquierda hasta su altura final, luego la siguiente a la columna de la izquierda una así sucesivamente. Esta regla nos va a permitir construir todo lo posible de la pared en una y sólo una manera.

Mientras seguimos a la izquierda-a-derecha principio, cada vez que entregamos un bloque, tenemos una opción para hacer: podemos añadir a la columna ya estamos construyendo, o podemos empezar una nueva columna a la derecha de la misma. Esta opción no se puede deshacer después, porque determina completamente si la columna actual de la final, la altura será su altura actual o algo superior.

Hay dos opciones para elegir entre cada vez que se pone un bloque, a excepción de la primera, que sólo puede ser puesto en un camino. Por lo tanto, si tenemos $n$ bloques en total, entonces el número de maneras en que todas las decisiones que se puede hacer es $$1 \times \underbrace{2 \times 2 \times \cdots \times 2}_{n-1\text{ factores}} = 2^{n-1}$$ y esto también debe ser el número de posibles diferentes acabados de las paredes.

Alternativa: El enfoque que se esboza en la pregunta también podría trabajar. Esto lleva a que el número de longitud-$m$ paredes con $n$ cubos siendo el coeficiente binomial $\binom{n-1}{m-1}$. Tomando la suma de esto para todas las $m$ da $2^{n-1}$ (que es un hecho acerca de los coeficientes binomiales que necesitaría saber de antemano).

Answer 3

Su método sugerido de trabajo.

Hay una forma de colocar el primer bloque.

Hay tres maneras de colocar el segundo bloque: a la izquierda, en la parte superior, o a la derecha del primer bloque.

El número de maneras de colocar el tercer bloque dependerá de la anchura de los dos bloques de la pared.

Así que vamos a $f(n,w)$ el número de maneras de construir una $n$-pared de bloques de anchura $w$. Empezar con $f(1,1)=1$ e $f(1,w)=0$ para $w \not = 1$. Entonces usted tiene $$f(n,w)=2f(n-1,w-1)+wf(n-1,w)$$

and the following table

            w   
f(n,w)      1   2   3   4   5   6

n   1       1   0   0   0   0   0
    2       1   2   0   0   0   0
    3       1   6   4   0   0   0
    4       1   14  24  8   0   0
    5       1   30  100 80  16  0
    6       1   62  360 520 240 32

Adding up the rows gives the sequence $1,3,11,47,227,1215,\ldots$ which turns out to be OEIS A035009, half of OEIS A001861.

Added:

Henning Makholm's comments suggest looking at the finished wall instead of the building. In that case, $f(n,w) = {n-1 \elegir w-1}$ (a basic result from counting compositions) and the sums over $w$ are $2^{-1}$ como dice en su respuesta.

Answer 4

Su definición es algo confuso; supongo que un bloque colocado en el suelo tiene que ser adyacente a la previamente construida la torre, o bien hay un número infinito de estas paredes.

Pero también, depende de cómo se está definiendo la descomposición. Las pilas de la pared puede ser construido en cualquier orden, y aquellos que son considerados como diferentes paredes. Por otro lado, suponiendo que estamos definiendo una descomposición como una representación de n como suma de m enteros positivos de dos cantidades diferentes en los distintos órdenes será el mismo.

Por lo tanto, si el orden importa en su descomposición, entonces estás en lo correcto: cualquier secuencia de (positivo) la adición de números enteros de n puede ser hecho en una pared por la construcción de una torre con la altura de la primera entero, a continuación, empezar con el segundo entero, etc. Del mismo modo, cualquier pared produce una secuencia de números enteros, así que esto le da un bijection entre los dos conjuntos de ser contada. Si usted hace caso omiso de la orden, el número de las paredes es mucho más grande.