OFFSET
1,2
COMMENTS
Minimal size of a set with n subsets such that no one contains another.
The proof that the minimal cardinality k of a set having n subsets not containg one other is the generalized central binomial coefficient binomial(k, floor(k/2)) (equivalent to: "the largest possible families of finite sets none of which contain any other sets in the family) is called "Sperner's Theorem" and is due to Sperner. - Renzo Benedetti, May 26 2021
Also the Schein rank of a contranominal scale of size n represented as a Boolean matrix (Kim, 1982; Marenich, 2010). - Dmitry I. Ignatov, Nov 25 2021
REFERENCES
K. H. Kim, Boolean matrix theory and applications. Marcel Dekker, New York and Basel (1982).
LINKS
David A. Corneth, Table of n, a(n) for n = 1..10000
Dmitry I. Ignatov and Yazag Meziane An asymptototic lower bound for A305233.
Evgeny E. Marenich, Determining the Schein Rank of Boolean Matrices. Matrix Methods: Theory, Algorithms and Applications (2010) 85-103.
Emanuel Sperner, Ein Satz über Untermengen einer endlichen Menge, Mathematische Zeitschrift 27, 544-548, (1928).
FORMULA
Asymptotic lower bound is log_2(sqrt(Pi/2)*n) + O(log_2(log_2(sqrt(Pi/2)*n)). - Dmitry I. Ignatov and Meziane Yazag, Dec 07 2023
MATHEMATICA
Array[Block[{k = 1}, While[Binomial[k, Floor[k/2]] < #, k++]; k] &, 105] (* Michael De Vlieger, Aug 02 2018 *)
PROG
(Python)
from sympy import binomial
def f(n): return binomial(n, n // 2)
sum([[i]*(f(i)-f(i-1)) for i in range(1, 10)], [1])
(PARI) a(n) = my(k=1); while (binomial(k, floor(k/2)) < n, k++); k; \\ Michel Marcus, Jul 10 2018
(PARI) first(n) = my(l=List(), t=1, res = vector(n), c=1); while(c<=n, listput(l, c); t++; c=binomial(t, t\2)); listput(l, c); res[1]=1; for(i=2, #l, m = max(n, l[i]); for(j=l[i-1] + 1, min(n, l[i]), res[j]=i)); res \\ David A. Corneth, May 22 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Jack Zhang, May 28 2018
STATUS
approved