# HW 2 Q3b

Hello, I’ve been thinking about this problem for quite a while and i don’t see a clear path towards the solution. Can someone give me a hint?

1. Part (a) is a hint: a problem that looks quite hard is in bijection with a problem that is easy to solve.

The same bijection is useful for part (b), and several ways to proceed (none of which is immediate). Another hint: algebraic methods may be easier than combinatorial methods in this problem.

the subsets $S_i$ as binary selection vectors ${\bf w}$ where $w_k = 1$ if $k\in S_i$
$n$ ideal switches that can be on or off. Then starting with all of them off, how many ways
are there to turn them on and off $k$ times so that they’re all off at the end.