|
%I #6 Jun 24 2014 01:08:33
%S 1,1,2,3,5,7,2,4,15,4,2,11,18,14,53,2,54,1606,482,104,754,536
%N Number of maximum-size antichains 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.
%e 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.
%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]], # ]&]]]]; 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. *)
%Y The corresponding sizes are in A076269.
%K nonn,more
%O 0,3
%A _Dean Hickerson_, Nov 14 2002
|
