|
| |
|
|
A333837
|
|
Number of ways to collapse an n-rowed 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
|
|
|
|
FORMULA
|
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.
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:
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 zeros.
|
|
|
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, then 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^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.
|
|
|
PROG
|
(C++)
/** a(n) = norm1(v(n)), v(n)=v(n-1)*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<<(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; }
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
