MathDB

sum of subsets with k elements from vertices of a tree with n vertices

Source: 2010 Indonesia TST stage 2 test 4 p2

December 16, 2020

combinatoricsgraph theory

Problem Statement

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

.

Back to Problems View on AoPS