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

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

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), 201-219.

Edward Early, Chain Lengths in the Dominance Lattice, June 8, 2013.

Edward Early, Chain Lengths in the Dominance Lattice, Discrete Mathematics, Volume 313, Issue 20, 28 October 2013, Pages 2168-2177.

C. Greene and D. J. Kleitman, Longest Chains in the Lattice of Integer Partitions ordered by Majorization, Europ. J. Combinatorics 7 (1986), 1-10.

Grant Kopitzke, The Gini Index of an Integer Partition, arXiv:2005.04284 [math.CO], 2020. Mentions this sequence.

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 A363336 A104410

Adjacent sequences: A076266 A076267 A076268 * A076270 A076271 A076272

Keyword

nonn,hard,more

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