I'm pretty much stuck with the following problem:
A boolean function B(m,n) of m variables evaluates to 1 only if at least n variables are 1.
How many nodes do you need in a decision tree to represent this function (the formula with explanation)?
This is what I've come up with so far:
1. the problem is recursive:
Going from the the first node (first variable) - on the branch where n1 = 1 the problem becomes B(m-1,n-1). On the other branch (n1 = 0) it becomes B(m-1,n). etc
2. The formula will have a binomial coefficient (because at least n out of m variables must evaluate to 1).
Empirically (by counting the nodes in trees with small m) I've come up with:
2 * (m+1 choose n) - 1 , but the explanation why this is true is beyond me.
I have virtually no background in discrete mathematics and it seems like I'm running in circles with this. Any hints or corrections will be more than welcome.