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

Author

Jochen Ziegenbalg, Dec 29 2020

Keywords

• nonn

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.

Examples

			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
		

Links

• Jochen Ziegenbalg, Independent subsets

Crossrefs

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

Programs

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
				

Maxima

/* version 2 */
a(n) :=
sum(
  sum(
    (b : n*d / a,
     if integerp(b) and b