|
Search: id:A121312
|
|
|
| A121312 |
|
Number of pairs of probabilistically independent subsets in a set composed of n elements. |
|
+0
1
|
|
| 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; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
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?
|
|
FORMULA
|
a(n) = sum_{u=0..n} sum_{(a,b) in [u,n] : ab=nu} binomial(n,a)*binomial(a,u)*binomial(n-a,b-u}; a(n)=sum_{u=0..n} sum_{(a,b) in [u,n] : ab=nu} binomial(n,u)*binomial(n-u,a-u)*binomial(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;
|
|
CROSSREFS
|
Sequence in context: A028399 A034508 A002932 this_sequence A091521 A050898 A009845
Adjacent sequences: A121309 A121310 A121311 this_sequence A121313 A121314 A121315
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Benoit Rittaud (rittaud(AT)math.univ-paris13.fr), Aug 25 2006
|
|
EXTENSIONS
|
Edited by Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net) and Joshua Zucker (joshua.zucker(AT)gmail.com), Oct 04 2006
|
|
|
Search completed in 0.002 seconds
|
