0
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – vadim123
    Commented Dec 8, 2017 at 14:59
  • $\begingroup$ 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? $\endgroup$ Commented Dec 8, 2017 at 14:59
  • $\begingroup$ (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. $\endgroup$ Commented Dec 8, 2017 at 15:10

1 Answer 1

0
$\begingroup$

I think I got it. It's a recurrence (as is usually the case with trees). I had to draw it out to several levels to see it.

$T(n,d) = T(n,d-1) + n*T(n-1,d-1)$

The first term on the right comes from the do nothing branch, because you have just as many options with one fewer depth to expand in. And the second term is because each of the other subtrees have one fewer choice and one fewer depth both, and although they are different sequences their shape is the same.

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .