

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 "nonplanar" otherwise.
This is analogous to the way in which subgroup lattices are called planar or nonplanar. Using this terminology, the above sequence gives the number of planar topologies on n labeled elements. If the number of nonplanar 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^(k3)(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

Table of n, a(n) for n=0..18.


FORMULA

a(n) = 2^(n1)  1 + Sum{C(n,k)*a(nk), 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^(n1)  1 + add(a122835(nk)*binomial(n, k), k=1..n); fi; end;


MATHEMATICA

a[n_]:=a[n]=2^(n1)1+Sum[a[nk]*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



