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

%I #10 Jun 11 2022 13:48:37

%S 0,1,2,5,15,47,156,527,1826,6407,22762,81587,294711,1070973,3912808,

%T 14358493,52893647,195498831,724704974,2693397035,10033263089,

%U 37452388361,140063288728

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

%C Similar to A344571 but here n is the number of vertices.

%F a(n) >= 2*a(n-1) for n > 0.

%e In the following examples, the origin is in the bottom left corner and graph edges are directed upwards and to the right.

%e The a(1) = 1 graph is:

%e .

%e The a(2) = 2 graphs are:

%e | __

%e .

%e The a(3) = 5 graphs are:

%e | __

%e | | __.__ __| |__

%e .

%e The a(4) = 15 graphs are:

%e | __

%e | | |__ __| __.__ | __

%e | | | | | |__ |__

%e .

%e __ | __

%e __.__.__ __.__| __|__ __| __| |__.__ |__| |__|

%e .

%e Other examples with 5, 6, and 7 vertices respectively include:

%e | __.__ __|__|

%e |__| |__.__| |__|

%Y Cf. A344571.

%K nonn,more

%O 0,3

%A _Roman Hros_, Apr 18 2022