CINXE.COM
A306445 - OEIS
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A306445 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A306445" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA306445">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A306445 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A306445 </div> <div class=seqname> Number of collections of subsets of {1, 2, ..., n} that are closed under union and intersection. </div> </div> <div class=scorerefs> 31 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>2, 4, 13, 74, 732, 12085, 319988, 13170652, 822378267, 76359798228, 10367879036456, 2029160621690295, 565446501943834078, 221972785233309046708, 121632215040070175606989, 92294021880898055590522262, 96307116899378725213365550192, 137362837456925278519331211455157, 266379254536998812281897840071155592</div> <div class=seqdatalinks> (<a href="/A306445/list">list</a>; <a href="/A306445/graph">graph</a>; <a href="/search?q=A306445+-id:A306445">refs</a>; <a href="/A306445/listen">listen</a>; <a href="/history?seq=A306445">history</a>; <a href="/search?q=id:A306445&fmt=text">text</a>; <a href="/A306445/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,1</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>R. Stanley, Enumerative Combinatorics, volume 1, second edition, Exercise 3.46.</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline><a href="/A306445/b306445.txt">Table of n, a(n) for n=0..18.</a></div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>a(n) = 1 + Sum_{d=0..n} Sum_{i=d..n} C(n,i)*C(i,i-d)*<a href="/A000798" title="Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.">A000798</a>(d). (Follows by caseworking on the maximal and minimal set in the collection.)</div> <div class=sectline>E.g.f.: exp(x) + exp(x)^2*B(exp(x)-1) where B(x) is the e.g.f. for <a href="/A001035" title="Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs).">A001035</a> (after Stanley reference above). - <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a>, Jan 19 2024</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>For n = 0, the empty collection and the collection containing the empty set only are both valid.</div> <div class=sectline>For n = 1, the 2^(2^1)=4 possible collections are also all closed under union and intersection.</div> <div class=sectline>For n = 2, there are only 3 invalid collections, namely the collections containing both {1} and {2} but not both {1,2} and the empty set. Hence there are 2^(2^2)-3 = 13 valid collections.</div> <div class=sectline>From <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Jul 31 2019: (Start)</div> <div class=sectline>The a(0) = 2 through a(4) = 13 sets of sets:</div> <div class=sectline> {} {} {}</div> <div class=sectline> {{}} {{}} {{}}</div> <div class=sectline> {{1}} {{1}}</div> <div class=sectline> {{},{1}} {{2}}</div> <div class=sectline> {{1,2}}</div> <div class=sectline> {{},{1}}</div> <div class=sectline> {{},{2}}</div> <div class=sectline> {{},{1,2}}</div> <div class=sectline> {{1},{1,2}}</div> <div class=sectline> {{2},{1,2}}</div> <div class=sectline> {{},{1},{1,2}}</div> <div class=sectline> {{},{2},{1,2}}</div> <div class=sectline> {{},{1},{2},{1,2}}</div> <div class=sectline>(End)</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>Table[Length[Select[Subsets[Subsets[Range[n]]], SubsetQ[#, Union[Union@@@Tuples[#, 2], Intersection@@@Tuples[#, 2]]]&]], {n, 0, 3}] (* <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Jul 31 2019 *)</div> <div class=sectline><a href="/A000798" title="Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.">A000798</a> = Cases[Import["https://oeis.org/<a href="/A000798" title="Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.">A000798</a>/b000798.txt", "Table"], {_, _}][[All, 2]];</div> <div class=sectline>a[n_] := 1 + Sum[Binomial[n, i]*Binomial[i, i - d]*<a href="/A000798" title="Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.">A000798</a>[[d + 1]], {d, 0, n}, {i, d, n}];</div> <div class=sectline>a /@ Range[0, Length[<a href="/A000798" title="Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.">A000798</a>] - 1] (* <a href="/wiki/User:Jean-Fran莽ois_Alcover">Jean-Fran莽ois Alcover</a>, Dec 30 2019 *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(Python)</div> <div class=sectline>import math</div> <div class=sectline># Sequence <a href="/A000798" title="Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.">A000798</a></div> <div class=sectline>topo = [1, 1, 4, 29, 355, 6942, 209527, 9535241, 642779354, 63260289423, 8977053873043, 1816846038736192, 519355571065774021, 207881393656668953041, 115617051977054267807460, 88736269118586244492485121, 93411113411710039565210494095, 134137950093337880672321868725846, 261492535743634374805066126901117203]</div> <div class=sectline>def nCr(n, r):</div> <div class=sectline> return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))</div> <div class=sectline>for n in range(len(topo)):</div> <div class=sectline> ans = 1</div> <div class=sectline> for d in range(n+1):</div> <div class=sectline> for i in range(d, n+1):</div> <div class=sectline> ans += nCr(n, i) * nCr(i, i-d) * topo[d]</div> <div class=sectline> print(n, ans)</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>The covering case with {} is <a href="/A000798" title="Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.">A000798</a>.</div> <div class=sectline>The case closed under union only is <a href="/A102897" title="Number of ACI algebras (or semilattices) on n generators.">A102897</a>.</div> <div class=sectline>The case closed under intersection only is (also) <a href="/A102897" title="Number of ACI algebras (or semilattices) on n generators.">A102897</a>.</div> <div class=sectline>The BII-numbers of these set-systems are <a href="/A326876" title="BII-numbers of finite topologies without their empty set.">A326876</a>.</div> <div class=sectline>Cf. <a href="/A001930" title="Number of topologies, or transitive digraphs with n unlabeled nodes.">A001930</a>, <a href="/A102895" title="Number of ACI algebras or semilattices on n generators with no identity element.">A102895</a>, <a href="/A102896" title="Number of ACI algebras (or semilattices) on n generators with no annihilator.">A102896</a>, <a href="/A326866" title="Number of connectedness systems on n vertices.">A326866</a>, <a href="/A326878" title="Number of topologies whose points are a subset of {1..n}.">A326878</a>, <a href="/A326882" title="Irregular triangle read by rows where T(n,k) is the number of finite topologies with n points and k nonempty open sets, 0 <=...">A326882</a>.</div> <div class=sectline>Sequence in context: <a href="/A132786" title="Column sums of triangle A132784.">A132786</a> <a href="/A298065" title="Number of nX3 0..1 arrays with every element equal to 2, 3, 4 or 6 king-move adjacent elements, with upper left element zero.">A298065</a> <a href="/A298714" title="Number of nX3 0..1 arrays with every element equal to 2, 3, 4, 6 or 7 king-move adjacent elements, with upper left element zero.">A298714</a> * <a href="/A216670" title="Tribonacci numbers which can be written in the form a^2 + b^2.">A216670</a> <a href="/A103845" title="Product of first n Lucas numbers, plus one.">A103845</a> <a href="/A055463" title="a(n) = 2*a(n-1)*a(n-2) - 3*a(n-3), with a(0) = 0, a(1) = 1, a(2) = 2.">A055463</a></div> <div class=sectline>Adjacent sequences: <a href="/A306442" title="Greatest integer N such that the number of base-n-zero containing numbers [<= N] <= the number of base-n-zerofree numbers [<...">A306442</a> <a href="/A306443" title="Number of ways of partitioning the set of the first n primes into two subsets whose sums differ at most by 1.">A306443</a> <a href="/A306444" title="A(n,k) = binomial((2*k+1)*n+2, k*n+1)/((2*k+1)*n+2), square array A(n,k) read by antidiagonals, for n >= 0, k >= 0.">A306444</a> * <a href="/A306446" title="a(n) is the number of connected components in the Fermi-Dirac factorization of n (see Comments for precise definition).">A306446</a> <a href="/A306447" title="Number of (undirected) Hamiltonian cycles in the n-antiprism graph.">A306447</a> <a href="/A306448" title="Pseudoprimes to base 9 that are not squarefree.">A306448</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="a sequence of nonnegative numbers">nonn</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:Yuan_Yao">Yuan Yao</a>, Feb 15 2019</div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>a(16)-a(18) from <a href="/A000798" title="Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.">A000798</a> by <a href="/wiki/User:Jean-Fran莽ois_Alcover">Jean-Fran莽ois Alcover</a>, Dec 30 2019</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified November 24 17:37 EST 2024. Contains 378083 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>