Displaying 1-10 of 13 results found.
Number of labeled antichains of finite sets spanning n vertices without singletons.
+0
23
1, 0, 1, 5, 87, 6398, 7745253, 2414573042063, 56130437190053518791691, 286386577668298410118121281898931424413687
COMMENTS
Also the number of antichains covering n vertices and having empty intersection (meaning there is no vertex in common to all the edges). For example, the a(3) = 5 antichains are:
{{3},{1,2}}
{{2},{1,3}}
{{1},{2,3}}
{{1},{2},{3}}
{{1,2},{1,3},{2,3}}
(End)
EXAMPLE
The a(3) = 5 antichains:
{{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
Table[Length[Select[stableSets[Subsets[Range[n], {1, n}], SubsetQ], And[Union@@#==Range[n], #=={}||Intersection@@#=={}]&]], {n, 0, 5}] (* Gus Wiseman, Jul 03 2019 *)
CROSSREFS
The binomial transform is the non-covering case A307249. The second binomial transform is A014466. Cf. A000372, A003182, A006126, A006602, A046165, A261005, A304996, A304997, A304998, A304999, A305000, A326358, A326359.
Number of minimal covers of n objects.
+0
21
1, 1, 2, 8, 49, 462, 6424, 129425, 3731508, 152424420, 8780782707, 710389021036, 80610570275140, 12815915627480695, 2855758994821922882, 892194474524889501292, 391202163933291014701953, 240943718535427829240708786, 208683398342300491409959279244
COMMENTS
No edge of a minimal cover can be a subset of any other, so minimal covers are antichains, but the converse is not true. - Gus Wiseman, Jul 03 2019 a(n) is the number of undirected graphs on n nodes for which the intersection number and independence number are equal. See Proposition 2.3.7 and Theorem 2.3.3 of the Deligeorgaki et al. paper below. - Alex Markham, Oct 13 2022
FORMULA
E.g.f.: Sum_{n>=0} (exp(x)-1)^n*exp(x*(2^n-n-1))/n!. - Vladeta Jovovic, May 08 2004 a(n) = Sum_{k=1..n} Sum_{i=k..n} C(n,i)*Stirling2(i,k)*(2^k - k - 1)^(n - i). - Geoffrey Critzer, Jun 27 2013 a(n) ~ c * 2^(n^2/4 + n + 1/2) / sqrt(Pi*n), where c = JacobiTheta3(0,1/2) = EllipticTheta[3, 0, 1/2] = 2.1289368272118771586694585485449... if n is even, and c = JacobiTheta2(0,1/2) = EllipticTheta[2, 0, 1/2] = 2.1289312505130275585916134025753... if n is odd. - Vaclav Kotesovec, Mar 10 2014
EXAMPLE
The a(1) = 1 through a(3) = 8 minimal covers:
{{1}} {{1,2}} {{1,2,3}}
{{1},{2}} {{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1},{2},{3}}
{{1,3},{2,3}}
(End)
MAPLE
a:= n-> add(add((-1)^i* binomial(k, i) *(2^k-1-i)^n, i=0..k)/k!, k=0..n):
MATHEMATICA
Table[Sum[Sum[Binomial[n, i]StirlingS2[i, k](2^k-k-1)^(n-i), {i, k, n}], {k, 2, n}]+1, {n, 1, 20}] (* Geoffrey Critzer, Jun 27 2013 *)
CROSSREFS
Minimal covering simple graphs are A053530.
Number of maximal antichains of subsets of {1..n}.
+0
18
1, 2, 3, 7, 29, 376, 31746, 123805914
COMMENTS
A set system (set of sets) is an antichain if no element is a subset of any other.
EXAMPLE
The a(0) = 1 through a(3) = 7 maximal antichains:
{} {} {} {}
{1} {12} {123}
{1}{2} {1}{23}
{2}{13}
{3}{12}
{1}{2}{3}
{12}{13}{23}
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n]], SubsetQ]]], {n, 0, 5}]
(* alternatively *)
maxachP[n_]:=FindIndependentVertexSet[
Flatten[Map[Function[s, Map[# \[DirectedEdge] s &, Most[Subsets[s]]]],
Subsets[Range[n]]]], Infinity, All];
PROG
(GAP) LoadPackage("grape");
maxachP:=function(n) local g, G;
g:=Graph(Group(()), Combinations([1..n]), function(x, g) return x; end,
function(x, y) return not IsSubset(x, y) and not IsSubset(y, x); end, true);
G:=AutGroupGraph(g);
return Sum(CompleteSubgraphs(NewGroupGraph(G, g), -1, 2),
function(c) return Length(Orbit(G, c, OnSets)); end);
end;
CROSSREFS
Minimal covering antichains are A046165. Maximal intersecting antichains are A007363. Maximal antichains of nonempty sets are A326359. Cf. A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305001, A305844, A326360, A326361, A326362, A326363.
Maximal self-dual antichains on n points.
(Formerly M2505)
+0
15
0, 1, 3, 5, 20, 168, 11748, 12160647
COMMENTS
If self-dual means (pairwise) intersecting, then a(n) is the number of maximal intersecting antichains of nonempty subsets of {1..(n - 1)}. A set of sets is an antichain if no part is a subset of any other, and is intersecting if no two parts are disjoint. For example, the a(2) = 1 through a(5) = 20 maximal intersecting antichains are:
{1} {1} {1} {1}
{2} {2} {2}
{12} {3} {3}
{123} {4}
{12}{13}{23} {1234}
{12}{13}{23}
{12}{14}{24}
{13}{14}{34}
{23}{24}{34}
{12}{134}{234}
{13}{124}{234}
{14}{123}{234}
{23}{124}{134}
{24}{123}{134}
{34}{123}{124}
{12}{13}{14}{234}
{12}{23}{24}{134}
{13}{23}{34}{124}
{14}{24}{34}{123}
{123}{124}{134}{234}
(End)
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n], {1, n}], Or[Intersection[#1, #2]=={}, SubsetQ[#1, #2]]&]]], {n, 0, 5}] (* Gus Wiseman, Jul 02 2019 *) (* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = FindClique[g, Infinity, All];
CROSSREFS
Intersecting antichains are A326372. Intersecting antichains of nonempty sets are A001206. Unlabeled intersecting antichains are A305857. Maximal antichains of nonempty sets are A326359. The case with empty edges allowed is A326363.
Number of nonempty pairwise coprime subsets of {1,...,n}, where a single number is not considered to be pairwise coprime unless it is equal to 1.
+0
15
1, 2, 5, 8, 19, 22, 49, 64, 95, 106, 221, 236, 483, 530, 601, 712, 1439, 1502, 3021, 3212, 3595, 3850, 7721, 7976, 11143, 11878, 14629, 15460, 30947, 31202, 62433, 69856, 76127, 80222, 89821, 91612, 183259, 192602, 208601, 214232, 428503, 431574, 863189
COMMENTS
Two or more numbers are pairwise coprime if no pair of them has a common divisor > 1.
EXAMPLE
The a(4) = 8 subsets of {1,2,3,4} are {1}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}. - Michael B. Porter, Jan 12 2019 The a(2) = 2 through a(6) = 22 sets:
{1} {1} {1} {1} {1}
{1,2} {1,2} {1,2} {1,2} {1,2}
{1,3} {1,3} {1,3} {1,3}
{2,3} {1,4} {1,4} {1,4}
{1,2,3} {2,3} {1,5} {1,5}
{3,4} {2,3} {1,6}
{1,2,3} {2,5} {2,3}
{1,3,4} {3,4} {2,5}
{3,5} {3,4}
{4,5} {3,5}
{1,2,3} {4,5}
{1,2,5} {5,6}
{1,3,4} {1,2,3}
{1,3,5} {1,2,5}
{1,4,5} {1,3,4}
{2,3,5} {1,3,5}
{3,4,5} {1,4,5}
{1,2,3,5} {1,5,6}
{1,3,4,5} {2,3,5}
{3,4,5}
{1,2,3,5}
{1,3,4,5}
(End)
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], CoprimeQ@@#&]], {n, 10}]
CROSSREFS
The case with singletons is A187106. The version without singletons (except {1}) is A276187. The version for divisors > 1 is A343654. The version for divisors without singletons is A343655. A018892 counts coprime unordered pairs of divisors.
A051026 counts pairwise indivisible subsets of {1...n}.
A087087 ranks pairwise coprime subsets of {1...n}.
A326675 ranks pairwise coprime non-singleton subsets of {1...n}.
Number of maximal intersecting antichains of subsets of {1..n}.
+0
15
1, 2, 4, 6, 21, 169, 11749, 12160648
COMMENTS
A set system (set of sets) is an antichain if no element is a subset of any other, and is intersecting if no two element are disjoint.
EXAMPLE
The a(1) = 1 through a(4) = 21 maximal intersecting antichains:
{} {} {} {}
{1} {1} {1} {1}
{2} {2} {2}
{12} {3} {3}
{123} {4}
{12}{13}{23} {1234}
{12}{13}{23}
{12}{14}{24}
{13}{14}{34}
{23}{24}{34}
{12}{134}{234}
{13}{124}{234}
{14}{123}{234}
{23}{124}{134}
{24}{123}{134}
{34}{123}{124}
{12}{13}{14}{234}
{12}{23}{24}{134}
{13}{23}{34}{124}
{14}{24}{34}{123}
{123}{124}{134}{234}
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n], {0, n}], Or[Intersection[#1, #2]=={}, SubsetQ[#1, #2]]&]]], {n, 0, 5}]
(* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = FindClique[g, Infinity, All];
CROSSREFS
The case with nonempty, non-singleton edges is A326362. Antichains of nonempty, non-singleton sets are A307249. Minimal covering antichains are A046165. Maximal intersecting antichains are A007363. Maximal antichains of nonempty sets are A326359. Cf. A000372, A003182, A006126, A006602, A014466, A051185, A058891, A261005, A305000, A305844, A326358, A326360, A326361.
Number of maximal intersecting antichains of sets covering n vertices with no singletons.
+0
13
1, 1, 1, 2, 12, 133, 11386, 12143511
COMMENTS
Covering means there are no isolated vertices. A set system (set of sets) is an antichain if no part is a subset of any other, and is intersecting if no two parts are disjoint.
EXAMPLE
The a(4) = 12 antichains:
{{1,2,3,4}}
{{1,2},{1,3,4},{2,3,4}}
{{1,3},{1,2,4},{2,3,4}}
{{1,4},{1,2,3},{2,3,4}}
{{2,3},{1,2,4},{1,3,4}}
{{2,4},{1,2,3},{1,3,4}}
{{3,4},{1,2,3},{1,2,4}}
{{1,2},{1,3},{1,4},{2,3,4}}
{{1,2},{2,3},{2,4},{1,3,4}}
{{1,3},{2,3},{3,4},{1,2,4}}
{{1,4},{2,4},{3,4},{1,2,3}}
{{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[stableSets[Subsets[Range[n]], Or[Intersection[#1, #2]=={}, SubsetQ[#1, #2]]&], Union@@#==Range[n]&]]], {n, 0, 5}]
(* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = Select[FindClique[g, Infinity, All], BitOr @@ # == n - 1 &];
CROSSREFS
Antichains of nonempty, non-singleton sets are A307249. Minimal covering antichains are A046165. Maximal intersecting antichains are A007363. Maximal antichains of nonempty sets are A326359. Cf. A000372, A003182, A006126, A006602, A014466, A051185, A058891, A261005, A305000, A305844, A326358, A326360, A326362, A326363.
Number of maximal pairwise coprime sets of divisors of n.
+0
13
1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 6, 2, 2, 3, 4, 1, 5, 1, 5, 2, 2, 2, 8, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 8, 2, 4, 2, 4, 1, 6, 2, 6, 2, 2, 1, 10, 1, 2, 4, 6, 2, 5, 1, 4, 2, 5, 1, 12, 1, 2, 4, 4, 2, 5, 1, 8, 4, 2, 1, 10, 2, 2
COMMENTS
Also the number of maximal pairwise coprime sets of divisors > 1 of n. For example, the a(n) sets for n = 12, 30, 36, 60, 120 are:
{6} {30} {6} {30} {30}
{12} {2,15} {12} {60} {60}
{2,3} {3,10} {18} {2,15} {120}
{3,4} {5,6} {36} {3,10} {2,15}
{2,3,5} {2,3} {3,20} {3,10}
{2,9} {4,15} {3,20}
{3,4} {5,6} {3,40}
{4,9} {5,12} {4,15}
{2,3,5} {5,6}
{3,4,5} {5,12}
{5,24}
{8,15}
{2,3,5}
{3,4,5}
{3,5,8}
EXAMPLE
The a(n) sets for n = 12, 30, 36, 60, 120:
{1,6} {1,30} {1,6} {1,30} {1,30}
{1,12} {1,2,15} {1,12} {1,60} {1,60}
{1,2,3} {1,3,10} {1,18} {1,2,15} {1,120}
{1,3,4} {1,5,6} {1,36} {1,3,10} {1,2,15}
{1,2,3,5} {1,2,3} {1,3,20} {1,3,10}
{1,2,9} {1,4,15} {1,3,20}
{1,3,4} {1,5,6} {1,3,40}
{1,4,9} {1,5,12} {1,4,15}
{1,2,3,5} {1,5,6}
{1,3,4,5} {1,5,12}
{1,5,24}
{1,8,15}
{1,2,3,5}
{1,3,4,5}
{1,3,5,8}
MATHEMATICA
fasmax[y_]:=Complement[y, Union@@Most@*Subsets/@y];
Table[Length[fasmax[Select[Subsets[Divisors[n]], CoprimeQ@@#&]]], {n, 100}]
CROSSREFS
The non-maximal version counting empty sets and singletons is A225520. The non-maximal version with no 1's is A343653. The non-maximal version is A343655. The version for subsets of {1..n} is A343659. The case without 1's or singletons is A343660. A018892 counts pairwise coprime unordered pairs of divisors.
A048691 counts pairwise coprime ordered pairs of divisors.
A048785 counts pairwise coprime ordered triples of divisors.
A100565 counts pairwise coprime unordered triples of divisors.
A305713 counts pairwise coprime non-singleton strict partitions.
A324837 counts minimal subsets of {1...n} with least common multiple n.
A325683 counts maximal Golomb rulers.
A326077 counts maximal pairwise indivisible sets.
Cf. A005361, A007359, A051026, A062319, A067824, A074206, A146291, A285572, A325859, A326359, A326496, A326675, A343654.
Number of maximal intersecting antichains of nonempty, non-singleton subsets of {1..n}.
+0
12
1, 1, 1, 2, 16, 163, 11742, 12160640
COMMENTS
A set system (set of sets) is an antichain if no part is a subset of any other, and is intersecting if no two parts are disjoint.
EXAMPLE
The a(4) = 16 maximal intersecting antichains:
{{1,2,3,4}}
{{1,2},{1,3},{2,3}}
{{1,2},{1,4},{2,4}}
{{1,3},{1,4},{3,4}}
{{2,3},{2,4},{3,4}}
{{1,2},{1,3,4},{2,3,4}}
{{1,3},{1,2,4},{2,3,4}}
{{1,4},{1,2,3},{2,3,4}}
{{2,3},{1,2,4},{1,3,4}}
{{2,4},{1,2,3},{1,3,4}}
{{3,4},{1,2,3},{1,2,4}}
{{1,2},{1,3},{1,4},{2,3,4}}
{{1,2},{2,3},{2,4},{1,3,4}}
{{1,3},{2,3},{3,4},{1,2,4}}
{{1,4},{2,4},{3,4},{1,2,3}}
{{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
MATHEMATICA
stableSets[u_, Q_]:=If[Length[u]==0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r==w||Q[r, w]||Q[w, r]], Q]]]];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n], {2, n}], Or[Intersection[#1, #2]=={}, SubsetQ[#1, #2]]&]]], {n, 0, 5}]
(* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = FindClique[g, Infinity, All];
CROSSREFS
Antichains of nonempty, non-singleton sets are A307249. Minimal covering antichains are A046165. Maximal intersecting antichains are A007363. Maximal antichains of nonempty sets are A326359. Cf. A000372, A003182, A006126, A006602, A014466, A051185, A058891, A261005, A305000, A305844, A326358, A326360, A326361, A326363.
Number of non-isomorphic antichains of nonempty subsets of {1,...,n}.
+0
11
1, 2, 4, 9, 29, 209, 16352, 490013147, 1392195548889993357, 789204635842035040527740846300252679
COMMENTS
a(n) is the number of "types" of log-linear hierarchical models on n factors in the sense of Colin Mallows (see the emails to N. J. A. Sloane). Two hierarchical models on n factors belong to the same "type" iff one can obtained from the other by a permutation of the factors.
The total number of hierarchical log-linear models on n factors (in all "types") is given by A014466(n) = A000372(n) - 1. The name of a hierarchical log-linear model on factors is based on the collection of maximal interaction terms, which must be an antichain (by the definition of maximality).
In his example on p. 1, Colin Mallows groups the A014466(3) = 19 hierarchical log-linear models on n = 3 factors x, y, z into a(3) = 9 types. See my example below for more details. (End)
LINKS
R. I. P. Wickramasinghe, Topics in log-linear models, Master of Science thesis in Statistics, Texas Tech University, Lubbock, TX, 2008, p. 36.
EXAMPLE
Non-isomorphic representatives of the a(0) = 1 through a(3) = 9 antichains:
{} {} {} {}
{{1}} {{1}} {{1}}
{{1,2}} {{1,2}}
{{1},{2}} {{1},{2}}
{{1,2,3}}
{{1},{2,3}}
{{1},{2},{3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}
We expand Colin Mallows's example from p. 1 of his list of 1991 emails. For n = 3, we have the following a(3) = 9 "types" of log-linear hierarchical models: Type 1: ( ), Type 2: (x), (y), (z), Type 3: (x,y), (y,z), (z,x), Type 4: (x,y,z), Type 5: (xy), (yz), (zx), Type 6: (xy,z), (yz,x), (zx,y), Type 7: (xy,xz), (yx,yz), (zx,zy), Type 8: (xy,yz,zx), Type 9: (xyz).
For each model, the name only contains the maximal terms. See p. 36 in Wickramasinghe (2008) for the full description of the 19 models.
Strictly speaking, I should have used set notation (rather than parentheses) for the name of each model, but I follow the tradition of the theory of log-linear models. In addition, in an interaction term such as xy, the order of the factors is irrelevant.
Models in the same type essentially have similar statistical properties.
For example, models in Type 7 have the property that two factors are conditionally independent of one another given each level (= category) of the third factor.
Models in Type 6 are such that two factors are jointly independent from the third one. (End)
CROSSREFS
Cf. A000372, A003182, A006126, A006602, A014466, A261005, A293606, A293993, A304996, A305000, A305001, A305857, A317674, A319721, A320449, A321679.
Search completed in 0.013 seconds
|