|
|
A121312
|
|
Number of pairs of probabilistically independent subsets in a set composed of n elements.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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:
|
|
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];
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Benoit Rittaud (rittaud(AT)math.univ-paris13.fr), Aug 25 2006
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|