Search: keyword:new
|
| |
|
|
A368411
|
|
Number of non-isomorphic connected multiset partitions of weight n contradicting a strict version of the axiom of choice.
|
|
+0
0
|
|
|
|
0, 0, 1, 2, 6, 15, 50, 148, 509, 1725, 6218
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Non-isomorphic representatives of the a(2) = 1 through a(5) = 15 multiset partitions:
{{1},{1}} {{1},{1,1}} {{1},{1,1,1}} {{1},{1,1,1,1}}
{{1},{1},{1}} {{1,1},{1,1}} {{1,1},{1,1,1}}
{{1},{1},{1,1}} {{1},{1},{1,1,1}}
{{1},{2},{1,2}} {{1},{1,1},{1,1}}
{{2},{2},{1,2}} {{1},{1},{1,2,2}}
{{1},{1},{1},{1}} {{1},{1,2},{2,2}}
{{1},{2},{1,2,2}}
{{2},{1,2},{1,2}}
{{2},{1,2},{2,2}}
{{2},{2},{1,2,2}}
{{3},{3},{1,2,3}}
{{1},{1},{1},{1,1}}
{{1},{2},{2},{1,2}}
{{2},{2},{2},{1,2}}
{{1},{1},{1},{1},{1}}
|
|
|
MATHEMATICA
|
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]& /@ sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]], {s, Flatten[MapIndexed[Table[#2, {#1}]&, #]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}], Length[Intersection@@s[[#]]]>0&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List /@ c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[brute /@ Select[mpm[n], Length[csm[#]]==1&&Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 6}]
|
|
|
CROSSREFS
|
The complement for labeled graphs is A129271, connected case of A133686.
This is the connected case of A368097.
|
|
|
KEYWORD
|
nonn,more,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A368400
|
|
Irregular triangle read by rows: T(n,k) is the position of k within the Christmas tree pattern (A367562) of order n, with n >= 1 and k >= 0.
|
|
+0
0
|
|
|
|
1, 2, 2, 3, 1, 4, 5, 6, 3, 7, 1, 2, 4, 8, 12, 13, 9, 14, 6, 7, 10, 15, 2, 3, 1, 4, 5, 8, 11, 16, 27, 28, 23, 29, 19, 20, 24, 30, 13, 14, 11, 15, 17, 21, 25, 31, 5, 6, 3, 7, 1, 2, 4, 8, 9, 10, 12, 16, 18, 22, 26, 32, 58, 59, 53, 60, 48, 49, 54, 61, 40, 41, 37, 42, 45
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Row n is a permutation of the integers in the interval [1, 2^n].
See A367508 for the description of the Christmas tree patterns, references and links.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Triangle begins:
.
n\k| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
--------------------------------------------------------
1 | 1 2
2 | 2 3 1 4
3 | 5 6 3 7 1 2 4 8
4 | 12 13 9 14 6 7 10 15 2 3 1 4 5 8 11 16
...
For example, the order 3 of the Christmas tree pattern is the following (binary on the left, converted to decimal in the middle, position within the pattern on the right):
.
100 101 | 4 5 | 1 2
010 110 | 2 6 | 3 4
000 001 011 111 | 0 1 3 7 | 5 6 7 8
.
The position of the elements within the pattern is therefore the following:
.
Element: 0 1 2 3 4 5 6 7
| | | | | | | |
V V V V V V V V
Position: 5 6 3 7 1 2 4 8
.
|
|
|
MATHEMATICA
|
A367562list[imax_]:=Map[FromDigits[#, 2]&, NestList[Map[Delete[{If[Length[#]>1, Map[#<>"0"&, Rest[#]], Nothing], Join[{#[[1]]<>"0"}, Map[#<>"1"&, #]]}, 0]&], {{"0", "1"}}, imax-1], {3}];
With[{nmax=6}, Map[Flatten[Values[KeySort[PositionIndex[Flatten[#]]]]]&, A367562list[nmax]]]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base,tabf,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A368399
|
|
Irregular triangle read by rows: row n lists the indices of rows of the Christmas tree pattern (A367508) of order n, sorted by row length and, in case of ties, by row index.
|
|
+0
0
|
|
|
|
1, 1, 2, 1, 2, 3, 1, 3, 2, 4, 5, 6, 1, 2, 4, 5, 7, 3, 6, 8, 9, 10, 1, 3, 7, 9, 13, 2, 4, 5, 8, 10, 11, 14, 15, 17, 6, 12, 16, 18, 19, 20, 1, 2, 4, 5, 7, 11, 12, 14, 15, 17, 21, 22, 24, 28, 3, 6, 8, 9, 13, 16, 18, 19, 23, 25, 26, 29, 30, 32, 10, 20, 27, 31, 33, 34, 35
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
Row n is a permutation of the integers in the interval [1, binomial(n,floor(n/2))].
See A367508 for the description of the Christmas tree patterns, references and links.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Triangle begins (vertical bars separate indices of rows having different lengths):
.
[1] 1;
[2] 1| 2;
[3] 1 2| 3;
[4] 1 3| 2 4 5| 6;
[5] 1 2 4 5 7| 3 6 8 9|10;
[6] 1 3 7 9 13| 2 4 5 8 10 11 14 15 17| 6 12 16 18 19|20;
...
For example, the order 4 of the Christmas tree pattern is the following:
.
1010 Row 1 length = 1
1000 1001 1011 Row 2 length = 3
1100 Row 3 length = 1
0100 0101 1101 Row 4 length = 3
0010 0110 1110 Row 5 length = 3
0000 0001 0011 0111 1111 Row 6 length = 5
.
and ordering the rows by length (and then by row index) gives 1, 3, 2, 4, 5, 6.
|
|
|
MATHEMATICA
|
With[{nmax=8}, Map[Flatten[Values[PositionIndex[#]]]&, SubstitutionSystem[{1->{2}, t_/; t>1->{t-1, t+1}}, {2}, nmax-1]]]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
| |
|
|
|
1, 0, 0, 1, 4, 17, 68, 267, 1041, 4049, 15739, 61194, 238081, 927071, 3613362, 14097113, 55050810, 215178232, 841813885, 3296075636, 12915801131, 50648751006, 198756000104, 780472848048, 3066651564995, 12056585499217, 47426685674204, 186657789816391, 734990466616069
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
MATHEMATICA
|
With[{nmax=30}, Diagonal[NestList[Accumulate, MoebiusMu[Range[nmax]], nmax-1]]]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A368465
|
|
Number of even terms in each row of the iterates of the Christmas tree pattern map (A367508).
|
|
+0
0
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 2, 1, 4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 3, 1, 5, 1, 1, 2, 1, 1, 2, 1, 2, 1, 4, 1, 1, 2, 1, 1, 2, 1, 2, 1, 4, 1, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 4, 1, 6, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
See A367508 for the description of the Christmas tree patterns, references and links.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The first 4 tree pattern orders are shown below (left), with the corresponding number of even terms on the right.
.
Order 1: |
0 1 | 1
|
Order 2: |
10 | 1
00 01 11 | 1
|
Order 3: |
100 101 | 1
010 110 | 2
000 001 011 111 | 1
|
Order 4: |
1010 | 1
1000 1001 1011 | 1
1100 | 1
0100 0101 1101 | 1
0010 0110 1110 | 3
0000 0001 0011 0111 1111 | 1
.
|
|
|
MATHEMATICA
|
With[{imax=8}, Map[Total, Map[Mod[FromDigits[#]+1, 2]&, NestList[Map[Delete[{If[Length[#]>1, Map[#<>"0"&, Rest[#]], Nothing], Join[{#[[1]]<>"0"}, Map[#<>"1"&, #]]}, 0]&], {{"0", "1"}}, imax-1], {3}], {2}]] (* Generates terms up to order 8 *)
|
|
|
PROG
|
(Python)
from itertools import islice
from functools import reduce
def uniq(r): return reduce(lambda u, e: u if e in u else u+[e], r, [])
def agen(): # generator of terms
R = [["0", "1"]]
while R:
r = R.pop(0)
yield sum(b[-1] == '0' for b in r)
if len(r) > 1: R.append(uniq([r[k]+"0" for k in range(1, len(r))]))
R.append(uniq([r[0]+"0", r[0]+"1"] + [r[k]+"1" for k in range(1, len(r))]))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A368463
|
|
Parity of the iterates of the Christmas tree pattern map (A367508), read by rows.
|
|
+0
0
|
|
|
|
0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1
|
|
|
COMMENTS
|
See A367508 for the description of the Christmas tree patterns, references and links.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
MAPLE
|
The first 4 tree pattern orders are shown below (left), with the corresponding parity on the right.
.
Order 1: |
0 1 | 0 1
|
Order 2: |
10 | 0
00 01 11 | 0 1 1
|
Order 3: |
100 101 | 0 1
010 110 | 0 0
000 001 011 111 | 0 1 1 1
|
Order 4: |
1010 | 0
1000 1001 1011 | 0 1 1
1100 | 0
0100 0101 1101 | 0 1 1
0010 0110 1110 | 0 0 0
0000 0001 0011 0111 1111 | 0 1 1 1 1
.
|
|
|
MATHEMATICA
|
With[{imax=6}, Map[Mod[FromDigits[#], 2]&, NestList[Map[Delete[{If[Length[#]>1, Map[#<>"0"&, Rest[#]], Nothing], Join[{#[[1]]<>"0"}, Map[#<>"1"&, #]]}, 0]&], {{"0", "1"}}, imax-1], {3}]] (* Generates terms up to order 6 *)
|
|
|
PROG
|
(Python)
from itertools import islice
from functools import reduce
def uniq(r): return reduce(lambda u, e: u if e in u else u+[e], r, [])
def agen(): # generator of terms
R = [["0", "1"]]
while R:
r = R.pop(0)
yield from map(lambda b: int(b[-1]), r)
if len(r) > 1: R.append(uniq([r[k]+"0" for k in range(1, len(r))]))
R.append(uniq([r[0]+"0", r[0]+"1"] + [r[k]+"1" for k in range(1, len(r))]))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A368464
|
|
Number of odd terms in each row of the iterates of the Christmas tree pattern map (A367508).
|
|
+0
0
|
|
|
|
1, 0, 2, 1, 0, 3, 0, 2, 0, 2, 0, 4, 1, 0, 3, 1, 0, 3, 0, 3, 0, 5, 0, 2, 0, 2, 0, 4, 0, 2, 0, 2, 0, 4, 0, 2, 0, 4, 0, 4, 0, 6, 1, 0, 3, 1, 0, 3, 0, 3, 0, 5, 1, 0, 3, 1, 0, 3, 0, 3, 0, 5, 1, 0, 3, 0, 3, 0, 5, 0, 3, 0, 5, 0, 5, 0, 7, 0, 2, 0, 2, 0, 4, 0, 2, 0, 2, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
See A367508 for the description of the Christmas tree patterns, references and links.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The first 4 tree pattern orders are shown below (left), with the corresponding number of odd terms on the right.
.
Order 1: |
0 1 | 1
|
Order 2: |
10 | 0
00 01 11 | 2
|
Order 3: |
100 101 | 1
010 110 | 0
000 001 011 111 | 3
|
Order 4: |
1010 | 0
1000 1001 1011 | 2
1100 | 0
0100 0101 1101 | 2
0010 0110 1110 | 0
0000 0001 0011 0111 1111 | 4
.
Apparently, removing the 0 terms from the order i pattern (for i >= 2), gives the row lengths of the order i-1 pattern (cf. A363718).
|
|
|
MATHEMATICA
|
With[{imax=8}, Map[Total, Map[Mod[FromDigits[#], 2]&, NestList[Map[Delete[{If[Length[#]>1, Map[#<>"0"&, Rest[#]], Nothing], Join[{#[[1]]<>"0"}, Map[#<>"1"&, #]]}, 0]&], {{"0", "1"}}, imax-1], {3}], {2}]] (* Generates terms up to order 8 *)
|
|
|
PROG
|
(Python)
from itertools import islice
from functools import reduce
def uniq(r): return reduce(lambda u, e: u if e in u else u+[e], r, [])
def agen(): # generator of terms
R = [["0", "1"]]
while R:
r = R.pop(0)
yield sum(1 for b in r if b[-1] == '1')
if len(r) > 1: R.append(uniq([r[k]+"0" for k in range(1, len(r))]))
R.append(uniq([r[0]+"0", r[0]+"1"] + [r[k]+"1" for k in range(1, len(r))]))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A368398
|
|
Iterates of the Christmas tree pattern map (A367508), where each row is interpreted as a single word and converted to decimal.
|
|
+0
0
|
|
|
|
1, 2, 7, 37, 22, 95, 10, 2203, 12, 1117, 622, 4991, 661, 598, 542327, 793, 346, 271739, 412, 136637, 72158, 1154559, 42, 166507, 44, 149869, 141742, 545667567, 50, 199795, 52, 83317, 75190, 272971255, 56, 99961, 42682, 136623867, 51004, 68474749, 35186622, 1125971967
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
See A367508 for the description of the Christmas tree patterns, references and links.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The first 4 tree pattern orders of A367508 are shown below (left). In the middle the elements of each row are joined into single words; decimal conversion is on the right.
.
Order 1: | |
0 1 | 01 | 1
| |
Order 2: | |
10 | 10 | 2
00 01 11 | 000111 | 7
| |
Order 3: | |
100 101 | 100101 | 37
010 110 | 010110 | 22
000 001 011 111 | 000001011111 | 95
| |
Order 4: | |
1010 | 1010 | 10
1000 1001 1011 | 100010011011 | 2203
1100 | 1100 | 12
0100 0101 1101 | 010001011101 | 1117
0010 0110 1110 | 001001101110 | 622
0000 0001 0011 0111 1111 | 00000001001101111111 | 4991
.
|
|
|
MATHEMATICA
|
With[{imax=7}, Map[FromDigits[StringJoin[#], 2]&, NestList[Map[Delete[{If[Length[#]>1, Map[#<>"0"&, Rest[#]], Nothing], Join[{#[[1]]<>"0"}, Map[#<>"1"&, #]]}, 0]&], {{"0", "1"}}, imax-1], {2}]] (* Generates terms up to order 7 *)
|
|
|
PROG
|
(Python)
from itertools import islice
from functools import reduce
def uniq(r): return reduce(lambda u, e: u if e in u else u+[e], r, [])
def agen(): # generator of terms
R = [["0", "1"]]
while R:
r = R.pop(0)
yield int("".join(r), 2)
if len(r) > 1: R.append(uniq([r[k]+"0" for k in range(1, len(r))]))
R.append(uniq([r[0]+"0", r[0]+"1"] + [r[k]+"1" for k in range(1, len(r))]))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A368461
|
|
a(n) is the number of unlabeled planar modular lattices on n nodes.
|
|
+0
0
|
|
|
|
1, 1, 1, 2, 4, 8, 16, 33, 70, 151, 329, 723, 1601, 3569, 8000, 18015, 40723, 92351, 209997, 478598, 1092856, 2499567, 5724970, 13128115, 30135636, 69238343, 159202607, 366308948, 843338278, 1942591448, 4476714720, 10320774953, 23802355725, 54911686727
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
LINKS
|
|
|
|
CROSSREFS
|
Cf. A006981 (modular lattices), A343161 (planar distributive lattices).
|
|
|
KEYWORD
|
nonn,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A368095
|
|
Number of non-isomorphic set-systems of weight n satisfying a strict version of the axiom of choice.
|
|
+0
1
|
|
|
|
1, 1, 2, 4, 8, 17, 39, 86, 208, 508, 1304
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements.
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Non-isomorphic representatives of the a(1) = 1 through a(5) = 17 set-systems:
{1} {12} {123} {1234} {12345}
{1}{2} {1}{23} {1}{234} {1}{2345}
{2}{12} {12}{34} {12}{345}
{1}{2}{3} {13}{23} {14}{234}
{3}{123} {23}{123}
{1}{2}{34} {4}{1234}
{1}{3}{23} {1}{2}{345}
{1}{2}{3}{4} {1}{23}{45}
{1}{24}{34}
{1}{4}{234}
{2}{13}{23}
{2}{3}{123}
{3}{13}{23}
{4}{12}{34}
{1}{2}{3}{45}
{1}{2}{4}{34}
{1}{2}{3}{4}{5}
|
|
|
MATHEMATICA
|
Table[Length[Select[bmp[n], UnsameQ@@#&&And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]!={}&]], {n, 0, 10}]
|
|
|
CROSSREFS
|
Minimal multiset partitions not of this type are counted by A368187.
Factorizations of this type are counted by A368414, complement A368413.
Cf. A001055, A007717, A302545, A306005, A316983, A319560, A321194, A321405, A330223, A367769, A367901.
|
|
|
KEYWORD
|
nonn,more,new
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.127 seconds
|
