cp's OEIS Frontend

A333837 Number of ways to collapse an n-rowed triangular formation of dominoes.

%I A333837 #37 Aug 02 2022 13:01:32
%S A333837 1,2,5,18,97,802,10565,228850,8289217,506526530,52501381765,
%T A333837 9260170733266,2784551512218145,1429063630276963426,
%U A333837 1252517782851235507141,1875484239084442842046130,4798818821638537354534159233,20984654018757393270224583817858
%N A333837 Number of ways to collapse an n-rowed triangular formation of dominoes.
%C A333837 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).
%H A333837 Math StackExchange user Bartek, <a href="/A333837/b333837.txt">Table of n, a(n) for n = 0..26</a>
%H A333837 Math StackExchange user Vepir, <a href="https://i.stack.imgur.com/b9SzO.png">Domino matrix M, for n=10</a>
%H A333837 Math StackExchange, <a href="https://math.stackexchange.com/q/3486414/318073">A sequence with dominoes</a>
%F A333837 a(n) = a(n-1) + Sum_{k=2..n} b(n,k)*(2^k-1), where b(n,k) is the number of ways to have k potentially falling dominoes in the n-th row of the domino triangle. We know b(n,2) = Sum_{k=2..n-1} k*b(n-1,k), but b(n,k) for k>=3 does not appear to have a simple recursion, and needs to be calculated explicitly, step by step.
%F A333837 a(n) = norm1(v(n)), where v(n) = v(n-1)*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, otherwise 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:
%F A333837      1 0     1 0     1 0     1 0
%F A333837     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 zeros.
%e A333837 A domino can fall if and only if one of the two dominoes above it falls.
%e A333837 For n=1,2,3,4,... we have the following domino formations:
%e A333837                                0
%e A333837                     0         0 0
%e A333837            0       0 0       0 0 0
%e A333837     0,    0 0,    0 0 0,    0 0 0 0,  ...
%e A333837 For n=1, we have a single domino which either falls or does not, hence a(1)=2.
%e A333837 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.
%e A333837 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, then we know the top domino is in either of the 2 states. Summing this up gives a(3)=18.
%e A333837 For n=4, we have four rows of dominoes in the triangular formation: We have a(4) = 18 + 7*(2^2-1) + 4*(2^3-1) + 2*(2^4-1) = 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.
%o A333837 (C++)
%o A333837 /** a(n) = norm1(v(n)),v(n)=v(n-1)*M formula **/
%o A333837 #include<boost/multiprecision/cpp_int.hpp>
%o A333837 #include<iostream>
%o A333837 #include<vector>
%o A333837 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;}
%Y A333837 Cf. A000217 (triangular numbers).
%K A333837 nonn,hard,nice
%O A333837 0,2
%A A333837 _Matej Veselovac_, Apr 07 2020
%E A333837 a(23)-a(26) from _Bartlomiej Bollin_, Apr 14 2020