cp's OEIS Frontend

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

%I A121312 #16 Sep 16 2020 06:08:35
%S A121312 1,4,12,28,84,124,972,508,8020,17164,130092,8188,1794156,32764,
%T A121312 23609052,55986868,274827860,524284,5338824444,2097148,63030243724,
%U A121312 117928401724,995282568732,33554428,15265553226604,14283226194724,216345187553052
%N A121312 Number of pairs of probabilistically independent subsets in a set composed of n elements.
%C A121312 A and B are independent iff |A|/n * |B|/n = |A intersect B| / n.
%C A121312 Is there a reasonably simple expression for a(n) depending on the prime decomposition of n?
%H A121312 Robert Israel, <a href="/A121312/b121312.txt">Table of n, a(n) for n = 0..1000</a>
%F A121312 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).
%F A121312 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).
%e A121312 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.
%p A121312 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;
%p A121312 # Alternative:
%p A121312 f:= proc(n) local u,a,b, s;
%p A121312      s:= 2^(n+1)-1;
%p A121312      for u from 1 to n do
%p A121312        for a in select(t -> t <= n and t>=u, numtheory:-divisors(u*n)) do
%p A121312           b:= u*n/a;
%p A121312           s:= s+binomial(n,a)*binomial(a,u)*binomial(n-a,b-u)
%p A121312      od od;
%p A121312      s
%p A121312 end proc:
%p A121312 map(f, [$1..100]); # _Robert Israel_, Jun 08 2015
%t A121312 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];
%t A121312 f /@ Range[0, 100] (* _Jean-François Alcover_, Sep 16 2020, after 2nd Maple program *)
%K A121312 easy,nonn
%O A121312 0,2
%A A121312 Benoit Rittaud (rittaud(AT)math.univ-paris13.fr), Aug 25 2006
%E A121312 Edited by _Franklin T. Adams-Watters_ and _Joshua Zucker_, Oct 04 2006