Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 DominatingIntegerPartitionQ

Source Notebook

Determine if one integer partition dominates another

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["DominatingIntegerPartitionQ"][p,q]

yields True if integer partition p dominates integer partition q and False otherwise.

Details

For two integer partitions p={p1,…,pk} and q={q1,…,kl} of some positive integer n, p is said to dominate q if the sum of the t largest parts of p is greater than or equal to the sum of the t largest parts of q, p1+…+pt≥q1+…+qt, for all t≥1, where the partition with fewer parts is padded with zeros at the end.
Partitions p and q can be incomparable with respect to dominance.

Examples

Basic Examples (2) 

Since 5+1<4+3, the first partition does not dominate the second:

In[1]:=
ResourceFunction[ "DominatingIntegerPartitionQ"][{5, 1, 1, 1}, {4, 3, 1}]
Out[1]=

The first partition dominates the second, since 4≥4, 4+4≥4+3 and 4+4≥4+3+1:

In[2]:=
ResourceFunction["DominatingIntegerPartitionQ"][{4, 4}, {4, 3, 1}]
Out[2]=

Applications (1) 

Display the domination lattice on integer partitions, using the resource function HasseDiagram:

In[3]:=
dominationLattice[n_, opts___] := ResourceFunction["HasseDiagram"][ResourceFunction[ "DominatingIntegerPartitionQ"], IntegerPartitions[n], opts, VertexShapeFunction -> "Name"]
In[4]:=
dominationLattice[8]
Out[4]=

Properties and Relations (3) 

DominatingIntegerPartitionQ[p,q] being False does not imply that DominatingIntegerPartitionQ[q,p] is True:

In[5]:=
p = {5, 1, 1, 1}; q = {4, 3, 1};
In[6]:=
ResourceFunction["DominatingIntegerPartitionQ"][p, q]
Out[6]=
In[7]:=
ResourceFunction["DominatingIntegerPartitionQ"][q, p]
Out[7]=

In this case, this is because the first element of q is smaller than the first element of p:

In[8]:=
First[q] < First[p]
Out[8]=

DominatingIntegerPartitionQ[p,q] and DominatingIntegerPartitionQ[q,p] can both yield True for certain p and q:

In[9]:=
p = q = {5, 1, 1, 1}
Out[9]=
In[10]:=
ResourceFunction["DominatingIntegerPartitionQ"][p, q]
Out[10]=
In[11]:=
ResourceFunction["DominatingIntegerPartitionQ"][q, p]
Out[11]=

Among the partitions of n, {n} is always the largest and {1,…,1} is the smallest:

In[12]:=
n = 8; {First[#], Last[#]} &[ Sort[IntegerPartitions[n], ResourceFunction[ "DominatingIntegerPartitionQ"]]]
Out[13]=

Version History

  • 1.0.1 – 31 January 2022
  • 1.0.0 – 28 July 2020

Related Resources

License Information