A sequence with dominoes

Solution 1:

Update: I found a recurrence in my alternative approach answer, here.

TL;DR

I've reduced the problem to calculating "domino coefficients".

But it appears these coefficients cannot be easily calculated, and that's where my answer stops.

Reducing the problem to "domino coefficients"

If $d_n$ is the number of scenarios with at least one fallen domino in the $n$th row, then

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

We define $D_0=1,d_1=1$. This gives $D_1=1+1=2$ as expected.

We say a domino is "activated" (can fall) if and only if a domino above it has fallen.

$\alpha_n(k)$ is the number of ways to have exactly $k$ "activated" dominoes in the $n$th row.

Now to calculate $d_n,n\ge2$ we have the expression:

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

Because every "activated" domino is either fallen or not, giving $2^k$ states, and we subtract $1$ for the case when they are all not fallen because that's the definition of $d_n$.

If a domino falls, it activates the two dominoes below it. This implies that $\alpha_n(1)=0$ because we never have exactly one activated domino. Hence we define $\alpha$ for $2\le k\le n$.

The problem is now calculating the "domino coefficients" $\alpha_n(k)$.

By brute force I've found the triangle that gives $\alpha_n(k)$'s for $2\le k\le 7$ is:

$$\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}$$

Reading rows $n=2,3,4,5,6,7$ and plugging the coefficients into the recursion:

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

Gives $D_n=5,18,97,802,10565,228850$ as expected. (Where $D_1=2$.)

Solving the domino coefficients?

For $k=2$, to activate exactly two dominoes in $(n)$th row, exactly one domino must fall in $(n-1)$th row. This gives the recursion for the first coefficient:

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

But for $k\ge 3$, I do not see an obvious recursion.

The number of ways activated dominoes in the $(n-1)$th row can fall now depends on the "islands" (consecutive runs of activated dominoes) and "gaps" (consecutive runs of non-activated dominoes). To write this as an expression,

Let $S(n-1,r)$ be the set of all $(n-1)$th row sequences of dominoes where exactly $r$ dominoes are activated. Then we have to sum over all $s\in S(n-1,r)$:

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

Where $f_k(s)$ returns a value depending on the size of each "island" $I\in s$ and depending on the value of the target number of activations $k$ in the $n$th row.

Collecting all $s$ sequences and evaluating $f_k(s)$ function on them is a problem now.

Notice that the number of elements of $S(n-1,r)$ is precisely $\alpha_{n-1}(r)$.

If $k=2$, we simply have $f_2(s)=r$ for all $s$, which gives the recursion $\alpha_{n}(2)$ from above.

If $k=3$, we have $f_3(s)=(r-1)$ if the $s$ contains exactly one island $I$ of length $r$. Otherwise, we need to observe individual islands, to get:

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

where $\mathcal L(I)$ is the length of the island $I\in s$. This is true because to have $k=3$ activated dominoes in the $(n)$th row, we need to have exactly two connected dominoes in the $(n-1)$th row.

For $k\ge 4$, the $f_k(s)$ is not anymore "as simple" as summing lengths of islands.

For $k=3$ we counted ways:

• to activate "single $2$-long partitions" of the islands

For $k=4$ we need to count ways:

• to activate "single $3$-long partitions" of the islands
• to activate "two $1$-long partitions" separated with gap of at least one

And so on, for larger $k$ we have more ways to "partition the activations" of islands.

I do not see how to simplify this into a "closed form (recursion) expression ".

Hence my answer stops here.

Solution 2:

Update: @Bartek implements this idea and calculates more new terms in their answer.

Edit: Thank you @Bartek for your comment, I made the suggested modification.

Remark. Alternative approach using "domino coefficients" is in my previous answer.

TL;DR

We can use a vector recurrence to keep track of new domino scenarios.

First fourteen terms given by the recurrence are: ($D_{14}$ is already larger than $10^{21}$.)

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

Recurrence

We define a sequence of vectors $v^{(n)}$ to count new domino scenarios, and a "domino matrix" $M$ to encode whether or not certain domino scenarios are possible. At the $n$th step, it is sufficient to observe the $v^{(n)}$ and $M$ as if they are of "dimension $(2^{n}+1)$".

The sequence $D_n$ for $n\in\mathbb N$ is then the Manhattan norm of the vector sequence:

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

Where the sequence of vectors $v^{(n)}=(v^{(n)}_1,v^{(n)}_2,\dots)^T$ is given by:

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

Where it starts with $v^{(1)}=(1,1,0,0,\dots)^T$ as the first term.

We will be filling the "domino matrix" $M$ with $1$'s and $0$'s to represent which binary strings can or can not be generated with the corresponding rows in the domino formation.

The matrix $M$

To fill in the $i$th row (starting at $i=0$) of matrix $M$, look at the binary representation $i_{(2)}$. To fill in the $j$th spot (starting at $j=0$) in the row, look at the binary representation $j_{(2)}$ (padding it with leading $0$'s if necessary). Treat $i_{(2)},j_{(2)}$ as consecutive rows in the domino triangle formation, where $0$'s represent standing dominoes and $1$'s represent fallen dominoes. If it is possible to have these rows in the domino formation, we place $1$ in the matrix. If it is not, we place $0$ in the matrix.

For example, If $i=2$ then its binary representation is $i_{(2)}=10$. This gives the only possible $j_{(2)}$'s are: $000,010,100,110$ because the rightmost domino can never fall in such case. This translates from binary to decimal as $j=0,2,4,6$. This gives that the $i=2$ row starts as $(1,0,1,0,1,0,1)$. The remainder of the row is filled with $0$'s up to the corresponding dimension.

I will give the example of $M$ when $n=4$: (The matrix is then $(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)$$

Where individual dots "$.$"s represent zeroes "$0$"s, for visibility.

Returning back to the recursion, this indeed gives $D_n=2,5,18,97\dots$ as expected.

To compute first $n$ terms, we need first $(2^{n}+1)$ rows of the matrix $M$.

Despite its size, the matrix can be generated fast once you notice its fractal structure.

Visualization - The fractal structure

We can treat $0$'s and $1$'s in the matrix $M$ as black and white pixels.

Then, here is the image of a $(2^{10}+1)\times (2^{10}+1)$ case ($n=10$) of matrix $M$: