A182988 - OEIS

%I #51 Oct 27 2023 21:53:34

%S 1,1,4,9,25,49,117,217,454,830,1594,2796,5159,8777,15415,25810,43819,

%T 71595,118629,190148,307519,485660,769382,1195807,1864617,2857630,

%U 4384962,6641332,10052272,15043925,22501510,33315580,49267369,72250341,105746966,153646123

%N 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.

%C 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.

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

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

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

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

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

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

%H Alois P. Heinz, <a href="/A182988/b182988.txt">Table of n, a(n) for n = 0..200</a> (terms n=1..55 from Stephen DeSalvo)

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Dominance_order">Dominance Order</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Majorization">Majorization</a>

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

%p b:= proc(n, m, i, j, t) option remember; `if`(n<m, 0,

%p       `if`(n=0, 1, `if`(i<1, 0, `if`(t and j>0,

%p        b(n, m, i, j-1, true), 0)+b(n, m, i-1, j, false)+

%p        b(n-i, m-j, min(n-i,i), min(m-j,j), true))))

%p     end:

%p a:= n-> 2*b(n$4, true)-combinat[numbpart](n):

%p seq(a(n), n=0..35);  # _Alois P. Heinz_, Dec 09 2015

%t 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_ *)

%Y Cf. A000041, A001255, A248476, A265506.

%K nonn

%O 0,3

%A _Stephen DeSalvo_, Feb 06 2011, Feb 13 2011

%E a(0)=1 prepended by _Alois P. Heinz_, Jul 07 2015