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
Keywords
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
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
Comments