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

 

Logo


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 March 26 05:21 EDT 2017. Contains 284111 sequences.