Displaying 81-90 of 205 results found.
page
1
...
5
6
7
8
9
10
11
12
13
14
15
... 21
Number of non-isomorphic set-systems covering n vertices with at least one endpoint/leaf.
+10
11
COMMENTS
A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.
Also covering set-systems with minimum vertex-degree 1.
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(3) = 14 set-systems:
{{1}} {{1,2}} {{1,2,3}}
{{1},{2}} {{1},{2,3}}
{{2},{1,2}} {{1},{2},{3}}
{{1,3},{2,3}}
{{3},{1,2,3}}
{{1},{3},{2,3}}
{{2,3},{1,2,3}}
{{2},{1,3},{2,3}}
{{2},{3},{1,2,3}}
{{3},{1,3},{2,3}}
{{1},{2},{3},{2,3}}
{{3},{2,3},{1,2,3}}
{{2},{3},{1,3},{2,3}}
{{2},{3},{2,3},{1,2,3}}
CROSSREFS
Unlabeled covering set-systems are A055621. The non-covering version is A327335 (partial sums).
Number of non-isomorphic set-systems of weight n with no singletons or endpoints.
+10
11
1, 0, 0, 0, 0, 0, 1, 1, 3, 5, 16, 24, 90, 179, 567, 1475, 4623, 13650, 44475, 144110, 492017, 1706956, 6124330, 22442687, 84406276, 324298231, 1273955153, 5106977701, 20885538133, 87046940269, 369534837538, 1596793560371, 7019424870960, 31374394197536, 142514998263015
COMMENTS
A set-system is a finite set of finite nonempty set of positive integers. A singleton is an edge of size 1. An endpoint is a vertex appearing only once (degree 1). The weight of a set-system is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
EXAMPLE
Non-isomorphic representatives of the a(7) = 1 through a(10) = 16 set-systems:
{12}{13}{123} {12}{134}{234} {12}{134}{1234} {12}{1345}{2345}
{12}{34}{1234} {123}{124}{134} {123}{124}{1234}
{12}{13}{24}{34} {12}{13}{14}{234} {123}{145}{2345}
{12}{13}{23}{123} {12}{345}{12345}
{12}{13}{24}{134} {12}{13}{124}{134}
{12}{13}{124}{234}
{12}{13}{14}{1234}
{12}{13}{24}{1234}
{12}{13}{245}{345}
{12}{13}{45}{2345}
{12}{34}{123}{124}
{12}{34}{125}{345}
{12}{34}{135}{245}
{13}{24}{123}{124}
{12}{13}{14}{23}{24}
{12}{13}{24}{35}{45}
PROG
(PARI)
WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={my(g=x*Ser(WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k)))); (1-x)*g-subst(g, x, x^2)}
S(q, t, k)={(x-x^2)*sum(j=1, #q, if(t%q[j]==0, q[j])) + O(x*x^k)}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(sum(t=1, n, subst(K(q, t, n\t)-S(q, t, n\t), x, x^t)/t )), n)); s/n!)} \\ Andrew Howroyd, Jan 27 2024
CROSSREFS
Non-isomorphic set-systems with no singletons are A306005. Non-isomorphic set-systems with no endpoints are A330054. Non-isomorphic set-systems counted by vertices are A000612. Non-isomorphic set-systems counted by weight are A283877.
BII-number of the VDD-normalization of the set-system with BII-number n.
+10
11
0, 1, 1, 3, 4, 5, 5, 7, 1, 3, 3, 11, 33, 19, 19, 15, 4, 5, 33, 19, 20, 21, 37, 23, 5, 7, 19, 15, 37, 23, 51, 31, 4, 33, 5, 19, 20, 37, 21, 23, 5, 19, 7, 15, 37, 51, 23, 31, 20, 37, 37, 51, 52, 53, 53, 55, 21, 23, 23, 31, 53, 55, 55, 63, 64, 65, 65, 67, 68, 69, 69
COMMENTS
First differs from A330101 at a(148) = 274, A330101(148) = 545, with corresponding set-systems 274: {{2},{1,3},{1,4}} and 545: {{1},{2,3},{2,4}}. A set-system is a finite set of finite nonempty sets of positive integers.
We define the VDD (vertex-degrees decreasing) 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, then selecting only the representatives whose vertex-degrees are weakly decreasing, and finally taking the least of these representatives, where the ordering of sets is first by length and then lexicographically.
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}}
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.
EXAMPLE
56 is the BII-number of {{3},{1,3},{2,3}}, which has VDD-normalization {{1},{1,2},{1,3}} with BII-number 21, so a(56) = 21.
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
fbi[q_]:=If[q=={}, 0, Total[2^q]/2];
sysnorm[m_]:=If[Union@@m!={}&&Union@@m!=Range[Max@@Flatten[m]], sysnorm[m/.Rule@@@Table[{(Union@@m)[[i]], i}, {i, Length[Union@@m]}]], First[Sort[sysnorm[m, 1]]]];
sysnorm[m_, aft_]:=If[Length[Union@@m]<=aft, {m}, With[{mx=Table[Count[m, i, {2}], {i, Select[Union@@m, #>=aft&]}]}, Union@@(sysnorm[#, aft+1]&/@Union[Table[Map[Sort, m/.{par+aft-1->aft, aft->par+aft-1}, {0, 1}], {par, First/@Position[mx, Max[mx]]}]])]];
Table[fbi[fbi/@sysnorm[bpe/@bpe[n]]], {n, 0, 100}]
CROSSREFS
This sequence is idempotent and its image/fixed points are A330100. Non-isomorphic multiset partitions are A007716. Unlabeled spanning set-systems counted by vertices are A055621. Unlabeled set-systems counted by weight are A283877. Cf. A000120, A000612, A048793, A070939, A300913, A319559, A321405, A326031, A326754, A330061, A330101. Other fixed points:
a(n) is the number of set-systems using nonempty subsets of {1,...,n} in which all sets have the same size.
+10
10
1, 2, 5, 16, 95, 2110, 1114237, 68723671292, 1180735735906024030715, 170141183460507917357914971986913657850, 7237005577335553223087828975127304179197147198604070555943173844710572689401
FORMULA
a(n) = 1 - n + Sum_{d = 1..n} 2^binomial(n, d).
EXAMPLE
a(3) = 16 set-systems in which all sets have the same size:
{}
{{1}}
{{2}}
{{3}}
{{1,2}}
{{1,3}}
{{2,3}}
{{1,2,3}}
{{1},{2}}
{{1},{3}}
{{2},{3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1},{2},{3}}
{{1,2},{1,3},{2,3}}
MAPLE
a := n -> 1-n+add(2^binomial(n, d), d = 1 .. n):
MATHEMATICA
Table[1+Sum[2^Binomial[n, d]-1, {d, n}], {n, 10}]
PROG
(PARI) a(n) = 1 - n + sum(d = 1, n, 2^binomial(n, d)); \\ Michel Marcus, Aug 10 2023
CROSSREFS
Cf. A000005, A001315, A007716, A038041, A049311, A058673 (labeled matroids), A283877, A298422, A306017, A306018, A306019, A306021.
Number of non-isomorphic strict multiset partitions (sets of multisets) of weight n with empty intersection.
+10
10
1, 0, 1, 3, 12, 37, 130, 428, 1481, 5091, 17979, 64176, 234311, 869645, 3295100, 12720494, 50083996, 200964437, 821845766, 3423694821, 14524845181, 62725701708, 275629610199, 1231863834775, 5597240308384, 25844969339979, 121224757935416, 577359833539428, 2791096628891679
COMMENTS
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
EXAMPLE
Non-isomorphic representatives of the a(2) = 1 through a(4) = 12 strict multiset partitions with empty intersection:
2: {{1},{2}}
3: {{1},{2,2}}
{{1},{2,3}}
{{1},{2},{3}}
4: {{1},{2,2,2}}
{{1},{2,3,3}}
{{1},{2,3,4}}
{{1,1},{2,2}}
{{1,2},{3,3}}
{{1,2},{3,4}}
{{1},{2},{1,2}}
{{1},{2},{2,2}}
{{1},{2},{3,3}}
{{1},{2},{3,4}}
{{1},{3},{2,3}}
{{1},{2},{3},{4}}
PROG
(PARI)
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={EulerT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
R(q, n)={vector(n, t, subst(x*Ser(K(q, t, n\t)/t), x, x^t))}
a(n)={my(s=0); forpart(q=n, my(f=prod(i=1, #q, 1 - x^q[i]), u=R(q, n)); s+=permcount(q)*sum(k=0, n, my(c=polcoef(f, k)); if(c, c*polcoef(exp(sum(t=1, n\(k+1), x^(t*k)*u[t] - subst(x^(t*k)*u[t] + O(x*x^(n\2)), x, x^2), O(x*x^n) ))*if(k, 1+x^k, 1), n))) ); s/n!} \\ Andrew Howroyd, May 30 2023
Number of antichain covers of n vertices by distinct sets whose dual is also an antichain of distinct sets.
+10
10
COMMENTS
The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
EXAMPLE
The a(1) = 1 through a(3) = 2 antichain covers:
1: {{1}}
2: {{1},{2}}
3: {{1},{2},{3}}
{{1,2},{1,3},{2,3}}
CROSSREFS
Cf. A006126, A007716, A049311, A059201, A283877, A293606, A316980, A316983, A318099, A319558, A319616- A319646, A300913.
Number of non-isomorphic set-systems of weight n with at least one endpoint.
+10
10
0, 1, 2, 4, 8, 18, 40, 94, 228, 579, 1508, 4092, 11478, 33337, 100016, 309916, 990008, 3257196, 11021851, 38314009, 136657181, 499570867, 1869792499, 7158070137, 28003286261, 111857491266, 455852284867, 1893959499405, 8017007560487, 34552315237016, 151534813272661
COMMENTS
A set-system is a finite set of finite nonempty sets of positive integers. An endpoint is a vertex appearing only once (degree 1). The weight of a set-system is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(5) = 18 multiset partitions:
{1} {12} {123} {1234} {12345}
{1}{2} {1}{12} {1}{123} {1}{1234}
{1}{23} {12}{13} {12}{123}
{1}{2}{3} {1}{234} {12}{134}
{12}{34} {1}{2345}
{1}{2}{13} {12}{345}
{1}{2}{34} {1}{12}{13}
{1}{2}{3}{4} {1}{12}{23}
{1}{12}{34}
{1}{2}{123}
{1}{2}{134}
{1}{2}{345}
{1}{23}{45}
{2}{13}{14}
{1}{2}{3}{12}
{1}{2}{3}{14}
{1}{2}{3}{45}
{1}{2}{3}{4}{5}
MATHEMATICA
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
brute[{}]:={}; brute[m_]:=If[Union@@m!={}&&Union@@m!=Range[Max@@Flatten[m]], brute[m/.Rule@@@Table[{(Union@@m)[[i]], i}, {i, Length[Union@@m]}]], First[Sort[brute[m, 1]]]]; brute[m_, 1]:=Table[Sort[Sort/@(m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}];
Table[Length[Select[Union[brute/@Join@@mps/@strnorm[n]], UnsameQ@@#&&And@@UnsameQ@@@#&&Min@@Length/@Split[Sort[Join@@#]]==1&]], {n, 0, 5}]
CROSSREFS
The complement is counted by A330054. The multiset partition version is A330058. Non-isomorphic set-systems with at least one singleton are A330053. Non-isomorphic set-systems counted by vertices are A000612. Non-isomorphic set-systems counted by weight are A283877.
Number of non-isomorphic set-systems of weight n with no endpoints.
+10
10
1, 0, 0, 0, 1, 0, 4, 4, 16, 26, 87, 181, 570, 1453, 4464, 13038, 41548, 132217, 442603, 1506803, 5305174, 19092816, 70548770, 266495254, 1029835424, 4063610148, 16366919221, 67217627966, 281326631801, 1199048810660, 5201341196693, 22950740113039, 102957953031700
COMMENTS
A set-system is a finite set of finite nonempty set of positive integers. An endpoint is a vertex appearing only once (degree 1). The weight of a set-system is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
EXAMPLE
Non-isomorphic representatives of the a(0) = 1 through a(8) = 16 multiset partitions (empty columns not shown):
0 {1}{2}{12} {12}{13}{23} {13}{23}{123} {12}{134}{234}
{1}{23}{123} {1}{3}{23}{123} {1}{234}{1234}
{1}{2}{13}{23} {3}{12}{13}{23} {12}{34}{1234}
{1}{2}{3}{123} {1}{2}{3}{13}{23} {1}{12}{34}{234}
{12}{13}{24}{34}
{1}{2}{134}{234}
{1}{2}{34}{1234}
{2}{13}{14}{234}
{2}{13}{23}{123}
{3}{13}{23}{123}
{1}{2}{13}{24}{34}
{1}{2}{3}{14}{234}
{1}{2}{3}{23}{123}
{1}{2}{3}{4}{1234}
{2}{3}{12}{13}{23}
{1}{2}{3}{4}{12}{34}
PROG
(PARI)
WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={my(g=1+x*Ser(WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k)))); (1-x)*g - subst(g, x, x^2)}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(sum(t=1, n, subst(K(q, t, n\t)/t, x, x^t) )), n)); s/n!)} \\ Andrew Howroyd, Jan 27 2024
CROSSREFS
The complement is counted by A330052. The multiset partition version is A302545. Non-isomorphic set-systems with no singletons are A306005. Non-isomorphic set-systems counted by vertices are A000612. Non-isomorphic set-systems counted by weight are A283877.
Number of set partitions of set-systems with total sum n.
+10
10
1, 1, 1, 4, 6, 11, 26, 42, 78, 148, 280, 481, 867, 1569, 2742, 4933, 8493, 14857, 25925, 44877, 77022, 132511, 226449, 385396, 657314, 1111115, 1875708, 3157379, 5309439, 8885889, 14861478, 24760339, 41162971, 68328959, 113099231, 186926116, 308230044
COMMENTS
Number of sets of disjoint nonempty sets of nonempty sets of positive integers with total sum n.
EXAMPLE
The a(6) = 26 partitions:
((6)) ((15)) ((123)) ((1)(2)(12))
((24)) ((1)(14)) ((1))((2)(12))
((1)(5)) ((1)(23)) ((12))((1)(2))
((2)(4)) ((2)(13)) ((2))((1)(12))
((1))((5)) ((3)(12)) ((1))((2))((12))
((2))((4)) ((1))((14))
((1))((23))
((1)(2)(3))
((2))((13))
((3))((12))
((1))((2)(3))
((2))((1)(3))
((3))((1)(2))
((1))((2))((3))
MATHEMATICA
ppl[n_, k_]:=Switch[k, 0, {n}, 1, IntegerPartitions[n], _, Join@@Table[Union[Sort/@Tuples[ppl[#, k-1]&/@ptn]], {ptn, IntegerPartitions[n]}]];
Table[Length[Select[ppl[n, 3], And[UnsameQ@@Join@@#, And@@UnsameQ@@@Join@@#]&]], {n, 0, 10}]
PROG
L(n)={eta(x^2 + O(x*x^n))/eta(x + O(x*x^n))}
BellP(n)={serlaplace(exp( exp(x + O(x*x^n)) - 1))}
seq(n)={my(c=L(n), b=BellP(n), v=Vec(prod(k=1, n, (1 + x^k*y + O(x*x^n))^polcoef(c, k)))); vector(#v, n, my(r=v[n]); sum(k=0, n-1, polcoeff(b, k)*polcoef(r, k)))} \\ Andrew Howroyd, Dec 29 2019
CROSSREFS
Cf. A007713, A050342, A050343, A279375, A279785, A283877, A294617, A330460, A330462, A323787- A323795, A330452- A330459.
Number of non-isomorphic set multipartitions of weight n satisfying a strict version of the axiom of choice.
+10
10
1, 1, 2, 4, 9, 18, 43, 95, 233, 569
COMMENTS
A set multipartition is a finite multiset of finite nonempty sets. The weight of a set multipartition 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 sequence of nonempty sets, it is possible to choose a sequence containing an element from each. In the strict version, the elements of this sequence must be distinct, meaning none is chosen more than once.
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(5) = 18 set multipartitions:
{{1}} {{1,2}} {{1,2,3}} {{1,2,3,4}} {{1,2,3,4,5}}
{{1},{2}} {{1},{2,3}} {{1,2},{1,2}} {{1},{2,3,4,5}}
{{2},{1,2}} {{1},{2,3,4}} {{1,2},{3,4,5}}
{{1},{2},{3}} {{1,2},{3,4}} {{1,4},{2,3,4}}
{{1,3},{2,3}} {{2,3},{1,2,3}}
{{3},{1,2,3}} {{4},{1,2,3,4}}
{{1},{2},{3,4}} {{1},{2,3},{2,3}}
{{1},{3},{2,3}} {{1},{2},{3,4,5}}
{{1},{2},{3},{4}} {{1},{2,3},{4,5}}
{{1},{2,4},{3,4}}
{{1},{4},{2,3,4}}
{{2},{1,3},{2,3}}
{{2},{3},{1,2,3}}
{{3},{1,3},{2,3}}
{{4},{1,2},{3,4}}
{{1},{2},{3},{4,5}}
{{1},{2},{4},{3,4}}
{{1},{2},{3},{4},{5}}
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]}]]];
Table[Length[Union[brute /@ Select[mpm[n], And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]!={}&]]], {n, 0, 6}]
CROSSREFS
Factorizations of this type are counted by A368414, complement A368413. The complement is counted by A368421.
Search completed in 0.081 seconds
| 