Problem

Source: 2010 Indonesia TST stage 2 test 4 p2

Tags: combinatorics, graph theory



Let $T$ be a tree with$ n$ vertices. Choose a positive integer $k$ where $1 \le k \le n$ such that $S_k$ is a subset with $k$ elements from the vertices in $T$. For all $S \in S_k$, define $c(S)$ to be the number of component of graph from $S$ if we erase all vertices and edges in $T$, except all vertices and edges in $S$. Determine $\sum_{S\in S_k} c(S)$, expressed in terms of $n$ and $k$.