I would like to count the paths in a tree that visit a subset of nodes in a particular order. For example, for the tree
The paths are exhaustively [[ 1 ], [1,2], [1,3], [1,2,1,3], [1,3,1,2]), there are 5.
Paths can double back if they need to in order to visit more nodes. Note that [1,2,1] is not a path I want to count.
For a bigger (also complete-binary) tree :
There are (I believe) 225 paths. For example [1,2,1,3,6,3,1,2,4,2,1,3,7,3,1,2,5] (or in a more compressed encoding ([{1,2}, {1,6}, {1,4}, {1,7}, {1,5}]). (This example is not the best since paths always need to return to the root. Paths don't always have to return to the root necessarily, just to the lowest common ancestor.)
Is there a name for these paths? And a way to count them? For the level 3 complete binary tree, there are more than 13 million (I don't know how much more. That's just as many as I had the patience to (let my computer) count).
For clarification, in a height 1 k-ary tree, the number of paths is the number of arrangements of a set with n elements. (https://oeis.org/A000522)
If I understand your question correctly, an admissible path can be represented as a word in the letters $a_i=\{1,i\}$ where $i$ is a non-root node, and where repeats are not allowed in one word.
Therefore to build a word of length $k$ you need to choose $k$ letters (from $N=2^{n+1}-2$ which is the number of non-root nodes), and then order them.
So the number of words for a binary tree of depth $n$ is $$\sum_{k=0}^N{N\choose k}k!\qquad\text{with $N=2^{n+1}-2$.}$$
It does give $5$ for $n=1$, but then $1957$ for $n=2$, and $236975164805$ for $n=3$ so maybe I didn't understand correctly what paths you are considering.