login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A340135 Number of pairs of independent nontrivial subsets of a finite set composed of n elements. 0
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 (list; graph; refs; listen; history; text; internal format)
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 * A308304 A265090 A174560

Adjacent sequences:  A340132 A340133 A340134 * A340136 A340137 A340138

KEYWORD

nonn

AUTHOR

Jochen Ziegenbalg, Dec 29 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 22 19:36 EDT 2021. Contains 347608 sequences. (Running on oeis4.)