A182988 The number of dominance pairs of integer partitions of n according to either/or dominance order, where dominance between two partitions x and y means that x is majorized by y or y is majorized by x.

1, 1, 4, 9, 25, 49, 117, 217, 454, 830, 1594, 2796, 5159, 8777, 15415, 25810, 43819, 71595, 118629, 190148, 307519, 485660, 769382, 1195807, 1864617, 2857630, 4384962, 6641332, 10052272, 15043925, 22501510, 33315580, 49267369, 72250341, 105746966, 153646123

Offset: 0

Author

Stephen DeSalvo, Feb 06 2011, Feb 13 2011

Keywords

• nonn

Comments

For two integer partitions of n chosen uniformly at random, a(n)/p(n)^2, where p(n) is the number of partitions of n, is the probability that one dominates the other.

As an example, consider the partitions (4,3,1) and (3,3,2).

4 >= 3, 4+3 >= 3+3, and 4+3+1 = 3+3+2, so we say (4,3,1) majorizes/dominates (3,3,2).

As a non-example, consider (4,1,1,1) and (3,3,1).

4 >= 3, but 4+1 < 3+3, so (4,1,1,1) does NOT dominate (3,3,1).

3 < 4, so (3,3,1) does NOT dominate (4,1,1,1).

Thus the pair (4,1,1,1) and (3,3,1) is not a dominance pair, and does not contribute to a(7).

Examples

			For n=1,2,3,4,5, a(n) = p(n)^2, since these values of n give a linear order for integer partitions.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n=1..55 from Stephen DeSalvo)
• Wikipedia, Dominance Order
• Wikipedia, Majorization

Crossrefs

Cf. A000041, A001255, A248476, A265506.

Programs

Maple

b:= proc(n, m, i, j, t) option remember; `if`(n0,
       b(n, m, i, j-1, true), 0)+b(n, m, i-1, j, false)+
       b(n-i, m-j, min(n-i,i), min(m-j,j), true))))
    end:
a:= n-> 2*b(n$4, true)-combinat[numbpart](n):
seq(a(n), n=0..35);  # Alois P. Heinz, Dec 09 2015

Mathematica

b[n_, m_, i_, j_, t_] := b[n, m, i, j, t] = If[n0, b[n, m, i, j-1, True], 0] + b[n, m, i-1, j, False] + b[n-i, m-j, Min[n-i, i], Min[m-j, j], True]]]]; a[n_] := 2*b[n, n, n, n, True] - PartitionsP[n]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Dec 09 2016 after Alois P. Heinz *)

Extensions

a(0)=1 prepended by Alois P. Heinz, Jul 07 2015