Una secuencia con fichas de dominó

Question

Mi amigo se encontró con este problema hace años. Me pidió ayuda, pero tampoco pude resolverlo. La configuración es la siguiente.

Las fichas de dominó se colocan en formación triangular. Algo así...

  (n=2)

Reglas: 1. Si una ficha de dominó es golpeada, puede caer o no. 2. 2. Si una ficha de dominó no es golpeada, no cae.

El problema: $D_n$ es el número de escenarios posibles para un determinado $n$ . Encuentre la fórmula explícita de $D_n$ .

Ejemplo: Para n=2, la ficha de dominó de la parte superior puede caer o no. Si no cae, las dos fichas de abajo no caen. Si lo hace, las dos fichas pueden o no caer. Por lo tanto, $D_2=5$ .

Aclaración: La regla es: la ficha superior puede caer; para cualquier ficha no superior, sólo puede caer si cae al menos una ficha por encima de ella.

Por favor, ayuda. Muchas gracias.

Answer 1

Actualización: Encontré una recurrencia en mi respuesta de enfoque alternativo, aquí .

---

TL;DR

He reducido el problema al cálculo de los "coeficientes de dominó".

Pero parece que estos coeficientes no se pueden calcular fácilmente, y ahí se acaba mi respuesta.

---

Reducir el problema a "coeficientes de dominó"

Si $d_n$ es el número de escenarios con al menos una ficha de dominó caída en el $n$ th fila, entonces

$$D_n=D_{n-1}+d_n$$

Definimos $D_0=1,d_1=1$ . Esto da $D_1=1+1=2$ como se esperaba.

Decimos que una ficha de dominó está "activada" (puede caer) si y sólo si una ficha de dominó por encima de ella ha caído.

$\alpha_n(k)$ es el número de maneras de tener exactamente $k$ fichas de dominó "activadas" en el $n$ th fila.

Ahora a calcular $d_n,n\ge2$ tenemos la expresión

$$d_n=\sum_{k=1}^n \alpha_n(k) \cdot (2^k-1)$$

Porque cada ficha de dominó "activada" se cae o no, dando $2^k$ estados, y restamos $1$ para el caso de que no estén todos caídos porque esa es la definición de $d_n$ .

Si una ficha de dominó cae, activa las dos fichas inferiores. Esto implica que $\alpha_n(1)=0$ porque nunca tenemos exactamente una ficha de dominó activada. Por lo tanto, definimos $\alpha$ para $2\le k\le n$ .

El problema es ahora calcular los "coeficientes de dominó" $\alpha_n(k)$ .

Por fuerza bruta he encontrado el triángulo que da $\alpha_n(k)$ 's para $2\le k\le 7$ es:

$$\begin{array}{} &&&&&& 1 \\ &&&&& 2 && 1 \\ &&&& 7 && 4 && 2 \\ &&& 34 && 21 && 18 && 6 \\ && 233 && 152 && 184 && 104 && 32 \\ & 2370 && 1609 && 2552 && 1888 && 1056 && 288 \\ .&& .&& .&& .&& .&& .&& .\\ \end{array}$$

Filas de lectura $n=2,3,4,5,6,7$ y se introducen los coeficientes en la recursión:

$$D_n=D_{n-1}+\sum_{k=2}^n \alpha_n(k) \cdot (2^k-1)$$

Da $D_n=5,18,97,802,10565,228850$ como se esperaba. (Donde $D_1=2$ .)

---

¿Resolver los coeficientes del dominó?

Para $k=2$ para activar exactamente dos fichas de dominó en $(n)$ th fila, debe caer exactamente una ficha de dominó en $(n-1)$ th fila. Esto da la recursión para el primer coeficiente:

$$\alpha_n(2)=\sum_{r=2}^{n-1}\alpha_{n-1}(r)\cdot r $$

Pero para $k\ge 3$ No veo una recursión obvia.

El número de formas de activar el dominó en el $(n-1)$ th La fila que puede caer ahora depende de las "islas" (carreras consecutivas de fichas de dominó activadas) y de los "huecos" (carreras consecutivas de fichas de dominó no activadas). Para escribir esto como una expresión,

Dejemos que $S(n-1,r)$ sea el conjunto de todos los $(n-1)$ th secuencias de filas de fichas de dominó donde exactamente $r$ se activan las fichas de dominó. Entonces tenemos que sumar sobre todas $s\in S(n-1,r)$ :

$$ \alpha_n(k)=\sum_{r=2}^{n-1}\sum_{s\in S(n-1,r)}f_k(s) $$

Donde $f_k(s)$ devuelve un valor en función del tamaño de cada "isla" $I\in s$ y en función del valor del número de activaciones objetivo $k$ en el $n$ th fila.

Recogiendo todo $s$ secuencias y evaluar $f_k(s)$ función en ellos es un problema ahora.

Obsérvese que el número de elementos de $S(n-1,r)$ es precisamente $\alpha_{n-1}(r)$ .

Si $k=2$ simplemente tenemos $f_2(s)=r$ para todos $s$ que da la recursión $\alpha_{n}(2)$ desde arriba.

Si $k=3$ tenemos $f_3(s)=(r-1)$ si el $s$ contiene exactamente una isla $I$ de longitud $r$ . De lo contrario, tenemos que observar las islas individuales, para obtener:

$$f_3(s)=\sum_{I\in s}(\mathcal L(I)-1)$$

donde $\mathcal L(I)$ es la longitud de la isla $I\in s$ . Esto es cierto porque para tener $k=3$ activó las fichas de dominó en el $(n)$ th fila, necesitamos tener exactamente dos fichas de dominó conectadas en el $(n-1)$ th fila.

Para $k\ge 4$ El $f_k(s)$ ya no es "tan simple" como sumar longitudes de islas.

Para $k=3$ contamos maneras:

• para activar el "single $2$ -particiones largas" de las islas

Para $k=4$ tenemos que contar maneras:

• para activar el "single $3$ -particiones largas" de las islas
• para activar "dos $1$ -particiones largas" separadas con un espacio de al menos un

Y así sucesivamente, para mayores $k$ tenemos más formas de "dividir las activaciones" de las islas.

No veo cómo simplificar esto en una "expresión de forma cerrada (de recursión)".

De ahí que mi respuesta se detenga aquí.

Answer 2

Actualización: @Bartek pone en práctica esta idea y calcula más términos nuevos en su respuesta .

Editar: Gracias @Bartek por tu comentario, he hecho la modificación sugerida.

Nota: . El enfoque alternativo que utiliza los "coeficientes de dominó" está en mi respuesta anterior .

---

TL;DR

Podemos utilizar una recurrencia vectorial para llevar la cuenta de nuevos escenarios de dominó.

Los primeros catorce términos dados por la recurrencia son: ( $D_{14}$ ya es mayor que $10^{21}$ .)

D(n) = 2, 5, 18, 97, 802, 10565, 228850, 8289217, 506526530, 52501381765, 9260170733266, 2784551512218145, 1429063630276963426, 1252517782851235507141,...

---

Recurrencia

Definimos una secuencia de vectores $v^{(n)}$ para contar nuevos escenarios de dominó, y una "matriz de dominó" $M$ para codificar si ciertos escenarios de dominó son posibles o no. En el $n$ th paso, basta con observar el $v^{(n)}$ et $M$ como si fueran de "dimensión $(2^{n}+1)$ ".

La secuencia $D_n$ para $n\in\mathbb N$ es entonces la norma de Manhattan de la secuencia de vectores:

$$ D_n=||v^{(n)}||_1$$

Donde la secuencia de vectores $v^{(n)}=(v^{(n)}_1,v^{(n)}_2,\dots)^T$ está dada por:

$$ v^{(n+1)}=v^{(n)}M $$

Donde se comienza con $v^{(1)}=(1,1,0,0,\dots)^T$ como primer término.

Vamos a llenar la "matriz de dominó" $M$ con $1$ y $0$ para representar qué cadenas binarias pueden o no generarse con las filas correspondientes en la formación de dominó.

La matriz $M$

Para rellenar el $i$ th fila (a partir de $i=0$ ) de la matriz $M$ , mira la representación binaria $i_{(2)}$ . Para rellenar el $j$ th (a partir de $j=0$ ) en la fila, mira la representación binaria $j_{(2)}$ (rellenándolo con el $0$ si es necesario). Tratar $i_{(2)},j_{(2)}$ como filas consecutivas en la formación del triángulo del dominó, donde $0$ representan fichas de dominó de pie y $1$ representan fichas de dominó caídas. Si es posible tener estas filas en la formación de dominó, colocamos $1$ en la matriz. Si no lo está, colocamos $0$ en la matriz.

Por ejemplo, si $i=2$ entonces su representación binaria es $i_{(2)}=10$ . Esto da la única posibilidad de $j_{(2)}$ son: $000,010,100,110$ porque la ficha de la derecha no puede caer nunca en ese caso. Esto se traduce del binario al decimal como $j=0,2,4,6$ . Esto hace que el $i=2$ La fila comienza como $(1,0,1,0,1,0,1)$ . El resto de la fila se rellena con $0$ hasta la dimensión correspondiente.

Pondré el ejemplo de $M$ cuando $n=4$ (La matriz es entonces $(2^4+1)\times(2^4+1)$ )

$$\left( \begin{array}{ccccccccccccccccc} 1 & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 1 & 1 & 1 & 1 & . & . & . & . & . & . & . & . & . & . & . & . & . \\ 1 & . & 1 & . & 1 & . & 1 & . & . & . & . & . & . & . & . & . & . \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & . & . & . & . & . & . & . & . & . \\ 1 & . & . & . & 1 & . & . & . & 1 & . & . & . & 1 & . & . & . & . \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & . \\ 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & . \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & . \\ 1 & . & . & . & . & . & . & . & 1 & . & . & . & . & . & . & . & 1 \\ 1 & 1 & 1 & 1 & . & . & . & . & 1 & 1 & 1 & 1 & . & . & . & . & 1 \\ 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & . & . & . & 1 & . & . & . & 1 & . & . & . & 1 & . & . & . & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 & . & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & 1 \\ \end{array} \right)$$

Donde los puntos individuales " $.$ "s representan ceros" $0$ "s", para la visibilidad.

Volviendo a la recursión, esto da efectivamente $D_n=2,5,18,97\dots$ como se esperaba.

Para calcular primero $n$ términos, necesitamos primero $(2^{n}+1)$ filas de la matriz $M$ .

A pesar de su tamaño, la matriz puede generarse rápidamente una vez que se observa su estructura fractal.

Visualización - La estructura fractal

Podemos tratar $0$ y $1$ en la matriz $M$ como píxeles en blanco y negro.

Entonces, aquí está la imagen de un $(2^{10}+1)\times (2^{10}+1)$ caso ( $n=10$ ) de la matriz $M$ :

Answer 3

He calculado el primer $n=22$ coeficientes de dominó basados en las ideas de Vepir. El algoritmo tiene una complejidad de tiempo $O(4^n)$ y la complejidad espacial $O(2^n)$ (cálculo para $n=22$ me llevó alrededor de $5$ horas), porque no almacenamos la matriz $M$ y calcular sus valores siempre que sea necesario (la comprobación se realiza en la sentencia if, tiene una forma sencilla gracias a la implementación de operaciones bitwise). El código está en C++ y estoy usando boost para poder usar tipos de datos más grandes en lugar de sólo $64$ bit long int (de hecho, $256$ bits es el tamaño más pequeño que se puede utilizar para calcular el primer $22$ coeficientes e incluso se agotará pronto - $D_{22} \approx 1.04159*10^{53}$ por lo que la secuencia efectivamente crece rápidamente).

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <vector>

int main() {
    const int n = 22;
    std::vector<boost::multiprecision::int256_t> v(1 << n), w = v;
    v[0] = 1;
    v[1] = 1;
    std::cout << "0: " << 1 << "\n1: " << 2 << "\n";
    for (int k = 2; k <= n; k++) {
        for (int j = 0; j < 1 << k; j++) {
            w[j] = 0;
            for (int i = 0; i < 1 << (k - 1); i++)
                if (!(j & ~i & ~(i << 1)))
                    w[j] += v[i];
        }
        boost::multiprecision::int256_t s = 0;
        for (int j = 0; j < 1 << k; j++) {
            v[j] = w[j];
            s += v[j];
        }
        std::cout << k << ": " << s << "\n";
    }
    return 0;
}

Los coeficientes resultantes son:
$D_{0\;} = 1$
$D_{1\;} = 2$
$D_{2\;} = 5$
$D_{3\;} = 18$
$D_{4\;} = 97$
$D_{5\;} = 802$
$D_{6\;} = 10565$
$D_{7\;} = 228850$
$D_{8\;} = 8289217$
$D_{9\;} = 506526530$
$D_{10 } = 52501381765$
$D_{11 } = 9260170733266$
$D_{12 } = 2784551512218145$
$D_{13 } = 1429063630276963426$
$D_{14 } = 1252517782851235507141$
$D_{15 } = 1875484239084442842046130$
$D_{16 } = 4798818821638537354534159233$
$D_{17 } = 20984654018757393270224583817858$
$D_{18 } = 156836820191186149182649796402611461$
$D_{19 } = 2003511561206789377122778581243926768018$
$D_{20 } = 43746600983206157305472349537031148375171041$
$D_{21 } = 1632720578386908900755016228846582339781524154786$
$D_{22 } = 104159355027420388820987121345303301272029996166458949$
$D_{23 } = 11358102129403917231432165494822142898736362479589146061682$
$D_{24 } = 2117071962387596476689143406365411645227548761608194942194112321$
$D_{25 } = 674510308152303132671249373016113929650762465949837199637457187249602$
$D_{26 } = 367337379241994889203376240956745359336562483947308610993230043730270521221$

El logaritmo de $D_n$ parece crecer de forma cuadrática (lo que se puede apreciar incluso mirando la forma de la lista anterior). Tenemos aproximadamente: $$D_n \approx 2^{0.386712 n^2 - 0.667456 n + 3.63662} = \exp(0.268048 n^2 - 0.462645 n + 2.52072)$$ Pero no sé qué precisión tiene esta aproximación ni cuáles podrían ser los coeficientes reales. Y tampoco dice mucho sobre la posible fórmula recursiva: parece que sigue estando fuera de alcance.

Este problema es un caso especial del más general - dado un grafo dirigido $G$ Cuántas formas hay de asignar números $0$ et $1$ a sus vértices de forma que las flechas siempre apunten en la dirección no decreciente (es decir, no de $1$ a $0$ )? Podemos suponer, sin pérdida de generalidad, que el grafo es conexo (si no, la respuesta es sólo un producto de las respuestas de los componentes) y que es acíclico (el ciclo implica que todos sus tienen que tener el mismo número, por lo que podemos colapsarlos en un vértice). Hay un algoritmo fácil para responder a este problema en el caso de un árbol dirigido (sólo la recursión de las hojas hacia arriba), pero con vértices que interactúan de una manera más compleja, como en este problema, parece difícil, si no imposible, para llegar a un algoritmo rápido, sobre todo teniendo en cuenta, lo rápido que estos coeficientes crecen (aunque, por ejemplo, la fórmula para los árboles binarios perfectos de profundidad $n$ crece aún más rápido y tiene una simple recursión $B_{n+1}=B_n^2+1$ con $B_0=1$ ).

EDITAR
La primera $5$ vectores $v_i$ generando estos $D_i$ son (se omiten los ceros finales):
$v_0=(0,1)$
$v_1=(1,1)$
$v_2=(2, 1, 1, 1)$
$v_3=(5, 2, 3, 2, 2, 1, 2, 1)$
$v_4=(18, 6, 11, 6, 11, 4, 9, 4, 6, 2, 4, 2, 6, 2, 4, 2)$
$v_5=(97, 28, 56, 28, 65, 20, 48, 20, 56, 16, 33, 16, 48, 14, 31, 14, 28, 8, 16, 8, 20, 6, 14, 6, 28, 8, 16, 8, 20, 6, 14, 6)$
Podemos encontrar la interpretación de cada coeficiente en este vector basándonos en las propiedades fractales de $M$ - por ejemplo el primer elemento del vector $v$ es sólo la suma de todos los elementos del vector anterior (y por lo tanto es sólo $D_{n-1}$ . El segundo elemento es la suma de cada elemento en la posición impar (si contamos las posiciones desde la izquierda empezando por $0$ ) y la tercera es la suma en cada posición no divisible por $4$ . Sin embargo, a medida que avanzamos los patrones se vuelven más complejos, pero analizándolos se puede obtener tal vez un algoritmo más rápido (por ejemplo en lugar de sumar $\frac{3}{4}$ de los elementos del vector anterior para obtener el tercer elemento se puede simplemente restar del primer elemento previamente calculado la suma de los $\frac{1}{4}$ elementos con índices divisibles por $4$ aunque esta mejora puede producir como máximo el doble de velocidad).

EDITAR 2
Pude calcular más términos de la secuencia (hasta $26$ en lugar de $22$ ) utilizando el siguiente algoritmo:

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <vector>

int main() {
    int k = 0, n = 26;
    std::vector<boost::multiprecision::int256_t> v(1 << n - 2, 1), a(n + 1, 1);
    for (int i = 2; i < a.size(); i++)
        a[i] = 3 * a[i - 1] + 2 * a[i - 2];
    for (int i = 0; i < v.size(); i++)
        for (int j = i | (i << 1); j; j >>= 1) {
            k += j & 1;
            if (!(j & 1 && j - 1)){
                v[i] *= a[k + 1];
                k = 0;
            }
        }
    for (int i = n - 3; i > 0; i--) {
        std::vector<boost::multiprecision::int256_t> w(1 << i, 0);
        for (int j = 0; j < 1 << i; j++)
            for (int k = 0; k < 1 << i + 1; k++)
                if (!(~(j | j << 1) & k))
                    w[j] += v[k];
        v = w;
        std::cout << n - i + 1 << " " << v[1] + 1 << "\n";
    }
}

Lo que puede ser fácilmente paralelizado acelerando el proceso aún más. La forma de calcular los números también es diferente. Dejemos que $D(s,n)$ denotan la configuración válida del dominó con la cadena binaria $s$ en la parte superior y teniendo $n$ capas - el problema inicial es evaluar $D('0',n)+D('1',n)=D('1',n)+1$ . Para obtener $D(s,n)$ observamos que para $n=1$ todos son iguales a uno y para mayor $n$ podemos considerar todas las cadenas $s'$ directamente debajo $n$ , calcula recursivamente todos los valores $D(s',n-1)$ y sumarlos. La complejidad asintótica es la misma, pero podemos acelerar el programa partiendo de $D(s,2)$ que es igual a $2$ a la potencia del número de unos en $s$ o (como en el algoritmo anterior) de $D(s,3)$ observando que el número $D(s_k,3)$ donde $s_k$ es la cadena formada por $k$ es igual a la OEIS A007483 que tiene una recursión simple y que para todos los demás $s$ es sólo el producto de estos números para cada bloque consecutivo de unos en $s$ . $a_k=D(s_k,4)$ , $b_k=D(s_k,5)$ et $c_k=(s_k,6)$ también tienen sus recurrencias: $$a_{k+3}=4a_{k+2}+12a_{k+1}+8a_k$$ $$b_{k+5}=5b_{k+4}+48b_{k+3}+108b_{k+2}+64b_{k+1}-32b_k$$ $$c_{k+8}=6c_{k+7}+164c_{k+6}+896c_{k+5}+1584c_{k+4}-992c_{k+3}-3328c_{k+2}+3584c_{k+1}-1024c_k$$ Con $a_0=b_0=c_0=1$ , $a_1=18=D_3$ , $a_2=96=D_4-1$ , $b_1=97=D_4$ , $b_2=801=D_5-1$ , $b_3=8961$ , $b_4=93697$ , $c_1=802=D_5$ , $c_2=10564=D_6-1$ , $c_3=207720$ , $c_4=3692192$ , $c_5=66924256$ , $c_6=1209149120$ , $c_7=21854550528$ . Para $D(s_k,7)$ No he encontrado tal serie - o no existe o (más probablemente) no hay suficientes términos para detectarla. Tampoco he encontrado una forma de calcular $D(s,n)$ para cualquier $n \ge 4$ para todas las cadenas $s$ por lo que el algoritmo sólo utiliza $D(s,3)$ - si uno es capaz de calcularlos directamente puede obtener términos más grandes de la secuencia. Sólo quiero mencionar que $D_{26} \approx 2^{247.7}$ es el término más grande por debajo de $2^{255}$ por lo que habrá que utilizar tipos enteros más grandes cuando se intente ir más allá.

Answer 4

He aquí otro enfoque, utilizando el principio de inclusión y exclusión. Queremos encontrar el número de 2 coloraciones de la cuadrícula triangular $i\in\{1,\dots,n\},\ j\in\{1,\dots,i\}$ que no tienen ninguna de las siguientes propiedades:

• célula $(i,1)$ es negro y la célula $(i+1,1)$ es blanco
• célula $(i,i)$ es negro y la célula $(i+1,i+1)$ es blanco
• células $(i,j)$ et $(i,j+1)$ son de color negro y la célula $(i+1,j+1)$ es blanco

Las expresiones de inclusión-exclusión para pequeños $n$ son los siguientes. \begin{align} n=1:&\quad 2^1 = \color{red}{2}\\ n=2:&\quad 2^3 - 2\cdot 2^1 + 2^0 = 8 - 4 + 1 = \color{red}{5}\\ n=3:&\quad 2^6 - (4\cdot 2^4 + 2^3) + (2^3 + 5\cdot 2^2) - 2^1 = 64 - 72 + 28 - 2 = \color{red}{18}\\ n=4:&\quad 2^{10} - (6\cdot2^8 + 3\cdot2^7) + (2^7 + 14\cdot2^6 + 11\cdot2^5) \\ &- (3\cdot2^5 + 18\cdot2^4 + 9\cdot2^3) + (4\cdot2^3 + 13\cdot2^2) - 6\cdot2^1+ 2^0 \\ &= 1024 - 1920 + 1376 - 456 + 84 - 12 + 1 = \color{red}{97} \end{align} En general $n$ Los tres primeros términos (hasta dos propiedades) son fáciles, pero a partir de ahí la cosa se complica.