edited by
614 views
4 votes
4 votes

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 \}]$

edited by

1 Answer

2 votes
2 votes
the question doesnt have direct answer,the graph is required like in above example to get the answer.but general idea is to find number of sub trees of size 1,size 2,size3,...,size n. and all all of them up.

also add a case where noting is deleted.

this has to be calculated manually.

Related questions

11 votes
11 votes
2 answers
4
go_editor asked May 27, 2016
1,050 views
Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers.If a language $L$ is accepted by an NFA with $n$ sta...