This question is from ZIO $2010$. I thought of using a bottom up approach, calculating the possible subsets from the leaves, and then making my way up. I'm not to sure why it isn't working. The question is:
Sales have slumped at the Zionoi noodle factory and the management may need to terminate the contracts of some employees. Every employee has one immediate boss. The seniormost person in the company is the president, who has no boss. For legal reasons, if an employee’s contract is not terminated, then his or her boss’s contract cannot be terminated either. For how many different sets of employees can the management legally terminate contracts? Note that one possibility that has to be counted explicitly is that no employees’ contracts are terminated (that is, the set of employees whose contract is terminated is the empty set).
For example, suppose there are four employees, organised as follows. Each arrow points from an employee to his or her boss.
Here, there are $7$ different ways to terminate contracts for a set of employees, as follows:
$\Bigg[\{1, 2, 3, 4\}, \{\}, \{4\}, \{2\}, \{3, 4\}, \{2, 4\}, \{2, 3, 4\}\Bigg]$
In each of the following cases, compute the number of different sets of employees whose contracts can be legally terminated by the management.
