Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Original Question

Consider an infinite tree of constant degree $k$. For such a tree we can consider the total number of nodes at depth $n$, $g(f)$, and the total number of paths from the root, $p(f)$, to be a function of the constant function, $f=k$. We define $G(f)$ to be the resulting infinite tree. Now let us generalize this idea to functions $f(n)$, with the normal convention that the root has depth $n=0$.

Some examples:

$G(1)$ is the infinite tree (path) of constant degree 1

$g(2) = 2^n$
$p(2) = 2^{n+1}-1$
$G(2)$ is the infinite complete binary tree

$g(a) = a^n$
$p(a) = \frac{a^{n+1}-1}{(a-1)}$ for a>1
$G(a)$ is the infinite complete tree of constant degree a

$g(f=n) = n!$
$p(f=n) = !n$
$G(f=n)$ is the infinite complete tree of incremental degree


where !! is the double-factorial

where !!! is the triple-factorial

$g(f=n^2) = n!^2$

$g(f=n^a) = n!^a$

$g(f=an^b) = a^{n}n!^b$ ; Sequences not in Sloan for a>1

$g(f=n^2+n+1)$ = ? ; Related to absolute values for Sloan A130031
$p(f=n^2+n+1)$ = ? ; Sequence: [1, 2, 7, 62, 1107, 31412, 1273917, ... ]


$p(f=2^n)= ?$ ; Sequence: [1,3,11,75,1099,33867, .... ]


$g (f=n!)$ = Sloan A000178

$g (f=2n!)$ = ? ; Related to Sloan A156926. Sequence: [1,2,8,96,4608,1105920,....]
$p (f=2n!)$ = ? ; Sequence: [1,3,11,107,4715,....]

$g (f=3n!)$ = ? ; Sequence: [1,3,18,324,23328,8398080,....]
$p (f=3n!)$ = ? ; Sequence: [1,4,22,346, 23674, 8421754,....]

$g(f=a^{a^n})= a^{a^{n+1}-a(3^n + 1)/2}$

My questions are: is this graph construction well known? I would be interested in any references to similar functional transformations on graphs.

Also, could anyone tell me what is the cardinality of the set of all paths in G(f=n)? Clearly it has at least Continuum cardinality. Since the factorial grows faster than $a^n$, yet slower than $2^{2^n}$, I would think it lands in the Continuum. I am not sure, though...


We can express p and g as functional equations:

$g(f(n))=f(n) g(f(n-1))$


$p(f(n))=\sum_{i=1}^{n} g(f(i))$

If we extend to the complex domain and consider the special case f(z)=z we have the functional equation:

$g(z)= z g(z-1)$

Which has the rather well known solution $g(z) = \Gamma (z+1)$

share|improve this question
What exactly do you mean by "total number of paths from the root"? –  Stefan Geschke Sep 29 '10 at 8:03
I mean the cardinality of the set of all paths from the root. For example, a complete binary tree of depth 2, has 7 paths from the root. One of length zero, Two of length 1, and 4 of length 2. –  Halfdan Faber Sep 29 '10 at 8:22
Surely the tag 'fa.functional-analysis' is inappropriate here? I'm not sure that I have enough rep to change it. –  Philip Brooker Sep 29 '10 at 18:09
I agree with Philip. Detagging. –  Yemon Choi Sep 29 '10 at 18:15
I have added a number of example transforms, since the original question. I expected g(f) to "monotonously" map to functions of higher order of growth. This appears to not be the case, as exponential functions are mapped into exponential functions. I suspect g has a non-trivial fixed point function, f*, of exponential order. At this point I only know the trivial fix point f=1. –  Halfdan Faber Sep 30 '10 at 6:43
show 6 more comments

1 Answer

up vote 3 down vote accepted

You ask for the size of $G(f)$. This tree is always countable, i.e., its set of nodes is countable. My guess is that you are really asking about is the number of branches (maximal chains). If every node has a node above it that has at least 2 immediate successors, then the number of branches is $2^{\aleph_0}$.
If the tree has too few nodes with at least two immediate succesors, then there are only countably many branches. Any number of branches between $\aleph_0$ and $2^{\aleph_0}$ is impossible (this is essentially the Cantor-Bendixson theorem).

Here I should add that I view the tree as a partial order. The root is the smallest element, all its neighbors are above the root and incomparable and so on.

This construction of trees comes up in set theory quite a lot, especially in forcing ($a$-Sacks forcing is forcing with subtrees of $G(f=a)$ ($a$ constant) in which every node has a node above it that has exactly $a$ immediate successors. The tree of incremental degree give rise to a forcing notion that I called Miller lite forcing in [A dual open coloring axiom, Annals of Pure and Applied Logic 140 (2006), 40-51], which can be found here.) But I have never seen your computations.

share|improve this answer
Thanks much, Prof. Geschke. Yes, I did mean the cardinality of the set of all paths (i.e. partial or complete paths). –  Halfdan Faber Sep 29 '10 at 8:29
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.