OFFSET
0,2
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?
LINKS
Robert Israel, Table of n, a(n) for n = 0..1000
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).
EXAMPLE
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.
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 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Benoit Rittaud (rittaud(AT)math.univ-paris13.fr), Aug 25 2006
EXTENSIONS
Edited by Franklin T. Adams-Watters and Joshua Zucker, Oct 04 2006
STATUS
approved