A121312 Number of pairs of probabilistically independent subsets in a set composed of n elements.

1, 4, 12, 28, 84, 124, 972, 508, 8020, 17164, 130092, 8188, 1794156, 32764, 23609052, 55986868, 274827860, 524284, 5338824444, 2097148, 63030243724, 117928401724, 995282568732, 33554428, 15265553226604, 14283226194724, 216345187553052

Offset: 0

Author

Benoit Rittaud (rittaud(AT)math.univ-paris13.fr), Aug 25 2006

Keywords

• easy
• nonn

Comments

A and B are independent iff |A|/n * |B|/n = |A intersect B| / n.

Is there a reasonably simple expression for a(n) depending on the prime decomposition of n?

Examples

			a(2)=12 because, denoting by {x,y} the full set, the number of its subsets is 2^2=4, so the number of pairs of subsets is 4^2=16, among which only the four pairs ({x}, {x}), ({x}, {y}), ({y}, {x}) and ({y}, {y}) are made of non-independent subsets.
		

Links

• Robert Israel, Table of n, a(n) for n = 0..1000

Programs

Maple

a:=proc(n) local a,b,u,s; s:=2^(n+1)-1; for u from 1 to n do for a from u to n do b:=n*u/a; if is(b=round(b)) then s:=s+binomial(n,a)*binomial(a,u)*binomial(n-a, b-u) fi; od; od; print(s); end;
# Alternative:
f:= proc(n) local u,a,b, s;
     s:= 2^(n+1)-1;
     for u from 1 to n do
       for a in select(t -> t <= n and t>=u, numtheory:-divisors(u*n)) do
          b:= u*n/a;
          s:= s+binomial(n,a)*binomial(a,u)*binomial(n-a,b-u)
     od od;
     s
end proc:
map(f, [$1..100]); # Robert Israel, Jun 08 2015

Mathematica

f[n_] := Module[{b, s}, s = 2^(n+1)-1; Do[b = u n/a; s += Binomial[n, a]* Binomial[a, u] Binomial[n-a, b-u], {u, n}, {a, Select[Divisors[u n], u <= # <= n&]}]; s];
f /@ Range[0, 100] (* Jean-François Alcover, Sep 16 2020, after 2nd Maple program *)

Formula

a(n) = Sum_{u=0..n} Sum_{(a,b) in [u,n] : ab=nu} C(n,a)*C(a,u)*C(n-a,b-u).

a(n) = Sum_{u=0..n} Sum_{(a,b) in [u,n] : ab=nu} C(n,u)*C(n-u,a-u)*C(n-a,b-u).

Extensions

Edited by Franklin T. Adams-Watters and Joshua Zucker, Oct 04 2006