|
|
A330109
|
|
BII-numbers of BII-normalized set-systems.
|
|
19
|
|
|
0, 1, 3, 4, 5, 7, 11, 12, 13, 15, 20, 21, 22, 23, 30, 31, 52, 53, 55, 63, 64, 65, 67, 68, 69, 71, 75, 76, 77, 79, 84, 85, 86, 87, 94, 95, 116, 117, 119, 127, 139, 140, 141, 143, 148, 149, 150, 151, 158, 159, 180, 181, 183, 191, 192, 193, 195, 196, 197, 199, 203
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
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 set-system 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.
We define the BII-normalization of a set-system to be obtained by first normalizing so that the vertices cover an initial interval of positive integers, then applying all permutations to the vertex set, and finally taking the representative with the smallest BII-number.
For example, 156 is the BII-number of {{3},{4},{1,2},{1,3}}, which has the following normalizations, together with their BII-numbers:
Brute-force: 2067: {{1},{2},{1,3},{3,4}}
Lexicographic: 165: {{1},{4},{1,2},{2,3}}
VDD: 525: {{1},{3},{1,2},{2,4}}
MM: 270: {{2},{3},{1,2},{1,4}}
BII: 150: {{2},{4},{1,2},{1,3}}
|
|
LINKS
|
|
|
EXAMPLE
|
The sequence of all nonempty BII-normalized set-systems together with their BII-numbers begins:
1: {1} 52: {12}{13}{23}
3: {1}{2} 53: {1}{12}{13}{23}
4: {12} 55: {1}{2}{12}{13}{23}
5: {1}{12} 63: {1}{2}{3}{12}{13}{23}
7: {1}{2}{12} 64: {123}
11: {1}{2}{3} 65: {1}{123}
12: {3}{12} 67: {1}{2}{123}
13: {1}{3}{12} 68: {12}{123}
15: {1}{2}{3}{12} 69: {1}{12}{123}
20: {12}{13} 71: {1}{2}{12}{123}
21: {1}{12}{13} 75: {1}{2}{3}{123}
22: {2}{12}{13} 76: {3}{12}{123}
23: {1}{2}{12}{13} 77: {1}{3}{12}{123}
30: {2}{3}{12}{13} 79: {1}{2}{3}{12}{123}
31: {1}{2}{3}{12}{13} 84: {12}{13}{123}
|
|
MATHEMATICA
|
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
fbi[q_]:=If[q=={}, 0, Total[2^q]/2];
biinorm[m_]:=If[Union@@m!={}&&Union@@m!=Range[Max@@Flatten[m]], biinorm[m/.Rule@@@Table[{(Union@@m)[[i]], i}, {i, Length[Union@@m]}]], First[SortBy[brute[m, 1], fbi[fbi/@#]&]]];
brute[m_, 1]:=Table[Sort[Sort/@(m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}];
Select[Range[0, 100], Sort[bpe/@bpe[#]]==biinorm[bpe/@bpe[#]]&]
|
|
CROSSREFS
|
Equals the image/fixed points of the idempotent sequence A330195.
Unlabeled covering set-systems counted by vertices are A055621.
Unlabeled set-systems counted by weight are A283877.
Other fixed points:
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|