A387943 - OEIS

A387943

Number of fully packed loops on an n X n grid with no cycle.

1, 1, 2, 7, 41, 395, 6212, 158757

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

A fully packed loop of size n is a subgraph of an n X n square grid, where each vertex inside the grid has degree exactly 2. Vertices on the border have degree 2 or 1 alternatingly, with corners counting as two vertices for the border conditions. Subgraphs which are the same under reflection or rotation are counted twice.

Fully packed loops are in bijection with alternating sign matrices, which are counted by Robbins numbers (A005130).

LINKS

Table of n, a(n) for n=0..7.

James Propp, The many faces of alternating-sign matrices, Discrete Mathematics and Theoretical Computer Science Proceedings AA (DM-CCG), 2001, 43-58.

EXAMPLE

The 7 fully packed loops of size 3 are:

|__ __| |__ __| | __| |__ |

__ __ __ __ __ __ __| |__ __ __ __| |__

| |__ __| | __ __ __ __

| | | | | | | |

|__ __| | __| |__ |

__ __ __ __ __| | __ __ | |__