Removing nodes from graphs such that one is dependent on other - ZIO $2010$, P$1$

Question

Greetings Community! The above problem you see is a combinatorics problem I could not solve. :( This problem is from ZIO $2010$, P$1$.

Here is what I did: Observe that every graph can be divided into "sub-groups" which may help in solving. We first remove the empty set. Then the singleton set. Consider the bigger but smaller than the sub-parts example: The singleton sets are $\{4,5,6\}$ which are at the least position in the graph. The dual sets are $\{2,4\}, \{3,5\}, \{3,6\}$, the bottom - two portions in the graph. The triplet sets are $\{2,4,5\}, \{4,5,6\}$ which we may manually count but for the bigger graphs in the sub-part, this may prove to be difficult and this is where I am stuck.

Any help would be appreciated. Thanks.

Answer 1

The idea here, is the "inversion" of the boss statement to the following :

If an employee's boss is sacked, he is sacked as well.

From which we get :

If a person is sacked, all his employees are sacked.

Therefore , we get the following : every "valid set of sackings" corresponds to a unique list of bosses who were sacked. And none of these bosses are bosses to any of the others.

For example, consider the example given in the question. The sacking $\{1,2,3,4\}$ corresponds to the sacking of boss $\{1\}$. The sacking $\{2,3,4\}$ corresponds to the list $\{2,3\}$ since $4$ below $3$ will also be sacked. Note that $\{2,3\}$ are not bosses of each other.

---

Why do we get the number $7$ now? Let us think.

The tree has root $1$, with two subtrees, one is $2$ and the other is $3 \to 4$.

Now, I claim the following : every valid sacking is of two types, one consisting of all being sacked, and the other being a union of valid sackings over all subtrees(may be empty).

This is obvious : indeed, given a valid sacking, look at the unique boss list, and these bosses are sitting in different subtrees of the original tree, so we get a sacking from each subtree by looking at the bosses in each of the subtrees.

Similarly, given valid sackings over all subtrees, you get by taking their union, a valid sacking, which is easy to check.

Let us take examples from the last given question to clarify what I mean, since I intend to use a complicated scenario here.

Let's take $(b)$. Consider the given sackings :

• The sacking $\{5,8,9,7,14\}$ corresponds to the unique boss list : $\{5,7\}$. Note that $\{5,8,9\}$ is a valid sacking of the subtree under $2$, and $\{7,14\}$ is a valid sacking of the subtree under $3$. Conversely, given these sackings, their union gives the full sack list.

• The sacking $\{4,8,11,13,16\}$ comes from the unique list $\{4,8,11,13\}$, and one sees that $\{4,8\}$ is a valid sacking of the subtree under $2$, similarly $\{11,13,16\}$ is a valid sacking of the subtree under $3$.

• In the original example (the $1,2,3,4$ one) the sacking corresponding to $\{3,4\}$ has unique boss list $\{3\}$ , and $\{\}$(nobody sacked : I suspect bribery here!) is a valid sacking under $2$ while $\{3,4\}$ is a valid sacking under $3$.

Thus, we can recursively count the number of valid sackings.

When we hit a tree, we either sack everybody, or choose a valid sacking from each child and put them together. Thus, we get :$$\textrm{No. of valid sackings} = 1 + \prod_{\textrm{child subtrees}} \textrm{no. of valid sackings of this child subtree} $$

Note : $\prod$ stands for product, we are choosing each subtree sacking independently so we take the product.

We need the base case as well : in a singleton tree, you either sack all or sack none, so that gives the number as $2$.

Finally, let us calculate using this formula, the answer for the original example.

---

No of sackings of $\{1,2,3,4\} = 1 + $ no of sackings of $\{2\} \times $ no of sackings of $\{3,4\}$.

No of sackings of $\{2\} = 2$ from base case.

No of sackings of $\{3,4\} = 1 + $ no of sackings of $\{4\}$ (there's only one subtree) $=1+2 = 3$.

So finally we get $1 + 2 \times 3 = 7$!

We need to do this procedure for the other trees. Let us do it for $(a)$, I leave you to see it for the others.

---

For $(a)$ : Let us use notation, with $N(t)$ the number of valid sackings for the subtree under $t$. Naturally we want to find $N(1)$.

Then : $N(1) = 1 + N(2)N(3)N(4)$. We compute each one separately below, from easiest to hardest.

---

$N(2) = 1 + N(5) = 1+2 = 3$.

---

$N(4) = 1 + N(8)N(9) = 1 + 2 \times 2 = 5$.

---

$N(3) = 1 + N(6)N(7)$. See $N(6) = 5$ yourself, and $N(7) = 1 + N(12)N(13)N(14) = 1 + 2 \times 2 \times 2 = 9$. So we get $N(3) = 46$.

---

Combining, $N(1) = 1 + 3 \times 5 \times 46 = 691$. So there are $691$ sackings possible here.

Answer 2

Hint: You need a recurrence.

Consider a sub-tree, rooted at node $x$.

Let $f(x) =$ the number of ways to fire people in this sub-tree (including not firing anyone).

Suppose $x$ has $k$ children.

• If $k=0$, i.e. $x$ is a leaf, then there are two ways to fire people involving this subtree, i.e. $\{\}$ and $\{x\}$.

• If $k=1$, let the child of $x$ be called $y$. Can you write $f(x)$ in terms of $f(y)$?

• If $k=2$, let the children by $y_1, y_2$. Can you write $f(x)$ in terms of $f(y_1), f(y_2)$?

• For general $k$, can you write $f(x)$ in terms of $f(y_1), \dots, f(y_k)$?

Once you have the recurrence, test it on the sample $4$-node tree, starting from the leaves and going up the tree - and remember that $f(\text{leaf}) = 2$ (not $1$). If you get the answer $7$ after you arrive at the root node, chances are your recurrence is correct.