A005465 -id:A005465 - cp's OEIS frontend

A014466 Dedekind numbers: monotone Boolean functions, or nonempty antichains of subsets of an n-set.

1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787, 286386577668298411128469151667598498812365

Offset: 0

A monotone Boolean function is an increasing functions from P(S), the set of subsets of S, to {0,1}.
The count of antichains includes the antichain consisting of only the empty set, but excludes the empty antichain.
Also counts bases of hereditary systems.
Also antichains of nonempty subsets of an n-set. The unlabeled case is A306505. The spanning case is A307249. This sequence has a similar description to A305000 except that the singletons must be disjoint from the other edges. - Gus Wiseman, Feb 20 2019
a(n) is the total number of hierarchical log-linear models on n labeled factors (categorical variables). See Wickramasinghe (2008) and Nardi and Rinaldo (2012). - Petros Hadjicostas, Apr 08 2020
From Lorenzo Sauras Altuzarra, Apr 02 2023: (Start)
a(n) is the number of labeled abstract simplicial complexes on n vertices.
A058673(n) <= a(n) <= A058891(n+1). (End)

			a(2)=5 from the antichains {{}}, {{1}}, {{2}}, {{1,2}}, {{1},{2}}.
From _Gus Wiseman_, Feb 20 2019: (Start)
The a(0) = 1 through a(3) = 19 antichains:
  {{}}  {{}}   {{}}      {{}}
        {{1}}  {{1}}     {{1}}
               {{2}}     {{2}}
               {{12}}    {{3}}
               {{1}{2}}  {{12}}
                         {{13}}
                         {{23}}
                         {{123}}
                         {{1}{2}}
                         {{1}{3}}
                         {{2}{3}}
                         {{1}{23}}
                         {{2}{13}}
                         {{3}{12}}
                         {{12}{13}}
                         {{12}{23}}
                         {{13}{23}}
                         {{1}{2}{3}}
                         {{12}{13}{23}}
(End)
From _Lorenzo Sauras Altuzarra_, Apr 02 2023: (Start)
The 19 sets E such that ({1, 2, 3}, E) is an abstract simplicial complex:
  {}
  {{1}}
  {{2}}
  {{3}}
  {{1}, {2}}
  {{1}, {3}}
  {{2}, {3}}
  {{1}, {2}, {3}}
  {{1}, {2}, {1, 2}}
  {{1}, {3}, {1, 3}}
  {{2}, {3}, {2, 3}}
  {{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}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
(End)

I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
Jorge Luis Arocha, "Antichains in ordered sets" [ In Spanish ]. Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico 27: 1-21 (1987).
J. Berman, "Free spectra of 3-element algebras," in R. S. Freese and O. C. Garcia, editors, Universal Algebra and Lattice Theory (Puebla, 1982), Lect. Notes Math. Vol. 1004, 1983.
G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.
J. Dezert, Fondations pour une nouvelle théorie du raisonnement plausible et paradoxal (la DSmT), Tech. Rep. 1/06769 DTIM, ONERA, Paris, page 33, January 2003.
J. Dezert, F. Smarandache, On the generating of hyper-powersets for the DSmT, Proceedings of the 6th International Conference on Information Fusion, Cairns, Australia, 2003.
M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 188.
W. F. Lunnon, The IU function: the size of a free distributive lattice, pp. 173-181 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.
S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.

Guillermo Alesandroni and Sungjin Kim, The probability that the Taylor resolution of a monomial ideal is minimal, J. Comm. Alg., 2024. See p. 3.
K. Atanassov, On Some of Smarandache's Problems.
K. S. Brown, Dedekind's problem.
Winfried Bruns, Pedro A. García-Sánchez, and Luca Moci, The monoid of monotone functions on a poset and arithmetic multiplicities for uniform matroids, arXiv:1902.00864 [math.CO], 2019.
Donald E. Campbell, Jack Graver, and Jerry S. Kelly, There are more strategy-proof procedures than you think, Mathematical Social Sciences 64 (2012) 263-265. - _N. J. A. Sloane_, Oct 23 2012
David Carey and Mordechai Katzman, Stanley-Reisner Ideals with Pure Resolutions, arXiv:2409.05481 [math.AC], 2024. See p. 52.
Fan Cheng, Optimality of routing on the wiretap network with simple network topology, Information Theory (ISIT), 2014 IEEE International Symposium on, June 29 2014-July 4 2014 Page(s): 786 - 790 INSPEC Accession Number: 14524545 Honolulu, HI.
Fan Cheng and Vincent Y. F. Tan, A Numerical Study on the Wiretap Network with a Simple Network Topology, arXiv preprint arXiv:1505.02862 [cs.IT], 2015.
Jean Dezert, Foundations for a new theory for plausible and paradoxical reasoning, Tech. Rep. DTIM/IED, ONERA, Paris, pp. 14-15, 2002.
Jean Dezert, Combination of paradoxical sources of information within the neutrosophic framework, Proceedings of the First International Conference on Neutrosophics (2001).
J. L. King, Brick tiling and monotone Boolean functions.
J. L. King, A change-of-coordinates from Geometry to Algebra applied to brick tilings, arXiv:math/9809176 [math.CO], 1998.
D. J. Kleitman, On Dedekind's problem: The number of monotone Boolean functions, Proc. Amer. Math. Soc. 21 (1969), 677-682.
D. J. Kleitman and G. Markowsky, On Dedekind's problem: the number of isotone Boolean functions. II, Trans. Amer. Math. Soc. 213 (1975), 373-390.
Y. Nardi and A. Rinaldo, The log-linear group-lasso estimator and its asymptotic properties, Bernoulli 18(3) (2012), 945-974; see Table 2 on p. 954.
Eric Weisstein's World of Mathematics, Antichain.
R. I. P. Wickramasinghe, Topics in log-linear models, Master of Science thesis in Statistics, Texas Tech University, Lubbock, TX, 2008. [For n = 2, the a(2) = 5 hierarchical log-linear models on two factors X and Y appear on p. 18. For n = 3, the a(3) = 19 hierarchical log-linear models on three factors X, Y, and Z, appear on p. 36. - _Petros Hadjicostas_, Apr 08 2020]
D. H. Wiedemann, A computation of the eighth Dedekind number, Order 8 (1991) 5-6.
Wikipedia, Abstract simplicial complex.
Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.
Index entries for sequences related to Boolean functions

Equals A000372 - 1 = A007153 + 1.

Cf. A003182, A005465, A006126, A006602, A058673 (labeled matroids), A058891 (labeled hypergraphs), A261005, A293606, A304996, A305000, A306505, A307249, A317674, A319721, A320449, A321679.

nn=5;
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[stableSets[Subsets[Range[n],{1,n}],SubsetQ]],{n,0,nn}] (* Gus Wiseman, Feb 20 2019 *)
A[s_Integer] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import["https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {, }][[All, 2]]];
A@372 - 1 (* Jean-François Alcover, Jan 07 2020 *)

Binomial transform of A307249 (or A006126 if its zeroth term is 1). - Gus Wiseman, Feb 20 2019

a(n) >= A005465(n) (because the hierarchical log-linear models on n factors always include all the conditional independence models considered by I. J. Good in A005465). - Petros Hadjicostas, Apr 24 2020

Last term from D. H. Wiedemann, personal communication.
Additional comments from Michael Somos, Jun 10 2002
Term a(9) (using A000372) from Joerg Arndt, Apr 07 2023

A058681 Number of matroids of rank 2 on n labeled points.

Original entry on oeis.org

0, 0, 1, 7, 36, 171, 813, 4012, 20891, 115463, 677546, 4211549, 27640341, 190891130, 1382942161, 10480109379, 82864804268, 682076675087, 5832741942913, 51724157711084, 474869815108175, 4506715736350171, 44152005850890042, 445958869286416681, 4638590332213222137

Offset: 0

N. J. A. Sloane, Dec 30 2000

Number of partitions of {1, 2, ..., n+1} in which at least one block of each partition contains a pair of nonconsecutive integers. E.g., B(4)-2^3 = 7: there are 7 partitions of {1,2,3,4} in which some block contains a pair of nonconsecutive integers, namely 124/3, 134/2, 14/23, 13/24, 13/2/4, 14/2/3, 1/24/3. - Augustine O. Munagi, Mar 20 2005
Number of complementing systems of subsets of {0, 1, ..., p^(n+1) - 1} (p a prime) in which at least one member is not of the form {0, x, 2x, ..., (c-1)x} for positive integers x and c. E.g., B(4)-p^3 = 7: there are 7 complementing systems of subsets of {0, 1, ..., p^4-1} in which at least one member is not of the form {0, x, 2x, ..., (c-1)*x}. Number of complementing systems of subsets of {0, 1, ..., p^4 - 1} reduces to B(4) and number of ordered factorizations of p^4 is p^3. - Augustine O. Munagi, Mar 20 2005
a(n) is the number of collections containing two or more nonempty subsets of {1,2,...,n} that are pairwise disjoint. - Geoffrey Critzer, Oct 10 2009

			a(3) = 7 because there are 7 collections (having more than one element)of nonempty subsets of {1,2,3} that are pairwise disjoint: {1}{2}; {1}{3}; {1}{2,3}; {2}{3}; {2}{1,3}; {1,2}{3}; {1}{2}{3}. - _Geoffrey Critzer_, Oct 10 2009

T. D. Noe, Table of n, a(n) for n = 0..100
W. M. B. Dukes, Tables of matroids.
W. M. B. Dukes, Counting and Probability in Matroid Theory, Ph.D. Thesis, Trinity College, Dublin, 2000.
W. M. B. Dukes, On the number of matroids on a finite set, arXiv:math/0411557 [math.CO], 2004.
I. J. Good, The number of hypotheses of independence for a random vector or for a multidimensional contingency table, and the Bell numbers, Iranian J. Science and Technology, 4, (1975), 77-83. [See Eq. (9), p. 80.]
Markus Kirchweger, Manfred Scheucher, and Stefan Szeider, A SAT Attack on Rota's Basis Conjecture, Leibniz International Proceedings in Informatics (LIPIcs 2022) Vol. 236, 4:1-4:18.
A. O. Munagi, k-Complementing Subsets of Nonnegative Integers, International Journal of Mathematics and Mathematical Sciences, 2005:2 (2005), 215-224.
Index entries for sequences related to matroids

Column k = 2 of A058669.
The triangle A340264 without the main diagonal provides a refinement of this sequence.
Cf. A005465.

egf := exp(x + exp(x) - 1) - exp(2*x); ser := series(egf, x, 24):
seq(simplify(n!*coeff(ser,x,n)), n=0..22); # Peter Luschny, Jan 08 2021

f[n_] := Sum[ StirlingS2[n + 1, k+2], {k, 1, n}]; Table[ f[n], {n, 0, 23}] (* Zerinvary Lajos, Mar 21 2007 *)
Table[BellB[n+1]-2^n,{n,0,30}] (* Harvey P. Dale, Oct 13 2011 *)

a(n) = sum(k=1, n, stirling(n+1, k+2, 2)); \\ Ruud H.G. van Tol, May 09 2024

my(x='x+O('x^33)); concat([0,0],Vec(serlaplace(exp(x + exp(x) - 1) - exp(2*x)))) \\ Joerg Arndt, May 10 2024

a(n) = B(n+1)-2^n, B = Bell numbers (A000110).
E.g.f.: d/dz (exp(exp(z)-1) - (1/2)*exp(2*z) - 1/2). - Thomas Wieder, Nov 30 2004
a(n) = Sum_{i=2..n} binomial(n,i)*(B(i)-1), B=Bell numbers A000110. - Geoffrey Critzer, Oct 10 2009
E.g.f.: exp(x + exp(x) - 1) - exp(2*x). - Peter Luschny, Jan 08 2021

More terms from James Sellers, Jan 03 2001

a(0) = a(1) = 0 prepended by Peter Luschny, Jan 08 2021

A005461 Number of simplices in barycentric subdivision of n-simplex.

Original entry on oeis.org

1, 15, 180, 2100, 25200, 317520, 4233600, 59875200, 898128000, 14270256000, 239740300800, 4249941696000, 79332244992000, 1556132497920000, 32011868528640000, 689322235650048000, 15509750302126080000, 364022962973429760000, 8898339094906060800000

Offset: 1

N. J. A. Sloane

			G.f. = x + 15*x^2 + 180*x^3 + 2100*x^4 + 25200*x^5 + 317520*x^6 + ...

R. Austin, R. K. Guy, and R. Nowakowski, unpublished notes, circa 1987.
R. K. Guy, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 1..440
R. Austin, R. K. Guy, and R. Nowakowski, Unpublished notes, 1987.
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets.
Rajesh Kumar Mohapatra and Tzung-Pei Hong, On the Number of Finite Fuzzy Subsets with Analysis of Integer Sequences, Mathematics, Vol. 10, No. 7 (2022), 1161.

Cf. A001113, A001620, A028246, A091725, A099285.
Cf. A005460, A005462, A005463, A005464, A005465.
Cf. A001297.

[Factorial(n-1)*StirlingSecond(n+3,n): n in [1..35]]; // G. C. Greubel, Nov 23 2022

a:=n->sum((n-j)*n!/4!, j=3..n): seq(a(n), n=4..17); # Zerinvary Lajos, Apr 29 2007

Table[(n(n+1)(n+3)!)/48,{n,20}] (* Harvey P. Dale, Mar 14 2012 *)
a[ n_] := If[ n < 0, 0, n (n + 1) (n + 3)! / 48]; (* Michael Somos, May 27 2014 *)

[factorial(m+1)*binomial(m-1,2)/24 for m in range(3, 19)] # Zerinvary Lajos, Jul 05 2008

[binomial(n,4)*factorial (n-2)/2 for n in range(4, 18)] #  Zerinvary Lajos, Jul 07 2009

a(n) = n*(n + 1)*(n + 3)!/48.
Essentially Stirling numbers of second kind - see A028246.
If we define f(n,i,x) = Sum_{k=i..n} Sum_{j=i..k} binomial(k,j)*Stirling1(n,k)*Stirling2(j,i)*x^(k-j) then a(n-3) = (-1)^n*f(n,4,-3), (n>=4). - Milan Janjic, Mar 01 2009
E.g.f.: t*(3*t + 2)/(2*(t - 1)^6). - Ran Pan, Jul 10 2016
a(n) ~ sqrt(Pi/2)*exp(-n)*n^(n+1/2)*(n^5/24 + 85*n^4/288 + 5065*n^3/6912 + 955841*n^2/1244160 + 3710929*n/11943936). - Ilya Gutkovskiy, Jul 10 2016
From Amiram Eldar, May 06 2022: (Start)
Sum_{n>=1} 1/a(n) = 16*(e + gamma - Ei(1)) - 64/3, where e = A001113, gamma = A001620, and Ei(1) = A091725.
Sum_{n>=1} (-1)^(n+1)/a(n) = 32*(gamma - Ei(-1)) - 16/e - 56/3, where Ei(-1) = -A099285. (End)
a(n) = (n-1)! * Stirling2(n+3, n). - G. C. Greubel, Nov 23 2022

More terms from Harvey P. Dale, Mar 14 2012

A005463 Number of simplices in barycentric subdivision of n-simplex.

Original entry on oeis.org

1, 63, 1932, 46620, 1020600, 21538440, 451725120, 9574044480, 207048441600, 4595022432000, 105006251750400, 2475732702643200, 60284572969420800, 1516762345722624000, 39433286715863040000, 1059143615076298752000, 29378569022287220736000, 841159994641469927424000

Offset: 4

N. J. A. Sloane

nonn

R. Austin, R. K. Guy, and R. Nowakowski, unpublished notes, circa 1987.
R. K. Guy, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 4..440
R. Austin, R. K. Guy, and R. Nowakowski, Unpublished notes, 1987
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Rajesh Kumar Mohapatra and Tzung-Pei Hong, On the Number of Finite Fuzzy Subsets with Analysis of Integer Sequences, Mathematics (2022) Vol. 10, No. 7, 1161.

Cf. A005460, A005461, A005462, A005464, A005465.

Cf. A028246, A112494.

[Factorial(n-4)*StirlingSecond(n+2,n-3): n in [4..35]]; // G. C. Greubel, Nov 22 2022

a:= n-> Stirling2(2+n,n-3)*(n-4)!:
seq(a(n), n=4..21);  # Alois P. Heinz, Apr 27 2022

Table[(n-4)!*StirlingS2[n+2, n-3], {n,4,35}] (* G. C. Greubel, Nov 22 2022 *)

[factorial(n-4)*stirling_number2(n+2,n-3) for n in range(4,36)] # G. C. Greubel, Nov 22 2022

Essentially Stirling numbers of second kind - see A028246.

a(n) = (n-4)! * Stirling2(n+2, n-3). - Alois P. Heinz, Apr 27 2022

More terms from Alois P. Heinz, Apr 27 2022

A005464 Number of simplices in barycentric subdivision of n-simplex.

Original entry on oeis.org

1, 127, 6050, 204630, 5921520, 158838240, 4115105280, 105398092800, 2706620716800, 70309810771200, 1858166876966400, 50148628078348800, 1385482985542656000, 39245951652171264000, 1140942623868343296000, 34060437199245929472000, 1044402668566817624064000, 32895725269182358302720000

Offset: 5

N. J. A. Sloane

R. Austin, R. K. Guy, and R. Nowakowski, unpublished notes, circa 1987.
R. K. Guy, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 5..440
R. Austin, R. K. Guy, and R. Nowakowski, Unpublished notes, 1987
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Rajesh Kumar Mohapatra and Tzung-Pei Hong, On the Number of Finite Fuzzy Subsets with Analysis of Integer Sequences, Mathematics (2022) Vol. 10, No. 7, 1161.

Cf. A005460, A005461, A005462, A005463, A005465.

Cf. A028246, A144969.

[Factorial(n-5)*StirlingSecond(n+2,n-4): n in [5..35]]; // G. C. Greubel, Nov 22 2022

seq((d+2)!*(63*d^5-945*d^4+5355*d^3-13951*d^2+15806*d-5304)/2903040,d=5..30) ; # R. J. Mathar, Mar 19 2018

Table[(n-5)!*StirlingS2[n+2, n-4], {n,5,35}] (* G. C. Greubel, Nov 22 2022 *)

[factorial(n-5)*stirling_number2(n+2,n-4) for n in range(5,36)] # G. C. Greubel, Nov 22 2022

Essentially Stirling numbers of second kind - see A028246.

a(n) = (n-5)! * Stirling2(n+2, n-4). - G. C. Greubel, Nov 22 2022

cp's OEIS Frontend

A014466 Dedekind numbers: monotone Boolean functions, or nonempty antichains of subsets of an n-set.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A058681 Number of matroids of rank 2 on n labeled points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A005461 Number of simplices in barycentric subdivision of n-simplex.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Sage

Formula

Extensions

A005463 Number of simplices in barycentric subdivision of n-simplex.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A005464 Number of simplices in barycentric subdivision of n-simplex.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula