A340135 Number of pairs of independent nontrivial subsets of a finite set composed of n elements.

0, 0, 0, 0, 24, 0, 720, 0, 7000, 15120, 126000, 0, 1777776, 0, 23543520, 55855800, 274565720, 0, 5337775872, 0, 63026049424, 117920013120, 995265791520, 0, 15265486117744, 14283091977000, 216344919117600, 240142901941800, 2854493961432480, 0, 55689696384165720

Offset

0,5

Comments

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.

Links

Table of n, a(n) for n=0..30.

Jochen Ziegenbalg, Independent subsets

Example

For n=4 and S={1,2,3,4} the a(4)=24 pairs of independent nontrivial subsets of S are
{{1, 2}, {1, 3}}, {{1, 2}, {1, 4}}, {{1, 2}, {2, 3}}, {{1, 2}, {2, 4}},
{{1, 3}, {1, 2}}, {{1, 3}, {1, 4}}, {{1, 3}, {2, 3}}, {{1, 3}, {3, 4}},
{{1, 4}, {1, 2}}, {{1, 4}, {1, 3}}, {{1, 4}, {2, 4}}, {{1, 4}, {3, 4}},
{{2, 3}, {1, 2}}, {{2, 3}, {1, 3}}, {{2, 3}, {2, 4}}, {{2, 3}, {3, 4}},
{{2, 4}, {1, 2}}, {{2, 4}, {1, 4}}, {{2, 4}, {2, 3}}, {{2, 4}, {3, 4}},
{{3, 4}, {1, 3}}, {{3, 4}, {1, 4}}, {{3, 4}, {2, 3}}, {{3, 4}, {2, 4}}
Tables:
     n                all        independent        independent
              independent             proper         nontrivial
                  subsets            subsets            subsets
            (see A121312)      (see A158345)               a(n)
     0                  1                  0                  0
     1                  4                  1                  0
     2                 12                  5                  0
     3                 28                 13                  0
     4                 84                 53                 24
     5                124                 61                  0
     6                972                845                720
     7                508                253                  0
     8               8020               7509               7000
     9              17164              16141              15120
    10             130092             128045             126000
    11               8188               4093                  0
    12            1794156            1785965            1777776
    13              32764              16381                  0
    14           23609052           23576285           23543520
    15           55986868           55921333           55855800
    16          274827860          274696789          274565720
    17             524284             262141                  0
    18         5338824444         5338300157         5337775872
    19            2097148            1048573                  0
    20        63030243724        63028146573        63026049424
    21       117928401724       117924207421       117920013120
    22       995282568732       995274180125       995265791520
    23           33554428           16777213                  0
    24     15265553226604     15265519672173     15265486117744
    25     14283226194724     14283159085861     14283091977000
    26    216345187553052    216345053335325    216344919117600
    27    240143438812708    240143170377253    240142901941800
    28   2854495035174300   2854494498303389   2854493961432480
    29         2147483644         1073741821                  0
    30  55689700679133012  55689698531649365  55689696384165720

Prog

(Maxima)   /* version 1 */
pairs_independent_nontrivial_subsets(n) :=
block([a, b, d, s : 0 ],
  for a:1 thru n-1 do
    for d:1 thru a do
        ( b : n*d / a,
          if integerp(b) and b<n
              then (s : s + binomial(n, a)*binomial(a, d)*binomial(n-a, b-d) ) ),
    s );
(Maxima)   /* version 2 */
a(n) :=
sum(
  sum(
    (b : n*d / a,
     if integerp(b) and b<n then
       binomial(n, a)*binomial(a, d)*binomial(n-a, b-d) else 0), d, 1, a), a, 1, n-1) ;

Crossrefs

Cf. A121312 (independent subsets), A158345 (independent proper subsets).

Sequence in context: A128379 A111983 A326857 * A364203 A308304 A265090

Adjacent sequences: A340132 A340133 A340134 * A340136 A340137 A340138

Keyword

nonn,changed

Author

Jochen Ziegenbalg, Dec 29 2020

Status

approved