A077765 Number of maximum-size antichains in partition lattice Par(n).

1, 1, 2, 3, 5, 7, 2, 4, 15, 4, 2, 11, 18, 14, 53, 2, 54, 1606, 482, 104, 754, 536

Offset

0,3

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..21.

Example

For n=10, the maximum size is A076269(10)=4. There are 2 maximum-size antichains: {5+1+1+1+1+1, 4+3+1+1+1, 4+2+2+2, 3+3+3+1} and {6+1+1+1+1, 5+2+2+1, 4+4+1+1, 4+3+3}. So a(10)=2.

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]], # ]&]]]]; maxantichains[l_] := If[Length[l]<=1, {l}, Module[{v, t}, v={}; If[maxac[l]==maxac[Drop[l, 1]], v=Join[v, maxantichains[Drop[l, 1]]]]; t=Select[l, !leq[ #, l[[1]]]&&!leq[l[[1]], # ]&]; If[maxac[l]==1+maxac[t], v=Join[v, Prepend[ #, l[[1]]]&/@maxantichains[t]]]; v]]; a[n_] := Length[maxantichains[Partitions[n]]] (* First do <<DiscreteMath`Combinatorica` *) (* maxac[l] = size of largest antichain in set l. maxantichains[l] = list of all maximum-length antichains in l. *)

Crossrefs

The corresponding sizes are in A076269.

Sequence in context: A038194 A111309 A007605 * A078400 A068951 A139752

Adjacent sequences: A077762 A077763 A077764 * A077766 A077767 A077768

Keyword

nonn,more

Author

Dean Hickerson, Nov 14 2002

Status

approved