# How many branches does this tree have as a function of depth and n objects?

I am working on a problem that can be described with a tree structure where at each node I either choose one of $n$ options or choose to do nothing. If I have chosen an action, I can no longer choose it and only have $n-1$ choices left (plus additionally the do nothing choice), but if I do nothing at any vertex, I keep the same number of actions for the next node.

It's clear that a tree without this 'do nothing' choice has $n!$ branches, and it's clear this tree with the do-nothing choice can have infinitely many branches if we do not limit depth because I can just keep taking the 'do nothing' branch.

I would like to know how the number of possible paths grows with the number of initial actions, $n$, and depth, $d$.

• If you start off by doing nothing $50$ times, then the next step you will have $n$ choices. If you start off by choosing non-"do nothing" choices $50$ times, then the next step you will have $n-50$ choices. Commented Dec 8, 2017 at 14:59
• Yes, I know. But starting at the root with n choices and d expected time steps, how many possible execution-sequences are there total, forward from that point? Commented Dec 8, 2017 at 14:59
• (n+1 choices at the root) + (n+1 choices at the do-nothing node + n choices at each of the n other nodes) + (n+1 in the subtree where do-nothing again + n^2 for the branches in that subtree where we select an action + n^2 for the do-nothing branches in the subtrees where w previously selected an action + (n-1)^2*n for the branches where we choose a second action) + ... I would like a closed form. Commented Dec 8, 2017 at 15:10

$T(n,d) = T(n,d-1) + n*T(n-1,d-1)$
The base cases will be $T(n,0)=1$ and $T(0,d)=1$. Use dynamic programming to find any answer you like efficiently.