A096267 -id:A096267 - cp's OEIS frontend

A348096 Array A(n,s) read by rows: the free n-polysticks of the square lattice with symmetry group of order 2^s.

0, 0, 1, 0, 0, 1, 1, 0, 1, 3, 1, 0, 8, 5, 1, 2, 39, 14, 2, 0, 187, 31, 4, 0, 880, 66, 4, 0, 4109, 142, 12, 2, 19274, 310, 7, 0, 90965, 694, 19, 0, 432545, 1445, 15, 0

Offset: 1

R. J. Mathar, Sep 30 2021

The array has 4 columns for symmetry groups of order 1, 2, 4 and 8 (subgroups of D_8).

Polysticks with group order 1 have no symmetry. Polysticks with group order 2 have either a mirror line (parallel to edges or along a diagonal of the lattice) or a rotation axis of order 2 (180-degree rotation). Polysticks of group order 4 have two orthogonal mirror lines and the 180-degree rotation. Polysticks of group order 8 have in addition a rotation axis or order 4 (90-degree rotations), i.e. the full symmetry of the square.

			The array starts
      0   0  1 0
      0   1  1 0
      1   3  1 0
      8   5  1 2
     39  14  2 0
    187  31  4 0
    880  66  4 0
   4109 142 12 2
  19274 310  7 0
  90965 694 19 0
A(4,3)=2 counts the fully-symmetric unit square and the cross.

Cf. A019988 (row sums), A096267 (fixed polysticks).

Sum_{s=0..3} A(n,s) = A019988(n).
8*A(n,0) + 4*A(n,1) + 2*A(n,2) + A(n,3) = A096267(n).
A(n,3) = 0 if n is not a multiple of 4.

Row n=11 added.- R. J. Mathar, Oct 05 2021

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

Original entry on oeis.org

1, 2, 5, 14, 42, 130, 412, 1326, 4318, 14188, 46950, 156258, 522523, 1754254, 5909419, 19964450, 67618388, 229526054, 780633253, 2659600616, 9075301990, 31010850632, 106100239080, 363428599306, 1246172974048, 4277163883744, 14693260749888, 50516757992258

Offset: 0

Roman Hros, May 23 2021

nonn

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

			In the following examples, the origin is in the bottom left corner and graph edges are directed upwards and to the right.
The a(1) = 2 graphs are:
  |   __
.
The a(2) = 5 graphs are:
  |   __
  |  |     __.__    __|   |__
.
The a(3) = 14 graphs are:
  |    __
  |   |     |__    __|    __.__    |      __
  |   |     |     |      |         |__   |__
.
                               __    |
  __.__.__   __.__|  __|__  __|    __|   |____  |_|
.
Other examples with 4, 6, and 7 edges respectively include:
     __      __.__      __|__|
    |__|    |__.__|    |__|

Roman Hros, Generating Subgraphs of Finite Grids, IIT.SRC 2018: 14th Student Research Conference in Informatics and Information Technologies.
Eric Weisstein's World of Mathematics, Polystick
Wikipedia, Polystick

Cf. A096267, A353028.

a(n)={
  local(M=Map());
  my(acc(hk, r)=my(z); mapput(M, hk, if(mapisdefined(M,hk,&z),z+r,r)));
  my(recurse(w,f,b,r) =
    if(w<=0, if(w==0, acc([w,1],r)), if(f==0, if(b, acc([w,b>>valuation(b,2)],r)),
    my(t=1<Andrew Howroyd, May 24 2021

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

Terms a(25) and beyond from Andrew Howroyd, May 24 2021

A385120 Number of fixed tree-like polyedges on the square lattice with n edges, rooted at a vertex.

Original entry on oeis.org

1, 4, 18, 88, 435, 2184, 11018, 55888, 284229, 1448800, 7396290, 37804344, 193405121, 990117104, 5072380140

Offset: 0

Ben Samberg, Jun 18 2025

			a(0) = 1: empty structure.
a(1) = 4: a single vertical or horizontal edge, rooted at one of the two vertices.
a(2) = 18: six unrooted two-edge polyedges (a straight path oriented in 2 possible ways and an L-shaped path oriented in 4 possible ways), each rooted at one of the three vertices.

Ben Samberg, a(2) visualization
Ben Samberg, Python algorithm

Cf. A096267 (not necessarily treelike), A056841 (free), A066158 (polyominoes).

Cf. A308409.

a(n) = A308409(n) * (n+1). - Andrei Zabolotskii, Jul 02 2025

cp's OEIS Frontend

A348096 Array A(n,s) read by rows: the free n-polysticks of the square lattice with symmetry group of order 2^s.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A385120 Number of fixed tree-like polyedges on the square lattice with n edges, rooted at a vertex.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula