login
Number of pairs of integer partitions of n where every part of the first is less than every part of the second.
6

%I #11 May 10 2021 07:40:57

%S 1,0,1,2,5,7,16,20,40,55,97,124,235,287,482,654,1033,1318,2137,2676,

%T 4157,5439,7891,10144,15280,19171,27336,35652,49756,63150,89342,

%U 111956,154400,197413,264572,336082,456724,568932,756065,959566,1261803,1576355,2078267

%N Number of pairs of integer partitions of n where every part of the first is less than every part of the second.

%F a(n) = Sum_{k=1..n-1} A026820(n, k) * A026794(n, k + 1).

%e The a(5) = 16 pairs of integer partitions:

%e (51)|(6)

%e (42)|(6)

%e (411)|(6)

%e (33)|(6)

%e (321)|(6)

%e (3111)|(6)

%e (222)|(6)

%e (222)|(33)

%e (2211)|(6)

%e (2211)|(33)

%e (21111)|(6)

%e (21111)|(33)

%e (111111)|(6)

%e (111111)|(42)

%e (111111)|(33)

%e (111111)|(222)

%p g:= proc(n, i) option remember; `if`(n=0 or i=1, 1,

%p g(n, i-1) +g(n-i, min(i, n-i)))

%p end:

%p b:= proc(n, i) option remember; `if`(n=0, 1,

%p `if`(i>n, 0, b(n, i+1)+b(n-i, i)))

%p end:

%p a:= proc(n) option remember; `if`(n=0, 1,

%p add(g(n-i, min(n-i, i))*b(n, i+1), i=1..n))

%p end:

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

%t Table[Length[Select[Tuples[IntegerPartitions[n],2],Max@@First[#]<Min@@Last[#]&]],{n,20}]

%t (* Second program: *)

%t g[n_, i_] := g[n, i] = If[n==0 || i==1, 1, g[n, i-1]+g[n-i, Min[i, n-i]]];

%t b[n_, i_] := b[n, i] = If[n==0, 1, If[i>n, 0, b[n, i+1] + b[n-i, i]]];

%t a[n_] := a[n] = If[n==0, 1, Sum[g[n-i, Min[n-i, i]]*b[n, i+1], {i, 1, n}]];

%t a /@ Range[0, 50] (* _Jean-François Alcover_, May 10 2021, after _Alois P. Heinz_ *)

%Y Cf. A265947, A317144, A318915, A322435, A322436, A322439.

%K nonn

%O 0,4

%A _Gus Wiseman_, Dec 08 2018