[seqfan] partitions: reverse lex order versus natural (dominance) ordering

Wouter Meeussen wouter.meeussen at telenet.be
Mon Oct 6 19:06:06 CEST 2014

given that the reverse lex ordering (of the partitions of n) is a total order,
we can consider two counts when comparing both orderings:

pairs that are successors in reverse lex order, but incomparable in dominance ordering,
pairs (not nescessarily successors) of partitions of n that are incomparable.

the first goes as f(n)= {0,0,0,0,0,2,3,4,6,9,12,17,22,30,39,51,65,85,107,136,171,216,268,335} 
offset 1, n=1 .. 24, 
the second as s(n)={0,0,0,0,0,4,8,30,70,170,340,770,1424,2810,5166,9542,16614,
(* remark that the second is always even since incomparability commutes *)

As expected, the second , ‘s(n)’ , is known in OEIS since 2011 (A182988 , Stephen DeSalvo),  but as p(n)^2- s(n).

Fair enough, but unless someone says otherwise, I’ll add  f(n) and s(n)/2 also.
Affectionado’s of partitions into more than one part are hereby invited to comment or suggest modifs.

As an aside, remark that f(n) starts to differ from A035952 only at n=12. Strong law of small partitions, I think.


More information about the SeqFan mailing list