OFFSET
0,3
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).
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
EXAMPLE
For n=1,2,3,4,5, a(n) = p(n)^2, since these values of n give a linear order for integer partitions.
MAPLE
b:= proc(n, m, i, j, t) option remember; `if`(n<m, 0,
`if`(n=0, 1, `if`(i<1, 0, `if`(t and j>0,
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[n<m, 0, If[n==0, 1, If[i<1, 0, If[t && j>0, 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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Stephen DeSalvo, Feb 06 2011, Feb 13 2011
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Jul 07 2015
STATUS
approved