The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #9 Dec 22 2024 16:24:23
%S 0,0,0,0,24,0,720,0,7000,15120,126000,0,1777776,0,23543520,55855800,
%T 274565720,0,5337775872,0,63026049424,117920013120,995265791520,0,
%U 15265486117744,14283091977000,216344919117600,240142901941800,2854493961432480,0,55689696384165720
%N Number of pairs of independent nontrivial subsets of a finite set composed of n elements.
%C A subset X of a set S is called a trivial subset, if it is equal to the empty set or to the full set S. The subsets A and B of a finite set S are called independent, if #A/#S * #B/#S = #(A \intersect B)/#S.
%H Jochen Ziegenbalg, <a href="https://jochen-ziegenbalg.github.io/materialien/Manuskripte/independent-subsets.pdf">Independent subsets</a>
%e For n=4 and S={1,2,3,4} the a(4)=24 pairs of independent nontrivial subsets of S are
%e {{1, 2}, {1, 3}}, {{1, 2}, {1, 4}}, {{1, 2}, {2, 3}}, {{1, 2}, {2, 4}},
%e {{1, 3}, {1, 2}}, {{1, 3}, {1, 4}}, {{1, 3}, {2, 3}}, {{1, 3}, {3, 4}},
%e {{1, 4}, {1, 2}}, {{1, 4}, {1, 3}}, {{1, 4}, {2, 4}}, {{1, 4}, {3, 4}},
%e {{2, 3}, {1, 2}}, {{2, 3}, {1, 3}}, {{2, 3}, {2, 4}}, {{2, 3}, {3, 4}},
%e {{2, 4}, {1, 2}}, {{2, 4}, {1, 4}}, {{2, 4}, {2, 3}}, {{2, 4}, {3, 4}},
%e {{3, 4}, {1, 3}}, {{3, 4}, {1, 4}}, {{3, 4}, {2, 3}}, {{3, 4}, {2, 4}}
%e Tables:
%e n all independent independent
%e independent proper nontrivial
%e subsets subsets subsets
%e (see A121312) (see A158345) a(n)
%e 0 1 0 0
%e 1 4 1 0
%e 2 12 5 0
%e 3 28 13 0
%e 4 84 53 24
%e 5 124 61 0
%e 6 972 845 720
%e 7 508 253 0
%e 8 8020 7509 7000
%e 9 17164 16141 15120
%e 10 130092 128045 126000
%e 11 8188 4093 0
%e 12 1794156 1785965 1777776
%e 13 32764 16381 0
%e 14 23609052 23576285 23543520
%e 15 55986868 55921333 55855800
%e 16 274827860 274696789 274565720
%e 17 524284 262141 0
%e 18 5338824444 5338300157 5337775872
%e 19 2097148 1048573 0
%e 20 63030243724 63028146573 63026049424
%e 21 117928401724 117924207421 117920013120
%e 22 995282568732 995274180125 995265791520
%e 23 33554428 16777213 0
%e 24 15265553226604 15265519672173 15265486117744
%e 25 14283226194724 14283159085861 14283091977000
%e 26 216345187553052 216345053335325 216344919117600
%e 27 240143438812708 240143170377253 240142901941800
%e 28 2854495035174300 2854494498303389 2854493961432480
%e 29 2147483644 1073741821 0
%e 30 55689700679133012 55689698531649365 55689696384165720
%o (Maxima) /* version 1 */
%o pairs_independent_nontrivial_subsets(n) :=
%o block([a, b, d, s : 0 ],
%o for a:1 thru n-1 do
%o for d:1 thru a do
%o ( b : n*d / a,
%o if integerp(b) and b<n
%o then (s : s + binomial(n,a)*binomial(a,d)*binomial(n-a,b-d) ) ),
%o s );
%o (Maxima) /* version 2 */
%o a(n) :=
%o sum(
%o sum(
%o (b : n*d / a,
%o if integerp(b) and b<n then
%o binomial(n,a)*binomial(a,d)*binomial(n-a,b-d) else 0), d,1,a), a,1,n-1) ;
%Y Cf. A121312 (independent subsets), A158345 (independent proper subsets).
%K nonn
%O 0,5
%A _Jochen Ziegenbalg_, Dec 29 2020