| Displaying 1-6 of 6 results found.
page
1
Number of connectedness systems on n vertices that contain all singletons and the set of all the vertices.
+10
15
1, 1, 8, 378, 252000, 18687534984
COMMENTS
Previous name was: a(1) = 1; for n > 1, a(n) = number of families of subsets of {1, ..., n} that contain both the universe and the empty set, are closed under union of nondisjoint sets, and contain no singletons.
A connectedness system is (as below) a set of (finite) nonempty sets that is closed under union of nondisjoint sets.
The old definition was: "Number of subsets S of the power set P{1,2,...,n} such that: {1}, {2},..., {n} are all elements of S; {1,2,...n} is an element of S; if X and Y are elements of S and X and Y have a nonempty intersection, then the union of X and Y is an element of S."
Comments on the old definition from Gus Wiseman, Aug 01 2019: (Start) If this sequence were defined similarly to A326877, we would have a(1) = 0. We define a connectedness system to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is connected if it is empty or contains an edge with all the vertices. a(n) is the number of connected connectedness systems on n vertices without singletons. For example, the a(3) = 8 connected connectedness systems without singletons are:
{{1,2,3}}
{{1,2},{1,2,3}}
{{1,3},{1,2,3}}
{{2,3},{1,2,3}}
{{1,2},{1,3},{1,2,3}}
{{1,2},{2,3},{1,2,3}}
{{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}
(End)
Conjecture concerning the original definition: a(n) is also the number of families of subsets of {1, ..., n} that contain both the universe and the empty set, are closed under intersection and contain no sets of cardinality n-1. - Tian Vlasic, Nov 04 2022. [This was false, as pointed out by Christian Sievers, Oct 20 2023. It is easy to see that for n>1, a(n) is also the number of families of subsets of {1, ..., n} that contain both the universe and the empty set, are closed under union of nondisjoint sets, and contain no singletons; whereas by duality, the sequence suggested in the conjecture is also the number of those families that are also closed under arbitrary union. For details see the Sievers link. - N. J. A. Sloane, Oct 21 2023]
EXAMPLE
a(3) = 8 because of the 8 sets: {{1}, {2}, {3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 3}, {1, 2, 3}}; {{1}, {2}, {3}, {2, 3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2, n}]], (n==0||MemberQ[#, Range[n]])&&SubsetQ[#, Union@@@Select[Tuples[#, 2], Intersection@@#!={}&]]&]], {n, 0, 4}] (* returns a(1) = 0 similar to A326877. - Gus Wiseman, Aug 01 2019 *)
CROSSREFS
The case with singletons is A326868.
AUTHOR
Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002
BII-numbers of connectedness systems.
+10
14
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 24, 25, 26, 27, 32, 33, 34, 35, 40, 41, 42, 43, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99
COMMENTS
We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges.
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges. The enumeration of these set-systems by number of covered vertices is given by A326870.
EXAMPLE
The sequence of all connectedness systems together with their BII-numbers begins:
0: {}
1: {{1}}
2: {{2}}
3: {{1},{2}}
4: {{1,2}}
5: {{1},{1,2}}
6: {{2},{1,2}}
7: {{1},{2},{1,2}}
8: {{3}}
9: {{1},{3}}
10: {{2},{3}}
11: {{1},{2},{3}}
12: {{1,2},{3}}
13: {{1},{1,2},{3}}
14: {{2},{1,2},{3}}
15: {{1},{2},{1,2},{3}}
16: {{1,3}}
17: {{1},{1,3}}
18: {{2},{1,3}}
19: {{1},{2},{1,3}}
24: {{3},{1,3}}
25: {{1},{3},{1,3}}
26: {{2},{3},{1,3}}
27: {{1},{2},{3},{1,3}}
32: {{2,3}}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
connsysQ[eds_]:=SubsetQ[eds, Union@@@Select[Tuples[eds, 2], Intersection@@#!={}&]];
Select[Range[0, 100], connsysQ[bpe/@bpe[#]]&]
CROSSREFS
Connectedness systems are counted by A326866, with unlabeled version A326867. The case without singletons is A326873. Set-systems closed under union are counted by A102896, with BII numbers A326875.
Number of subsets S of the power set P{1,2,...,n} such that: {1}, {2},..., {n} are all elements of S; {1,2,...,n} is an element of S; if X and Y are elements of S and X and Y have a nonempty intersection, then the union of X and Y is an element of S. The sets S are counted modulo permutations on the elements 1,2,...,n.
+10
12
1, 1, 1, 4, 40, 3044, 26894586
COMMENTS
We define a connectedness system to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is connected if it is empty or contains an edge with all the vertices. Then a(n) is the number of unlabeled connected connectedness systems without singletons on n vertices. - Gus Wiseman, Aug 01 2019
EXAMPLE
a(3) = 4 because of the 4 sets: {{1}, {2}, {3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}}; {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
CROSSREFS
The case with singletons is A326869.
AUTHOR
Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002
Number of unlabeled connected connectedness systems on n vertices.
+10
9
1, 1, 3, 20, 406, 79964, 1689032658
COMMENTS
We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is connected if it contains an edge with all the vertices.
EXAMPLE
Non-isomorphic representatives of the a(3) = 20 connected connectedness systems:
{{1,2,3}}
{{3},{1,2,3}}
{{2,3},{1,2,3}}
{{2},{3},{1,2,3}}
{{1},{2,3},{1,2,3}}
{{3},{2,3},{1,2,3}}
{{1},{2},{3},{1,2,3}}
{{1,3},{2,3},{1,2,3}}
{{1},{3},{2,3},{1,2,3}}
{{2},{3},{2,3},{1,2,3}}
{{2},{1,3},{2,3},{1,2,3}}
{{3},{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}
{{1},{2},{3},{2,3},{1,2,3}}
{{1},{2},{1,3},{2,3},{1,2,3}}
{{2},{3},{1,3},{2,3},{1,2,3}}
{{3},{1,2},{1,3},{2,3},{1,2,3}}
{{1},{2},{3},{1,3},{2,3},{1,2,3}}
{{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
{{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
CROSSREFS
The case without singletons is A072445. The not necessarily connected case is A326867. Euler transform is A326871 (the covering case).
Number of connected connectedness systems on n vertices.
+10
8
1, 1, 4, 64, 6048, 8064000, 1196002238976
COMMENTS
We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges. It is connected if it is empty or contains an edge with all the vertices.
EXAMPLE
The a(3) = 64 connected connectedness systems:
{{123}} {{1}{123}}
{{12}{123}} {{2}{123}}
{{13}{123}} {{3}{123}}
{{23}{123}} {{1}{12}{123}}
{{12}{13}{123}} {{1}{13}{123}}
{{12}{23}{123}} {{1}{23}{123}}
{{13}{23}{123}} {{2}{12}{123}}
{{12}{13}{23}{123}} {{2}{13}{123}}
{{2}{23}{123}}
{{3}{12}{123}}
{{3}{13}{123}}
{{3}{23}{123}}
{{1}{12}{13}{123}}
{{1}{12}{23}{123}}
{{1}{13}{23}{123}}
{{2}{12}{13}{123}}
{{2}{12}{23}{123}}
{{2}{13}{23}{123}}
{{3}{12}{13}{123}}
{{3}{12}{23}{123}}
{{3}{13}{23}{123}}
{{1}{12}{13}{23}{123}}
{{2}{12}{13}{23}{123}}
{{3}{12}{13}{23}{123}}
.
{{1}{2}{123}} {{1}{2}{3}{123}}
{{1}{3}{123}} {{1}{2}{3}{12}{123}}
{{2}{3}{123}} {{1}{2}{3}{13}{123}}
{{1}{2}{12}{123}} {{1}{2}{3}{23}{123}}
{{1}{2}{13}{123}} {{1}{2}{3}{12}{13}{123}}
{{1}{2}{23}{123}} {{1}{2}{3}{12}{23}{123}}
{{1}{3}{12}{123}} {{1}{2}{3}{13}{23}{123}}
{{1}{3}{13}{123}} {{1}{2}{3}{12}{13}{23}{123}}
{{1}{3}{23}{123}}
{{2}{3}{12}{123}}
{{2}{3}{13}{123}}
{{2}{3}{23}{123}}
{{1}{2}{12}{13}{123}}
{{1}{2}{12}{23}{123}}
{{1}{2}{13}{23}{123}}
{{1}{3}{12}{13}{123}}
{{1}{3}{12}{23}{123}}
{{1}{3}{13}{23}{123}}
{{2}{3}{12}{13}{123}}
{{2}{3}{12}{23}{123}}
{{2}{3}{13}{23}{123}}
{{1}{2}{12}{13}{23}{123}}
{{1}{3}{12}{13}{23}{123}}
{{2}{3}{12}{13}{23}{123}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {1, n}]], n==0||MemberQ[#, Range[n]]&&SubsetQ[#, Union@@@Select[Tuples[#, 2], Intersection@@#!={}&]]&]], {n, 0, 4}]
CROSSREFS
The case without singletons is A072447. The not necessarily connected case is A326866. The BII-numbers of these set-systems are A326879.
BII-numbers of connectedness systems without singletons.
+10
5
0, 4, 16, 32, 64, 68, 80, 84, 96, 100, 112, 116, 256, 288, 512, 528, 1024, 1028, 1280, 1284, 1536, 1540, 1792, 1796, 2048, 2052, 4096, 4112, 4352, 4368, 6144, 6160, 6400, 6416, 8192, 8224, 8704, 8736, 10240, 10272, 10752, 10784, 16384, 16388, 16400, 16416
COMMENTS
We define a connectedness system (investigated by Vim van Dam in 2002) to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges.
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges. The enumeration of these set-systems by number of covered vertices is given by A326877.
EXAMPLE
The sequence of all connectedness systems without singletons together with their BII-numbers begins:
0: {}
4: {{1,2}}
16: {{1,3}}
32: {{2,3}}
64: {{1,2,3}}
68: {{1,2},{1,2,3}}
80: {{1,3},{1,2,3}}
84: {{1,2},{1,3},{1,2,3}}
96: {{2,3},{1,2,3}}
100: {{1,2},{2,3},{1,2,3}}
112: {{1,3},{2,3},{1,2,3}}
116: {{1,2},{1,3},{2,3},{1,2,3}}
256: {{1,4}}
288: {{2,3},{1,4}}
512: {{2,4}}
528: {{1,3},{2,4}}
1024: {{1,2,4}}
1028: {{1,2},{1,2,4}}
1280: {{1,4},{1,2,4}}
1284: {{1,2},{1,4},{1,2,4}}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
connnosQ[eds_]:=!MemberQ[Length/@eds, 1]&&SubsetQ[eds, Union@@@Select[Tuples[eds, 2], Intersection@@#!={}&]];
Select[Range[0, 1000], connnosQ[bpe/@bpe[#]]&]
CROSSREFS
Connectedness systems without singletons are counted by A072446, with unlabeled case A072444. Connectedness systems are counted by A326866, with unlabeled case A326867. BII-numbers of connectedness systems are A326872.
Search completed in 0.011 seconds
| 