

A300795


Number of vertices of the master corner polyhedron on the cyclic group of order n + 1.


0



1, 2, 3, 5, 7, 10, 16, 19, 31, 32, 55, 53, 89, 89, 147, 128, 232, 191, 356, 301, 491
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The master corner polyhedron P(G_{n+1},n) on the additive cyclic group G_{n+1} of order n+1 (with addition modulo n+1) is the convex hull of solutions t=(t_1,t_2,..,t_n) in R^n, t_i integer, t_i >= 0, to the equation t_1 + 2*t_2 + ... + n*t_n == n (mod (n+1)).
The master corner polyhedron P(G,g_0) was defined by R. E. Gomory for an arbitrary finite Abelian group G and arbitrary group element g_0. It is of great importance for integer linear programming.
R. E. Gomory computed vertices of P(G,g_0) for all groups G of the order up to 11 and all g_0 in G.
The point t=(0,0,0,0,1,0,0,0,3,0) was erroneously indicated to be a vertex of P(G_11,10).
a(11)a(21) were computed with the use of the Parma Polyhedra Library [(PPL)].  Dominic Yang, Oct 04 2018


LINKS

Table of n, a(n) for n=1..21.
R. E. Gomory, source links to R. E. Gomory's papers.
R. E. Gomory, Some polyhedra related to combinatorial problems, Journal of Linear Algebra and Its Applications, 1969. Vol. 2, No. 4, 451558.
V. A. Shlyk, Master corner polyhedron: vertices, European Journal of Operational Research, 2013. Vol. 226, No. 2, 203210.
Vladimir A. Shlyk, Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number, arXiv:1805.07989 [math.CO], 2018.


EXAMPLE

The 6 integer points in the convex hull of the vertices of P(G_5,4) are (4,0,0,0), (2,1,0,0), (1,0,1,0), (0,2,0,0), (0,0,3,0), (0,0,0,1) but a(4) = 5 since (2,1,0,0) = (1/2)(4,0,0,0) + (1/2)(0,2,0,0).


CROSSREFS

Similar to A203898.
Sequence in context: A116975 A286227 A134792 * A033068 A234368 A052011
Adjacent sequences: A300792 A300793 A300794 * A300796 A300797 A300798


KEYWORD

nonn,more


AUTHOR

Vladimir A. Shlyk, Mar 13 2018


EXTENSIONS

a(11)a(21) from Dominic Yang, Oct 04 2018


STATUS

approved



