cp's OEIS Frontend

A344571 Number of subgraphs of the directed square lattice with n edges and all vertices reachable from the origin.

%I A344571 #20 Jun 11 2022 13:48:06
%S A344571 1,2,5,14,42,130,412,1326,4318,14188,46950,156258,522523,1754254,
%T A344571 5909419,19964450,67618388,229526054,780633253,2659600616,9075301990,
%U A344571 31010850632,106100239080,363428599306,1246172974048,4277163883744,14693260749888,50516757992258
%N A344571 Number of subgraphs of the directed square lattice with n edges and all vertices reachable from the origin.
%C A344571 Equivalently, the number of fixed polysticks (see A096267) that can be constructed starting from a fixed vertex by only adding edges on top of an existing vertex or to the right of an existing vertex. If the polystick is rotated counterclockwise by 45 degrees, then the polystick is supported from the starting vertex. - _Andrew Howroyd_, May 24 2021
%H A344571 Roman Hros, <a href="http://www2.fiit.stuba.sk/iitsrc/iit-src2018-proceedings.pdf#page=14">Generating Subgraphs of Finite Grids</a>, IIT.SRC 2018: 14th Student Research Conference in Informatics and Information Technologies.
%H A344571 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Polystick.html">Polystick</a>
%H A344571 Wikipedia, <a href="https://en.wikipedia.org/wiki/Polystick">Polystick</a>
%F A344571 a(n) >= 2*a(n-1) for n > 0.
%e A344571 In the following examples, the origin is in the bottom left corner and graph edges are directed upwards and to the right.
%e A344571 The a(1) = 2 graphs are:
%e A344571   |   __
%e A344571 .
%e A344571 The a(2) = 5 graphs are:
%e A344571   |   __
%e A344571   |  |     __.__    __|   |__
%e A344571 .
%e A344571 The a(3) = 14 graphs are:
%e A344571   |    __
%e A344571   |   |     |__    __|    __.__    |      __
%e A344571   |   |     |     |      |         |__   |__
%e A344571 .
%e A344571                                __    |
%e A344571   __.__.__   __.__|  __|__  __|    __|   |____  |_|
%e A344571 .
%e A344571 Other examples with 4, 6, and 7 edges respectively include:
%e A344571      __      __.__      __|__|
%e A344571     |__|    |__.__|    |__|
%o A344571 (PARI)
%o A344571 a(n)={
%o A344571   local(M=Map());
%o A344571   my(acc(hk, r)=my(z); mapput(M, hk, if(mapisdefined(M,hk,&z),z+r,r)));
%o A344571   my(recurse(w,f,b,r) =
%o A344571     if(w<=0, if(w==0, acc([w,1],r)), if(f==0, if(b, acc([w,b>>valuation(b,2)],r)),
%o A344571     my(t=1<<logint(f,2)); f-=t; self()(w,f,b,r); self()(w-1,f,bitor(b,t),r); self()(w-1,f,bitor(b,2*t),r); self()(w-2,f,bitor(b,3*t),r)  )));
%o A344571   mapput(M, [n,1], 1);
%o A344571   for(n=1, n, my(L=Mat(M)); M=Map();
%o A344571     for(i=1, matsize(L)[1], my([hk,r]=L[i,]); recurse(hk[1], hk[2], 0, r)));
%o A344571   mapget(M, [0,1]);
%o A344571 } \\ _Andrew Howroyd_, May 24 2021
%Y A344571 Cf. A096267, A353028.
%K A344571 nonn
%O A344571 0,2
%A A344571 _Roman Hros_, May 23 2021
%E A344571 Terms a(25) and beyond from _Andrew Howroyd_, May 24 2021