A343257 Triangle read by rows: T(n,k) is the number of n+2-sided polygons whose points lie on a circle and with the property that one makes k turns on itself, always in the same direction (right or left) while following its edges, 1 <= k <= ceiling(n/2).

1, 1, 1, 1, 1, 8, 1, 29, 1, 1, 80, 47, 1, 193, 513, 1, 1, 432, 3338, 244, 1, 925, 16633, 7305, 1, 1, 1928, 70713, 103616, 1186, 1, 3953, 271441, 990289, 92145, 1, 1, 8024, 972548, 7438204, 2717321, 5536, 1, 16189, 3321009, 47629761, 47637225, 1076409, 1

Offset

1,6

Comments

Polygons that differ by rotation or reflection are counted separately.

The polygons considered here are those that can be drawn by connecting n+2 equally spaced points on a circle (possibly self-intersecting).

The number of turns a polygon makes on itself while following its edges is called the turning number. See the Wikipedia article for additional explanation. The condition that the turns are in the same direction means that all the internal angles are less than 180 degrees (stars are allowed, but figure of eights are not).

Links

Table of n, a(n) for n=1..49.

Ludovic Schwob, Illustration of T(6,k), 1<=k<=3

Wikipedia, Turning number

Formula

T(n,1)=1 and T(2*n-1,n)=1 for all n>=1: the only solutions are the polygons with respective Schläfli symbols {n+2} and {2*n+1/n}.

T(n,2) = A030110(n+1) for all n>=1.

T(2*n,n-1) = A029760(n-2) for all n>=2.

Example

Triangle begins:
     1;
     1;
     1,    1;
     1,    8;
     1,   29,    1;
     1,   80,   47;
     1,  193,  513,   1;

Prog

(PARI)
B(n, m, x)={
  local(Cache=Map());
  my(recurse(k, p, q, b) = my(hk=[k, p, q, b], z); if(!mapisdefined(Cache, hk, &z),
  z = if(k==0, q>p && q>m, sum(j=1, n-(q-p)%n, my(r=(q+j)%n); if(!bittest(b, r), if(r<q, x, 1)*self()(k-1, q, r, b+(1<<r)) )));
  mapput(Cache, hk, z)); z);
  recurse(n-2, 0, m, 1+(1<<m));
}
T(n)={Vecrev(sum(i=1, n-1, B(n, i, 'x)))}
{ for(n=3, 12, print(T(n))) } \\ Andrew Howroyd, May 15 2021

Crossrefs

Row sums give A295264(n+1).

Cf. A029760, A030110, A342968.

Sequence in context: A075155 A028943 A050311 * A224997 A275790 A351242

Adjacent sequences: A343254 A343255 A343256 * A343258 A343259 A343260

Keyword

nonn,tabf

Author

Ludovic Schwob, Apr 09 2021

Extensions

a(31)-a(49) from Andrew Howroyd, May 15 2021

Status

approved