Number of tree walks of bounded degree Define a tree walk to be a walk $w$ on some tree starting and ending at the origin. Its support $\text{supp}(w)$ is the subtree consisting of the vertices and edges it traverses. Define the maximal degree of a walk $w$ to be the maximal degree of $\text{supp}(w)$. Identify two tree walks $w_1$, $w_2$ if there is a tree isomorphism $\text{supp}(w_1)\to \text{supp}(w_2)$ that takes one walk to the other. 
How many tree walks of length $2 k$ and maximal degree $\leq d$ are there? Is it $\leq (C \max(d, \log k))^{k}$ or thereabouts?
(And is there a more standard name than "tree walk"?)
 A: To get a more precise count, I tried a generating functions approach. I didn't find a good way to deal with the $w$ variable below, but I have recorded my progress, which is the nicest generating functions expression I have seen for this, in case it is helpful to others (if only as a warning.)
We can consider a more general quantity. Let $N(d,k,w, \ell)$ be the number of walks of length $2k$, where each time when the walk is at the origin is given a nonnegative integer weight, through a tree where every vertex has degree $\leq d$ and the origin has degree $\leq \ell$,  up to isomorphism, with total weight $w$.
Now let $F_{d,w,\ell}( x) = \sum_{k=0}^{\infty} N(d,k,w,\ell) x^k$.
We should be able to get an asymptotic if we understand the location and behavior of the first singularity of $F_{d,0,d}(x)$.
We might be able to do this using the recurrence relation $$F_{d,w,\ell}(x) = 1 + \sum_{v=1}^{\infty} { w +v \choose v} x^v F_{d,v-1, d-1}(x) F_{d, v+ w-1, \ell-1} (x) $$ and the initial condition $F_{d,w,0} = 1$.
Proof of recurrence relation: The 1 term is the walk of length zero. For all other walks, we must leave the starting vertex $A$, and pass to another vertex $B$. Let $v$ be the number of times we walk from $A$ to $B$. We also walk $v$ times back, so these $2v$ paths walks give a factor of $x^v$.
Deleting the edge from $A$ to $B$, we can split our walk into two walks, one starting at the vertex $B$ and one starting at $A$ and avoiding $B$. The walk starting at $B$ has at most $d-1$ vertices adjacent to the starting vertex and the walk starting at $A$ has at most $\ell-1$ vertices adjacent to the starting vertex, after removing $B$.
But to interleave these two walks, we need some additional data. To the walk starting at $B$ we need to add $v-1$ trips back to $A$, which corresponds to the weight of $v-1$, and to the walk starting at $A$ we need to add $v-1$ trips to $B$ after the first one and a weight of $w$, which we can combine into a weight of $w+v-1$, after choosing an ordering of the $w$ weight and the $v$ trips to $B$.
Sorry if that is not very clear. 
A: If we disregard $d$, we can get much more than $(\log k)^k$. Here is an easy construction to get $k^{k/2(1-\epsilon)}$, and a harder one for $k^{k(1-\epsilon)}$. I will also show that, if we hold $d$ fixed, we can achieve $(4d-\epsilon)^k$, matching the leading bound. 
All three of these constructions work as follows: First, use $o(k)$ steps to build a small tree $T$ whose automorphism group is $O(1)$. Then use the remaining $(2-o(1))k$ steps to walk within this tree. The tree $T$ is designed to have a large number of closed walks and, since its automorphism group is $O(1)$, that doesn't change the asymptotics. 
Achieving $k^{k/2(1-\epsilon)}$: Use the first $O(k^{1-\epsilon})$ steps to make paths from the origin and back of lengths $1$, $2$, $3$, $k^{1/2-\epsilon}$. The point of this is to make sure our tree has no automorphisms. Then use the remaining $(2-o(1))k$ steps to walk one step away from the origin and back, never getting more than one step from the origin. The origin has degree $k^{1/2-\epsilon}$, so we get $k^{(1/2-\epsilon) (1-o(1)) k} = $k^{k/2(1-\epsilon)}$ walks.
Achieving $k^{k(1-\epsilon)}$:  The previous paragraph used a rooted tree with no automorphisms, $o(k)$ vertices and root of degree $k^{1/2-\epsilon}$. We could do better if we had a rooted tree with no automorphisms, $o(k)$ vertices and root degree $k^{1-\epsilon}$ for some $c>0$. Actually, we don't need to have no automorphisms; just having no automorphisms that nontrivially permute the children of the root would already make all the walks in the previous paragraph distinct.
The number of isomorphism classes of rooted trees with $n$ vertices grows like $\alpha^n$ where $\alpha \approx 2.9558$, according to the OEIS citing Kunth and Polya. So we can find $k^{1-\epsilon}$ nonisomorphic rooted trees with $O(\log k)$ vertices. Attach all of their roots as children of the origin to get a tree $T$ where the origin has degree $k^{1-\epsilon}$ and there are $O((\log k) k^{1-\epsilon})$ vertices. Build this tree with the first $O((\log k) k^{1-\epsilon})$ steps of your walk, and then use all the rest to walk back and forth next to the origin as before.
Achieving $(4d-\epsilon)^k$. Now we take $d$ fixed, and we also fix an auxilliary positive integer $r$. Let $T_{d,r}$ be the rooted tree where the root and all descendents of the root up to the $r$-st generation have $d$ children, and then everyone at the $(r+1)$-st generation is childless. So there are $1+d+d^2+\cdots + d^r$ vertices in $T_{d,r}$. Again, we will use the first part of our walk to build $T_{d,r}$ and the rest to walk around in it. This time, we will not require ourselves to stay next to the root of $T_{d,r}$ in the second stage, but will explore it freely.
Since $T_{d,r}$ is a fixed tree, its number of vertices and automorhpism group are both $O(1)$ as $k \to \infty$. So all that remains is to count the number of closed walks from the origin to itself of length $(2-o(1))k$ in $T_{d,r}$. 
Let $A$ be the $(r+1) \times (r+1)$ matrix with entries $A_{(i+1)i} = d$, $A_{i(i+1)}=1$ and all other $A_{ij}$ constant. This is a transition matrix 
for how walks in $T_{d,r}$ get closer to and further from the root. The number of walks of length $\ell$ from the root to itself is the $(1,1)$ entry of $A^{\ell}$. Of course, this is controlled by the largest eigenvalue of $A$.
Conjugating $A$ by a diagonal matrix whose diagonal entries are $(1,d^{1/2}, d, d^{3/2}, d^2, \dots)$ turns $A$ into the matrix $B$ where $B_{i(i+1)} = B_{(i+1)i} = \sqrt{d}$ and all other off diagonal entries are $0$. Write $B = \sqrt{d} P$, where $P$ is the adjacency matrix of the path of length $r+1$. It is well known (see, for example, Section 3.2 here) that the eigenvalues of $P$ are $2 \cos \tfrac{\pi j}{r+2}$ for $1 \leq j \leq r+1$. We are only concerned about even powers of $A$, and hence about the squares of these eigenvalues, which are $4 \cos^2 \tfrac{\pi j}{r+2}$, so the largest of these is $(4-\epsilon_r)$ where the quantity $\epsilon_r$ goes to $0$ as $r \to \infty$. 
Unwinding, the number of walks from root to root of length $(2-o(1))k$ in $T_{d,r}$ is $((4-\epsilon_r) d)^{(1-o(1))k}$.
Now, sending $r \to \infty$, we match the Catalan bound.
A: Edited to fix conflicting notation and to add clarification.
This started out as a comment, but got too long.
I'm assuming that $d\ll k$ and sweeping a lot of dependence on $d$ into a factor $c_d$ and $o_d$. The following construction then gives a lower bound of $(4-o_d(1))^{k}(d-1)^k$.
Take some depth $\ell$, to be chosen later. We will stay in the complete $d-1$-regular tree of depth $\ell$. Split into subwalks of length $2\ell$, at the end of each of which we must return to the root. So we take a dive into our tree on length $2\ell$, with the only requirement being that we return to the root after $2\ell$ steps. Then (letting $C_\ell$ be the $\ell$th Catalan number) we get at least $c_dC_\ell (d-1)^\ell$ choices for each subwalk of length $\ell$. Thus total choices are $c_d(C_\ell (d-1)^\ell)^{k/\ell}=(2-o(1))^{2k}(d-1)^k$ where the $o(1)$ is a limit as $\ell\to\infty$ and comes from approximating $C_\ell$ as $2^{2\ell}$. I am thinking of having $\ell$ grow very slowly with $k$ for fixed $d$. It may be possible to improve the upper bound to match, as we only have $d-1$ choices to go down anywhere other than the root.
A: A lower bound of d^(k-n) is easily found. Do a depth first traversal of the tree until a node of out degree d has had all d children visited. Then bounce around that node and it's children until you need to visit the remaining nodes and return to the root. Note that since all d children have been visited, they are effectively labeled at that point, giving the power of d.
If you count depth first traversals of a labelled tree visiting each of the n other nodes before returning to the root (so traversing each edge exactly twice) then the count is a product of factorials of out degrees of each node. For the identification that Harald wants, replace factorial of out degree by a multinomial coefficient, with "numerator" the factorial of the out degree and denominator the factorial of the counts of isomorphic rooted subtrees whose roots are the children of the node. This number is then a multiplicative factor in front of the previous power of d.
One can tighten things up a bit. However, the key is to realize that at each  node, at most d choices take one further from the root, and only one choice takes one closer. This holds for many nodes even when not all of the tree has been visited, just the d children from the present node, for by then they have been labelled by the walk as visiited in some order.
Gerhard "Time To Take A Walk" Paseman, 2019.11.06.
