Siguiente: PB visto como un Un nivel arriba: Expresiones regulares y sistemas Anterior: Introducción

El mundo de los bloques

Consideremos n bloques, enumerados con los números naturales $\mbox{\bf n}=[1, 2, \ldots, n]$. Asociémosle al piso el número 0. El mundo es $\mbox{\bf n+1}=\{0\}\cup\mbox{\bf n}$. En cada estado, o configuración del universo, tendremos un cierto número de columnas, cada una de ellas constituída por bloques apilados. Ya que cada bloque está bien sobre el piso o bien sobre algún otro bloque, a cada configuración podemos asociarle una función $\mbox{\it apoyo\/}: \mbox{\bf n}\rightarrow\mbox{\bf n+1}$. Naturalmente, si $\mbox{\it apoyo\/}( i ) = j$ tendremos que el bloque i está sobre el objeto j. Así pues,tendremos las siguientes propiedades para una tal función apoyo:

1.

``Sólo el piso puede ser apoyo de más de un bloque''. En símbolos

$$\forall i , j \in \mbox{\bf n} : \mbox{\it apoyo\/}( i ) = \m... ...}( j ) \& i \not= j \ \Rightarrow\ \mbox{\it apoyo\/}( i ) = 0.$$

2.

``El número de columnas en un estado coincide con el de bloques apoyados en el piso''. En símbolos:

$$\mbox{\it n\'umero\_columnas\/} = \mbox{\it card\/}[\mbox{\it apoyo\/}^{-1}{ 0 } ].$$

3.

``Las columnas no son aros''. En símbolos:

$$\forall i \in\mbox{\bf n}\forall k \geq 1 : \mbox{\it apoyo\/}^k( i ) \not= i.$$

4.

``Cada columna tiene una base en el piso''. En símbolos:

$$\forall i \in\mbox{\bf n}\exists k \geq 1 : \mbox{\it apoyo\/}^k( i ) = 0.$$

5.

``Cada bloque está sobre su apoyo''. En símbolos:

$$\forall i e \mbox{\bf n} : \mbox{\it sobre\/}( i , \mbox{\it apoyo\/}( i ) ).$$

Los estados del universo corresponden de manera biunívoca con las funciones de apoyo. Por tanto, contar los posibles estados en el PB equivale a contar las funciones de apoyo. Sea pues

$$A_n= \{\mbox{\it apoyo\/}:\mbox{\bf n}\rightarrow\mbox{\bf n+1}\mbox{\rm cumple con las propiedades } 1-5\}.$$

Para una función $\mbox{\it apoyo\/}\in A_n$, sea k el número de columnas que define y $\forall j\leq k$ sea h_j el número de bloques en la columna j-ésima. Supondremos a las columnas ordenadas de manera no-decreciente en cuanto a sus alturas. Entonces tendremos que $0 \leq h_1 \leq \ldots \leq h_k$ y además $h_1 + \ldots + h_k = n$. En este sentido, diremos que el estado determina a la sucesión $( h_1, \ldots , h_k)$. Surge pues la necesidad de analizar al conjunto de sucesiones

$$H_{n,k}= \{ ( h_1, \ldots , h_k) \in\mbox{\bf n}^k\vert \leq h_1 \leq \ldots \leq h_k \&\sum_{j=1}^k h_j=n\}.$$

Observamos que dos estados $\mbox{\it apoyo\/}_1$ y $\mbox{\it apoyo\/}_2$ determinan a una misma sucesión $( h_1, \ldots , h_k)\in H_{n,k}$ si y sólo si el estado $\mbox{\it apoyo\/}_1$ difiere del estado $\mbox{\it apoyo\/}_2$ tan sólo por una permutación de los n bloques en el Mundo. Tenemos n! permutaciones tales. Ahora, para una sucesión $( h_1, \ldots , h_k)\in H_{n,k}$ podemos tener varias de sus entradas iguales, en otras palabras, en cada estado que determine a la sucesión, varias de sus columnas pueden tener una misma altura. Tomemos pues el conjunto de valores distintos que aparecen en ella. Sea éste $\mbox{\it con\/}( \mbox{\bf h} ) = \{ h \in\mbox{\bf n}\vert \exists i\leq k : h = h_i\}$. Para cada $h \in \mbox{\it con\/}( \mbox{\bf h} )$, contemos sus repeticiones en $\mbox{\bf h}$, sea pues $\mbox{\it repet\/}( h ) = \mbox{\it card\/}\{ i \leq k \vert h_i = h \}$. Convengamos también en identificar columnas de igual tamaño. De esta manera, $\forall h \in \mbox{\it con\/}( \mbox{\bf h} )$, $\left[\mbox{\it repet\/}( h )\right]!$ permutaciones de columnas de altura h quedarán identificadas. Luego, habrá $c(\mbox{\bf h}) = {\displaystyle \prod_{h \in \mbox{\it con\/}( \mbox{\bf h} )}\left[\mbox{\it repet\/}( h )\right]!}$ estados identificados, cada uno de los cuales determina a la sucesión $\mbox{\bf h}$. Hechas las observaciones anteriores, un minuto de reflexión basta para convencerse de que vale la relación siguiente:

$$\mbox{\it card\/}(A_n)=n!\sum_{k=1}n\sum_{\mbox{\bf h}\in H_{nk}}\frac{1}{c(\mbox{\bf h})}$$ (44)

Pasemos ahora a encontrar una expresión equivalente cuya evaluación sea más sencilla. Dados n > 1 y $k \leq n$, ¿de cuántas formas podemos expresar a n como una suma de k sumandos enteros positivos?. En otras palabras, si definimos

$$S_{nk}= \{ ( h_1, \ldots , h_k)\in\mbox{\bf n}^k\vert \sum_{j=1}^k h_j=n\},$$

¿cuál es la cardinalidad de S_nk? Observemos que, en su representación unaria, n se escribe como una sarta de n 1's, es decir, como n ``palitos contiguos''. En esa sarta tendremos n-1 separaciones entre palitos adyacentes. Si elegimos a k-1 de tales separaciones para introducir otras tantas marcas separadoras, los n palitos quedarán agrupados en k hatos contiguos, cada uno con al menos un palito, y la suma de todos ellos nos da, en efecto, los n palitos. Así pues, tendremos que $\mbox{\it card\/}(S_{nk})={n-1\choose k-1}$. Ahora, cada sucesión $\mbox{\bf h}\in H_{nk}$ tiene a sus entradas ordenadas de manera no-decreciente. Si omitimos esta exigencia de orden, un segundo minuto de reflexión nos convencerá de que la sucesión $\mbox{\bf h}$ dará origen a $\frac{k!}{c(\mbox{\bf h})}$ elementos distintos en S_nk. Al conjuntar estas dos observaciones, tenemos que $\sum_{\mbox{\bf h}\in H_{nk}}\frac{k!}{c(\mbox{\bf h})}=\mbox{\it card\/}(S_{nk})$ y consecuentemente

$$\sum_{\mbox{\bf h}\in H_{nk}}\frac{1}{c(\mbox{\bf h})}=\frac{1}{k!}{n-1\choose k-1}$$ (45)

Una mera manipulación algebraica da $\frac{1}{k!}{n-1\choose k-1}=\frac{1}{n(k-1)!}{n\choose k}$. Así pues, logramos nuestro objetivo al sustituir 4.34 en 4.33:

$$\mbox{\it card\/}(A_n)=(n-1)!\sum_{k=1}^n\frac{1}{(k-1)!}{n\choose k}$$

Lo que equivale a que

$$\mbox{\it card\/}(A_n)=\sum_{k=0}^{n-1}k!{n-1\choose k}{n\choose k}=:a_n$$ (46)

Esta última relación nos da la naturaleza explosiva del PB. En la Tabla 4.3 presentamos algunos números de estados resultantes con diversos números de bloques.

  

Table 4.3: Estados en el PB en función de los bloques.

Se ve que $\mbox{\it card\/}(A_n)=\Omega(10^{n})$. Este crecimiento rápido del número de estados es lo que, en la práctica, hace intratable al PB con este enfoque. Sin embargo, aún nos dedicaremos a él para ilustrar el uso de expresiones regulares.
Siguiente: PB visto como un Un nivel arriba: Expresiones regulares y sistemas Anterior: Introducción