Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 2 / c

Table of contents
- Solution c

Solution

Partition the power set into disjoint classes according to subset size. The class of size-

i

subsets has cardinality

(i n)

, while the whole power set has cardinality

2^{n}

. Counting every subset once gives

i = 0 \sum n (i n) = 2^{n} .

This is also the binomial theorem evaluated at

1 + 1

, but the counting proof follows directly from the earlier parts.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version