- #1

- 170

- 1

## Homework Statement

Let X = {1,2,3, ... ,17}. Find the number of subsets Y of X with odd cardinalities.

## Homework Equations

None.

## The Attempt at a Solution

Well, I think I'm correct: 17C1 + 17C3 + 17C5 + ... + 17C17 = 65536

The problem is, I'm not supposed to use a calculator and I supposed to take less than 6min to get this done (maybe I'm just slow...).

So, I have 2 questions:

- I noted that 65536 = 2^16, so I guessed there should be some useful theorems to help me out with this - I did a quick search on 'combinatorial sums', but it seems like I didn't get the right description for this kind of problem. Are there some other equations that I'm supposed to be familiar with for this?

- Are there any heuristics to speed up the evaluation of combinations/permutations? The solutions to some problems that I had came across reduced to numbers like 48C12, which I could manage with prime factorization, but I felt it could have been faster.