Sales have slumped at the Siruseri 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 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:
$[ \{1,2,3,4 \}, \{ \}, \{ 4 \}, \{ 2 \}, \{ 3, 4 \}, \{ 2, 4 \}, \{ 2, 3, 4 \}]$