This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A122835 Number of topologies on n labeled elements in which no element belongs to any pair of noncomparable members of the topology. 3
 1, 1, 4, 19, 112, 811, 7024, 70939, 818752, 10630891, 153371344, 2433948859, 42137351392, 790287522571, 15962014455664, 345424786466779, 7973482022972032, 195556150543703851, 5078301994885267984 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS The number of topologies on n labeled elements is a fundamental sequence (A000798), which many mathematicians believe is impossible to completely determine. The present sequence is an elegant recursion that enumerates the topologies on n labeled elements that can be "drawn" (as, for example, on page 76 of Munkres) in such a way that the boundaries of the subsets do not "cross" one another. Thus I recommend that topologies be classified as "planar" if their members can be drawn without crossings and "non-planar" otherwise. This is analogous to the way in which subgroup lattices are called planar or non-planar. Using this terminology, the above sequence gives the number of planar topologies on n labeled elements. If the number of non-planar topologies on n labeled elements (see A122836) could be enumerated, then so could the total number of topologies on n labeled elements. Another way to state the definition is that any two members of the topology are comparable or disjoint. - Rainer Rosenthal, Jan 02 2011 Conjectural closed form for n>0: 3*2^(k-3)(LerchPhi[1/4, -k, 1/2] + 2 PolyLog[-k, 1/4]) - 1/2. - Vladimir Reshetnikov, Jan 07 2011 REFERENCES J. Munkres, Topology, Prentice Hall, (2000), p. 76. LINKS FORMULA a(n) = 2^(n-1) - 1 + Sum{C(n,k)*a(n-k), k = 1 ... n} E.g.f.: (3/4) / (1 - exp(x)/2) - exp(x)/2. - Michael Somos, Jan 07 2011 a(n) = (A000629(n) + 0^n) * (3/4) - 1/2. - Michael Somos, Jan 07 2011 MAPLE a122835:=proc(n) option remember; if n=0 then 1 else 2^(n-1) - 1 + add(a122835(n-k)*binomial(n, k), k=1..n); fi; end; MATHEMATICA a[n_]:=a[n]=2^(n-1)-1+Sum[a[n-k]*Binomial[n, k], {k, 1, n}]; a[0]=1; Table[a[n], {n, 0, 25}] a[ n_] := (3/4) * (PolyLog[ -n, 1/2] + Boole[n==0]) - 1/2 (* Michael Somos, Jan 07 2011 *) PROG (PARI) {a(n) = local(A); if( n<1, n==0, A = exp(x + x * O(x^n)) / 2; n! * polcoeff( (3/4) / (1 - A) - A, n))} /* Michael Somos, Jan 07 2011 */ CROSSREFS Cf. A000798, A122836. Sequence in context: A060905 A174123 A127548 * A013185 A186359 A203268 Adjacent sequences:  A122832 A122833 A122834 * A122836 A122837 A122838 KEYWORD easy,nice,nonn AUTHOR Nathan K. McGregor (mcgregnk(AT)ese.wustl.edu), Sep 15 2006 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.