A076269 - OEIS

%I #27 May 13 2020 10:56:50

%S 1,1,1,1,1,1,2,2,2,3,4,4,5,6,7,9,10,11,14,17,20,24,29,35,40,48,55

%N Size of largest antichain in partition lattice Par(n).

%C Par(n) is the set of partitions of n under "dominance order": partition P is <= partition Q iff the sum of the largest k parts of P is <= the corresponding sum for Q for all k.

%H T. Brylawski, <a href="http://dx.doi.org/10.1016/0012-365X(73)90094-0">The lattice of integer partitions</a>, Discrete Math. 6 (1973), 201-219.

%H Edward Early, <a href="https://web.archive.org/web/20150911055028/http://myweb.stedwards.edu/edwarde/partitions.pdf">Chain Lengths in the Dominance Lattice</a>, June 8, 2013.

%H Edward Early, <a href="http://dx.doi.org/10.1016/j.disc.2013.05.016">Chain Lengths in the Dominance Lattice</a>, Discrete Mathematics, Volume 313, Issue 20, 28 October 2013, Pages 2168-2177.

%H C. Greene and D. J. Kleitman, <a href="http://dx.doi.org/10.1016/S0195-6698(86)80013-0">Longest Chains in the Lattice of Integer Partitions ordered by Majorization</a>, Europ. J. Combinatorics 7 (1986), 1-10.

%H Grant Kopitzke, <a href="https://arxiv.org/abs/2005.04284">The Gini Index of an Integer Partition</a>, arXiv:2005.04284 [math.CO], 2020. Mentions this sequence.

%F Order of growth is between n^(-5/2)e^(Pi*sqrt(2n/3)) and n^(-1)e^(Pi*sqrt(2n/3)).

%e a(10)=4; one antichain consists of 5+1+1+1+1+1, 4+3+1+1+1, 4+2+2+2 and 3+3+3+1.

%t leq[p_, q_] := If[Length[p]<Length[q], False, Module[{i, ds}, For[i=1; ds=0, i<Length[q], i++, If[(ds+=q[[i]]-p[[i]])<0, Return[False]]]; True]]; maxac[l_] := If[Length[l]<=1, Length[l], maxac[l]=Max[maxac[Drop[l, 1]], 1+maxac[Select[l, !leq[ #, l[[1]]]&&!leq[l[[1]], # ]&]]]]; a[n_] := a[n]=maxac[IntegerPartitions[n]]

%Y Cf. A006463, A077765, A076779.

%K nonn,hard,more

%O 0,7

%A _Edward Early_, Nov 05 2002

%E Edited by _Dean Hickerson_, Nov 09 2002

%E a(22)-a(26) by _Paul Tabatabai_, Dec 05 2018