

A333837


Number of ways to collapse an nrowed triangular formation of dominoes.


1



1, 2, 5, 18, 97, 802, 10565, 228850, 8289217, 506526530, 52501381765, 9260170733266, 2784551512218145, 1429063630276963426, 1252517782851235507141, 1875484239084442842046130, 4798818821638537354534159233, 20984654018757393270224583817858
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Every domino either falls or does not. A domino can fall if and only if one of the two dominoes above it falls. The total number of dominoes in the formation is A000217(n).


LINKS

Math StackExchange user Bartek, Table of n, a(n) for n = 0..26
Math StackExchange user Vepir, Domino matrix M, for n=10
Math StackExchange, A sequence with dominoes


FORMULA

a(n) = a(n1) + sum(b(n,k)*(2^k1), k=2...n), where b(n,k) is the number of ways to have k potentially falling dominoes in the nth row of the domino triangle. We know b(n,2) = sum( k*b(n1,k), k=2...n1), but b(n,k) for k>=3 does not appear to have a simple recursion, and needs to be calculated with numerical methods.
a(n) = norm1(v(n)), where v(n)=v(n1)*M is a sequence of (2^n+1) dimensional vectors starting with v(1)=e1+e2=(1,1,0,...). The matrix M is the (2^n+1)x(2^n+1) dimensional "domino matrix" M = ((1,0,...),(1,1,1,1,0,...),(1,0,1,0,1,0,1,0,...),(1,1,1,1,1,1,1,1,0,...),...) which is calculated as follows: The M(i,j) entry (where i,j = 0,1,2,...) of the matrix M is 1 if and only if the binary representations of i,j are in a valid state (0's are standing dominoes and 1's are fallen dominoes) when taken as consecutive rows of the triangular domino formation, else it is 0. For example, i=2 has the binary representation 01. If we look at the next row of the triangular domino formation, then the following formations are possible:
1 0 1 0 1 0 1 0
0 0 0, 0 1 0, 1 0 0, 1 1 0. Translating the next row scenarios j = 000, 010, 100, 110 from binary to decimal, we obtain j = 0, 2, 4, 6. Hence, the i=2 row of the domino matrix M will start as (1,0,1,0,1,0,1). The remainder of the row is filled with zeroes.


EXAMPLE

A domino can fall if and only if one of the two dominoes above it falls.
For n=1,2,3,4,... we have the following domino formations:
0
0 0 0
0 0 0 0 0 0
0, 0 0, 0 0 0, 0 0 0 0, ...
For n=1, we have a single domino which either falls or does not, hence a(1)=2.
For n=2, we have two rows of dominoes in the triangular formation: If the top domino falls, then the bottom two can both fall (or not) giving 2^2=4 scenarios. The fifth scenario is when the first domino does not fall, then the bottom two can't either. This gives a(2)=4+1=5.
For n=3, we have three rows of dominoes in the triangular formation: If both dominoes in the second row fall, then the third row can fall in 2^3=8 ways. If only one of the two dominoes in the second row falls, then the third row can fall in 2^2 ways in both cases which totals 2*2^2=8. If none of the two dominoes in the second row fall, the we know the top domino is in either of the 2 states. Summing this up gives a(3)=18.
For n=4, we have four rows of dominoes in the triangular formation: We have a(4) = 18 + 7*(2^21) + 4*(2^31) + 2*(2^41) = 97, because there are 7,4,2 ways to have 2,3,4 potentially falling dominoes in the last row, and 18 is the number of ways for the previous rows to fall if we ignore the last row. We subtract 1 state from every 2^k states of k potentially falling dominoes, because those states are counted in the previous added 18 scenarios.


PROG

(C++)
/** a(n) = norm1(v(n)), v(n)=v(n1)*M formula **/
#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<<(k1); 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; }


CROSSREFS

Cf. A000217 (triangular numbers).
Sequence in context: A335547 A075441 A187008 * A075634 A322396 A007127
Adjacent sequences: A333834 A333835 A333836 * A333838 A333839 A333840


KEYWORD

nonn,hard,nice


AUTHOR

Matej Veselovac, Apr 07 2020


EXTENSIONS

a(23)a(26) from Bartlomiej Bollin, Apr 14 2020


STATUS

approved



