login
Number of vertices of the integer partition polytope.
3

%I #46 Sep 12 2021 16:26:30

%S 1,2,3,4,6,7,11,12,17,19,29,25,41,41,57,56,84,75,117,99,146,140,211,

%T 169,258,237,330,291,433,342,544,464,646,587,825,670,1008,869,1214,

%U 1027,1491,1193,1805,1496,2032,1794,2573,2058,2983,2488,3444

%N Number of vertices of the integer partition polytope.

%C This sequence is the sequence of the numbers of vertices of the integer partition polytopes. Partitions of n are considered as the points x in R^n: each x_i is the number of times the part i enters the partition. The partition polytope P_n is the convex hull of all partitions of n.

%C This sequence is dominated by A108917 since each vertex is proved to be a knapsack partition. This sequence was computed by A. S. Vroublevski with the sporadic aid of Polymake.

%D Vladimir A. Shlyk, Polytopes of partitions of numbers, Vesti Ac. Sci. Belarus, Ser. phys.-mat. nauk, No. 3 (1996), 89-92 (in Russian).

%D Vladimir A. Shlyk, On the vertices of the polytopes of partitions of numbers, Dokl. Nats. Akad. Nauk Belarusi, 52.3 (2008), 5-10 (in Russian).

%H Vladimir A. Shlyk, <a href="/A203898/b203898.txt">Table of n, a(n) for n = 1..105</a>

%H Shmuel Onn and Vladimir A. Shlyk, <a href="https://doi.org/10.1016/j.dam.2014.08.015">Some Efficiently Solvable Problems over Integer Partition Polytopes</a>, Discrete Appl. Math., Vol. 180 2015, 135-140.

%H Vladimir A. Shlyk, <a href="https://doi.org/10.1016/j.ejc.2004.08.004">Polytopes of Partitions of Numbers</a>, European J. Combin., Vol. 26/8 2005, 1139-1153.

%H Vladimir A. Shlyk, <a href="https://www.academia.edu/37926631/Polyhedral_Approach_to_Integer_Partitions">Polyhedral Approach to Integer Partitions</a>, J. Combin. Math. Combin. Computing, Vol. 89 2014, 113-128.

%H Vladimir A. Shlyk, <a href="http://www1.jinr.ru/Preprints/2008/018(E5-2008-18).pdf">Recursive Operations for Generating Vertices of Integer Partition Polytopes</a>, Communication of the Joint Institute for Nuclear Research, E5-2008-18. Dubna, 2008.

%H Vladimir A. Shlyk, <a href="https://core.ac.uk/reader/290214970">A Criterion of Representability of an Integer Partition as a Convex Combination of Two Partitions</a>, Vestnik BGU. Ser. 1, No. 2 (2009), 109-114 (in Russian).

%H Vladimir A. Shlyk, <a href="http://csl.bas-net.by/xfile/doklad/2009/06-2009/0b4s2g.pdf">Combinatorial Operations for Generating Vertices of Integer Partition Polytopes</a>, Dokl. Nats. Akad. Nauk Belarusi, 53.6 (2009), 27-32 (in Russian).

%H Vladimir A. Shlyk, <a href="https://core.ac.uk/download/pdf/290213708.pdf">On the Relation of Vertices of Integer Partition Polytopes to Their Nontrivial Facets</a>, Vestnik BGU. Ser. 1, No. 1 (2010), 153-156 (in Russian).

%H Vladimir A. Shlyk, <a href="http://csl.bas-net.by/xfile/v_fizm/2011/1/m1baf.pdf">On the Adjacency of Vertices of the Integer Partition Polytope. Part I</a>, Izvestia National Acad. Sci. Ser. Phys.-Math. Sci, No. 1 (2011), 112-117 (in Russian).

%H Vladimir A. Shlyk, <a href="http://csl.bas-net.by/xfile/v_fizm/2011/3/wslg3.pdf">On the Adjacency of Vertices of the Integer Partition Polytope. Part II</a>, Izvestia National Acad. Sci. Ser. Phys.-Math. Sci, No. 3 (2011), 105-111 (in Russian).

%H Vladimir A. Shlyk, <a href="https://doi.org/10.1016/j.endm.2013.07.050">Integer Partitions from the Polyhedral Point of View</a>, Electron. Notes Discrete Math, Vol. 43 2013, 319-327.

%H Vladimir A. Shlyk, <a href="https://doi.org/10.1016/j.ejor.2012.11.011">Master Corner Polyhedron: Vertices</a>, Eur. J. Oper. Res., 226/2 (2013), 203-210.

%H Vladimir A. Shlyk, <a href="https://arxiv.org/abs/1805.07989">Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number</a>, arXiv:1805.07989 [math.CO], 2018.

%H A. S. Vroublevski and Vladimir A. Shlyk, <a href="https://core.ac.uk/reader/276362850">Computing vertices of integer partition polytopes</a>, <a href="https://inf.grid.by/jour/article/view/178/180">Computing vertices of integer partition polytopes</a>, Informatics, 48.4 (2015), 34-48 (in Russian).

%e The partition x=(2,1,0,0) of 4 corresponds to 4=2+1+1. It is not a vertex of P_4 since x=((4,0,0,0)+(0,2,0,0))/2. The partition x=(0,0,2,1,1,0^{10}) of n=15 is the first partition that is a convex combination of 3 partitions: x=((0,0,0,0,3,0^{10})+(0,0,1,3,0,0^{10})+(0,0,5,0,0,0^{10})/3.

%Y Cf. A000041, A108917, A203899, A300795.

%K nonn

%O 1,2

%A _Vladimir A. Shlyk_, Jan 07 2012