On 03/05/2025 14:00, Waldek Hebisch wrote:
On Sat, May 03, 2025 at 01:17:34PM +0200, Kurt Pagani wrote:
Hi Martin
On 29/04/2025 18:25, Martin Baker wrote:
This Wiki page says "There is no known simple formula to compute T(n)
for arbitrary n"
The "simple" is puzzling. I know no formula at all that could tell T(n) for
arbitrary n. Do you?
"Cardinality of set of topologies on [1,...,n]" is a simple formula,
but somewhat inconvenitent one. There is also relatively simple
formula in terms of number of T_0 topologies.
I meant a practical one, T(100)=?, not reducing to other "uncomputable"
figures. To my knowledge the statement in the quotation below still holds?
--- https://oeis.org/A000798
Although no general formula is known for a(n), by considering the number
of topologies with a fixed number of open sets, it is possible to
explicitly represent the sequence in terms of Stirling numbers of the
second kind.
For example: a(n,3) = 2*S(n,2), a(n,4) = S(n,2) + 6*S(n,3), a(n,5) =
6*S(n,3) + 24*S(n,4).
Lower and upper bounds are known: 2^n <= a(n) <= 2^(n*(n-1)), n > 1.
This follows from the fact that there are 2^(n*(n-1)) reflexive
relations on a set with n elements.
Furthermore: a(n+1) <= a(n)*(3a(n)+1).
---
and forums like this:
https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-
finite-set-of-n-elements
seem to suggest that an efficient algorithm is an open problem.
What's the meaning of "efficient"?
https://codegolf.stackexchange.com/questions/2773/calculate-the-number-of-topologies-on-1-2-n
All these codes play out for n<=10, so one should identify the time/space
complexity of the algorithm:
O(1) - Excellent/Best
Impossible, O(1) algorithm can only give fixed number of answers.
O(log n) - Good
Very unlikely to be useful, would need some funky compression scheme
for answers. Of corses, writing "T(n)" (with explicit n) attains
this complexity, but is useless.
O(n) - Fair
O(n log n) - Bad
O(n^2),
That is the best possible with binary encoding of the result.
O(2^n) and O(n!) - Horrible/Worst
Probably much better than any known method...
--
You received this message because you are subscribed to the Google Groups "FriCAS -
computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/fricas-devel/add6afcf-3ca6-4a6b-bd06-f4851509fffb%40gmail.com.
