login
This site is supported by donations to The OEIS Foundation.

 

Logo

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

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

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 22 15:13 EST 2017. Contains 295089 sequences.