

A076269


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


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,7


COMMENTS

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.


LINKS

Table of n, a(n) for n=0..26.
T. Brylawski, The lattice of integer partitions, Discrete Math. 6 (1973), 201219.
Edward Early, Chain Lengths in the Dominance Lattice, June 8, 2013;
C. Greene and D. J. Kleitman, Longest Chains in the Lattice of Integer Partitions ordered by Majorization, Europ. J. Combinatorics 7 (1986), 110.


FORMULA

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


EXAMPLE

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.


MATHEMATICA

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]]


CROSSREFS

Cf. A006463, A077765, A076779.
Sequence in context: A035382 A094988 A173911 * A143644 A104410 A018048
Adjacent sequences: A076266 A076267 A076268 * A076270 A076271 A076272


KEYWORD

hard,more,nonn


AUTHOR

Edward Early, Nov 05 2002


EXTENSIONS

Edited by Dean Hickerson, Nov 09 2002
a(22)a(26) by Paul Tabatabai, Dec 05 2018


STATUS

approved



