Timeline for Does the Ackermann function count something?
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 16, 2021 at 6:38 | comment | added | Per Alexandersson | So, I do not know what the Ackermann function counts, but the TREE function does count something explicit and combinatorial, and the Ackermann function is tiny in comparison with TREE. mathoverflow.net/questions/93828/how-large-is-tree3 | |
| May 10, 2021 at 17:55 | comment | added | Ville Salo | The inverse Ackermann function appears in some algorithms, e.g. using a "soft heap" you can find the minimum spanning tree in time $O(m\alpha(m, n))$. A decade ago I probably knew why and whether something was being counted. | |
| May 10, 2021 at 15:47 | comment | added | darij grinberg | Interesting question. Maybe some nested set-partition-like structures? A stupid answer would be to take a deterministic rewrite system that takes $A\left(n,m\right)$ steps to terminate (I think there should be one), and just say "the intermediate states of this rewrite system". | |
| May 10, 2021 at 15:13 | history | edited | Francesco Polizzi | CC BY-SA 4.0 |
added 30 characters in body
|
| May 10, 2021 at 15:07 | comment | added | fosco | There is a whole "school" of enumerative combinatorics done using Joyal's species! Relevant names are Joyal himself, Labelle, Leroux, Viennot, Mendez, Rajan... | |
| May 10, 2021 at 14:57 | comment | added | Paul Taylor | Not sure why this (good) question has a category theory tag, but there is a kind of "categorical number theory / combinatorics" that was studied by Steve Schanuel. I don't know any more than that. | |
| May 10, 2021 at 14:46 | comment | added | fosco | @SimonHenry even though the question isn't phrased in this way, I suspect it is asking about a species of structure with the Ackermann function as generating species. I have no idea what the sequence $a_n=A(n,n)$ could be counting, though, and throwing the very few terms of the sequence that can be computed at OEIS doesn't seem a viable choice: is there a combinatorial interpretation for those numbers? | |
| May 10, 2021 at 14:45 | comment | added | Simon Henry | @fosco : yes but,I am not aware of anything that forces the exponential generating function of combinatorial species to converge, so why would the convergence brings anything to the question ? But maybe you have in mind some result proving the convergence for some class of "nice" species ? | |
| May 10, 2021 at 14:44 | comment | added | catlyn | @SimonHenry yes you can associate some category but I wondered if there was a natural (in the vague sense of the word) choice. Maybe a structure arising independently elsewhere in mathematics. | |
| May 10, 2021 at 14:42 | comment | added | Simon Henry | I'm not sure how to understand this question. For any function $f:\mathbb{N} \to \mathbb{N}$ I can chose a sequence of sets $P_n$ such that $\# P_n = f(n)$ and take $C$ to be a naively defined category with an object for each $i \in P_n$ mapping to a set with $n$ elements... so any functions can be obtained this way. | |
| May 10, 2021 at 14:40 | comment | added | fosco | hi @SimonHenry ! To a combinatorial species you can associate various formal power series, and especially from the exponential series you can understand a lot about the species itself --although not everything. Ad yes, that series it's not convergent, so there is no associated function you can study. This makes the problem elusive, even provided you find a meaning for what kind of structure $A(n,n)$ is counting. | |
| May 10, 2021 at 14:37 | comment | added | LSpice | @fosco, surely not; $f(n) \ge (n!)^2$ eventually. | |
| May 10, 2021 at 14:37 | comment | added | Simon Henry | @fosco : why is the convergence of the series relevant to the question ? | |
| May 10, 2021 at 14:36 | comment | added | fosco | oh, fair enough; well, is the series $\sum \frac{f(n)}{n!}X^n$ convergent in at least a disk $B(0,\epsilon[$? | |
| May 10, 2021 at 14:35 | comment | added | catlyn | @fosco I had in mind $f(n)=A(n, n)$ | |
| May 10, 2021 at 14:34 | comment | added | fosco | The Ackermann function $A(m,n)$ takes two inputs; apart from this, if I understand well, you're asking about the existence of a species of structure whose associated exponential series (in the variables X,Y) is $\sum \frac{A(m,n)}{n!m!}X^nY^m$. First of all, is this series convergent? | |
| May 10, 2021 at 14:21 | review | First posts | |||
| May 10, 2021 at 14:24 | |||||
| May 10, 2021 at 14:20 | history | asked | catlyn | CC BY-SA 4.0 |