What combinatorial quantity the tetration of two natural numbers represents?

Question

Tetration is a generalization of exponentiation in arithmetic and a part of a series of other generalized notions, Hyperoperators. Consider $m\uparrow n$ denotes the tetration of $m$ and $n$. i.e. $$\underbrace{m^{m^{m^{.^{.^{.^{m}}}}}}}_{n-times}$$

Note that one can find a combinatorial description of each one of operators sum, multiplication and exponentiation as follows:

• $m+n$ is the size of disjoint union of two sets with $m$ and $n$ elements.

• $m.n$ is the size of Cartesian product of two sets with $m$ and $n$ elements.

• $m^n$ is the size of set of all functions from a set with $n$ elements to a set with $m$ elements.

• $m\uparrow n$ is the size of ... (?)

Question: Is it possible to introduce a combinatorial set (defined by $m$, $n$) which its size is $m\uparrow n$ as well as the case of $m+n$, $m.n$, $m^n$? What about other Hyperoperators like pentation and hexation? The simple and most natural expressions are more interesting.

Answer 1

This is probably not what you want. but we can create the notion of the $n$'th dual of a set (I'm borrowing this notation from linear algebra).

Given sets $X$ and $Y$ consider the dual of $X$ with respect to $Y$ to be the the functions from $X$ to $Y$.

Define recursively the $n$'th dual of a set $X$ to be the dual of $X$ with respect to $X$ for $n=1$ and the dual of the $n-1$'th dual of $X$ with respect to $X$ for $n>1$. Then $m\uparrow n$ is the order of the $n$'th dual of a set of $m$ elements.

Answer 2

$2 \uparrow \uparrow (n-1)$ is the number of sets of rank $n$. Intuitively, the rank of a set is the depth of the nesting braces needed to write it. Recursively, the rank of the empty set is zero, and the rank of a nonempty set is the one plus the maximum rank of its elements. It is also the depth of the stack needed by a pushdown automaton to recognize the braces are balanced. In short, $2 \uparrow \uparrow (n-1) = |V_n|$ where

$$V_\alpha = \bigcup_{\beta < \alpha} \mathcal{P}(V_\beta)$$

Answer 3

Here is a visualization of @JorgeFernandez's answer, if you are familiar with the idea of a simplicial complex from topology. We can view a function from the set of size $m$ to itself as a certain kind of oriented $1$-dimensional simplicial complex on itself. Then we can grow these into higher dimensional simplicial complexes to represent $m\uparrow n$. Essentially we are just recursively looking at the entire collection of functions from the previous iteration, and imagining all of the ways to map that set back to the set of size $m$.

$m\uparrow n$ is the number of ways to construct a simplicial complex according to the scheme laid out below. Try following the steps and drawing one of the $2\uparrow 3=16$ simplicial complexes that these steps describe to understand it better.

• If we add any one-simplices, they will have an orientation.
• Start with $m$ vertices. These are the $0$-simplices of the complex. If $n=1$, each of these individual $0$-simplices is counted to get $m\uparrow 1$.
• If $n=2$, skip to last step. If $n\geq3$, start the complex with one copy of every possible directed $1$-simplex. Note this includes loops.
• If $n=3$, skip to last step. If $n\geq4$, extend a $1$-simplex from the previous step into a $2$-simplex, by choosing a point in the set as a third vertex, adding $1$-simplices that complete the triangle and point to the chosen point, and attaching the $2$-simplex using that triangle as the boundary. Then do this for every $1$-simplex from the previous step, for every possible target point.
• If $n=4$, skip to last step. If $n\geq5$, extend a $2$-simplex from the previous step into a $3$-simplex, by choosing a point in the set as a fourth vertex, adding $1$-simplices that complete the shell of a tetrahedron and point to the chosen point, adding three more $2$-simplices to complete the shell of the tetrahedron, and attaching the $3$-simplex to fill out the tetrahedron. Then do this for every $2$-simplex from the previous step, for every possible target point.
• Higher dimensional analogies of the previous steps...
• Finally, we reach a point where we have just added a lot of $(n-2)$-simplices in the previous step. In this last step we will attach $(n-1)$-simplices, but in a slightly different way. Extend a $(n-2)$-simplex from the previous step into an $(n-1)$-simplex, by choosing a point in the set as an $n$th vertex, adding $1$-simplices that complete the shell of a hypertetrahedron and point to the chosen point, adding more $2$-simplices, $3$-simplices, etc. until you complete the shell of the hypertetrahedron, and attaching the $(n-1)$-simplex to fill out the hypertetrahedron. Then do this for every $(n-2)$-simplex from the previous step, but just choosing one target point for each $(n-2)$-simplex.

Answer 4

"What about other Hyperoperators like pentation and hexation?"

I have analysed the holomorphic properties of tetration and pentation. Some links and complex maps of tetration and pentation are suggested in http://mizugadro.mydns.jp/2014ACKER/67.pdf Does it help?