A340135 - OEIS

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

(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(

(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

AUTHOR

Jochen Ziegenbalg, Dec 29 2020

STATUS

approved